Hi tobias !!! I have great news for you.

AHHHHH ! You posted an image showing that THE GRID IS COMPLETELY REGULAR! When seen from overhead, your grid is completely regular like a chess board. Great news!

Before beginning work on the game, renumber all the vertices entries so that they obey a simple relationship to that plain!

So you need only know the XZ coordinates of your character, and you can easily map that to the "grid" of 100x100.

Now you need to find the Y point relative to that square.

If we could trust that the square is not bent: looking at the next image, simply find the height of E and F by leaping from AB and CD respectively. They lerp EF to find the height of X.

Unfortunately the square ABCD is two triangles, so it is bent!

So you must find out which directed side of the line CB is the point X on! Fortunately this is a well known-problem!

http://www.blackpawn.com/texts/pointinpoly/default.html
http://www.gamedev.net/topic/542870-determine-which-side-of-a-line-a-point-is/
http://paulbourke.net/geometry/insidepoly/

here is how to do it:

     function pseudocode to find if point (P) is left or right of line (AB) P A B
     {
     //is "p" on the "right" side of any general directed line AB ?
     
     rightOfLineFactor = (aX-bX) * (pY-bY) - (aY-bY) * (pX-bX);
     
     if ( rightOfLineFactor > 0.0 )
         // it is on the right of the line
         // in this case travel from G to E in the final step explained below!
     else
         // it is on the left!
         // in this case travel from G to F in the final step explained below!
     }

{Just to be clear, in that code fragment, "AB" are local variables! I am not referring to "our" AB. In fact you would use such a routine to decide which side of our line "CB" the point X falls upon. Also obviously, where it refers to "xy" that would be "xz" in the context we are working, of course.}

You have now incredibly quickly found which triangle it is in, on the whole plain. You get another raise at your job at Nintendo!

Finally - again since everything is in a grid - just lerp lerp lerp lerp to find the height. Here's a diagram:

Just lerp along CB (use either the horizontal or vertical travel of X) to find the new point G.

Then finally you must travel from either G to E, or, G to F to at last get the height of X.

So ultimately you have the height of X with incredibly few calculations - awesome.

There are a couple of important points:

(1) the idea of making the grid a completely regular plain, is an incredibly good idea. If you were working at Nintendo they'd give you a raise. In fact it is such a good idea that: say the plain was NOT a completely regular grid: you would have to REMAKE the mesh so that it WAS a completely regular grid. Anything you can do at compile-time that saves you massive amounts of work at runtime, is an incredibly good idea.

(2) To repeat, if you do find that your grid is not regular (say for some reason it goes haywire on one side or whatever) - it fact you will actually have to remake the grid so that it is regular.

(3) If you are not yet familiar with renumbering vertices and so on- you will have to learn how :)

(4) When you are doing (3), there is a very important fact you need to know. Amongst people who are new to working in 3D, there is a common misconception that vertices in 3D models "have to be" shared, or "usually are" shared, when you get the model out of Maya or whatever. In fact that is totally and absolutely wrong. There is absolutely no reason at all that vertices in a 3D model have to be shared (even if they can be).

In practice in the real world any model you get contains a mess of shared/not-shared vertices - you absolutely cannot rely on them being either shred or not-shared.

To repeat, it is critical to understand this point!

If you are new to fooling around with 3D models, it is very important to realise this fact. If you are doing mesh manipulation work, it is SOP that you first have to change the mesh so that it is "all not shared" or "all shared" depending on what is convenient for you and for whatever type of work you are doing.

Now, here is a useful long discussion about it: note the three images:

http://answers.unity3d.com/questions/193695/in-unity-is-there-a-fast-way-to-find-nearby-triang.html

Be sure to download the three models and experiment. So when you rewrite the mesh so that the vertices are regularly counted across and down, in this situation it will be best if make sure they are "all shared". BTW by sheer luck, it may be that your mesh model is already organised so that all the vertices count across and then down in rows -- if so, your job is done.

One final happy point!

n your VERY SPECIAL CASE of a completely regular grid: Notice the pseudo code for "side of line".

In fact, the factors ....

 (aX-bX)
 (aY-bY)

are always the same!!!!!!!!!!!!!!!!!!!!!!!!!!!! If you wish, replace them with fixed values. You're just got another raise at your job at Nintendo! :) Personally: the solution is so elegant and the code is so fast that I would personally just leave it as the variables, so that if you or anyone uses the code in the future it will work perfectly regardless. Or at least, make a clear comment in your code to that effect. (If you end up using your "side of AB" routine in other situations, you will be annoyed that it does not work if you have the fixed values ! :) )

ONE VERY FINAL POINT!

f you want to be a real-smart arse, it might be that it is NOT GOOD ENOUGH to merely find EXACTLY where the point X sits on the triangles. You may have to smooth it - interpolate - as if the points on the mesh represent some theoretical platonic surface that is smooth.

In the unlikely case that you need to do this, almost certainly the approach to take is to use Catmull-Rom splines to produce an interpolation concept. Fortunately they are very easy to use, and, because of your incredible "regular grid" feature, again very easy in your specific clever situation, so you get yet ANOTHER raise at your Nintendo job. Calculating Catmull-Rom splines (which is easy) is beyond the scope of this question so you'd have to look it up and apply it to your special situation.

In my opinion, you would very likely never do this: if the original grid was not smooth enough: I would simply build a finer grid before beginning the show.

{Indeed, deciding on the size of that grid, is a big part of tuning the game so it works well. In practice you will probably annoyingly have to build a rig for tuning that factor - so you can easily try hundreds of different specific grid sizes. As usual, where building !@£!@$ rigs to tune setup factors, is more work than the game itself!}

Don't forget too: it is very likely you will not just "move" your character to the "new position" you have found on the grid. Almost certainly, you will lerp the position of the character from measurement-to-measurement, as the character goes about his business (just like any movement, at all, in any video game - do not even mention that the "camera follow point" of the character would almost certainly be again smoothed, in all meaningful situations) so it is very likely it would be pointless to further smooth your underlying measuring operations.

But I just wanted to mention it for the record.