Jump to content

  • Log In with Google      Sign In   
  • Create Account

Terrain Stitching


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
17 replies to this topic

#1 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 11 September 2011 - 09:06 PM

Hey all,

I think terrain stitching is generic to most LoD designs, although I am using GeoMipMaps. I think I understand what to do but I'm hoping someone can double check my design just incase!

So it seems that if you have a block with say level 0 mipmap LoD on the left and a block with level 1 mipmap LoD on the right, then the block that has a lower resoltuon on the right has to make its edge vertices be identical to the higher resolution LoD on the left. This would involve creating a unique index buffer that handles the left edge of the block (it would essentially be as if the edge has level 0 LoD while the rest of the block has level 1 LoD).

This situation would have to be handled for all 4 edges and for all combinations of LoD's, so if a block is level 2 LoD and has a level 0 on its right and a level 1 on its left, it would need a unique index buffer just for that situation. This would lead to a stupid amount of index buffers, which makes me think I have something wrong here.

Sponsor:

#2 Trienco   Crossbones+   -  Reputation: 2171

Like
1Likes
Like

Posted 11 September 2011 - 10:26 PM

You either have an insane amount of buffers for each combination, split your rendering into multiple calls to render the center and the linking pieces seperately or do what most will suggest and just use skirts to somewhat hide the transitions.

I was going with linker pieces, alternating the subdivision of quads to get a nicer diamond like look and got two things out of it:
-everytime I look at my code to generate the linking pieces I get a headache
-chunks are already very inefficient, because each render call is drawing a stupidly small amount of geometry.. making that up to 5 draw calls doesn't make me any happier

However, even if having a complete index buffer for each combination, at 32x32 chunks you have 7776 combinations, a rough estimate would be that you get away with 16-20mb for index buffers (I might be completely off).
f@dzhttp://festini.device-zero.de

#3 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 12 September 2011 - 12:50 AM

Thanks for the reply Trienco. The deeper I get into terrain LoD the more I am left with a bitter taste in my mouth.

In de Boer's paper he talks about using triangle fans to render the seams together. I'm assuming he is suggesting to add 4 extra draw calls to each block (worst case scenario).
I'm starting to see why John Carmack said that terrain LoD is, for the most part, worthless.

Are there no terrain LoD solutions that don't involve consuming large amount of excess memory and injecting huge amounts of draw calls?

I haven't looked into skirts yet but if they can make things look good, cheaply, then I may go with that.

#4 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 12 September 2011 - 02:03 AM

Thinking about this more I've come up with the following conclusions:

-If you want to have any type of view frustum culling you will have to break the terrain into blocks, which gives you repeated data along shared edges and requires a seperate draw call for each block. This is independent of any LoD scheme, so it's not necessarily a result of GeoMipMaps. Also, I believe there are clever ways to group many draw calls into one draw call, although I haven't looked into those techniques yet.

-In order to solve geometry gaps, having an index buffer for every type of mipmap/edge combination is a bit insane, but if you put a restriction that neighboring blocks can only differ by 1 mipmap level (which is the typical case anyways, due to the spatial locality of the player and the blocks) then it will greatly reduce the number of index buffers. You would have one for the default block and 4 for each edge case, so essentially 5*MaxMipMapLevels. It increases your index buffer memory usage by 500%, but the alternative of draw calls just to handle stitching a few vertices would absolutely kill CPU performance.

-Additionally, if you're design allows you to reuse the same index buffer for each block that you render, then the memory usage of your index buffer is dependent on the size of your blocks. This means that no matter how large the terrain gets, the size of your index buffer can remain the same (say for a 33X33 block you have 32X32 cells, 6 indices per cell, 2 bytes per index, for a total of a whopping 12KB and the smaller resolution mipmaps have a fraction of that). A 500% increase on 12KB is not an amount of memory worth worrying about. Even a block size of 129X129 we get 192KB + lower resolution indices. Were still only talking somewhere between 1-2MB of memory.

I think this is a decent solution to the problem. Any comments or criticisms are welcomed.

Thanks,
Dark

#5 Infernal-rk   Members   -  Reputation: 135

Like
1Likes
Like

Posted 12 September 2011 - 10:19 AM

There is a simpler work around that may work for you.. may not as well.

At the boundary between higher and lower res chunks, there is not real GAP from top down view, just gaps formed by T junctions of the different mesh densities. The gaps can only then be seen from sideways view.

One of the simplest solutions I've seen is to take the low res chunk's edge vertices and extrude them down below the high res chunk, towards the player. This forms an extra strip that will block any gaps where the high res mesh would be lower than the low res mesh from a side on view. In the case where the high res mesh is vetically higher than the low res mesh, there will be no gap to void to view through from the vantage point of the camera.

