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\$

2 Answers 2

Reset to default
26
\$\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\$
2
  • \$\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, 2015 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\$
    – user1430
    Mar 27, 2015 at 20:48
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\$
4
  • \$\begingroup\$ How do you do collision detection on shapes made up of triangles? \$\endgroup\$
    – JackOfAll
    Mar 26, 2015 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, 2015 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\$
    – Vaillancourt ♦
    Mar 26, 2015 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, 2015 at 14:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .