Not logged in, Join Here! or Log In Below:  
News Articles Search    

Submitted by Jack Strohm, posted on March 17, 2001

Image Description, by Jack Strohm

These are some screenshots from an engine I've been working on for over a year called Geek. This engine dynamically generates a mesh from a 3D voxel data structure. The voxel structure used to create these images was 128x128x128. I plan on supporting a voxel structure of 65536x65536x65536. I have a long way to go before I can call it complete. I plan on adding a portal basted indoor engine also. A friend of mine is writing a scripting language for it. Check out the website for more details.

Going clockwise, the top right picture shows some terrain that fades into fog. The next image is a wireframe showing LOD in action. Note the more distant terrain has fewer triangles. My cost function for generating the LOD sucks but will be improved soon The next image is what I like to call "green swiss cheese". This model is created using a perlin noise function. The final image shows real-time editing. (Still not as real-time as I would like). When you modify the voxel structure all affected meshes and textures are recalculated allowing you to see your changes immediately.

The engine and the editor are the same. My goal is to have an engine that allows for real-time map deformation. Imagine throwing a bomb and find a hole in the ground where it landed, along with being able to see the grass on the edge and the dirt under the grass from where the bomb exploded. Well that's my goal anyway, hope I can get that far. Current features include:
  • Underlying data structure are voxels contained in an octree.
  • Dynamically Generated Mesh, Textures, and Texture coordinates.
  • Terrain doesn't have to be flat. It can have holes and caves in it easily.
  • Allows modifying of the voxels which in turn causes all affected meshes to be recalculated.
  • Real time editing (this is still slow, but hasn't been optimized yet)
  • Early LOD, as you move farther away I use lower resolution meshes.
  • Saving and Loading of all data structures.
  • Preliminary console implemented.
  • Implemented in C++ and OpenGL under Linux
  • Currently only tested on TNT2 and Geforce2MX
  • Multithreaded (Except can't run in MT mode on SMP machines running NVidia drivers, bug in drivers).
  • Sky sphere has been implented.
  • I'm sure there is more, but I don't remember.
  • You can download the linux executable (Mandrake 7.2) and see more screenshots at

    I'm most proud of the dynamic texturing. I can take a OpenGL texture and generate texture coordinates to wrap it around an arbitrary surface. I'm not talking about projection mapping, but I am able to give every triangle it's own area of the texture image and still generate triangle strips that can quickly be fed thru OpenGL. On my TNT2 I can get between 1 and 1.5 million triangles a second. Once some of the driver features that are available under windows for the Geforce2 are implemented under Linux I should be able to get 5-8 million triangles a second on a Geforce2MX.

    Thanks for any comments and constructive criticism,

    Jack Strohm

    Image of the Day Gallery


    Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )
    Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
    The Wolf

    March 17, 2001, 10:52 AM

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


    March 17, 2001, 11:50 AM

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


    March 17, 2001, 01:10 PM

    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

    Jaap Suter

    March 17, 2001, 01:19 PM


    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.


    Jaap Suter

    Leon Rauis

    March 17, 2001, 02:50 PM

    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?

    David Olsson

    March 17, 2001, 02:55 PM

    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.


    March 17, 2001, 03:25 PM

    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!


    March 17, 2001, 03:48 PM

    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.


    March 17, 2001, 04:52 PM

    Is there Win32 executable?


    March 17, 2001, 05:29 PM

    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 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.


    March 17, 2001, 05:37 PM

    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 :)


    March 17, 2001, 08:01 PM

    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 )

    Jan Niestadt

    March 17, 2001, 08:15 PM


    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.

    Adrian Lark

    March 17, 2001, 09:09 PM

    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

    Sebastian Sylvan

    March 17, 2001, 09:19 PM

    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:

    Lion V

    March 18, 2001, 01:06 AM

    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 ?


    March 18, 2001, 04:14 AM

    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


    March 18, 2001, 05:08 AM

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


    March 18, 2001, 05:36 AM

    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!

    Bart Coppens

    March 18, 2001, 05:39 AM

    >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!


    March 18, 2001, 05:46 AM

    Suse 6.4 should work fine with your GeForce


    March 18, 2001, 06:25 AM

    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

    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? )


    March 18, 2001, 06:28 AM

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


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

    Dean Harding

    March 18, 2001, 07:01 AM

    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!

    Igur Nebli

    March 18, 2001, 07:21 AM

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

    Dean Harding

    March 18, 2001, 07:28 AM

    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.


    March 18, 2001, 07:30 AM

    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.

    Johan Runeson

    March 18, 2001, 08:05 AM

    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.


    Sebastian Sylvan

    March 18, 2001, 08:14 AM

    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?

    Sebastian Sylvan

    March 18, 2001, 08:27 AM

    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.

    This thread contains 48 messages.
    First Previous ( To view more messages, select a page: 0 1 ... out of 1) Next Last
    Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.