Posted Image

Granted in this old project (2003) I did over extrude them a bit too low.

#6 dave j   Members   -  Reputation: 592

Like
1Likes
Like

Posted 12 September 2011 - 10:55 AM

You might find this Seamless Patches for GPU-Based Terrain Rendering paper interesting. It still uses square terrain chunks but renders them using four triangular patches with the LOD changes implemented by choosing different index buffers for the triangles.

#7 Trienco   Crossbones+   -  Reputation: 2171

Like
1Likes
Like

Posted 12 September 2011 - 12:33 PM

but if you put a restriction that neighboring blocks can only differ by 1 mipmap level (which is the typical case anyways, due to the spatial locality of the player and the blocks) then it will greatly reduce the number of index buffers.


A single spike in a chunk will require a high lod. By limiting the difference to 1, you end up dragging a potentially completey flat surrounding to a high lod. Of course that's more of a special case.

You might find this Seamless Patches for GPU-Based Terrain Rendering paper interesting. It still uses square terrain chunks but renders them using four triangular patches with the LOD changes implemented by choosing different index buffers for the triangles.


Since I found the numbers in that paper a little underwhelming I dug out my old terrain renderer using the entire map of Oblivion at 4096x4096, cranked up the detail to get a nice number of triangles (about 500k) and my fps are still well above 1000 with my average frame time being below 3000 "kilo ticks". Even just running fraps to double check reduced it to 950.

For fans of statistics and memory usage:
-vertex buffer: 66mb
-index buffers: 64kb
-heightmap: 32mb
-chunk data: 160kb (not including the geometry obviously)
-quadtree: 64kb (only for culling)

Thats slightly less than 100MB, with the majority stored in video memory

Screenshot with slightly more polygons (1.2million) and showing the connections between lods

Posted Image

Obviously the number of draw calls isn't such a big deal. I also wouldn't worry too much about every detail without first deciding what you want to use it for, how large your terrain will be and what you focus on (personally I tried to save on memory).
f@dzhttp://festini.device-zero.de

#8 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 12 September 2011 - 09:28 PM

Interesting posts guys. Thanks for the support! It is tricky making an engine just to make an engine, I don't know if memory or CPU usage will be my biggest constraint. Given that it's in javascript I'm leaning towards CPU, so I will probably implement the method I suggested (once I'm done with this lame OS homework). Hopefully constricting my mipmaps to be within 1 LoD of each other won't hurt things too much. I'll post some screenshots in a few weeks when it's all done. =)

#9 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 13 September 2011 - 01:48 AM

As I'm starting to implement the design I thought I would mention that my math above was wrong. There are 16 separate index buffers for all combinations (1 for no LoD + 4 choose 1 + 4 choose 2 + 4 choose 3 + 4 choose 4).

Here are some rough estimates on index buffer memory (I calculate by (width-1)*(height-1)*6*2*16, width-1 *height-1 gives the number of cells, 6 indices (2 triangles) per cell, 2 bytes for each index and 16 index buffers).

129X129 = ~3mb
65X65 = ~0.8mb
33X33 = ~0.2mb
17X17 = ~0.05mb

For each lower mipmap you will accumulate down the list obviously.

Given that 129X129 is the highest possible block size and 65X65 is a more likely average choice, a little over 1MB isn't too bad for a 65X65 + all mipmaps. In de Boer's paper he said that connecting a lower mipmap's edge to a higher mipmap can result in a "missing pixels effect" due to floating point inaccuracy. I haven't noticed this in my design, but I haven't implemented the whole thing yet.

I simply construct the index buffer as normal and then add a few triangles to it that handle the edge seamed to a higher mipmap. There may be a smarter way that saves a few triangles, if anyone knows please let me know =)

#10 smasherprog   Members   -  Reputation: 432

Like
0Likes
Like

Posted 13 September 2011 - 01:04 PM

There is a simpler work around that may work for you.. may not as well.

At the boundary between higher and lower res chunks, there is not real GAP from top down view, just gaps formed by T junctions of the different mesh densities. The gaps can only then be seen from sideways view.

One of the simplest solutions I've seen is to take the low res chunk's edge vertices and extrude them down below the high res chunk, towards the player. This forms an extra strip that will block any gaps where the high res mesh would be lower than the low res mesh from a side on view. In the case where the high res mesh is vetically higher than the low res mesh, there will be no gap to void to view through from the vantage point of the camera.


Granted in this old project (2003) I did over extrude them a bit too low.


