Nearest Vertex Calculations for Heightmap


First post here and I’ll try and be as clear as possible but its quite complex.

I currently have a program which renders a terrain and a character on the screen. Both are read from file (the character model is an md2) and the terrain is read from a unique file format (as in one that is not commercially available). Both draw correctly but in order to update the characters y-position based on his position on the map I need to find the nearest vertex to the character.

The terrain is made using a GLTriangleBatch of which I already know all the coordinates of the vertices (in the terrain file), and I have the formula to calculate the required y-offset of the character based on the nearest vertex.

Is there any way for me to find the nearest vertex to the character based on where he is on the terrain?

Seems pretty complex to me, I’ve been going over it for several days now and cant see how to get there.

Any help would be much appreciated!

How you do it depends on how the terrain is defined. There are two variables you need to deal with: the X and the Z coordinate of your character. If your terrain is defined on a regular grid (in X and Z), then it should be very easy to find the terrain vertex that is nearest (in X and in Z) your character’s X and Z because all the X and Z are linear. Basically, just map your X (and your Z) to the appropriate index in your terrain matrix. One line of code for X, and one line of code for Z. If your terrain grid in X and Z is not regular (or it is not axis aligned), then you will need a more complex method that searches for the nearest vertex. There’s always the brute force method: calculate the 2D (X & Z) distance of each terrain grid point from the character’s (X, Z) position. The smallest distance you find is the nearest grid point. There are various ways to optimize that, depending on the nature of your stuff. At the very least, you can probably exploit frame-to-frame coherence, i.e., if your character doesn’t move much from one frame to the next frame, then the nearest vertex will likely never be one than one away from the nearest vertex of the previous frame.

One idea: take the vertex of character’s “center”, then cast a ray downwards and find the intersection with the heightmap.

A kd-tree could help. Search ‘nearest neighbor kd-tree’.
Octree as well, but kd-trees are so simple to implement…