PDA

View Full Version : converting a height map to a mesh of "planar" quads



tarantula
03-26-2002, 04:30 AM
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).]

Bob
03-26-2002, 04:47 AM
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.

tarantula
03-26-2002, 04:55 AM
Yeah then it would have been simple. But since I'm using this for a terrain i would'nt want any cracks http://www.opengl.org/discussion_boards/ubb/frown.gif

zeckensack
03-26-2002, 05:34 AM
If you don't want cracks, use tristrips. It's that simple.

DFrey
03-26-2002, 06:28 AM
Or use triangle fans (though only if you also are using some form of adaptive LOD).

tarantula
03-26-2002, 06:42 AM
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.

knackered
03-26-2002, 07:34 AM
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... http://www.opengl.org/discussion_boards/ubb/smile.gif

or....forget "the other feature".

Devulon
03-26-2002, 07:52 AM
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.

tarantula
03-26-2002, 08:58 AM
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).

I wanted to know if there is a method to get the best fit quad mesh for a height map.


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

DFrey
03-26-2002, 09:36 AM
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.

tarantula
03-26-2002, 09:54 AM
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.

mphanke
03-26-2002, 12:19 PM
glHi,

take a look at this:
1) libMini - a Terrain library, which comes with source!
http://wwwvis.informatik.uni-stuttgart.de/~roettger/ (http://wwwvis.informatik.uni-stuttgart.de/~roettger/index2.html)
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).]

DFrey
03-26-2002, 01:08 PM
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?

Decimal Dave
03-26-2002, 01:21 PM
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.

tarantula
03-26-2002, 01:50 PM
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.
anyway thanks for your reply.

[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).]

Decimal Dave
03-26-2002, 02:26 PM
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).]

tarantula
03-26-2002, 02:30 PM
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 http://www.opengl.org/discussion_boards/ubb/wink.gif.
thanks again for your reply.

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

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

DFrey
03-26-2002, 02:59 PM
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).]

tarantula
03-26-2002, 03:06 PM
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.

DFrey
03-26-2002, 03:29 PM
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).]

tarantula
03-26-2002, 03:45 PM
I need to do real fast terrain collision detection say with thousands of objects.The terrain need not be too geometrically detailed.If I have quads (planar) then accurate collision detection can be done pretty fast.
What I'm trying to speed up here using planar quads is the collision detection not the rendering speed or something else so i'm better off without triangles.
thanks again.

Decimal Dave
03-26-2002, 04:20 PM
Originally posted by tarantula:
I need to do real fast terrain collision detection say with thousands of objects.The terrain need not be too geometrically detailed.

If your terrain is not very detailed to begin with, you could probably just treat the groups of 4 vertices as a planar quad even if it technically isn't. Assuming elevation changes are very gradual, the quads might be "planar enough" for your purposes.

To avoid depth buffer problems when rendering in this situation, either disable the depth test after you draw the terrain, or triangulate your quads such that they have a lower-seam bias (if that even makes sense).

tarantula
03-26-2002, 04:51 PM
less geometric detail = less number of quads.
less number of quads + low elevaton change = inclined plane http://www.opengl.org/discussion_boards/ubb/wink.gif .
Sorry if I wasnt clear, but I dont have low elevation changes.
thanks for your time.