How should I go about making terrain collision system without hightmap ?

What I have tried is building a heightmap from a blender model, but that works only if the vertices are evenly spaced. Mine are not and I am not sure how to proceed from here.

How do i store the mesh info ? Do I store a Plane object for every triangle in the mesh and then plug those in some kind of grid/quad tree etc ? Is that the best thing to do ? My terrain has around 2000 faces, wouldn't that be too much ?

  • \$\begingroup\$ Does your terrain contain features like overhangs, caves, or tunnels, or is a vertical projection like a heightmap viable if you can solve the variable density problem? \$\endgroup\$ – DMGregory Sep 20 '18 at 9:11
  • \$\begingroup\$ no things like that, the only difference from regular heightmap are the vertex distance \$\endgroup\$ – Martin Spasov Sep 20 '18 at 9:17

A heightmap is just a mapping from 2D horizontal positions to heights. It's often implemented as a regular grid of height samples we could encode in say a texture's grid of pixels, but that's by no means a requirement.

Instead, we could implement it as a 2D quadtree/bounding volume hierarchy (or other spatial partition), storing our vertices or triangles by their horizontal positions/extents. This lets us quickly isolate which triangles of the terrain lie within the footprint of a prospective collider. If each node of the tree also tracks its max height, we can use this as an early-out to skip checks for objects elevated above the terrain.

Once you have the potential triangles involved, then it's just a series of triangle-primitive collision checks, like a regular mesh collision. We just use the nature of the terrain to help us isolate the relevant triangles more easily.

"My terrain has around 2000 faces, wouldn't that be too much?"

That's a question for your profiler, but there's no particular reason to expect it would be. A good spatial partition should let us get to the relevant triangles in a number of steps logarithmic in the number of faces, so you're looking at a tree depth of a dozen or less. After that, your time spent on collisions will be determined by how many triangles you need to check, so as long as your colliding objects aren't spanning hundreds of triangles worth of terrain, you should be fine. (And if they are, it might be a good idea to let them collide with a simplified terrain with fewer triangles - if I'm trying to simulate a cruise liner, it's not going to care about every little bump and divot.)

| improve this answer | |
  • \$\begingroup\$ ty for the answer, can you explain in a bit more detail how exactly storing our vertices or triangles by their horizontal positions/extents works ? \$\endgroup\$ – Martin Spasov Sep 20 '18 at 10:13
  • \$\begingroup\$ If your coordinate system is, for example, x: right, z: forward, y: up, then this just means breaking down your terrain into the 2D spatial partition of your choice using its XZ coordinates. So, say we decided to store it as a bounding volume hierarchy of triangles (in 2D, an R-tree). Each triangle's bounds would be its XZ-aligned bounding rectangle. \$\endgroup\$ – DMGregory Sep 20 '18 at 10:17

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.