Geomipmapping and Triangle Strips
Author
I'm looking into doing an implementation of geomeipmapping and i've been working out the details. I've read Willem H. de Boer's paper and understand the theory behind it, but I've still got a few questions.
My biggest question is given a patch with any LOD and any configuration of neighboring LOD's is it possible to render the patch with a single draw call using triangle strips as the primitive. Or do you have to resort to using fans or some other primitive for the edges.
I've done up some images in trying to work this out.
This is the base patch. Can be drawn using 1 call (each row linked with degenerates)
Image 1
This is with the top row going down 1 LOD level to match the patch above it. I'm pretty sure this can be done with a single draw call.
Image 2
This is with the left and top edges knocked down one LOD level however, I'm not sure this can be done with one call.
Image 3
Beyond this, im not sure.
Any insight on this would be appreciated.
-=[ Megahertz ]=-
It can be done in a single call using either strips or lists. The key is degenerate triangles.
The idea is very simple. We have to identify triangles that are going to cause cracks with their neighbors, and degnerate them out of existence, by modifying their indices. I already have code for doing this, but I know some people would rather solve a problem on their own...if you'd like to just see the solution, feel free to ask. But my suggestion is to hack at it for a little while; the problem solving effort is worth the time [smile]
The idea is very simple. We have to identify triangles that are going to cause cracks with their neighbors, and degnerate them out of existence, by modifying their indices. I already have code for doing this, but I know some people would rather solve a problem on their own...if you'd like to just see the solution, feel free to ask. But my suggestion is to hack at it for a little while; the problem solving effort is worth the time [smile]
Author
Ahh, just the person I was hoping would reply. =)
I've read over your thread and skimmed over the code you supplied, however I noticed you used the GL_TRIANGLES primitive, so I wasnt sure if it was possible to do it with strips or not.
Well as long as I know its possible, then I'll have a crack at it (is that a pun?). I'll toy around with it see what I come up with, but its good to know that the offer to help is there.
Thanks for the info.
-=[ Megahertz ]=-
I've read over your thread and skimmed over the code you supplied, however I noticed you used the GL_TRIANGLES primitive, so I wasnt sure if it was possible to do it with strips or not.
Well as long as I know its possible, then I'll have a crack at it (is that a pun?). I'll toy around with it see what I come up with, but its good to know that the offer to help is there.
Thanks for the info.
-=[ Megahertz ]=-
Author
K, I think i got it.
Basically what you do is you go ahead and generate the lod patch like it was pretty much its own standalone patch. Then you go back and fix up the cracks by more or less sliding the verts that dont belong in the seam over to the next vert thats used in the LOD. However, you dont really move the vert, just replace the index that vert would normally use with the index of the other vert, effectively "moving" it.
After that you just render the patch as normal. The degenerates automatically take care of themselves.
Werd!
Now that I got the theory down. Time to implement it. One issue I'm going to have is finding adjacent patches due to the way my world is stored. Basically I have the entire world divided up into chunks, where each chunk is made up of 64 patches (8x8). Each patch is a 16x16 heightmap. (Subject to changed depending on the performance gain from the LOD stuff).
This way I can load new chunks in and drop the old chunks as the player moves across the terrain.
In any event, I'll figure that out in due time. =)
-=[ Megahertz ]=-
Basically what you do is you go ahead and generate the lod patch like it was pretty much its own standalone patch. Then you go back and fix up the cracks by more or less sliding the verts that dont belong in the seam over to the next vert thats used in the LOD. However, you dont really move the vert, just replace the index that vert would normally use with the index of the other vert, effectively "moving" it.
After that you just render the patch as normal. The degenerates automatically take care of themselves.
Werd!
Now that I got the theory down. Time to implement it. One issue I'm going to have is finding adjacent patches due to the way my world is stored. Basically I have the entire world divided up into chunks, where each chunk is made up of 64 patches (8x8). Each patch is a 16x16 heightmap. (Subject to changed depending on the performance gain from the LOD stuff).
This way I can load new chunks in and drop the old chunks as the player moves across the terrain.
In any event, I'll figure that out in due time. =)
-=[ Megahertz ]=-
Quote:Original post by Megahertz
K, I think i got it.
Basically what you do is you go ahead and generate the lod patch like it was pretty much its own standalone patch. Then you go back and fix up the cracks by more or less sliding the verts that dont belong in the seam over to the next vert thats used in the LOD. However, you dont really move the vert, just replace the index that vert would normally use with the index of the other vert, effectively "moving" it.
After that you just render the patch as normal. The degenerates automatically take care of themselves.
Yes.
Quote:
Now that I got the theory down. Time to implement it. One issue I'm going to have is finding adjacent patches due to the way my world is stored. Basically I have the entire world divided up into chunks, where each chunk is made up of 64 patches (8x8). Each patch is a 16x16 heightmap. (Subject to changed depending on the performance gain from the LOD stuff).
This way I can load new chunks in and drop the old chunks as the player moves across the terrain.
Getting adjacency information is your own problem :P
I was under the impression that degenerate polygons weren't a good idea on modern hardware. I don't have an explanation and it seems like a good idea to reduce the number of indices required, can anyone give an argument to confirm/dispute this claim?
I use indexed triangle lists which seems plenty fast, even on a TNT2/GF2MX. Unless you are developing on similarly low-end hardware the difference probably isn't an issue, since you don't need more than 50,000 polys on screen at once.
I use indexed triangle lists which seems plenty fast, even on a TNT2/GF2MX. Unless you are developing on similarly low-end hardware the difference probably isn't an issue, since you don't need more than 50,000 polys on screen at once.
Degnerate triangles are just ignored by modern hardware which can apprently detect them, that said triangle strips are very often not worth the hastle unless things stripify simply. A triangle list with indices in triangle strip order will give you performance pretty much on par with triangle strips, you are sending across the same amount of data, just a couple more indices and in the grand scheme of things a couple of extra 'short's wizzing across the bus shouldnt kill you [smile].. if you are using 'int's however you deserve all the pain you bring apon yourself unless you've a damned good reason for drawing more than ~65K triangles in one go [razz]
Author
Ok, I have returned. =)
Perhaps im not using degenerate triangles correctly, but following the plan I described above im getting extra lines in the rendering. See the following image:
Clicky
Just to test and see how this would work I just hardcoded the rendering as a bunch of glVertex3f calls and manually put in the coordinates. I've altered the vertex positions to simulate the substitution of the indices during the crack fixing stage.
In using the degenerates to stitch together the rows of tri-strips I dulplicate the last vertex and first vertex of the adjoining strips.
On a normal patch with no crack fixing, the lines are still present but get hidden due to the rendering of the bottom edge of each triangle. However once the verts on the left need to slide down to match the adjacent LOD this leaves a clear area for the line to show up. =(
Where be I goin' wrong?
-=[ Megahertz ]=-
Perhaps im not using degenerate triangles correctly, but following the plan I described above im getting extra lines in the rendering. See the following image:
Clicky
Just to test and see how this would work I just hardcoded the rendering as a bunch of glVertex3f calls and manually put in the coordinates. I've altered the vertex positions to simulate the substitution of the indices during the crack fixing stage.
In using the degenerates to stitch together the rows of tri-strips I dulplicate the last vertex and first vertex of the adjoining strips.
On a normal patch with no crack fixing, the lines are still present but get hidden due to the rendering of the bottom edge of each triangle. However once the verts on the left need to slide down to match the adjacent LOD this leaves a clear area for the line to show up. =(
Where be I goin' wrong?
-=[ Megahertz ]=-
//test case 2 glTexCoord2f(0.0f,0.0f); glVertex3f(0.0f,0.0f,0.0f); glTexCoord2f(0.0f,2.0f); glVertex3f(0.0f,0.0f,2.0f); glTexCoord2f(2.0f,0.0f); glVertex3f(2.0f,0.0f,0.0f); glTexCoord2f(1.0f,1.0f); glVertex3f(1.0f,0.0f,1.0f); glTexCoord2f(2.0f,0.0f); glVertex3f(2.0f,0.0f,0.0f); glTexCoord2f(2.0f,1.0f); glVertex3f(2.0f,0.0f,1.0f); glTexCoord2f(4.0f,0.0f); glVertex3f(4.0f,0.0f,0.0f); glTexCoord2f(3.0f,1.0f); glVertex3f(3.0f,0.0f,1.0f); glTexCoord2f(4.0f,0.0f); glVertex3f(4.0f,0.0f,0.0f); glTexCoord2f(4.0f,1.0f); glVertex3f(4.0f,0.0f,1.0f); //degen glTexCoord2f(4.0f,1.0f); glVertex3f(4.0f,0.0f,1.0f); glTexCoord2f(0.0f,2.0f); glVertex3f(0.0f,0.0f,2.0f); glTexCoord2f(0.0f,2.0f); glVertex3f(0.0f,0.0f,2.0f); glTexCoord2f(0.0f,2.0f); glVertex3f(0.0f,0.0f,2.0f); glTexCoord2f(1.0f,1.0f); glVertex3f(1.0f,0.0f,1.0f); glTexCoord2f(1.0f,2.0f); glVertex3f(1.0f,0.0f,2.0f); glTexCoord2f(2.0f,1.0f); glVertex3f(2.0f,0.0f,1.0f); glTexCoord2f(2.0f,2.0f); glVertex3f(2.0f,0.0f,2.0f); glTexCoord2f(3.0f,1.0f); glVertex3f(3.0f,0.0f,1.0f); glTexCoord2f(3.0f,2.0f); glVertex3f(3.0f,0.0f,2.0f); glTexCoord2f(4.0f,1.0f); glVertex3f(4.0f,0.0f,1.0f); glTexCoord2f(4.0f,2.0f); glVertex3f(4.0f,0.0f,2.0f); //degen glTexCoord2f(4.0f,2.0f); glVertex3f(4.0f,0.0f,2.0f); glTexCoord2f(0.0f,2.0f); glVertex3f(0.0f,0.0f,2.0f); glTexCoord2f(0.0f,2.0f); glVertex3f(0.0f,0.0f,2.0f); glTexCoord2f(0.0f,4.0f); glVertex3f(0.0f,0.0f,4.0f); glTexCoord2f(1.0f,2.0f); glVertex3f(1.0f,0.0f,2.0f); glTexCoord2f(1.0f,3.0f); glVertex3f(1.0f,0.0f,3.0f); glTexCoord2f(2.0f,2.0f); glVertex3f(2.0f,0.0f,2.0f); glTexCoord2f(2.0f,3.0f); glVertex3f(2.0f,0.0f,3.0f); glTexCoord2f(3.0f,2.0f); glVertex3f(3.0f,0.0f,2.0f); glTexCoord2f(3.0f,3.0f); glVertex3f(3.0f,0.0f,3.0f); glTexCoord2f(4.0f,2.0f); glVertex3f(4.0f,0.0f,2.0f); glTexCoord2f(4.0f,3.0f); glVertex3f(4.0f,0.0f,3.0f); //degen glTexCoord2f(4.0f,3.0f); glVertex3f(4.0f,0.0f,3.0f); glTexCoord2f(0.0f,4.0f); glVertex3f(0.0f,0.0f,4.0f); glTexCoord2f(0.0f,4.0f); glVertex3f(0.0f,0.0f,4.0f); glTexCoord2f(0.0f,4.0f); glVertex3f(0.0f,0.0f,4.0f); glTexCoord2f(1.0f,3.0f); glVertex3f(1.0f,0.0f,3.0f); glTexCoord2f(1.0f,4.0f); glVertex3f(1.0f,0.0f,4.0f); glTexCoord2f(2.0f,3.0f); glVertex3f(2.0f,0.0f,3.0f); glTexCoord2f(2.0f,4.0f); glVertex3f(2.0f,0.0f,4.0f); glTexCoord2f(3.0f,3.0f); glVertex3f(3.0f,0.0f,3.0f); glTexCoord2f(3.0f,4.0f); glVertex3f(3.0f,0.0f,4.0f); glTexCoord2f(4.0f,3.0f); glVertex3f(4.0f,0.0f,3.0f); glTexCoord2f(4.0f,4.0f); glVertex3f(4.0f,0.0f,4.0f);
Do the lines only show up in wireframe mode, or also when textured? I've noticed that (at least on the ATI I used) this may affect whether the triangle is rendered or not. It makes sense in that a textured degenerate triangle has zero area so it doesn't need to be rendered, but in wireframe the long edges have a visible length...
Author
So far they'll only visible in wireframe maode, but I've not really used some good textures to see if they show up/cause artifacts in filled mode. To be honest, im not sure what would constitute a "good" texture for checking this.
I think I've found the solution. I've been looking at some code posted over at www.freeworld3d.org and it seems the trick is to actually switch directions of the tri-strip every other row.
Still working out the details tho. I want to understand why it works and how to implement it on my own before using somebody elses code.
-=[ Megahertz ]=-
I think I've found the solution. I've been looking at some code posted over at www.freeworld3d.org and it seems the trick is to actually switch directions of the tri-strip every other row.
Still working out the details tho. I want to understand why it works and how to implement it on my own before using somebody elses code.
-=[ Megahertz ]=-
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
