# Collision between player and heightmap

Im programming a small project, an opengl height map. It is build of triangles, which points are fit to the right y position (read out of an image).

The player is represanted by a cuboid. (p1, p2, ... p8). now, i want to implement collision detection between the player and the heightmap.

I thought about split the whole world in cubes, and this cubes again in cubes, and then distribute the triangles of the heightmap in this cubes (then check for the big cube, the smaller cube, which contains the player, and then check all triangles for collision).

But which collision detection method would be the best here, and how could i implement it? (By the way, im using lwjgl [java])

It may not be necessary to go the Quadtree route as you're suggesting. How about breaking the problem down into two parts:

1. Store the heightmap data in a 2D array so that nodes can be accessed with O(1) time complexity.
2. Decide how far apart each node is in world-space coordinates. E.g. The coordinate (64, 64) might correspond to the "terrain-space" coordinate (4, 4) if nodes are 16 units apart. So when you want to know the height at a particular coordinate, all you need to do is heightMap[x>>4][z>>4] for example.
3. For the spaces in between just use bilinear interpolation of the surrounding node heights (also just by getting them from your array; no need to reference them anywhere else).

Now you have a method that can quickly give you the interpolated height of your terrain under any given coordinate.

1. So now you take your player's position and cuboid, and for each point (x, y, z):
• Sample your terrain height at (x, z).
• If any of the player's vertices' y-coords are less than the terrain height, you know that your player is colliding and you also know how far in they're colliding. No need to test with individual triangles.

Of course you can still do bilinear interpolation with any other data structure you store your terrain heightmap in like a QuadTree if you're doing any LOD or frustum culling stuff but it would be slower. You might even deem is sufficient to simply test terrain height against the centre of your player and a fixed (or averaged) distance threshold for "player height".