I thought about doing that, but did something different. I chose to instead overlap the terrain patches by one unit on each side. This effectivley removes any seams and leads to much simpler code. The only difference is that if you are using say 64 x 64 sized patches, make it 65 x 65 instead. Pretty damned simple to me . . . check it out
Wisdom is knowing when to shut up, so try it.
--Game Development http://nolimitsdesigns.com: Reliable UDP library, Threading library, Math Library, UI Library. Take a look, its all free.

#11 Tasche   Members   -  Reputation: 222

Like
1Likes
Like

Posted 13 September 2011 - 03:34 PM

using the 16 index buffer approach works pretty well, however i have still to figure out on how to do vertex morphing to hide the quite visible pops in my engine. if you go with this approach, and get vertex morphing done, write a tutorial fo me^^

cheers,
tasche

#12 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 14 September 2011 - 03:00 AM

using the 16 index buffer approach works pretty well, however i have still to figure out on how to do vertex morphing to hide the quite visible pops in my engine. if you go with this approach, and get vertex morphing done, write a tutorial fo me^^


That will probably be the next thing on my "to do" list. I may try trilinear GeoMipMapping as de Boer suggests, but I haven't dug into the details too much yet. I'm assuming if you have a good interpolation system between mipmap changes you can crank up your threshhold to a higher value?

#13 Trienco   Crossbones+   -  Reputation: 2171

Like
0Likes
Like

Posted 14 September 2011 - 12:15 PM

I'm assuming if you have a good interpolation system between mipmap changes you can crank up your threshhold to a higher value?


Not too much. Personally I find hills or spikes that suddenly grow out of nowhere over a few frames to be almost as irritating as having them just pop up. Considering the extra effort it takes I'd rather stick with a higher lod.
f@dzhttp://festini.device-zero.de

#14 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 14 September 2011 - 12:29 PM

I agree. The heightmap I'm using has a lot of small bumpy hills as well as larger hills. When using a terrain with a decent amount of detail, the lower LoD's look pretty crappy, even from a distance. I'd say that the terrain has to be designed to be smooth for it to look good, otherwise the threshold has to be such that even somewhat distant blocks are only 1 LoD below normal.

#15 Infernal-rk   Members   -  Reputation: 135

Like
0Likes
Like

Posted 14 September 2011 - 12:42 PM

ultra smooth terrains are boring!

granted stuff coded here looks mugh nicer, but go look at minecraft worlds. where the mountains are all jutting up and doing weird things. people travel all over the game to find these areas because they are interesting.

the smooth rolling hills areas, they ignore because literally, there's nothing to see.


perhaps some pre-processing of the terrian mesh to determine areas of high rate of height change/sharp corners and allow those small portions of the mesh to always render in higher LOD than the smoother areas of the same distance from viewer.

#16 Trienco   Crossbones+   -  Reputation: 2171

Like
0Likes
Like

Posted 14 September 2011 - 10:36 PM

granted stuff coded here looks mugh nicer, but go look at minecraft worlds. where the mountains are all jutting up and doing weird things. people travel all over the game to find these areas because they are interesting.


Creating terrain like in MC would require a completely different approach. A heightmap as such simply doesn't allow overhangs, arches, caves or anything "interesting".

perhaps some pre-processing of the terrian mesh to determine areas of high rate of height change/sharp corners and allow those small portions of the mesh to always render in higher LOD than the smoother areas of the same distance from viewer.


? That's the whole point of calculating the (screen) error for each lod of each chunk. You calculate the max height difference for all points in the chunk compared to the highest lod, scale it (for example by camera distance) and select an lod where the scaled error is below x.
f@dzhttp://festini.device-zero.de

#17 Infernal-rk   Members   -  Reputation: 135

Like
0Likes
Like

Posted 15 September 2011 - 01:53 PM

in conversation a good point was made about all these LOD systems.

What happens when a person uses binoculars or a view zoom in the game? We implement that as an FOV change.. which is more or less accurate, but I've now noticed that many engines fail to make the LOD of the area being zoomed into any higher, resulting in some really crappy looking stuff when you zoom in.

Do your terrain-camera systems accommodate this? I know I haven't implemented anything to deal with this yet.

#18 Trienco   Crossbones+   -  Reputation: 2171

Like
0Likes
Like

Posted 15 September 2011 - 10:33 PM

Do your terrain-camera systems accommodate this? I know I haven't implemented anything to deal with this yet.


That's a good point, but easily fixed by considering the projection. My camera class is dealing with the frustum width/height for a lot of things like culling anyway, so assuming a simple case where your camera is always upright, you can just scale with the frustum height (else you'd have to take the cameras up vector, multiply with frustum width/height and use the length of the resulting vector for scaling).
f@dzhttp://festini.device-zero.de




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS