13
\$\begingroup\$

I understand that any shape can be created (or approximated) by smaller triangles. Any rectangle can be created by 2 smaller triangles. Any circle can be created by many thin "pizza slice" triangles. How does this translate to collision detection?

I understand how to calculate rectangle overlap using the vertices. I understand how to calculate circle overlap using the center, radii, and distance.

But, how does one do collision detection on shapes made of small triangles? Not specifics, but just the general concept....

\$\endgroup\$
27
\$\begingroup\$

But, how does one do collision detection on shapes made of small triangles?

By not doing it.

Collision detection against an arbitrary triangle collection (or worse, between two collections of arbitrary triangles) is prohibitively expensive.

Instead, we typically perform collection detection in a hierarchical fashion, beginning first with extremely crude, simple shapes (like boxes or spheres) that approximate (poorly) the underlying object.

This allows us to quickly reject the majority of potential collisions as "not occurring," which is the usual case. In the case where a such a crude check passes, that indicates a potential actual collision, and we proceed to perform the check against a more-detailed approximation of the underlying shape (such as one made of multiple tightly-fitted capsule shapes, or many aligned bounding boxes).

Essentially, collision detection starts with crude tests and, as those tests pass, continues to more and more detailed representation. This image, provided by Shiro in a comment to Alexandre's answer, illustrates how a complex model (a human) may be represented by a series of simpler shapes:

hitboxes

Rarely do we actually need to perform collision at the individual triangle level, and when we do we've usually used the cruder methods to drill down to a very small set of potential triangles to test against. At that point, specific algorithms are used to perform the tests, just like you'd test if two rectangles overlap. For example, you can determine if and where a ray hits a triangle.

\$\endgroup\$
  • \$\begingroup\$ Thanks. Yes, if I were actually making a game, I would just use some existing engine. But, I just want to understand the basic ideas that are implemented in a pre-made collision detection engine. In your diagram above, you would be using rectangle math to see if anything is touching ANY of the dozens of rectangles that make up the man. Is that the basic idea? \$\endgroup\$ – JackOfAll Mar 27 '15 at 20:29
  • \$\begingroup\$ Those are oriented bounding boxes (3D) not rectangles. But yes. If I was going to test if a ray (representing, say, a bullet) collided with the player I'd be testing the ray against those boxes -- possibly after first testing against one giant box representing the whole character -- not against every triangle of the render mesh). \$\endgroup\$ – Josh Mar 27 '15 at 20:48
  • \$\begingroup\$ The idea is that you can use a rough approximation of the character, such as the oriented bounding boxes shown in the image above, and test that first to do a less expensive hit test, and if there is collision then drill down to a lower level IF NECESSARY, testing individual triangles contained with the bounding box. Typically there can be several different BVs used hierarchically, with the outer one being less accurate but the fastest to test (sphere, bounding box), and drilling down to something more specific (k-DOP), and potentially drilling down even further (triangles) \$\endgroup\$ – Kik Mar 27 '15 at 20:49
4
\$\begingroup\$

The collision detection is based on geometry (primitives like line, planes, spheres, boxes, capsules, cylinders).

If you need to perform collision detection on shapes made out of triangle, for instance a terrain that is not flat, you have to test against all the triangles that form the mesh.

If you get to that point, I would strongly advise to use a pre-made collision detection engine, as this kind of stuff get pretty complex, pretty fast.

\$\endgroup\$
  • \$\begingroup\$ How do you do collision detection on shapes made up of triangles? \$\endgroup\$ – JackOfAll Mar 26 '15 at 19:39
  • \$\begingroup\$ @JackOfAll he already mentioned that in his reply, it is by using geometry shapes usually i.stack.imgur.com/CAhxn.jpg \$\endgroup\$ – dimitris93 Mar 26 '15 at 19:42
  • \$\begingroup\$ @JackOfAll I edited my answer; and like Shiro says, if you have more complex "items" in your environment (bodies, chairs, cars, etc...), in game development they're usually made out of simpler primitives that are tied together. The detection of collisions is made on the primitive shapes, but the physics simulation is then made on the whole body. \$\endgroup\$ – Alexandre Vaillancourt Mar 26 '15 at 19:48
  • 4
    \$\begingroup\$ I'm not literally trying to make a game, I just want to understand the basic ideas that are implemented in a pre-made collision detection engine. If I were actually making a game, I clearly would not be reinventing the wheel, agreed. \$\endgroup\$ – JackOfAll Mar 27 '15 at 14:42

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.