如何三维碰撞/对象检测的工作？ [英] How does 3D collision / object detection work?
问题描述
我心中已经一直想知道这一点。在这样一场比赛 GTA 那里有成千上万个对象10S，如何做游戏中只要你是一个健康包知道吗？
I'v always wondered this. In a game like GTA where there are 10s of thousands of objects, how does the game know as soon as you're on a health pack?
目前不可能是一个事件侦听器为每个对象？迭代也不好？我只是想知道它是如何实际上已经完成了。
There can't possibly be an event listener for each object? Iterating isn't good either? I'm just wondering how it's actually done.
推荐答案
有没有人回答这个，但是大的世界往往是空间分割利用沿一个的quadtree 或 kd树这使搜索时间寻找下面的线性时间的近邻（分数电源，或在最坏的情况O（N ^（2/3））的3D游戏）。这些方法通常被称为的 BSP 的二进制空间分割
There's no one answer to this but large worlds are often space-partitioned by using something along the lines of a quadtree or kd-tree which brings search times for finding nearest neighbors below linear time (fractional power, or at worst O( N^(2/3) ) for a 3D game). These methods are often referred to as BSP for binary space partitioning.
使用关于碰撞检测，每一个对象还通常具有的边界体积的目（组多边形形成一个凸包）与它相关联。这些高度简化的网格（有时只是一个立方体）中没有画出，但在碰撞的检测中使用。最基本的方法是创建一个平面垂直于连接每个对象的中点与平面相交的线在该行的中点的线。如果对象的边界体积对这个平面的两侧分，这是一个冲突（你只需要测试对飞机的两个边界卷之一）。另一种方法是增强<一href="http://en.wikipedia.org/wiki/Gilbert%E2%80%93Johnson%E2%80%93Keerthi%5Fdistance%5Falgorithm">GJK距离算法。如果你想有一个教程，通过潜水，看看讷河制作'OpenGL的教训＃30
With regards to collision detection, each object also generally has a bounding volume mesh (set of polygons forming a convex hull) associated with it. These highly simplified meshes (sometimes just a cube) aren't drawn but are used in the detection of collisions. The most rudimentary method is to create a plane that is perpendicular to the line connecting the midpoints of each object with the plane intersecting the line at the line's midpoint. If an object's bounding volume has points on both sides of this plane, it is a collision (you only need to test one of the two bounding volumes against the plane). Another method is the enhanced GJK distance algorithm. If you want a tutorial to dive through, check out NeHe Productions' OpenGL lesson #30.
顺便提及，包围盒也可用于其它的优化，如所谓的遮挡查询的。这是确定哪些对象是后面其它目的（封堵器），因此不需要进行处理/呈现的处理。包围盒也可用于域剔除的是确定的方法，该对象是立体观看体积之外（太近，太远，或超过视场的你的角度），因此不需要被渲染。
Incidently, bounding volumes can also be used for other optimizations such as what are called occlusion queries. This is a process of determining which objects are behind other objects (occluders) and therefore do not need to be processed / rendered. Bounding volumes can also be used for frustum culling which is the process of determining which objects are outside of the perspective viewing volume (too near, too far, or beyond your field-of-view angle) and therefore do not need to be rendered.
正如Kylotan指出的，使用的是边界体积可以产生假阳性检测闭塞时，只是不为某些类型的对象，例如环形（例如，通过在孔中寻找一个圆环）在所有的工作。有了这样的物体遮挡正确的是完全是另外一个线程的门户扑杀的。
As Kylotan noted, using a bounding volume can generate false positives when detecting occlusion and simply does not work at all for some types of objects such as toroids (e.g. looking through the hole in a donut). Having objects like these occlude correctly is a whole other thread on portal-culling.
这篇关于如何三维碰撞/对象检测的工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
