轴对齐边界框与边界椭圆
为什么现在大多数（如果不是全部）碰撞检测算法都要求每个 2D 体都有一个 AABB 仅供广泛阶段使用？
在我看来，简单地在 2D 主体的质心处放置一个圆，并将半径延伸到圆包围整个主体的位置将是最佳选择。在主体旋转和广泛的重叠计算会更快。正确的？
奖金：
边界椭圆对于宽相位计算也适用吗，因为它可以更好地表示又长又细的形状？或者是否需要大量计算，从而违背了宽相的目的？
Why is it that most, if not all collision detection algorithms today require each 2D body to have an AABB for the use in the broad phase only?
It seems to me like simply placing a circle at the 2D body's centroid, and extending the radius to where the circle encompasses the entire body would be optimal. This would not need to be updated after the body rotates and broad overlap-calculation would be faster to. Correct?
Bonus:
Would a bounding ellipse be practical for broad phase calculations also, since it would better represent long, skinny shapes? Or would it require extensive calculations, defeating the purpose of broad-phase?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
边界框由线性不等式约束表示，而圆和椭圆则需要二次不等式约束。人们可以同时使用两者，但线性情况一如既往地更容易通过算法解决（它只涉及矩阵乘法）。如果边界框与世界坐标轴对齐，则所有检查看起来都像
xa - xb > dxa + dxb，ya - yb > dya + dyb 和 za - zb > dza + dzb，其中d$i$j是$i$中对象$j周围边界框的尺寸> 方向。不过，椭圆碰撞检测正在进行中。数学要困难得多，而且实施和计算工作可能不值得节省。无论如何，我在谷歌学者中搜索了“椭圆碰撞检测”，第一页上至少有两篇论文似乎正是关于这个主题的： http://hub.hku.hk/bitstream/10722/47091/1/121854.pdf?accept=1 和 ftp://crack.seismo.unr.edu/downloads/russell/doven_2005_neighbor_list_collision_driven_MD_II.PDF
Bounding boxes are represented by linear inequality constraints while circles and ellipses need quadratic inequality constraints. One can work with both, but the linear case, as always, is much simpler to solve algorithmically (it only involves a matrix multiplication). If the bounding boxes are aligned with the world coordinate axes then all the checks look like
xa - xb > dxa + dxb,ya - yb > dya + dybandza - zb > dza + dzb, whered$i$jis the dimensions of the bounding box around object$jin the$i$direction.Ellipse collisions detection is being done, however. The math is significantly harder and the implementation and computational effort might not be worth the savings. In any case, I searched Google scholar for "ellipse collision detection" and at least two papers on the first page seemed to be exactly on this topic: http://hub.hku.hk/bitstream/10722/47091/1/121854.pdf?accept=1 and ftp://crack.seismo.unr.edu/downloads/russell/doven_2005_neighbor_list_collision_driven_MD_II.PDF
如果被近似的物体是圆形的，那么球体才是真正好的近似。在一般情况下，边界球最终比被近似的对象大得多。想象一个长矩形。即使矩形旋转，AABB 也能提供比球体更紧密的近似。
球体重叠测试很便宜，但 AABB 重叠测试也很便宜。
为了使用球体提供最佳拟合，球体需要偏离对象的质心。对象的质心仅提供对称对象的最佳拟合。
找到任意对象的最佳拟合似乎是一个不小的问题。请参阅此处：如何计算最小边界球包围其他边界球
仅使用基于质心的方法（除非您预先计算偏移，将其存储在某处并在对象移动时通过对象的位置和旋转来变换它），正如已经提到的那样，它不能提供最紧密的配合。由于配合通常不紧密，因此您的宽相不会过滤掉许多物体，并且您最终会浪费更多时间进行更昂贵的检查。
椭球体在数学上很难处理，任何与椭球体的相交测试都会远远超过它们提供的更紧密拟合的好处。
然而，有一种特殊情况：轴对齐的椭球体。
如果您的椭球体是一个球体，只能沿 X、Y 或 Z（或其组合）拉伸，而不是沿任何轴拉伸（或沿 X、Y 或 Z 拉伸然后旋转），则有一个技巧：
如果将椭球体的半径除以自身，则最终会得到一个单位球体。
如果您对针对椭球体进行检查的对象执行相同的操作，您最终会得到单位球体与 X 的测试。
以下是检查轴对齐椭球体是否与 AABB 重叠的算法示例：
position_es（es = 椭球空间）。aabb_es。position_es的单位球体检查aabb_es。上述算法是以下论文中提出的扫掠椭球体碰撞检测背后的思想：
Kasper Fauerby 的“改进碰撞检测和响应”：https://peroxy.dk/papers/collision /碰撞.pdf
A sphere is only really a good approximation if the object being approximated is round-ish. In the general case, a bounding sphere ends up being much bigger than the object being approximated. Imagine a long rectangle. Even if the rectangle is rotated, an AABB provides a tighter approximation than a sphere.
A sphere overlap test is cheap, but so is an AABB overlap test.
To provide the best fit using a sphere, the sphere would need to be offset from the object's centroid. The object's centroid only provides the best fit for symmetrical objects.
Finding the best fit for arbitrary objects seems to be a non-trivial problem. See here: How to compute the smallest bounding sphere enclosing other bounding spheres
Only with a centroid-based approach (unless you precalculate the offset, store it somewhere and transform it by the object's position and rotation, whenever it moves), which as already mentioned doesn't provide the tightest fit. Since the fit usually isn't tight, your broadphase doesn't filter out many objects, and you end up wasting more time doing more expensive checks.
Ellipsoids are very difficult to handle mathematically and any intersection tests with ellipsoids would far outweigh the benefits of the tighter fit they provide.
There is a special case however: Axis-aligned ellipsoids.
If your ellipsoid is a sphere that can only be stretched along X, Y or Z (or a combination thereof), instead of along any axis (or stretched along X, Y or Z and then rotated), there is a trick:
If you divide an ellipsoid's radii by themselves, you end up with a unit sphere.
If you do the same to the object being checked against the ellipsoid, you end up with a unit sphere vs X test.
Here's an example of an algorithm that checks if an axis-aligned ellipsoid overlaps an AABB:
position_es(es = ellipsoid space).aabb_es.aabb_esagainst the unit sphere positioned atposition_es.The above algorithm is the idea behind swept ellipsoid collision detection presented in the following paper:
"Improved Collision detection and Response" by Kasper Fauerby: https://peroxide.dk/papers/collision/collision.pdf