6

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.

Iustin
  • 1,220
  • 1
  • 12
  • 17
  • There are a lot of questions built into this, and they should all be asked separately instead of lumped into one question. Typically a "3d object" that'd you'd work with isn't just a [point cloud](http://en.wikipedia.org/wiki/Point_cloud), it is usually a [polygon mesh](http://en.wikipedia.org/wiki/Polygon_mesh) and/or a set of 3D curves. If you're really starting with a point cloud, then you might want to look up algorithms that are designed to create polygon meshes from point clouds before you work further on mesh->mesh overlap detection. – Merlyn Morgan-Graham Mar 17 '13 at 05:21
  • Once you have a a polygon mesh, then you'd start applying the optimizations that Gareth/James are talking about to avoid comparing every triangle in one mesh to every triangle in the other mesh. It would never be about every *possible* triangle that could be created from all the vertices of each mesh, as your question seems to imply. But every triangle in a mesh -> every triangle in the other mesh is still slow, and that's why you optimize further :) – Merlyn Morgan-Graham Mar 17 '13 at 05:23

2 Answers2

4

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).

Gareth Rees
  • 64,967
  • 9
  • 133
  • 163
1

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

James
  • 5,355
  • 2
  • 18
  • 30