• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Triad_prague

A good heightmap LOD technique (no VTF please)

28 posts in this topic

Hi, I'm kinda confused now. I'm trying to make an island with a heightmap of size 1025*1025. It can't be possible without LOD in my PC (p4 2.26 GHZ, GF7300GT, 1GB ram). I've been hearing the geoclipmapping methot mentioned, but when I read the paper it said that it used VTF (vertex texture fetching). That's just inaffordable for me (I downloaded a simple demo consisting of a 128*128 grid with VTF and it just as slow as hell). So I don't think I will use that. Can you suggest any other good methods that use no VTF but still can achieve a huge framerate? (kinda sick when my PC is just too old :( )

basically I need a LOD scheme with these constraints:
- no VTF
- support at least 1025*1025 (2049*2049 is highly appreciated)
- support terrain editing (my game would be a business simulation game)
- quite simple

currently I'm looking at an article presented by the maker of SoulRide[sup]tm[/sup], but I need as much reading as I could get, and I run out of keywords here, hehe
0

Share this post


Link to post
Share on other sites
Yes I'd like to know too, I've been looking for a while and still don't have a good solution. Its one major feature missing in my engine grrr.
0

Share this post


Link to post
Share on other sites
[quote name='Triad_prague' timestamp='1328849419' post='4911546']
basically I need a LOD scheme with these constraints:
- no VTF
- support at least 1025*1025 (2049*2049 is highly appreciated)
- support terrain editing (my game would be a business simulation game)
- quite simple
[/quote]
1st step: consider brute force it (albeit the hardware limit for your video card could be around 1 Mega points, I don't remember).
I'm not familiar with 7300 but GeForce4 could render 256k vertices with ease in a single batch. 6600 could do 2-4 vertices per pixel and still run interactive!
Anyway, look into geo-mipmapping. It is simple. It has basically no limit on point count. It runs on everything (CPU-based, preprocessing).
It does not natively support terrain modification but it's fairly close. Hopefully it will allow an incremental operation on data structures.

As a side note VTF is very viable on midrange GeForce since generation 6xxx (albeit initial drivers were a bit slow).
When it comes to 7300 I'm afraid it either does not support the feature or it is extremely bandwidth-constrained (if memory serves VTF required 32bit float channels).
0

Share this post


Link to post
Share on other sites
You may use same vertex buffer but with different index buffer for LoD > 0.

For example, If your terrain is split into 16x16 sectors.

LOD0 IB = 16x16 cells
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
17,18,19,20,21,22,23,24,25,26,27,28,29,30,31
32,33,34,...

LOD1 IB = 8x8 cells
0,2,4,6,8,10,12,14,16
17,19,21,23,...

LOD2 IB = 4x4 cells..
0

Share this post


Link to post
Share on other sites
[quote name='Promit' timestamp='1328855078' post='4911575']
Geomipmapping should work fairly well... 1025 is not a large terrain.
[/quote]

I've got a [s]geomipmapping[/s] geoclipmapping (doh) implementation that can render 128km square terrain with 1m the highest resolution on weaker cards at 10ms/frame (100fps). And thats with a terribly inefficient, unoptimized implementation. As long as the card supports SM3.0 you geomipmapping should work great.
0

Share this post


Link to post
Share on other sites
The [url="http://research.microsoft.com/en-us/um/people/hoppe/proj/geomclipmap/"]original geometry clipmaps paper[/url] didn't use VTF.
It's more work on the CPU though - so it still might not be usable.
2

Share this post


Link to post
Share on other sites
[quote name='dave j' timestamp='1328905598' post='4911778']
The [url="http://research.microsoft.com/en-us/um/people/hoppe/proj/geomclipmap/"]original geometry clipmaps paper[/url] didn't use VTF.
It's more work on the CPU though - so it still might not be usable.
[/quote]
There's a footnote on that page with [url="http://research.microsoft.com/en-us/um/people/hoppe/proj/gpugcm/"]a link to here[/url] and an explanation that they were able to move pretty much all the work to the GPU.
0

Share this post


Link to post
Share on other sites
Great paper, has anyone thought of using disc shapes instead of grids and just scale with view height?
0

Share this post


Link to post
Share on other sites
[quote name='Lee Stripp' timestamp='1328927490' post='4911858']
Great paper, has anyone thought of using disc shapes instead of grids and just scale with view height?
[/quote]
Hi Lee [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] , the point of using a grid is its simplicity... How would you implement something similar to the L-Shaped strip that is used to reduce flickering of vertices?

There is also [url="http://www.vertexasylum.com/downloads/cdlod/cdlod_latest.pdf"]CDLOD[/url].
0

Share this post


Link to post
Share on other sites
[quote name='Cornstalks' timestamp='1328907181' post='4911784']
[quote name='dave j' timestamp='1328905598' post='4911778']
The [url="http://research.microsoft.com/en-us/um/people/hoppe/proj/geomclipmap/"]original geometry clipmaps paper[/url] didn't use VTF.
It's more work on the CPU though - so it still might not be usable.
[/quote]
There's a footnote on that page with [url="http://research.microsoft.com/en-us/um/people/hoppe/proj/gpugcm/"]a link to here[/url] and an explanation that they were able to move pretty much all the work to the GPU.
[/quote]


I know - but that requires VFT which the OP doesn't want to use. Hence the link to the original paper.
0

Share this post


Link to post
Share on other sites
[quote name='dave j' timestamp='1328956713' post='4911931']
[quote name='Cornstalks' timestamp='1328907181' post='4911784']
[quote name='dave j' timestamp='1328905598' post='4911778']
The [url="http://research.microsoft.com/en-us/um/people/hoppe/proj/geomclipmap/"]original geometry clipmaps paper[/url] didn't use VTF.
It's more work on the CPU though - so it still might not be usable.
[/quote]
There's a footnote on that page with [url="http://research.microsoft.com/en-us/um/people/hoppe/proj/gpugcm/"]a link to here[/url] and an explanation that they were able to move pretty much all the work to the GPU.
[/quote]


I know - but that requires VFT which the OP doesn't want to use. Hence the link to the original paper.
[/quote]
You're totally right. This is when doing a quick text search for "VFT" in a paper, and assuming that since it doesn't contain "VFT," it must not use VFT, is a stupid assumption. Thanks.
0

Share this post


Link to post
Share on other sites
[quote name='TiagoCosta' timestamp='1328955712' post='4911928']There is also [url="http://www.vertexasylum.com/downloads/cdlod/cdlod_latest.pdf"]CDLOD[/url].
[/quote]I'm not quite sold on that. By the way, the author presents it as "Continuous Distance-Dependent Level of Detail for Rendering Heightmaps" but at its core it's just an interpolated discrete lod. Both geomipmapping and geoclipmapping feature some kind of interpolation: that does not make it a continuous metod.
Perhaps I am misunderstanding it big way but...
Let me quote:
[quote][size=1]{1} Using CDLOD, each vertex is morphed individually based on its own LOD metric unlike the method in [Ulrich 02], where the morph is performed per-node (per-chunk).
...
{2} First, the approximate distance between the observer and the vertex is calculated to determine the amount of morph required
...
{3} Finally, the z-component is obtained by sampling the heightmap with texture coordinates calculated from x and y components using a bilinear filter (filtering is only needed for vertices in the morph region). When all vertices of a node are morphed to this low-detail state, the mesh then effectively contains four times fewer triangles and exactly matches the one from the lower LOD layer; hence it can be seamlessly replaced by it.
...
{4} Settings used to generate the quadtree and run the algorithm need to be [b]carefully [/b]chosen to match terrain dataset characteristics while providing the best performance. In the accompanying examples, each dataset defines its own settings.
...
{5} Since the LOD works in three dimensions, this problem will be enhanced when using extremely rough terrain with large height differences: thus, different settings might be required for each dataset.
In the provided data examples, LOD settings are tuned so that the ranges are always acceptable...
...
{6} Two example projects are provided: BasicCDLOD and StreamingCDLOD. Both projects are written in C++, using DirectX9 and HLSL, and should work on most GPUs that support vertex shader texture sampling, i.e., ones supporting Shader Model 3.0
...
{7} The performance bottleneck on the GPU is either the vertex texture fetch cost (used for displacement of terrain vertices), or the triangle rasterization and pixel shader cost. This mostly depends on the settings, GPU hardware, and display resolution.[/size]
[/quote][list=1]
[*]He's actually suggesting geoclipmaps to be bad? Or limited? This is a bit odd to me. Nyquist theorem anyone?
[*]I seriously hope this is not going to happen on CPU! The only possible way to do so is VTF.
[*]Please note how he's basically admitting the algorithm to be interpolated across discrete states. Having worked on a method that was based on displacing vertices similarly, I am surprised it does not produce consistent wobble.
[*]I don't know what he means by [i]carefully[/i]. I am against everything that requires [i]careful [/i]tuning. Note: neither geomipmapping nor geoclipmaps require to be [i]carefully [/i]tuned in my opinion (albeit clipmapping requires [i]some [/i]tuning and streaming needs tuning as well).
[*]Note similar issues happen when using geomipmapping (probably because it's doing something very similar?)
[*]Geomipmapping runs on everything. If SM3 is required, I suppose I might just bite the bullet and use clipmapping.
[*]Sure, it would have been nice to post the shaders. A simple fill will give no troubles to anyone.
[/list]
Anyway, I downloaded the 210MiBs required to look at the system. It required me to build the data set on my system. The non-interactive program uses a single core and took like 2 minutes to run. It then took a few minutes (I'd say close to 15m) at runtime to start. Again, single-core. The program blowed about 210 MiBs of RAM to produce around 1 Gig of data. When running, it takes about 180 MiBs.
The method has been "tuned" so most triangles are about... I'd say 4 pixels wide.
Basically what it shows is the algorithm converges to a correct result... at an extreme cost.
I'd take it with [i]some [/i]salt.

I look forward to tune this iteratively! Edited by Krohm
-1

Share this post


Link to post
Share on other sites
[quote name='Krohm' timestamp='1328972119' post='4911965']at its core it's just an interpolated discrete lod. Both geomipmapping and geoclipmapping feature some kind of interpolation: that does not make it a continuous metod.[/quote]

There's a big difference though, the interpolation method is seamless and continuous (thus the name): one segment is morphed completely into another before it's 'swapped', with no seams between LOD levels. Geoclipmaps, geomipmaps (and ChunkedLOD) have T seams between LOD levels and require 'stitching strips' on one hand, and on the other the morphing method only works (reasonably) well for heights but you're still swapping between two different meshes so there's inevitable popping if you're vertex fetching and trying to interpolate other data types (such as normals).
(Another difference is that CDLOD interpolates completely predictably based on the 3D distance between the vertex and the camera, unlike geoclipmaps/chunkedlod.)


[quote]I seriously hope this is not going to happen on CPU! The only possible way to do so is VTF.[/quote]

No, of course, vertex texture fetching is used, read the paper.


[quote]Please note how he's basically admitting the algorithm to be interpolated across discrete states. Having worked on a method that was based on displacing vertices similarly, I am surprised it does not produce consistent wobble.[/quote]

It doesn't wobble because it's not morphing it in a simplistic way: all morph levels are pre-generated to avoid that. (Seriously, try reading the paper? [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] )

I don't understand what would satisfy your definition of a continuous algorithm - ROAM maybe? Whatever you do it still has to be discretized into render calls unless you can store all the heightmap, normalmap and other data into one big buffer and render from it using tessellation or something similar?


[quote]Anyway, I downloaded the 210MiBs required to look at the system. It required me to build the data set on my system. The non-interactive program uses a single core and took like 2 minutes to run. It then took a few minutes (I'd say close to 15m) at runtime to start. Again, single-core. The program blowed about 210 MiBs of RAM to produce around 1 Gig of data. When running, it takes about 180 MiBs.

The method has been "tuned" so most triangles are about... I'd say 4 pixels wide.[/quote]

Well if the triangles are 4 pixels wide on your device then why not try dropping the quality level? You're hardware is probably not the 'target audience' (for example, on my monitor they look around 10ish pixels wide, probably the same dataset): there's a button on the HUD saying "Render grid size:" - drop that one notch and reduce the viewing distance. If you want to save on memory, drop the HeightmapLODOffset and NormalmapLODOffset by one, should reduce the memory use to approx 30-40% of the current. Also, the demo you mention uses a texture splatting technique which must take at least 10MiB RAM without any terrain data loaded - remove that and you've saved some more.
-1

Share this post


Link to post
Share on other sites
[quote name='TiagoCosta' timestamp='1328955712' post='4911928']
[quote name='Lee Stripp' timestamp='1328927490' post='4911858']
Great paper, has anyone thought of using disc shapes instead of grids and just scale with view height?
[/quote]
Hi Lee [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] , the point of using a grid is its simplicity... How would you implement something similar to the L-Shaped strip that is used to reduce flickering of vertices?

There is also [url="http://www.vertexasylum.com/downloads/cdlod/cdlod_latest.pdf"]CDLOD[/url].
[/quote]

I was thinking simple.. build the disc shape in advance, the natral expanding of the shape itself creates LOD (But do this with some care) anyway and then split into sections for frustum cull.. I was just making an observation, I haven't done any tests on that at all.
0

Share this post


Link to post
Share on other sites
CDLOD paper was interesting BUT
he makes no mention of what data is transferred, how and when to the GPU
I can't believe he is transferring a screen full every frame?
my current sketch for VTF-less terrain works by loading all the potentially visible vertices into the gpu
using a vertex buffer managed as a heap of blocks, with deallocated blocks waiting 3 frames before being made available for reallocation (to save buffer space on gpu)
the index buffer is tiny and just contains a generic pattern for each LOD level (draw with a vertexoffset to address the correct block of vertices)
this means I only send terrain data to the GPU when it becomes potentially visible
(using a simple modulo grid - which is also used for frustum culling - just project the frustum into "grid space" and you have a list of visible blocks - essentially spatial index query by rasterization!)
(and changing the LOD level of a block just comes down to changing the indexbuffer start offset)
the downside is a large number of draw calls - which I don't think is a real problem as there are no resource changes between them
given the choice of 50 draw calls versus sending 100,000 vertices ... (too lazy to actually profile that right now)
0

Share this post


Link to post
Share on other sites
Here is an idea that is simple to code and highly performant:

1) create a static vertex buffer with the same layout as the height texture (scan lines of texels become contiguous vertices)
2) create a static index buffer containing a disk split into 8 segments (so each disk can be rendered by setting index buffer offset and count) this disk has a concentric LOD pattern
3) now you can move the disk around the height map by calculating vertex offset = pos.x + pos.z * stride and using 1 draw call for each section of the disk that is visible

for a square terrain of 1024 texels and a vertex size of 16 bytes you will need 16MiB, for 2048 64MiB

you can use ushort4 for position and ushort4 for normal - leaving 3 ushorts spare for other things ... texture coords are derived from position

this is very similar to my vtf terrain - but I am swapping vtf for using more video memory
0

Share this post


Link to post
Share on other sites
[quote name='skytiger' timestamp='1329481120' post='4913879']
Here is an idea that is simple to code and highly performant:

1) create a static vertex buffer with the same layout as the height texture (scan lines of texels become contiguous vertices)
2) create a static index buffer containing a disk split into 8 segments (so each disk can be rendered by setting index buffer offset and count) this disk has a concentric LOD pattern
3) now you can move the disk around the height map by calculating vertex offset = pos.x + pos.z * stride and using 1 draw call for each section of the disk that is visible

