宽相碰撞检测方法呢？ [英] Broad-phase collision detection methods?

问题描述

我要建一个2D物理引擎，我想补充广泛相碰撞检测，虽然我只知道2或3种类型：

I'm building a 2D physics engine and I want to add broad-phase collision detection, though I only know of 2 or 3 types:

• 检查对一切的一切（为O（n ^ 2）复杂性）
• 扫描和清理（排序和扫描）
• 在一些有关二进制空间分区（不知道如何做到这一点）

但是肯定有更多的选择权？他们是什么？而且既可以对每个提供或链接描述的基本描述？

But surely there's more options right? what are they? And can either a basic description of each be provided or links to descriptions?

我见过的<一个href="http://stackoverflow.com/questions/414553/broad-phase-collision-detection-quadtrees-bsp-etc">this但我要求的算法可供选择的列表，而不是最适合我的需要。

I've seen this but I'm asking for a list of algorithms available, not the best one for my needs.

在这种情况下，宽相碰撞检测是由物理引擎，以确定他们的模拟身体是足够接近值得进一步调查和可能的冲突解决方法。

In this case, "Broad phase collision detection" is a method used by physics engines to determine which bodies in their simulation are close enough to warrant further investigation and possibly collision resolution.

推荐答案

最好的方法取决于特定的用途，但底线是，你要细分你的世界空间，使得（一）每一个身在只有一个细分，（b）每分舱是足够大，使得氨基酸体在一个特定的细分只能与在同一细分或相邻的细分，以及（c）机构在一个特定的细分数机构碰撞是尽可能地小。

The best approach depends on the specific use, but the bottom line is that you want to subdivide your world space such that (a) every body is in exactly one subdivision, (b) every subdivision is large enough that a a body in a particular subdivision can only collide with bodies in that same subdivision or an adjacent subdivision, and (c) the number of bodies in a particular subdivision is as small as possible.

你怎么做，取决于你有多少机构有，他们是如何移动的，你的性能要求，以及多少时间，你想花你的引擎。如果你在谈论的身体在很大程度上空地走动，最简单的方法将世界划分为一个网格，每个单元格是比你的大目标大，并跟踪每个单元中对象的列表。如果你正在构建的东西上的一个经典的街机游戏的规模，这种解决方案很可能就足够了。

How you do that depends on how many bodies you have, how they're moving, what your performance requirements are, and how much time you want to spend on your engine. If you're talking about bodies moving around in a largely open space, the simplest technique would be divide the world into a grid where each cell is larger than your largest object, and track the list of objects in each cell. If you're building something on the scale of a classic arcade game, this solution may well suffice.

如果你正在处理的机构朝着一个更大的开放的世界，一个简单的网格将成为压倒pretty的快，你可能需要某种形式的基于树的结构是怎样的四叉树，因为Arriu建议。

If you're dealing with bodies moving in a larger open world, a simple grid will become overwhelming pretty quickly, and you'll probably want some sort of a tree-based structure like quadtrees, as Arriu suggests.

如果你谈论的是有界的空间，而不是开放的空间内到处移动身体，那么你可以考虑 BSP树;树分区世界进入空间，你可以走在和墙，和裁剪身体到树确定它是否是一个合法的地位。根据世界几何，你还可以在全球使用BSP为您的广泛相位检测碰撞物体之间。

If you're talking about moving bodies around within bounded spaces instead of open spaces, then you may consider a BSP tree; the tree partitions the world into 'space you can walk in' and 'walls', and clipping a body into the tree determines whether it's in a legal position. Depending on the world geometry, you can also use a BSP for your broad-phase detection of collisions between bodies in the world.

有关机构在运动界的空间会是一个门户引擎的另一个选择;如果你的世界可以由凸多边形区域，其中多边形的每一侧或者是一个坚实的墙壁或门户到另一个凹陷空间，你可以很容易地确定一个机构是否是一个区域内有一个点在多边形测试仅看同一地区的机构或连接区域简化碰撞检测。

Another option for bodies moving in bounded space would be a portal engine; if your world can consist of convex polygonal regions where each side of the polygon is either a solid wall or a 'portal' to another concave space, you can easily determine whether a body is within a region with a point-in-polygon test and simplify collision detection by only looking at bodies in the same region or connected regions.

这篇关于宽相碰撞检测方法呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！