# 3D solid object in terrain

Im trying to make a solid object to stay always in the terrain level, but I am facing some problems. The terrain is not flat, I mean, it can have mountains and craters for example. I just have a ASE (ASCII Scene Export) file of the 3D map. The problem is, I know what is the object's X & Z values are, but I don't know how to determine the Y value for that specific location. I suppose I'd need Y value to always stays with the ground level, so I can realistically make the object walk through the cratter or the mountain.

The only info I have of the map (which I think it should help but I'm not that good in physics or in math, so I can't do much with it) is some vertex coordinates, like:

*MESH {
*TIMEVALUE 0
*MESH_NUMVERTEX 5424
*MESH_NUMFACES 8357
*MESH_VERTEX_LIST {
*MESH_VERTEX         0  32472.1055  52576.4922  1245.4102
*MESH_VERTEX         1  32660.6992  52576.4922  1245.4102
*MESH_VERTEX         2  32472.1055  52632.8086  1245.4102
*MESH_VERTEX         3  32660.6992  52632.8086  1245.4102
*MESH_VERTEX         4  32467.2617  52576.4922  1550.3711
*MESH_VERTEX         5  32607.6055  52576.4922  1550.3711
*MESH_VERTEX         6  32467.2617  52632.8086  1550.3711
*MESH_VERTEX         7  32607.6055  52632.8086  1550.3711
*MESH_VERTEX         8  32578.9648  52576.4922  1396.7617
....

*MESH_FACE_LIST {
*MESH_FACE         0:    A:         7 B:         6 C:         4 AB:    1 BC:    1 CA:    1   *MESH_SMOOTHING 1  *MESH_MTLID 0
*MESH_FACE         1:    A:         4 B:         5 C:         7 AB:    1 BC:    1 CA:    1   *MESH_SMOOTHING 1  *MESH_MTLID 0
*MESH_FACE         2:    A:        15 B:         0 C:         1 AB:    1 BC:    1 CA:    1   *MESH_SMOOTHING 1  *MESH_MTLID 0
*MESH_FACE         3:    A:         1 B:        12 C:        15 AB:    1 BC:    1 CA:    1   *MESH_SMOOTHING 1  *MESH_MTLID 0
*MESH_FACE         4:    A:        12 B:         1 C:         3 AB:    1 BC:    1 CA:    1   *MESH_SMOOTHING 1  *MESH_MTLID 0
*MESH_FACE         5:    A:         3 B:        13 C:        12 AB:    1 BC:    1 CA:    1   *MESH_SMOOTHING 1  *MESH_MTLID 0
*MESH_FACE         6:    A:        13 B:         3 C:         2 AB:    1 BC:    1 CA:    1   *MESH_SMOOTHING 1  *MESH_MTLID 0
*MESH_FACE         7:    A:         2 B:        14 C:        13 AB:    1 BC:    1 CA:    1   *MESH_SMOOTHING 1  *MESH_MTLID 0
*MESH_FACE         8:    A:        14 B:         2 C:         0 AB:    1 BC:    1 CA:    1   *MESH_SMOOTHING 1  *MESH_MTLID 0
*MESH_FACE         9:    A:         0 B:        15 C:        14 AB:    1 BC:    1 CA:    1   *MESH_SMOOTHING 1  *MESH_MTLID 0
....


Should I take all the vertices and faces and draw the whole map to simulate the object walking server-side to pass the correct Y values to the client, or can I use somekind of math equation to get them? I don't think it would be wise to "render" the map in the server aswell...

So your terrain is made of triangles (Mesh faces). Each mesh face has 3 vertices (A, B, C). I don't exactly know what AB, BC and CA are, but they're always 1, so they're probably some normals or scale factors or whatever.

Your solution is to find out in which triangle your object currently is and by interpolation of those 3 vertices find out correct height on exact location in triangle.

So first you will ignore Y coordinate (height) and just find (with some heuristic) the correct triangle - triangle containing your object position. Then you should use these steps (let's say you have point X in triangle ABC):

You will get line CX and find intersection of this line and AB - let's call this point I. You will interpolate height of A and B points to get height of I.

Then you will interpolate I and C to get height of X. And you are done ;)

Terrain is usually represented by a uniform grid of quads, not triangles. So it's much easier to find quad containing your object. I don't know if your mesh is also uniform grid - it that case, it would be really easy.

• How should I proceed to find out which triangle I am in? Can you show me some examples? I should take 3 from 3 vertex in the ASE, construct a triangle and store in an array or something, and then look for the triangle whose X is aprox. equal to my object X? Jun 7 '13 at 19:00
• Not exactly - you want to find which triangle contains you point - just try to google "Point Triangle intersection" or something like that. The slow approach is to test all triangles. Better approach is to use some heuristic. Maybe your triangles are in some grid (I don't know). But remember - you don't care about height for this problem, so you are working in 2D. Jun 7 '13 at 19:31
• For example, if your triangle is ABC clockwise, you want to determine, if point X lies to the right from all lines AB, BC, CA. And this can be determined with cross product. (blackpawn.com/texts/pointinpoly) Jun 7 '13 at 19:34
• You say I need to find which triangle contains my point, but how am I going to construct this triangle? I take the vertices from the ASE file, every three lines, and create a triangle and store them in some container? Jun 7 '13 at 20:53
• For example. It's up to you. You don't need any triangle at all. Vertices are enough. Naive solution: Take 3 vertices, make "triangle" (i.e.: some struct), put it in array. Take your object and it's location X, go through all triangles until one is found, which satisfies condition, that X lies to the right from all lines AB, BC and CA. When you have this triangle, use interpolation to get height of X. Jun 7 '13 at 21:25