That is very nice!! So do you re-partition the octree when you're changing things dynamically?

nice, love the noise generated cave.. but I think you should fog the skysphere.

Nice. But, just curious, what is the memory requirement to hold a voxel structure of 65536x65536x65536? I could figure that a 128x128x128 could be 256k, but 65536x65536x65536, way to big.

Jean-Francois Dube

Hi,

nice image.
Could you tell me more about your texture-coordinate mapping? Giving each triangle its own piece of a texture is just what I need for some lightmapping stuff I'm doing, yet I haven't been able to find a decent solution yet.

Thanks,

Jaap Suter

I must say, that is horribly impressive.

Thats great work. I'm also curious about mem requirements. 128x128x128 isn't that much. But I imagine when you add textures and all the data structures to support the engine it probably ends up having a footprint similar to a decently sized app. Now 65536x65536x65536 is going to just f**king huge!

How are you planning on dealing with this?

In some cases you only have to store the surface of the structure, not every single voxel.
Or you could use some kind of compression. Volumetric data should be rather compression friendly.

65536x65536x65536 is huge! (256 TB or 32 TB if you use bit fields)
But presuming you could swing it with compression and what not
(actually I assume you have a structure with only the filled voxels entered?) it would be be pretty cool. For refrence that would allow you to have a voxel model of the earth to a resolution of 650 feet!

I would like to talk more about some laws, which are derived from our personal experience and in some cases 're distorted by huge impact of our politicians.

1)Importance of LOD is not always so high as it sometimes considered.
2)'raw' terrain cannot be a final solution, as well as mix of solutions can be not better than one single solution.
3) importance of linux binary is not always at the top of importance scale.
4)Top memory requirements not necessarily indicates top gameplaying
5)however, screenshots are important in some cases.

Is there Win32 executable?

Thanks for the comments, I love to hear them all.

To answer a few questions:

The Wolf - Yes - I do repartition the octree. Nodes come and go as they please.

Spark - Sorry, I'm not sure what you mean by "fog the skysphere"?

deks - Memory requirements are steep, but I'm working on that. The entire voxel mesh is not allocated. Instead only the part areas that contain changes. So a mesh that contains a large flat terrain would take up about as much memory as just a simple heightfield map.
I'm also going to add a caching mechanism. This will allow me to take part of the octree offline. A map might take a few gigs on disk but only a few hundred megs in memory.

Jaap Suter - I added a new section to my homepage just for you explaining my algorithm. I'm terrible at explanations so feel free to email me for clarifications. Check out http://home.jam.rr.com/jstrohm/projects.html and look on the left.

Leon Rauis - See deks answer.

David Olsson - Exactly what I'm doing :)

IOHazard - A friend of mine keeps wanting me to do that. To put a fully spherical planet in the engine and simulate gravity, non of that flat terrain engine stuff. I might think about it, but I've got a ways to go.

STZ - I'm confused as to what you are saying, but thanks for the comments anyway.

malkia/eastern.analog - Sorry their isn't a Windows executable for a number of reason.
I quit programming in windows about 2 years ago and I haven't regretted it yet. I went to BeOS and then to Linux (Better NVidia 3D support).
I haven't had my Linux box crash while developing this year.
I've gotten fed up with Microsoft. There API's are terrible. I know, I know everyone says DX8 is much better (I used DX3 I think.). I looked at DX8 and it's finally looking more like OpenGL. hmm wonder where they got that idea? :)
Biggest reason, I don't have a Windows compiler. I hope to port to windows someday. That's where all the gamers are.

This application is pretty much 100% OpenGL, GLU, & GLUT so it should port to Windows fairly well . . . hint hint, anyone want to port for me?


While I have the podium I just wanted to say something. . . hope this doesn't start a flame war. It's said with the kindest regards.

STOP USING ROAM!!!! ; - )

I see a whole lot of engines using roam (and it's a WONDERFUL algorithm), but with todays cards you need to be able to push
a lot more triangles to the card. I mean my Geforce2MX can hit 8 million triangles a second fairly easily. That's insane but to do that
you need to organize your polygons well and do a lot of bulk dumps of triangles to the card. I haven't seen a lot of engines that focus on this.

Anyone out there writing their own engine, look at the number of triangles per second you get. Can your engine push 8+ million triangle a second? If not, your old news (not trying to be depressing.).

Sorry if I've been ranting, this has been on my mind for quite awhile. This isn't directed at anyone I just wanted to see what the community had to say about this kinda of stuff. I may be totally offbase.
I'm tired, been programming all night. TTYL.

On the subject of the data requirements... are we really assuming that the space will be filled with data such that using full bit per point representation will be needed? I find that unlikely.

I think you'd probably use a trainer on some different examples of landscapes to see how much memory you'd need for a typical landscape at that resolution. You're in trouble when you start building landscapes that are too complicated, but just like normal you simply have to make sure that that won't happen in normal (and typical) use.

IOHazard - nice calculation :)

