Sign in to follow this  
schupf

Some questions about GeoMipMapping

Recommended Posts

Hello! I have read the original De Boer article about GeoMipMapping (link) and want to implement this technique now. Unfortunately I have some questions about GeoMipMapping: 1) Is it possible that two adjacent patches (for example a 17x17 block) have GeoMipMap levels which differ in more than 1 level? For example a block with GeoMipMapLevel 0 (max detail) besides a block with GeoMipMapLevel2 (2 level coarser) - is this possible? 2) For every GeoMipMap a max error value called sigma ("change of height") is calculated. Is this sigma for GeoMipMap Level N calculated by comparing the height change of level N to level N-1 (the next finer level) or by comparing level N to level 0 (always the max detailed level)? 3) I have read in an article that you can't mix GeoMipMapping with a dynamic lighting model that is based on vertex normals. But wouldn't it be possible if I use N vertex buffers (one for each GeoMipMap Level), where VB 0 stores the vertices of level0 (the full terrain with all vertices), VB 1 the vertices of level 1 (where each second vertex is omitted) and so on. Additionally the vertex normals for all buffers are computed with the corresponding grid. Wouldnt this work to use GeoMipMapping AND normal lighting? 4) Just to be sure that I have understood the algorithm a short recap (please tell me if I am right or wrong): I divide the whole terrain grid in smaller blocks and for EVERY block I calculate N GeoMipMaps (level0 has the original vertices, level1 kicks every second vertex etc.). For example if I divide the terrain in 16 blocks and use 3 MipMapLevels I have 16*3 GeoMipMaps. Now I compute a value D for every GeoMipMap for every block (D tells that I can only use this MipMap if the distance of the camera to this block is > D). At runtime I use this algorithm (pseudo code):
for every visible block in the terrain {
      miplevel = 0
      for(int n=1; n < N ; n++) {
         if(distanceFromCameraToThisBlock > D[n])
	    mipLevel = n
      }
      DrawThisBlockWithMipMapLevel(mipLevel)
   }

Is this correct? 5) Finally my last (and most important) question: The gaps. I have understood the solution to this problem but I am not sure how I could implement it in an efficient way. At runtime first I determine the best MipMapLevel for every visible block. With this information I could create a 2D matrix which stores the block GeoMipMapLevels, for example like this:
| 1 | 1 | 0 | ...
| 1 | 0 | 0 |
  ...

Now I have the connectivy information which is needed to avoid gaps. In this example the top left block (index [0][0]) has a mip map level of 1 and all neighbors also have mipmaplevel 1, so I could render block [0][0] with the default index buffer. But this won't work with block [0][1], because the right and bottom neighbor of [0][1] have lower mipmap levels and therefore block [0][1] needs another index buffer compared to block [0][0] to handle the right and bottom edge. So in order to use static index buffers (I really really want to avoid using dynamic index buffers!) I would need tons of index buffers. Is there an easier way to solve the gaps problem of geomipmapping? Thanks!

Share this post


