# Finding current face in terrain

This topic is 5392 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I need to find a face (triangle) in my terrain so I can do terrain following. I'm planning on doing this by finding the current face and interpolating the exact height based on the heights of the three corners of the face (weighted by their distance to the point). What's the best way to do this? Thanks as always for the help! Onnel

##### Share on other sites
If the grid is axis-aligned and the quads are all split in the same direction, then it is pretty easy.
x0,y2,z2   +   | \    |   \  h |  *  \    | x,y   \    +--------+ x1,y0,z1       wx0,y0,z0

1. Figure out which quad it is in.
2. Figure out which triangle it is in by comparing the X and Y coordinates. If x1-x > y-y0 it is in the lower-left otherwise it is in the upper right. If the quad is split along the other diagonal, the test is similar.

3. z = z0 + (z1-z0)*(x-x0)/w + (z2-z0)*(y-y0)/h

It's actually a little more complicated than this but you can figure it out.

##### Share on other sites
in case you have some sort of lodding going on, i would advice against using the mesh for collision, but rather interpolate heightdata.

if its for a static mesh, your method sounds right. you need to find the position in triangle coordinates, also called barycentric coordinates if im not mistaken. mathworld will tell you all you need to know about them, but you can easily find them and use them as weights for each vertex position, like you suspected.

##### Share on other sites
On the lodding issue, as long as the lodding doesn't make the mesh more difficult to access and interpret, I am compeled to disagree with Eelco for several reasons:

1. One usually wants their vehicles to follow the terrain as it is rendered, not as it should be theoretically. That is, one wants the displayed data to be consistant: if you follow the rendered mesh, your vehicles will always appear to be on the ground; if you follow the full-detail height data, the vehicles may sometimes appear to be "flying" or "submerged" at lower lods.

2. At short distances, the rendered terrain is in full or almost-full detail, so following the rendered mesh still gives correct results.

3. At larger distances, the "error" that results from not following the exact height data is not very noticable. On the contrary, following the exact data may lead to visual artifacts (see point 1).

4. If the height data is generated procedurally, it may be expensive to generate or chache full-detail geometry all over.

5. Again for procedural data, there may not even be a "full-detail" level, as you can always add more detail as necessary.

A caveat of this though, is that you have to update the vertical position of all your vehicles (and other objects, for that matter) every time the lod changes. But since that is done (almost) every frame anyway, that's not that much of an issue.

##### Share on other sites
Thanks, worked like a charm and was VERY simple to impliment! I am going from my original data and NOT the triangles I render (so my ais slightly different, but uses your basic idea). I definitely want them moving according to real data and not the displayed triangles, since angles can effect things like speed. I don't want gameplay factors changing based on what triangles/angles the engine decides to display.

Nice to see my creatures following the terrain. Of course, it's not pretty yet, since it's based on the middle point of the model and especially with four legged creatures they cut in to the terrain.

I guess the only way to really handle that nicely (if I want to bother) is to make a joint/spring in the creature, make all the feet touch the ground first, and then have the body modify itself as needed to keep the feet on the ground.

Any better ideas?

Onnel

##### Share on other sites
Quote:
 Original post by technobotOn the lodding issue, as long as the lodding doesn't make the mesh more difficult to access and interpret, I am compeled to disagree with Eelco for several reasons:

as do i :)
Quote:
 1. One usually wants their vehicles to follow the terrain as it is rendered, not as it should be theoretically. That is, one wants the displayed data to be consistant: if you follow the rendered mesh, your vehicles will always appear to be on the ground; if you follow the full-detail height data, the vehicles may sometimes appear to be "flying" or "submerged" at lower lods.2. At short distances, the rendered terrain is in full or almost-full detail, so following the rendered mesh still gives correct results.

2 solves 1.

Quote:
 3. At larger distances, the "error" that results from not following the exact height data is not very noticable. On the contrary, following the exact data may lead to visual artifacts (see point 1).

!. visual problems will only fade away with distance. if your lod is decent, visual error will be contant everywhere, aswell as small.

Quote:
 4. If the height data is generated procedurally, it may be expensive to generate or chache full-detail geometry all over.

good point.

Quote:
 5. Again for procedural data, there may not even be a "full-detail" level, as you can always add more detail as necessary.

yes, but you probably dont care about high frequency noise, so you can ommit it for physics.

Quote:
 A caveat of this though, is that you have to update the vertical position of all your vehicles (and other objects, for that matter) every time the lod changes. But since that is done (almost) every frame anyway, that's not that much of an issue.

id say its a big issue. i think this discontinuity is much more appearant (although also fading away with lod) than the alternative. besides its just not 'right'...

its a case of a discontinuous vehicle (which not every physics engine willbe able to handle without quirks) vs a maximum of a pixel or two floatation/penetration worst case, IF you lie down on the groud making an effort to look for it.

besides the heightmap will give a much smoother ride for entitys not close to the camera. far away terrain will produce a much less C1 continuous ride, resulting in inconsistent and not reproducable behaviour which might be very relevant for far away things like AI entities. also, having physical behaviour depend on machine power is rarely a good idea.

it seems we very much disagree, and i believe we have before on this issue. im always up for a good discussion though :)

