I wanted to mention one more thing. Ray casting was suggested to determine on which triangle the character is standing. If you have a large set of triangles, you do not want to simply iterate over all triangles to search for the containing triangle.

Instead, take advantage of space-time coherency. Given an index array for the triangles, {i0,i1,i2,i3,i4,i5,...}, where triangle 0 is <V(i0),V(i1),V(i2)>, triangle 1 is <V(i3),V(i4),V(i5)>, and so on. It is relatively easy to build an adjacency list, {a0,a1,a2,...}. a0 is the index of the triangle that is adjacent to the triangle 0 edge <i0,i1>. a1 is the index of the triangle that is adjacent to the triangle 0 edge <i1,i2>. a2 is the index of the triangle that is adjacent to the triangle 0 edge <i2,i0>. If there is no adjacent triangle, set the adjacent index to -1.

If the character is currently in triangle t and the character moves, start the search at triangle t. If the motion is small relative to the size of the triangle, the probability is large that you are still in triangle t. However, if the character is not in triangle t, use a breadth-first search for the containing triangle by using the adjacency index list. The expected time for the search is O(1) [constant time] assuming the motion is small relative to the triangle size.

Quote:Original post by mikenovemberoscar
Another problem is that what happens with two-storey buildings? Just searching x and z won't be enough!

Well, your subject title is "Walking on a terrain ..." :)

When you throw in other objects such as buildings, then you have a problem that requires collision avoidance and path finding. I described such a system in "3D Game Engine Design, 2nd edition" (section 8.5). I had implemented this for a contract (so I cannot make the code public) and it worked well. You could walk around the terrain, into and out of buildings, stay on floors, stairs, etc.

Quote:Original post by mikenovemberoscar
Do you suggest I write my own level editor, so I can place a 'terrain' then add houses, etc? Or have two seperate OBJ meshes, one for terrain and one for buildings?

When I wrote terrain I actually meant anything, but I couldn't come up with a better word.

My original method was finding the closest triangle, so doing that shouldn't be a problem.

"Terrain" means something specific to me. And it is important to know whether the terrain mesh is a height field (only one triangle can be intersected by a vertical ray) or otherwise (you might have an overhanging cliff).

What I am suggesting is that staying on a height-field terrain is relatively simple. When you add world objects, the scene is more complicated and the problems you need to solve are more difficult.

For a terrain (height field with z-axis the up vector), you can cast a vertical ray and iterate over all triangles to determine the triangle that contains your character's (x,y) location. Then you can adjust the height (z-value) so that the character is standing on the triangle.

Consider now a character that is about to ascend a flight of stairs. You want the character to stay on the stairs as he ascends. You cast a ray to find out that it intersects *three* triangles. A stair triangle, a floor triangle (the floor is below the stairs), and a ceiling triangle (the ceiling is above the stairs). Which triangle do you select? Well, you have knowledge that the character is about to ascend the stairs, so you'll select the stair triangle.

Now let's make it slightly more difficult. The stairs are exposed, say, a wrought-iron fire escape. The character is not standing at the base of the stairs; rather, he wants to walk *under* the stairs. You cast a ray and find that it intersects three triangles (floor, stairs, ceiling). Which triangle do you select? Once again, you need knowledge of what the character wants to do. In this case, you'll select the floor triangle.

The problem is that your mesh is not a height field. And keeping the character on the correct triangles as he moves requires more than just geometric information.

Quote:Original post by Dave Eberly
Consider now a character that is about to ascend a flight of stairs. You want the character to stay on the stairs as he ascends. You cast a ray to find out that it intersects *three* triangles. A stair triangle, a floor triangle (the floor is below the stairs), and a ceiling triangle (the ceiling is above the stairs). Which triangle do you select? Well, you have knowledge that the character is about to ascend the stairs, so you'll select the stair triangle.

Now let's make it slightly more difficult. The stairs are exposed, say, a wrought-iron fire escape. The character is not standing at the base of the stairs; rather, he wants to walk *under* the stairs. You cast a ray and find that it intersects three triangles (floor, stairs, ceiling). Which triangle do you select? Once again, you need knowledge of what the character wants to do. In this case, you'll select the floor triangle.

The problem is that your mesh is not a height field. And keeping the character on the correct triangles as he moves requires more than just geometric information.

This problem(s) is pretty easily solved by shortening the ray used for casting. Typically a ray casted from the character's pelvic bone down to at most an inch below his feet will be sufficient. You then place the character at the first hit always.

This will lift your character up onto anything reasonable in height. You can choose to reject or otherwise handle step changes over a threshold.

If the ray does not intersect something, the character has left the ground and enters a physics based falling mode.

Lastly, ray cast against everything. Often physics engines are highly optimized ray casting machines, but ideally that would happen at the graphics detail level. It doesn't make sense when bullets or characters are hovering over the graphics because they're colliding with the physics primitive.

The odds of you getting a response to that are pretty slim. There's two very seperate things here. Ray casting, and character control. The ray casting part is a trivial math and data organization exercise that you'll benefit from doing yourself.

The ray casting should accept a world space ray (origin and extent) and return the first intersection point along that ray.

Then you simply put your character on this intersection point.

Math::Ray ray( characterPelvicPos, characterFeetPos - characterPelvicPos );RayCaster caster( ray );world.RayCast( caster );if( caster.HitSomething ){  Vec3 worldPos = ray.Evaluate( caster.TimeOfFirstHit );  MoveCharactersFeetToPos( worldPos );}

The time of hit is refering to a zero to one value along the ray. So Evaluate looks like this:

Vec3 Ray::Evaluate( float t ) { return Origin + Extent * t; }