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.

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.

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.

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").

Quote:Original post by Trienco
though 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 onnel
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?

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...