Sign in to follow this  
roastedamoeba

Geomipmapping - solving cracks

Recommended Posts

Okay, so I've got the basics of geomipmapping up and running - i.e. the LOD is determined based on the error values that are calculated at load time. Now, of course, I have the usual problem that cracks appear between patches of different LOD. I know that I need to change the indices of the patch neighbours with lower detail. I understand how to do this, however, I have a question - what do other people do for this? Do you generate all possible configurations at loadtime? I.e., for all LOD, calculate the index configurations for all possible neighbour LODs. This is what I would like to do, since I don't want to be modifying my index buffer at runtime. Also, because I only use one index buffer for all patches, I don't think the memory requirements will be that high, even for all possible configurations. While I'm on the subject, how do other people write the functions which connect the patch to neighbouring patches? My code is currently bordering on being a massive "hardcoded" function, where I work out the indices myself - that seems easier than trying to compute what the indices should be.

Share this post


Link to post
Share on other sites
Currently working on this problem myself.

You could just pregenerate the LOD's index buffers but personally I'm going to try and generate them on the fly when the LOD changes for a given patch and see how performance is. I'm hoping it wont be too cpu intensive but if it is, then I'll fall back to pregenerating them. It's just something I'm going to have to benchmark and see.

www.freeworld3d.org has some demo code available that tackles this problem and it's worth taking a look at. It's not a tutorial mind you, so you're just gonna hafta dig through the code and figure out what's going on.

The demo code is in the community section of the site (forums) and is under the Announcements forum.

Here's a link to the demo stuff

http://freeworld3d.org/Geomipmapping.zip

HTH
-=[ Megahertz ]=-

Share this post


Link to post
Share on other sites
I dont really see a reason for generating them at runtime. If you limit the neighbour patch to being == the current lod level or current lod-1, then theres only 2^4=16 combinations per LOD level. So if you have like 4 or 5 lod levels, thats only 4 or 5 * 16 combinations, which isnt really alot. So thats something that is really worth precalculating because when you have all combinations, pretty much zero time is needed to switch an lod at runtime.

Share this post


Link to post
Share on other sites
In my implementation I figure everything out when the terrain is generated, and each 'mip' or whatever the chunk of land is called keeps track of which of it's neighbors have a higher level of detail than it, and it'll show just the extra triangles on that edge only. It wasn't an easy task to really get dirty and figure out which triangles bordered which, but once I got rolling with a good set of tests to perform, it was all a matter of getting the logic straight in my head, and then in code.

Share this post


Link to post
Share on other sites
When I was experimenting with terrain, I found that generating index buffers whenever the LOD of a patch (or its neighbors) changes performs just fine. I used the vertex skipping method for the edges so that a patch can connect to any neighbor with a lower level of detail... It's really easy to code too; for each edge vert you detect if it's going "in between" the vertices of the neighboring (lower-LOD) patch and then use the index of the nearest valid vertex. The resulting degenerate triangles aren't rendered by the hardware.

Share this post


Link to post
Share on other sites
Thanks very much for your help guys!

I've gone for the "compute everything beforehand" approach. I have a patch size of 17, so I've got 5 LOD's. This means I have (4 * 16) plus 16 = 80 sets of indices. (The most detailed level only needs one set of indices).

I can't really comment on performance as I haven't implemented it any other way, so I can't compare.

Anyway, in case anybody's interested, here's the screenshots of what it looks like now (these two are taken from the same angle):





Right then, I guess I better implement some culling...

Share this post


Link to post
Share on other sites
IMHO, skirts are a good way of fixing cracks between different LOD levels. They're easy to create and totally static so you only have to do minimal amounts of extra work at run time to fix the cracks. Depending on how else you fix cracks they're probably going to be less memory as well.

Share this post


Link to post
Share on other sites
Quote:
Original post by roastedamoeba
Thanks very much for your help guys!

I've gone for the "compute everything beforehand" approach. I have a patch size of 17, so I've got 5 LOD's. This means I have (4 * 16) plus 16 = 80 sets of indices. (The most detailed level only needs one set of indices).

I can't really comment on performance as I haven't implemented it any other way, so I can't compare.

Anyway, in case anybody's interested, here's the screenshots of what it looks like now (these two are taken from the same angle):





Right then, I guess I better implement some culling...


It seems in your images that you implemented the correct way for choosing the appropriate LOD level. Would you be willing to share your code for doing that ?

Share this post


Link to post
Share on other sites
Quote:
Original post by OrangyTang
IMHO, skirts are a good way of fixing cracks

My god, someone who agrees with me about skirts! Worth mentioning though, that you really have to use a screenspace error metric for skirts to be reliably unnoticeable.

Quote:
Original post by oconnellseanm
Would you be willing to share your code for doing that ?

Promit was kind enough to do so when I was trying to figure it out. See this thread.



Share this post


Link to post
Share on other sites
Quote:
Original post by roastedamoeba
I've gone for the "compute everything beforehand" approach. I have a patch size of 17, so I've got 5 LOD's. This means I have (4 * 16) plus 16 = 80 sets of indices. (The most detailed level only needs one set of indices).


