# converting a height map to a mesh of "planar" quads

I have a flat grid of quads. I need to displace this grid by a height map. If the grid were made of tris I can simply read off the corresponding values from the height map. But with quads I have to ensure that the quad is planar that is all the four vertices must lie on a plane.Is there a way to generate the quads with the above restriction?

[This message has been edited by tarantula (edited 03-26-2002).]

If you want adjacent quads to be conencted to eachother, then I believe there is not way to do it. Otherwise you can find the normal of the heightmap, and create a quad from that normal. Literally all quad will be independent, and you will have huge cracks between the quads.

Yeah then it would have been simple. But since I’m using this for a terrain i would’nt want any cracks

If you don’t want cracks, use tristrips. It’s that simple.

Or use triangle fans (though only if you also are using some form of adaptive LOD).

If I could use tris I wouldnt have posted this question.Using quads is a must.I need them for some other feature.

thanks for the posts anyway.

Using quads is a must.I need them for some other feature

It’s impossible to use quads in this way - you could always fill in any gaps with tris…

or…forget “the other feature”.

Anybody care to point out that quads are really just tri strips with every two tri’s being planar. You can use tri strips and force ever 2 tris to be planar.

As for the actual question I am confused about keeping the quads planar. My suggestion if I am understanding you correctly. Would be to look at the average of the normals at the four points (in the height field). And use the averaged normal as the normal for the quad. That will keep in planar.

Happy Coding.

Well knackered I completely overlooked the possibility of filling the gaps with tris. But to look good it shouldnt be done that way as all the gap filling tris will be in the vertical plane.

I was thinking along these lines:
If I set 3 vertices of the first quad the other vertex could be determined. For the adjacent quad two have already been set, I have to set one more and determine the other and so on, in this way I can do it using quads only ( i need quads for very fast collision detection ,faster than quad trees).

[This message has been edited by tarantula (edited 03-26-2002).]

I don’t understand what your problem really is. You are saying you want to find a way to draw them in this way because of collision detection. That doesn’t really make sense to me. Drawing and collision detection are two seperate things. Draw the mesh using tristrips, and do collision detection with your quads. It won’t be perfect, but nothing usually is if you compromise.

Originally posted by DFrey:
Drawing and collision detection are two seperate things. Draw the mesh using tristrips, and do collision detection with your quads.

come on, I know I can draw quads as tris. My problem is not concerned with drawing. Its concerned with the generation of the quads.

glHi,

take a look at this:

1. libMini - a Terrain library, which comes with source!
http://wwwvis.informatik.uni-stuttgart.de/~roettger/
2. A lot of Information on terrain stuff http://www.vterrain.org

When I was doing that stuff I found alot of papers and code snippets on how to implement terrain and collision detection.

glGreets,

Martin

[This message has been edited by mphanke (edited 03-26-2002).]

tarantula said:

i need quads for very fast collision detection

Could you explain why you need quads? And why it is important to draw them instead of triangles?

Originally posted by tarantula:
come on, I know I can draw quads as tris. My problem is not concerned with drawing. Its concerned with the generation of the quads.

Dude; triangles can be treated as quads, just at a quad with a side length close to zero can be treated as a triangle. You can triangulate the surface, but use a duplicate representation of one vertex for each triangle in your code. Your algorithm doesn’t have to know what’s really going on.

thanks for the enlightenment, Decimal Dave. suppose the grid is like this . . . these are my quads initially .all Z values zero.
(ignore the dots damn this posting system whisked all my spaces away!)

±±±+
.|…|…|…|
±±±+
.|…|…|…|
±±±+
.|…|…|…|
±±±+

^Y
|
|
±–>X

Now I displace them only along the axis going out of the screen ie only in Z (ie X and Y coordinates remain unchanged.) THIS is how my algorithm requires the mesh to be.

[This message has been edited by tarantula (edited 03-26-2002).]

[This message has been edited by tarantula (edited 03-26-2002).]

[This message has been edited by tarantula (edited 03-26-2002).]

Generating planar quads from a height map is not a trivial thing because there is no guarantee that any four elevations on the map will be on the same plane. I think I see what you are trying to do though… With such a vertex arrangement, you can instantly calculate what face will be involved in a collision at any x,y coordinate (no checking actual vertex coordinates beforehand is required) since the vertex spacing is constant. Is this a correct assumption?

A lot of terrain engines actually work like that… The trick is that once you know four vertices in the applicable “quad”, they are further decomposed into triangles for more precise collision detection. The advantage is that vertices in the mesh can be placed arbitrarily instead of having the planar requirement.

[This message has been edited by Decimal Dave (edited 03-26-2002).]

Yeah you got it decimal dave! I know its not trivial that’s why I started the thread in the first place,I dont need much detail in the terrain but I want the detection to be VERY fast maybe for a thousand ants .

[This message has been edited by tarantula (edited 03-26-2002).]

[This message has been edited by tarantula (edited 03-26-2002).]

I would just split the quads into two triangles, and do the same thing, it is just one additional step to what you want to do. First find the “quad” the point of interest projects onto, and then determine which of the two triangles the point projects onto. Very simple.

[This message has been edited by DFrey (edited 03-26-2002).]

thanks DFrey, but I know what to do once I have the Quads. I dont know the best way to get the Quads that’s all.

I’m sorry you are confusing me, earlier you say you have the quads and want to find out how to connect them into a mesh. Well, that’s really not possible without distorting the collision hull away from the true mesh surface.

Also, you didn’t seem to get what I was saying earlier. When I referred to the “quad” I meant to imply that the “quad” was non-planar. Unlike your insistence that it be planar. I really don’t see what you are going to gain by this insistence, when triangles can be used in the exact same fashion, and without any of the hassle of trying to find a mesh that is constrained as you wish. My suggestion, drop the quads, go with triangles.

[This message has been edited by DFrey (edited 03-26-2002).]