0
\$\begingroup\$

I'm implementing my physics engine for my 3D game. So far I've been able to implement collision detection between OBB, spheres and planes. The engine generate contacts and resolve them with an iterative impulse-based approach.

The result is this (so far).

Now I need to detect and generate contacts between a height map terrain and those bounding volumes (sphere and OBB). The terrain looks like this:

enter image description here

I don't know how to do it. I need to detect collisions and generate contact data (contact point, contact normal and interpenetration to feed my existing engine). I know I can't use a SAT because the terrain in not convex. What about ad hoc code for boxes and spheres? or is there a general approach?

EDIT

I narrowed down my problem to detecting (and resolving) collisions between a simple convex collidable (sphere/OBB) and triangles (always convex). Since the terrain is stored as an height map I can easily select a subset of triangles to run the algorithm against. I can use the SAT to detect interpenetrations. But what about collision response? How can I generate the necessary contact data (collision point and collision normal) to resolve the collision?

Improve this question
\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

Terrain is a difficult collision detection example, as it is complex, so you reduce the complexity of the problem. One possible solution, for static terrain meshes:

Make your terrain out of small manageable chunks. Organise each of them into triangles.

When you load your terrain meshes, generate an AABB and triangle set from the the vertex data. The AABB is for your broadphase, and the triangle set is for your narrow phase.

Once a possible collision is detected, you then perform an OBB/triangle, or sphere/triangle collision check. You can use any narrow phase algorithm you wish at that stage.

This is by no means the most optimal solution, but it's one possible workable solution.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ I'd like to test against the terrain mesh for the fine collision detection. Maybe some ad hoc code for OBB and spheres will suffice. I was thinking of getting the bounding volume's position relative to the terrain (x and z), then extract a subgrid of terrain vertices and perform collision on that subset. But since the terrain can be concave I don't know how to perform the test and generate contact data. (SAT and GJK work only for convex polyhedra as I understand). \$\endgroup\$
    – Luca
    Nov 6, 2018 at 10:05
  • \$\begingroup\$ That is true, most algorithms only work on convex shapes. This is precisely why you need to base your fine (narrow phase) detection on triangles. It's makes the detection code very simple. Testing against the vertices could become very expensive, depending on how high the polygon count is in your terrain. Maybe something inbetween the two extremes would suit you as an approximation. \$\endgroup\$
    – Ian Young
    Nov 6, 2018 at 11:12
  • \$\begingroup\$ can you please show me some example, or point me to some resource? I don't understand quite well what you mean. \$\endgroup\$
    – Luca
    Nov 6, 2018 at 20:19
  • \$\begingroup\$ Ok, I've searched the web and came to the same conclusion as the one you pointed out. I need to perform OBB/triangle or sphere/triangle collision detection on a subset of the terrain's traingle mesh. Since a triangle and a box/sphere are convex I can use SAT. But how can I test the volume against each triangle and still have good performance? \$\endgroup\$
    – Luca
    Nov 6, 2018 at 22:07
  • \$\begingroup\$ There are small optimisations you can make per set of triangles. You can easily find the nearest subset via volume position, then check those. My advice is to get the basic algorithm working, then experiment once you understand fully how it works. \$\endgroup\$
    – Ian Young
    Nov 7, 2018 at 9:40

You must log in to answer this question.

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