Much, much too small. Your max batch size is 512 tris. Slide up to at least 33x33...my tests found 65x65 to be optimal for my usage. Preserve the same 5 LoDs...even 4, if you want. The rest of the LoDs run well into the diminishing returns area. It's simply not productive to reduce an entire patch to a single quad.

As for the skirts people, would one of you please detail exactly how skirts work? My understanding leads me to believe that they're a pretty miserable hack, and I'd like to be on the same page as everyone else while discussing this.


My own code uses cached index generation. I modify the index buffers to link up correctly (I remove vertices rather than adding, and I impose no limits on neighbor LoD deltas). I've also written things that prevent LoD from changing by more than one step every .5s to prevent popping, so the frequency with which indices change is really quite low. I cache the indices for the visible patches, and update as needed. My caching mechanism at the moment is really quite crude, and indeed it happens to a fairly large chunk of memory anyway. I'm planning to write a more sophisticated LRU slot based cache later, but it's not a pressing something.

I guess my main thing is that I can cope with the patch levels of detail as they are, and I don't need to impose the rather common restriction that most people have; that is, that a neighbor's level of detail can differ by at most one level. I don't like that restriction, as it artificially increases the detail levels of patches.

Share this post


Link to post
Share on other sites
Quote:
Original post by Promit
As for the skirts people, would one of you please detail exactly how skirts work? My understanding leads me to believe that they're a pretty miserable hack, and I'd like to be on the same page as everyone else while discussing this.

I'll have a go. It's now 4am, and this is a bit of a brain dump, I apologise. I might edit it for readability tomorrow.

Essentially skirts are triangle strips that bound each patch. Their top edge follows the existing vertices and their bottom edge uses the same x,z but displaces the y by some amount. Thus, when patches with different LOD are drawn next to one another, the user sees the skirt instead of a crack. This looks really crappy unless the screenspace error is small. I figure you already know this much [smile].

(as an aside, I wanted to use triangle fans for the skirts to keep it 'simple' - one centre vert displaced and one at either corner. As it turned out this doesn't handle all situations well, and is in fact more complex to code than triangle strips. Extra geometry helps balance the pipline too.)

As such, skirts are much better suited for Chunked LOD than for geomipmapping, as the mesh decimation scheme for geomipmapping doesn't take screenspace error into account. I've written my terrain stuff so that it should be fairly simple to drop in a diferent tesselation/decimation scheme, so skirts are more 'portable' in that sense.

That said, with max screen space error set to less than about 20 pixels, it's still unnoticeable for most heightmaps (at least all the ones I've tested. The ones where it would mess up would be ones with high frequency changes in altitude, but GMM falls down there anyway.) It's important to use the same texture coordinates and normals as for the existing vertices to fool the eye into thinking that it's a smooth continuation. In fact I'm faily sure it's using the same normal that completes the illusion.

The major downside to skirts is they eat extra fill rate. I draw mine as the very last thing in the scene, so in most cases it's just a ztest and discard instead of filling the same pixels multiple times. The only skirt fragments to get filled are where the background would otherwise show through.

The amount by which the skirts's y is displaced should be as small as possible to conserve fillrate (well, ztest rate... but you know what I mean). It needs to be longer than any possible simplifcation of the edge. Sounds simple, but I've yet to find a metric I'm happy with. Max geometric error of the verts in the edge seems a good indicator, but thats a measure of the LOD patch's difference from the full detail mesh, not a lower detail mesh, which may actually be more...

The idea behind them being longer than any possible simplification of the mesh, is that the same skirt can then be used no matter what the difference in LOD of the neighbouring patches. The best thing about them is the implicit knowledge that you will only ever see max_screen_error pixels of a skirt.

I implemented my skirts as display lists. This makes them fast, and hopefully take less vid memory than having lots of index buffers, though I can't be sure as I've no idea what kind of storage overhead display lists impose. They certainly save AGP bandwidth over updating the indices regularly.

At the moment I draw a skirt for every patch edge. This is far from optimal, but the framerate hit isn't too bad. Really I should only draw those edges that border a patch with different LOD and face the viewer. I have an idea for a fast way to work out which skirts face the viewer and draw only them, but it relies on a quadtree trick I haven't quite solidified yet. I'll proably leave it until it's a problem, and then decide if it's worth trading the cpu time for the gpu time.

Quote:
Original post by Promit
I guess my main thing is that I can cope with the patch levels of detail as they are, and I don't need to impose the rather common restriction that most people have; that is, that a neighbor's level of detail can differ by at most one level. I don't like that restriction, as it artificially increases the detail levels of patches.


This is the main reason I went for skirts - they avoid the restriction and are simple to implement. In short, they're not perfect, but give the benefit of scaleability and are much simpler to implement than the alternative (IMHO).

