3D 中三角形到三角形碰撞检测
我了解两个三角形之间的三角形到三角形的碰撞检测。 有人可以解释一下我如何将它与由 1000 个顶点组成的 3D 对象一起使用吗？ 如何为每个网格创建三角形列表？ 我必须接受顶点的每个排列吗？ 这将导致 O(n^3)，我觉得这非常糟糕。
我该如何概括这一点？
我需要从某种格式读取数据。如果一切都失败了，有人可以建议一种用三角形制作网格的格式吗？我还需要该格式的网格目录，至少对于初学者来说是这样。
非常感谢。
I understand triangle to triangle collision detection betwheen 2 triangles.
Can someone explain how could I use this with a 3D object made-up of 1000s of vertexes?
How can I create a list of triangles for each Mesh?
Do I have to take every permutation of vertexes?
That would lead up to O(n^3) which I find very bad.
How can I generalise this?
I will require to read data from a format. If all else fails, can someone suggest a format that makes the Mesh from triangles? I would also need a catalog of Meshes for the format, at least for starters.
Thanks very much.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以应用许多优化来检测网格之间的碰撞：
空间分区，如 James 所描述。
使用边界体积进行早期拒绝。例如，球体与球体的碰撞成本很低，因此在测试网格体 A 和 B 是否发生碰撞之前，您可能会看看 A 周围的球体是否与 B 周围的球体发生碰撞。如果球体未命中，则显然网格体不会发生碰撞，因此不会发生碰撞需要测试它们。不同类型的对象可能需要不同类型的包围体：轴对齐的长方体和圆柱体很常见。
缓存见证人。在某些碰撞测试中，您最终会计算碰撞的“见证”，例如，当您应用分离轴测试您计算一个分离轴。如果某个轴在时间 t 时将两个对象分开，则它很可能会在时间 t 时继续将它们分开 + δ，因此可以支付缓存该轴的费用您找到了并下次先尝试一下（请参阅 Rabbitz，Graphics Gems IV 中的“移动凸多面体的快速碰撞检测”）。
There are lots of optimizations you can apply to detecting collisions between meshes:
Space partitioning, as described by James.
Early rejection using bounding volumes. For example, sphere–sphere collision is cheap, so before testing whether meshes A and B collide, you might see if a sphere surrounding A collides with a sphere surrounding B. If the spheres miss, obviously the meshes can't collide, so no need to test them. Different kinds of objects might need different kinds of bounding volumes: axis-aligned cuboids and cylinders are common.
Caching of witnesses. In some collision tests you end up computing a "witness" to the collision, for example when you apply the separating axis test you compute a separating axis. If an axis separates two objects at time t, it's likely that it continues to separate them at time t + δ, so it can pay to cache the axis you found and try it first next time (see Rabbitz, "Fast Collision Detection of Moving Convex Polyhedra" in Graphics Gems IV).
http://en.wikipedia.org/wiki/Binary_space_partitioning
BSP树是一种非常有效的方法检查静态网格物体的碰撞，但它确实需要对网格物体进行一些预处理以确保没有三角形相交。它的工作原理是将网格划分为半空间。这使得碰撞检查和物理变得更加容易。
编辑：
我觉得我还应该提到八叉树。与 BSP 树的总体思路相同，但它将模型划分为递归更小的立方体而不是半空间。
http://en.wikipedia.org/wiki/Octree
在回答你的第二个问题时，有一些像 .obj 文件格式可能就是您正在寻找的。
http://en.wikipedia.org/wiki/Wavefront_.obj_file
http://en.wikipedia.org/wiki/Binary_space_partitioning
A BSP tree is a very efficient way of checking collision of static meshes, but it does require some preprocessing of the mesh to make sure no triangles intersect. It works by partitioning the mesh into half-spaces. This makes collision checking and physics easier.
EDIT:
I feel as though I should also mention the Octree. Same general idea as the BSP tree but it partitions the model into recursively smaller cubes instead of half-spaces.
http://en.wikipedia.org/wiki/Octree
In answer to your second question, something like the .obj file format might be what you are looking for.
http://en.wikipedia.org/wiki/Wavefront_.obj_file