Woohoo a linux demo!! No need to reboot or pray that wine works!!

It works, but it is fairly slow on my system:
Pentium 2 300
nvidia TNT

linux 2.2.18
X 4.0.2
NVIDIA 0.9-6 drivers

The animated skydome is very nice.

When in browse mode it is very slow when i move, especially when getting
closer to the landscape from the starting position. But when using the
mouse to look around it is ok.

I couldn't edit the landscape in brush mode - i'd set my brush action
and type, position the brush and press space - half the landscape goes
black and it seems to be recalculating something but the landscape isn't
changed when its finished ?? Maybe i'm doing this wrong ??

I'm sure when it's run on a faster machine than mine its great :)
( beats my generic roam landscape engine )

> STOP USING ROAM!!!!

I'd love to, if I had a good alternative. I'm implementing a displacement mapping algorithm for my masters project, and obviously I need some kind of LOD. Is there another LOD technique that makes triangle stripping (or another kind of triangle batch approach) easier? I'm fairly new to 3d, so these kinds of optimizations are not one of my strong points.

I agree with you about ROAM, Hoyle. Immediate mode engines like ROAM do not make good use of hardware T&L. I think the fastest new OpenGL terrain engines will be dynamic LOD's using gldrawelements. Up till now I've been developing a static LOD terain engine using gldrawelements. I get 7 M/Tris per sec. The problem with using vertex arrays is that they require a lot more memory than immediate mode. If I use vertex arrays my total mesh size will have to be a lot less than if I use immediate mode.

Nice image btw

About not using ROAM for terrain. I agree completly

I think dynamic LOD is highly overrated. People tend to think "oh I've reduced the poly-count by 30%, this is really good" but they often spend too much time on the actual poly-count reduction that the whole thing doesn't run any faster.

I think you'll find that on modern hardware (T&L) it is faster to simply render a heightfield at full detail using triangle strips. You can find the start point of a triangle row or column (which one is optimal is depending on the direction of the camera) in the heightfield and start drawing triangles (using strips) to the end-point of that row or column. No quadtree is necessary. The geometry is completly uniform consisting of (looking from above) completly equal sized triangles. So just check against the left-plane of the frustrum to find the first visible triangle, then check against the right plane to find the last visible triangle. Then just render that entire row. You might have to render it in colums instead of rows depending on how the camera is orientated. To further optimize (reduce the number of frustrum checks) you can cull only every tenth triangle or so against the frustrum, and when a triangle is visible you step back 10 triangle and start drawing there.

Basically, you're trying to touch as little data as possible. Doing distance based LOD-schemes take more time than they save on T&L hardware.

If you can do a static LOD however, that might be worth your while. Create a triangulation of the most important vertices (you can specify the exact amount of vertices here) and use only those for rendering. If you can divide this triangulation into triangle-strips or fans, and in an optimized manner partition them in a quad-tree you might be able to get very good performance. Perhaps better than just rendering the terrain without any LOD at all.
Plus, using static LOD eliminates that nasty geometry popping that most ROAM algorithms suffer from (if they don't have morphing which requires even more data to be touched). ROAM was a nice transistion-algorithm. Doing terrain on low-poly systems. But it is just to CPU-intensive to cut it on modern hardware.
I refer you to this terrain-simplification algorithm: http://graphics.cs.uiuc.edu/~garland/software/scape.html

A beaut of pix, that cave.
Hey....whats a T&L card ? people throw the term around, I havnt a clue what it means. Transformation and Lighting ?
~V'lion

T&L means Transform and Lighting. T&L cards can do these operations in hardware.
T&L cards available are: Geforce 1&2&3, Radeon
Look at nvidia developer site for more information

In the top left picture you can see the mountains fade inte white, but the sky at the same depth is not white...

This application is pretty much 100% OpenGL, GLU, & GLUT so it should port to Windows fairly well . . . hint hint, anyone want to port for me?

I'd be a whole lot easier to port it if the source was available. Now I know what it's like being on the short-end of the OS stick :) .

From the description and the screenshot, I feel compelled to say this is one of the most impressive things I've seen in quite some time. The mind boggles at the possibilities.

I've been lurching here for over a year, and this is the first time I've felt compelled to post... and state my obvious frustration for being unable to play with your demo. Argh!

>I went to BeOS and then to Linux (Better NVidia 3D support).
I would like to try the demo, but I fear Linux (SUSE 6.4) won't work with my Geforce 256 :-(
And like some said before, the white doesn't match the end of the mountains. For the rest it's great!

Suse 6.4 should work fine with your GeForce

Dynamic LOD isn't just about removing detail to gain a speed up, it
enables you to add detail in the foreground within a reasonable poly
budget.

At the extreme end, imagine a whole planet which has a surface given
by some mathmatical formula, detailed right down to tiny ridges under
your feet.