##### Share on other sites
Well actually I was refering purely to rendering purposes. For physics/AI simulation I agree that the "full-detail" version is generally better suited. Of course, that would require one to calculate slope and height twice, once for rendering and once for simulation. I suppose the benefit of that depends highly on the LOD implementation and the type of simulation one is doing. Regardless, the generation/storage issue for the procedural case is still a difficult problem. That said, allow me to adress your points individually:

Quote:
Original post by Eelco
Quote:
 1. One usually wants their vehicles to follow the terrain as it is rendered, not as it should be theoretically. That is, one wants the displayed data to be consistant: if you follow the rendered mesh, your vehicles will always appear to be on the ground; if you follow the full-detail height data, the vehicles may sometimes appear to be "flying" or "submerged" at lower lods.2. At short distances, the rendered terrain is in full or almost-full detail, so following the rendered mesh still gives correct results.

2 solves 1.

At close range, yes; at longer range it depends on the LOD implementation details.
Quote:
 if your lod is decent, visual error will be contant everywhere, aswell as small.

Good point.
Quote:
Quote:
 5. Again for procedural data, there may not even be a "full-detail" level, as you can always add more detail as necessary.

yes, but you probably dont care about high frequency noise, so you can ommit it for physics.

Although I was only refering to rendering, you can ommit high frequencies there as well, as far the vehicle placement is concerned. But I decided to mention this anyway, if only for the sake of completeness.
Quote:
 its a case of a discontinuous vehicle (which not every physics engine willbe able to handle without quirks) vs a maximum of a pixel or two floatation/penetration worst case, IF you lie down on the groud making an effort to look for it.besides the heightmap will give a much smoother ride for entitys not close to the camera. far away terrain will produce a much less C1 continuous ride, resulting in inconsistent and not reproducable behaviour which might be very relevant for far away things like AI entities. also, having physical behaviour depend on machine power is rarely a good idea.

The discontinuities should not be very visible as far as the rendering is concerned, but for the purpose of simulation, that is a good point indeed.

##### Share on other sites
that would make it interesting for multiplayer games.

-you yourself have highest detail
-other player is far away, sees lowest detail
-where to place you now?

if he starts shooting and you use different positions he will shoot far above and below you, so it would look silly if you still got hit. and i really wouldnt want to even think about compensating that kind of stuff by making even the shots go in different directions on different machines just to look right. i guess id rather render the part with a player on it with high enough detail to make the error small enough (after all, NOT seeing that guy shooting at you because he is inside a hill isnt fun either.. though you could probably say "ehm.. he's hiding in a bush").

##### Share on other sites
Quote:
 Original post by Triencothough you could probably say "ehm.. he's hiding in a bush".

LOL, yea..

Anyway, I'd like to add a few notes, plus address the multiplayer concern:

If the full-detail height data (ignoring the unimportant high frequency details) for the entire visible part of the terrain is available, then it is probably better to use that data for the vehicle positioning as well as the simulation. This would resolve all the simulation issues (including multiplayer concerns). Also, as noted by Eelco, given a proper LOD system, the visual artifacts of "flying" and "sinking" should be minimal, perhaps even completely unnoticable. Using separate height/slope calculations for the rendering is probably not really worth the effort.

On the other hand, if you're dealing with procedural terrain (as in my case), and find that generating or caching full-detail data for the entire visible area is too expensive, then using the LODed data is perhaps your only choice.

As it turns out, AI often doesn't need to be as smart far away from the camera as it has to be at close range. This is called AI LOD. The same applies to physics: for example, you may be doing full rigid body dynamics near the camera, but there is no point doing that at large distances as well. So if the simulation is designed and implemented well, the view dependancy that results from using the LODed data can actually be a good thing, helping to improve performance.

As for discontinuities (which no self-respecting physics engine likes much), geomorphing would solve any temporal discontinuities (e.g. a vehicle dropping from y=100 to y=90 because the LOD just changed). Spacial discontinuities (the sharp bends where two or more trangles connect) are far less of an issue: a good physics engine should be able to deal with those reasonably well. In addition, such discontinuities become less significant closer to the camera, but at longer distances a simpler and therefore more tollerant simulation can be used. Further, any silght errors that do result from the spacial discontnuities, will also be partially masked by the perspective effect.

For multiplayer (again assumming procedural data), it seems the best choice would be to use the "server view" for simulation: the detail should vary based on the minimal distance to any (human?) player, and not just the one that's sitting at the given client terminal. Or, one could use the client view for local simulation, and apply periodical corrections supplied by the authoritative server, which obviously uses the server view.

EDIT: Just noticed the extra question by onnel:
Quote:
 Original post by onnelNice to see my creatures following the terrain. Of course, it's not pretty yet, since it's based on the middle point of the model and especially with four legged creatures they cut in to the terrain.I guess the only way to really handle that nicely (if I want to bother) is to make a joint/spring in the creature, make all the feet touch the ground first, and then have the body modify itself as needed to keep the feet on the ground.Any better ideas?

A full IK solution will probably give better results for organic creatures, but if you don't want to mess with that, then a joint/spring system may be a good start. Not sure what else you can do in between the two...

• 21
• 16
• 9
• 17
• 13