4
\$\begingroup\$

For collision detection (moving vs. non-moving) in my current project, I decided to implement an octree approach after the preselection.

The only collision detection I'm currently using is a AABB-vs.-AABB collsion detection. Now, if this detection returns true for two objects (n, m), I want to subdivide the AABB into eight smaller axis-aligned boxes, and so on. (Octree)

Implementing the subdivision itself is now problem for me, but I'm stuck at the following: How can I determine whether a node needs to be divided further, or whether further subnodes are unnecessary?

Since I got objects of various complexity (a model with ca. 1500 vertices vs. a cube with 8), I can't simply check for the amount of vertices inside an octant.

What ways are there to determine whether a subdivision is necessard? Or am I even using a wrong approach any something else might work better?

Edit: I now think that an octree might be the wrong approach. What would be the best way to check for a more exact collision detection after an AABB collision detection returns true?

Improve this question
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Octrees, just like quadtrees, usually have some number of objects they hold per-node before they subdivide. I have an implementation here if you wanted to check it out. \$\endgroup\$ – fastinvsqrt Jul 31 '14 at 1:01
  • \$\begingroup\$ Actually I now think an octree might be the wrong approach... DO you have a better idea? \$\endgroup\$ – s3lph Jul 31 '14 at 12:49
  • \$\begingroup\$ Instead of AABB, you might want to look into OBB (oriented bounding boxes). It's more complex, but you could have an OBB per-part (arm, leg, etc) and that might give you the more exact collision detection you're looking for. \$\endgroup\$ – fastinvsqrt Jul 31 '14 at 15:28
  • \$\begingroup\$ The problem is that I am generating the BBs during runtime (after loading the mesh's data from a PLY file). Generating an AABB isn't hard, but I can't get a per-part-OBB from these data (vertices, normals). For the player figure I could embed the OBBs in the config, but it's something else for various obstacles... \$\endgroup\$ – s3lph Jul 31 '14 at 22:27
  • \$\begingroup\$ Are you going for mesh collision tests? \$\endgroup\$ – AturSams Oct 31 '14 at 20:26
2
\$\begingroup\$

If you are looking for precise mesh collision detection then you need to compare each pair of faces that are in the same cube in the 3d grid. You are right about avoiding an octree. Build a 3d grid that contains both objects an populate it with faces and check faces that are in the same cubes in the grid for intersection.

Please realize this is a slow (computationally intensive) process and therefore using a low-poly representative mesh for collision testing is recommended vs. using the high poly mesh which should only be used for rendering and may slow down collision testing extensively.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.