You can't retain that kind of detail over a that large area without
dynamic LOD - and even if you had hardware that can, you could always
want details the next level smaller.

It's a mater of using the right algorithm for the right application.
Sure dynamic roam ain't for quake, but it has its place.

(I wish i could remember the link to a dynamic LOD planet program i saw
on flipcode last year. Can anyone help? )

Your card certainly has linux support, but it may not work straight
out the box with your suse.

Try

http://www.nvidia.com/Products/Drivers.nsf/Linux.html

You will need X4 if suse 6.4 doesn't include it ( a bit tricky )

Have a look at the recent article on gamasutra, here. It's about rendering an entire planet, up to a very small resolution. It's actually a start at modelling an entire galaxy, with millions of such planets, so the article focuses more on generating predictable random terrains, but it still quite a good LOD algorithm. What I find most interesting about it, is that it uses ROAM on a spherical body, not a flat one.

I love your IOTD, btw, great work!

The real advance is not to stop using ROAM or any other algorythm. The real advance is to stop using heightfields!

True, heightfields are BORING! ROAM was designed to handle arbitrary meshes, heaightfields are just easier to implement. And that's the thing, isn't it? Heightfields are easy. Just take a grayscale image (exported from any paint program) and there's your terrain. Using arbitrary meshes to describe terrain as detailed as you see now-days with heightfields is going to be very difficult.

The only way I can see this happening is if you start with a heightfield, and then use techniques like Jack's "edit sphere" for destroying/creating extra features. Imaging creating an entire 65kx65kx65k voxel-map with this edit sphere! As has been pointed out, this is enough to a fairly high-res model of the earth - that's a lot of modelling! You need something to flesh out the basic structure (e.g. a height field) and then you can add details.

This is of course assuming that you know you're programming for a machine that *can* push a lot of triangles and do T&L. If you were making a commercial game and you did it without some sort of scalability, you could well cut out a lot of your paying audience.

Instead, why not work on clever time slicing algorithm to incorporate that will allow people with ridiculously fast machinces not to do any LOD, while people that need it can do some pre-pocessed static LOD followed by a small amount of dynamic LOD?

That HAS to be a better solution than assuming anything either way.

Here's an idea. Base the LOD on large-ish pre-triangulated areas, at different resolutions. Then use the
wheighted vertex hardware to morph continously between two levels of LOD for each area. Sort of like
the geo-morhping in the ROAM paper, just instead of with time you morph with the LOD cost function (eg
distance), and for a whole block of triangles at a time. Where two areas of different LOD levels meet, you
have to adjust the triangles along the shared edge. Still, with an N x N landscape, there are O(N^2) triangles
in total, but only O(N) lies on shared area edges. Should allow you to push lots more triangles through the
pipe, while totally avoiding popping.

/Johan

Nexus. Yes, that's what I'm thinking about doing (research phase right now). You have a full-detail heightmap that you load into memory, and then if the user has selected a detail-level other than "heighest" in the options I'll do a mesh-simplification on it (see previous URL) and then split this mesh up into triangle fans/strips (any good algorithms?) and then I'll build a tree "backwards" from that. So I'll have a bunch of clusters (strips or fans) and I'll group them together in twos or threes or any arbitrary number, and then I'll group these groups together and by doing so recursively I'll build up a tree from the back end. And it will be completely optimized in that there are no duplicate triangles, and the leaf-nodes are already optimized in fans or strips. And then I'll add bounding boxes for each node to allow for hiarchial frustrum culling.

I'm not planning on having any distance based LOD though. It's just the idea of having geometry pop up in front of you that bothers me most. And morphing is out of the question since that requires a lot of data to be touched. Plus, most algorithms I've come across requires a BUNCH of data to be touched each frame even without morphing, and I just want to avoid that. Geomipmaps is the one algorithm that I might consider later on though. Any other tips?

I thought about that and the simplification that needs to be done on each "cluster" when it has a neighbour at a lower LOD is just to much for me. I just want to avoid touching any data at all costs. Just flush it down the pipeline!

Plus, if I want to morph it in a trilinear fashion (using the mipmap analogy) I'll have to keep a cache of each vertex position in the next LOD level, because some of the vertices don't really exist at the next LOD level. If I don't want to keep this cache (which means a lot of extra memory required) I have to find the position of a vertex on the polygon of the next LOD-level which is a lot of extra math each frame. Either way there's extra overhead.
Plus the vertex-weighting might not be available in hardware, which means I'll have to do it in software, which means even more overhead.

Basically, I don't like morphing at all, it always mean a lot of extra overhead. I'd rather have popping and move the LOD threshold back a bit so that it becomes invisible, than have lower detail and seamless transition between different LOD-levels.

But that cluster-simplification algorithm, while useful on GPU-limited systems, is just to CPU-intensive, even if it is WAY better than ROAM in that area. Plus, if you define your terrain in clusters that are supposed to be simplified, you aren't going to be able to precalculate triangle strips or fans.