Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  Derija93 Apr 28 '13 at 20:08
2  
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. –  Byte56 Apr 28 '13 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. –  danijar Nov 21 '13 at 7:40

2 Answers 2

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.
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.