So there you go - not perfect, but the right tool for the job in my case. I'm not sure if they're any less perfect than index tricks, and I'd be interested to find out. Chances are though that time I could spend trying it would be better spent making it use a better (preprocess) decimation scheme and sticking to skirts.

here are some shots of my skirts taken while implementing them, which may be useful to illustrate.

Share this post


Link to post
Share on other sites
Quote:

As for the skirts people, would one of you please detail exactly how skirts work? My understanding leads me to believe that they're a pretty miserable hack, and I'd like to be on the same page as everyone else while discussing this.

I agree with mrbastard.

The reason I used skirts was to avoid the development effort implementing a system that could patch the cracks at run-time - with geomipmapping it might not be so hard but with a quad-tree chunked system it got pretty hard so I gave up and used skirts which were easy and worked well (although I wasn't using normal maps at the time - though the small screen-space error should make that unnoticeable I guess - just like it did with regular textures). I determined the world-space vertical skirt displacements at pre-compile time to be big enough to cover a gap all the way to the high-resolution mesh which is quite easy to implement - this is a little sub-optimal since the lower-res LODs will typically not be adjacent to a full-res LOD - so it does result in larger skirts but I don't think it really matters that much since the fast zculling h/w these days should help alot there (as mrbastard says).

Each chunk had 4 edges worth of skirts (surrounding the chunk) dumped in with the chunk geometry so that each chunk+skirts is 1 draw call (which is very important in Direct3D because, as Promit says, you really need at least ~1k verts per draw call for current GPUs to avoid unnecessarily loading the CPU) - for a NxN vertex chunk you have NxN + 4(N-1) vertices (including skirts) which is not a big deal when N is 33. I let back-face culling handle any skirts that are not facing the viewer. No need for strips - just throw the chunk tris and skirts tris in together and optimise as a triangle list per chunk (for the PC anyway).

The run-time is so easy - just draw the chunks and don't worry about any crack geometry or crack metrics - your regular LOD chunk metric by itself (the one that doesn't worry about cracks) ensures that the LOD'ed chunk will not deviate from the full-resolution mesh by more than P pixels and the byproduct of this is that no more than P pixels of your skirts will be exposed.

Extending skirts to arbitrary topology is problematic though so I don't use them anymore.

Share this post


Link to post
Share on other sites
Quote:
Original post by Promit
Much, much too small. Your max batch size is 512 tris. Slide up to at least 33x33...my tests found 65x65 to be optimal for my usage. Preserve the same 5 LoDs...even 4, if you want. The rest of the LoDs run well into the diminishing returns area. It's simply not productive to reduce an entire patch to a single quad.


Admittedly, I haven't played around with this yet - I've just gone with de Boer's recommendation of 17*17. But my code to calculate the indices isn't hardcoded, so I can easily change this to find the optimal size. I'm planning to have quite large terrains, so I imagine that I'll end up with 65*65, or something like that.

Quote:
Original post by Promit
I guess my main thing is that I can cope with the patch levels of detail as they are, and I don't need to impose the rather common restriction that most people have; that is, that a neighbor's level of detail can differ by at most one level. I don't like that restriction, as it artificially increases the detail levels of patches.


I agree, it is annoying having to impose the limitation of only one LOD difference between patches. Although it would be possible to write code to cope with all possible configurations, I'm not sure I'm going to.

However, the memory requirements of having 80 sets of indices can't be very high, because the number of indices in each buffer is relatively small (admittedly, I don't have any figures to back me up). And I like the idea of having it all generated beforehand.

I'm certainly not suggesting that my method is best though [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by oconnellseanm
It seems in your images that you implemented the correct way for choosing the appropriate LOD level. Would you be willing to share your code for doing that ?


Do you still want to see the code? If so, let me know your e-mail address, and I'll send it over.

Share this post


Link to post
Share on other sites
Been working on my implementation a bit and have come to the decision that I think i'm going to precompute the indexlists for the LOD's.

The main reason that prompted this decision is one of saving memory.

The way I'm storing the world is as follows:

The world is made up of at most 64x64 terrain chunks, each chunk is made up of 16x16 patches with each patch being either a 17x17 or 33x33 heightmap. There will be 9 chunks loaded at any one time. 1 in the center where the player is and 8 surrounding the one.

Before I started implementing the LOD stuff I had one index list that I used to draw each patch. I could precompute this index list and store it as a member or the world class, bind it once and use it for each of the draw calls. I'm using VBO's so the index list gets uploaded and bound on the card.

Once I started putting in the code for LOD's I figured I would have each terrain patch have a list of indices used to draw the patch since each patch was going to have a different LOD and the neighbor patches would vary as well. Once I got to the point where I was generating the indexlists and uploading them to the card I realized two things. A) I'm going to be uploading a ton of index lists to the card and B) I'd have to make the index lists dynamically updateable. It just didnt seem very efficient.

I think what I'm going to do now is precompute the indexlists and then just figure out which one I need to use based on the patches LOD and neighboring patch LOD's.

Thoughts?

-=[ Megahertz ]=-

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this