Link to post
Share on other sites
Quote:
Original post by schupf
1) Is it possible that two adjacent patches (for example a 17x17 block) have GeoMipMap levels which differ in more than 1 level? For example a block with GeoMipMapLevel 0 (max detail) besides a block with GeoMipMapLevel2 (2 level coarser) - is this possible?
Yep, easily. Consider the pathological case of a very rocky patch next to a completely flat patch. I handle this case smoothly with stitching; other people restrict the difference to a single level. (So the flat area would be artificially raised in poly count.)
Quote:
2) For every GeoMipMap a max error value called sigma ("change of height") is calculated. Is this sigma for GeoMipMap Level N calculated by comparing the height change of level N to level N-1 (the next finer level) or by comparing level N to level 0 (always the max detailed level)?
I believe I computed it against the next level, but doing it against the top level works too. The goal is to identify the distance at which you're going to require each level.
Quote:
3) ...
Haven't really bothered to think about lighting any time recently, maybe someone else will jump in.
Quote:
4) Just to be sure that I have understood the algorithm a short recap (please tell me if I am right or wrong): I divide the whole terrain grid in smaller blocks and for EVERY block I calculate N GeoMipMaps (level0 has the original vertices, level1 kicks every second vertex etc.). For example if I divide the terrain in 16 blocks and use 3 MipMapLevels I have 16*3 GeoMipMaps.
Now I compute a value D for every GeoMipMap for every block (D tells that I can only use this MipMap if the distance of the camera to this block is > D).
At runtime I use this algorithm (pseudo code):
*** Source Snippet Removed ***Is this correct?
Pretty much -- there is one caveat. I found in my initial implementation that I was getting some spazzy behavior, so I recommend wrapping a cylinder around the patch and computing the distance to that, NOT the center. In other words, use the minimum possible distance, and clamp the distance to 0 when you're inside it. Luckily, all this requires is subtracting sqrt(2) * patchSize from your distance and clamping it. Trust me, this will stop all sorts of "shifting sand" behaviors.
Quote:
5) Finally my last (and most important) question: The gaps.
I have understood the solution to this problem but I am not sure how I could implement it in an efficient way.
At runtime first I determine the best MipMapLevel for every visible block. With this information I could create a 2D matrix which stores the block GeoMipMapLevels, for example like this:
*** Source Snippet Removed ***
Now I have the connectivy information which is needed to avoid gaps. In this example the top left block (index [0][0]) has a mip map level of 1 and all neighbors also have mipmaplevel 1, so I could render block [0][0] with the default index buffer. But this won't work with block [0][1], because the right and bottom neighbor of [0][1] have lower mipmap levels and therefore block [0][1] needs another index buffer compared to block [0][0] to handle the right and bottom edge. So in order to use static index buffers (I really really want to avoid using dynamic index buffers!) I would need tons of index buffers. Is there an easier way to solve the gaps problem of geomipmapping?
Index buffers almost never live in video memory, so making them dynamic is not a big deal. I patch my index buffers dynamically to fix cracks*. Other people simply render extra geometry (skirts) to cover up; I don't like that approach but it seems to work well enough in practice.

* Specifically, what I do is to use a small set of large dynamic index buffers, and copy system memory only index buffer templates into those buffers, keeping track of the offsets where they're ending up for each patch. The crack patching is part of this copy step; it changes bad index values to ones that won't create cracks. Then I make draw calls that use parts of the dynamic index buffer as appropriate. The index buffers are restricted by byte size to something reasonable like 1 MB, I forget the details. You can kind of think of the index buffers like a deque, which allocates as many fixed size chunks as is necessary to store everything.

[Edited by - Promit on October 14, 2008 9:09:59 AM]

Share this post


Link to post
Share on other sites
Thanks for your answer Promit.

But I still don't know how I can effeciently solve the problem with the cracks. Currently I think I have to do the following:

+ Find all visible patches (per quadtree)
+ Iterate through all visible patches and check all 4 Neighbors (left, top, right, bottom) for mip map level differences.

But the problem is the huge amount of possibilites in step2! Lets say I currently process a patch with mipmaplevel2. Then there could be a patch left to the current patch with mipmaplevel 1 (the rest have the same level); it could be possible that the left and top neighbor have mipmaplevel 1; it could be possible that the top neighbor has mipmaplevel 0 and the bottom has mipmaplevel 1 and so on. There are just so many possible configurations!
How can I solve this? With dozens of Indexbuffers? Or should I create basic index templates (for each LOD) and then modify them at runtime and fill a dynamic indexbuffer with it? Or something else? :/

Thanks for any help!

Share this post


Link to post
Share on other sites
The many possibilities between the levels of adjacent patches, is the primary reason that many approaches limit the difference between levels to at most 1 (in the literature it is often called a Restricted Quadtree). As pointed out this means that the LOD algorithm will produce more vertices for some patches than is strictly necessary - as determined by the LOD criteria. If you go with the Skirts technique (Chunked LOD by Thatcher), then what you save on vertices (you can get away with arbitrary level difference), you might have to spend on fillrate rendering the skirts (assuming unified shader model). Implementing skirts to cover the cracks from arbitrary level difference is trivial but I wouldn't recommend using them if you plan to do non-trivial texturing of the terrain surface. If you want to minimize GPU load, you should probably go with the idea suggested by Promit. If you want to minimize CPU load and want to avoid a more complicated implementation, you should probably go with the idea of restricting level difference and let the GPU chew through the redundant workload.

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