# How to determine character's foot contact point on a uniform triangle mesh terrain?

For a terrain that is modelled by a heightmap with a uniform triangle mesh, what are some techniques I could use to determine the contact point of the foot of a character standing on the terrain?

Since the terrain's Y values are altered by the heightmap, they won't be flat any more. As the character moves on the terrain, it has to know at which values of Y-value its foot should be. Conceptually, what are some methods and techniques to determine the contact point of the character's foot standing on the terrain?

• I'm not very experienced, so I'm not going to post a full answer. Anyways, in some basic examples I've seen a really simple method using collisions. The character could not fall through the terrain. Using "gravity", it would "stick" to the ground. However, the entity also slowly slided down hills... These examples though were for BlitzBasic which provides such a collision API natively. I guess another way would be to translate the height map into actual 3D-space coordinates and use them to set the height of your entity. Or mash a terrain collision system yourself. Commented Apr 28, 2013 at 20:08
• If you know how your mesh is generated, you can easily use something like linear interpolation to find the height at the contact point. Using the distance to the surrounding points, and their height values, you can find the height value at the contact point. Commented Apr 28, 2013 at 20:43
• You might want to consider using a third party physics engine at this point, which provides you with functions to cast a ray through the physics simulation and gives you back the position, normal and body of impact. Commented Nov 21, 2013 at 7:40

While the topic can be quite bi,g I will summarize the process in 3 steps. I will try to be concise:

### Identify the set triangle(s) that your character is likely be standing on (Broad phase)

This is a classic problem in collision detection, which is identifying the possible collisions (also called broad phase) in your world instead of checking for each pairs (the character and every triangle in your case).

The problem lays in the usually huge number of possible collisions, for example if your terrain consists of 1 million triangles, then here is one million checks just to know which triangle the character is standing on.

The good news is, such cases are typically solved by exploiting the spatial coherency of the world, closer object are more likely to hit each other than farther away objects. A classic implementation of such an idea is typically some kind of spatial data structures like uniform grids, kd-trees, and octrees. These will potentially narrow down the number of collision tests from O(n^2) to O(n), which (loosely speeking) most likely be "few number" of intersection tests.

I want to add, that in case your terrain triangles count or number of objects are small it's ok to use brute force which will take O(n^2), since it's "fine" for small sets.

### Check ray intersection with the potential triangles

Once you identified the potential triangles, you need to perform intersection test, from a ray that is dropped down from your character with the potential set of triangles, and calculate the intersection point.

### Calculate character standing height

Once you calculate the intersection point, you can do one of two things, depending on the situation:

• Directly use the "Y" of the calculated intersection point to adjust the standing point of your character.
• Use bi-linear interpolation, in case your character is still in the same cell, and is intersecting with the same set of triangles, to calculate the height and adjust the character's position.

First, you need to identify the triangle in your heightmap. Then you must find the point of intersection between the triangle's plane and the line that drops down vertically through it.

If you want more explanation, maybe this post will help.