for a square terrain of 1024 texels and a vertex size of 16 bytes you will need 16MiB, for 2048 64MiB

you can use ushort4 for position and ushort4 for normal - leaving 3 ushorts spare for other things ... texture coords are derived from position

this is very similar to my vtf terrain - but I am swapping vtf for using more video memory
[/quote]

That is exactly what [s]geomipmapping[/s] geoclipmapping is. You don't mention how you update the vertex heights; in the original algorithm heights were calculated on the cpu, that was later moved to the gpu by using vtf.
0

Share this post


Link to post
Share on other sites
[quote name='turch' timestamp='1329487958' post='4913911']
That is exactly what geomipmapping is. You don't mention how you update the vertex heights; in the original algorithm heights were calculated on the cpu, that was later moved to the gpu by using vtf.
[/quote]

You need to re-read my post. It isn't geomipmapping.

The reason I didn't mention HOW I update the vertex heights is because I DON'T update them, ever. This is 100% static technique.

(edit) a pseudocode sample will help illuminate things:
[CODE]
DrawIndexedPrimitives(
BaseVertexIndex = (use this to position the mesh in world space using = Origin.X + Origin.Z * Stride)
, StartIndex = (use this to pick a segment of the disk // the index buffer includes 360 + 180 degrees of disk)
, PrimitiveCount = (use this to pick how many segments to render)
)
[/CODE]

The index buffer is a "pattern" that is positioned over the the uniform grid of vertices - I have moved the height data from a texture into a vertex buffer and instead of sampling it I use offsets to map indices to the correct vertices.

There is a good explanation here:
[url="http://msdn.microsoft.com/en-us/library/windows/desktop/bb147325%28v=vs.85%29.aspx"]http://msdn.microsoft.com/en-us/library/windows/desktop/bb147325%28v=vs.85%29.aspx[/url]
0

Share this post


Link to post
Share on other sites
Ah, I misunderstood what you said. So instead of storing a grid of heights in a texture you store in a vertex buffer.

In that case, what are the 8 segments that you split a disk into?
0

Share this post


Link to post
Share on other sites
[quote name='turch' timestamp='1329507800' post='4913995']
In that case, what are the 8 segments that you split a disk into?
[/quote]

The vertex buffer is "all terrain"
The disk is "potentially visible terrain"
The segments are "visible terrain"

By intersecting the view frustum with the segments you can render only the segments that are visible.

You can also use a draw call per segment and using the startindex and primcount to render only the visible depth band
This can handle degenerate case of camera pointing straight down (requiring small depth range of all 8 segments)
Also consider using a "plug" for the inner disk to simplify things.
0

Share this post


Link to post
Share on other sites
[Doh, when I said geomipmapping in my previous posts i meant geoclipmapping]

What I meant was, what are the actual shapes of the 8 segments. Are you using the same shapes as for geoclipmapping? The blocks, fixup and interior segments like here:
[img]http://research.microsoft.com/en-us/um/people/hoppe/proj/gpugcm/gpugcm.mid.jpg[/img]
0

Share this post


Link to post
Share on other sites
No, I am using "pizza slices" similar to my XNA Large Terrain

[img]http://skytiger.files.wordpress.com/2010/11/terraintransforms.png?w=512[/img]

But using 8 slices (instead of 16) to simplify things (and keep straight edges for all segments)

There are no "fix ups" as the LOD is static, again same as my other system:

[img]http://skytiger.files.wordpress.com/2010/11/terrainvertextexela1.png?w=780[/img]

(ignore the catmull rom stuff)

I've managed to build a working implementation using SlimDX (9) today
it proves the concept - tomorrow I will finish the index buffer builder
and then it only needs frustum intersection and its done
2

Share this post


Link to post
Share on other sites
Ah so the slices look like this?
[img]http://oi39.tinypic.com/2l9gm14.jpg[/img]

And also, this means you can't do any kind of interpolation correct? You just "point sample" the vertex grid.
0

Share this post


Link to post
Share on other sites
exactly
using PC DX9 I can't think of a way to perform interpolation
on XBOX DX9 you could vfetch and interpolate
-1

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  
Followers 0