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.

    March 18, 2001, 10:00 AM

    So we should all be pushing a heap of tri's down to the card in strips/arrays whatever...

    I'd like to know what people see as the best way to texture those triangles in a t&l firendly way...



    March 18, 2001, 11:28 AM

    Spark - The sky and the mountains are not at the same depth. I was trying to implement a haze. Go look at mountains or any landscape and you will see this effect. The sky should never turn into the fog color. I don't plan on doing fog just to hide areas I can't draw polygons to (simple LOD or frustrum clipping). I just want to use fog (or haze) when it looks like haze.

    I'll post answers to more questions later, gotta go . . . . .


    March 18, 2001, 11:58 AM

    I'd be very tempted to do a first pass over the heightmap data with a very stringent variance, then use this pass to remove areas that are never going to need subdividing beyond a certain depth (flat areas most likely), travel up the tree a little to bunch some together (not merging). You could put them into a vertex array if you wanted, then put them in your tree as leaves.

    I know what you mean about Popping and Morphing - I remember when I played Project IGI, apart from the fact that the terrain was featureless and bland for a FPS (at least on the demo level), you could very visibly see it morphing before you, it actually made me feel a little ill.

    Perhaps you could put in a distance based LOD, and since you weren't planning on using one anyway, only assume that you want to remove a few triangles out of the most distant areas (for example, those areas that you might be fogging excessively anyway).


    March 18, 2001, 03:25 PM

    first of all, this is the most impressive showing of a voxel terrain engine, ive seen so far. my question involves the new n-patches, or whatever they're called, from the new OpenGL SDK from NVidia. Couln't you use the same size voxel structure (128^3), to control these n-patches instead of quads or poly strips, whatever you're using. That way you could have the same ammount of detail using less world data and you wouldn't need a voxel structure bigger than 1024^3 to represent thousands units of area. I hope you can understand what im saying, im kinda typing this in a rush.


    March 18, 2001, 04:59 PM

    hi Jack, nice screenshots. it's always good to see people trying something new instead of just getting stuck in the "what's best? I'll just use that" mindset.

    given your topic, I recommend you check out a shape representation called Adaptive Distance Fields (ADF). there are several good papers around, including an ADF intro from the MERL lab people from last year's SIGGRAPH (see the main idea of a signed distance field is for each point in space to store the distance to the nearest surface. so it's kind of in-between a volume and a surface representation (with some nice characteristics of both). adaptive sampling allows for octree-based storage with an interpolating reconstruction function.

    as others have mentioned here, ROAM is not just for heightfields. I'll admit I'm biast (actually, I'm a student&employee of Mark D, the original ROAM author, whom I work with on ROAM stuff at LLNL in the summer), but ROAM has a much brighter future than people are generally aware of. there are methods for making ROAM scream on modern T&L hardware (with clustering), using arbitrary geometry, doing realtime modification, etc. imho, the publications & public knowledge will catch up with the research in the next couple years. ultimately, it scales better and is the most general algo going for view-dependant LOD.

    I thought I'd mention that I'm working on a general visibility algorithm for arbitrary multires geometry, and have recently had some ideas about using ADF's and building multires meshes from them automagically. neat stuff.

    anyway, kudos for doing something different :) and I think if you check out the ADF and signed distance literature, you may like what you find.



    March 18, 2001, 06:07 PM

    Nexus - "bit per point", I actually store a short int per voxel point. This allows me to specify a surface type (grass, sand, rock, etc.). These will all be dynamically generated textures. Most of the time when an area is composed of the same type I just make a not of that in the octree node and don't have to break the tree down any further.

    Zoraldin - Sorry that my demo is sooo slooow. It's really very rough. I'm running a Dual Celeron 533 and it's slow on my system. :). Although I've been adding a lot of changes, see below for more info.

    Nexus - When I first started working on this project I was using Software OpenGL (under BeOS). But when I bought a Geforce2MX and started playing with accelerated GL under Linux I decided to assume I would always have this type of hardware or better. I would think that any game company that was starting to work on a new game would have a release date of 2 to 3 years. Maybe I'm wrong, but I would think that in 2 to 3 years everyone will have a T&L card that can handle millions of triangles.

    Sebastian Sylvan - ". . . It's just the idea of having geometry pop up in front . . ."
    If you use static LOD and "pop" them in far enough away it's impossible to see the "pop".

    NEGA - I understand what you are saying. I believe the features you are talking about are only accelerated with the GeForce3 (I may be wrong). So I can't play with them yet. They might be interesting to experiment with.

    Igur Nebli - Good point, that's probably a better statement. I'll say it loudly Height Fields SUCK!!!! (just kidding). But they limit you so much. Of course they are EASY, but as a programmer I like something more challengine personally.

    Bobtree - Thanks for the ADF info. Sounds VERY cool, I will check it out. Who knows maybe I'll throw them into my engine. Thanks for not getting angry with me about downing ROAM. You mentioned new methods for speeding up ROAM on T&L machines. Care to point us to some docs?

    Ok, I want to thank everyone for there comments. I've really enjoyed all this discussion. This is my first post to flipcode and it's been a lot of fun and I've got a lot of cool ideas I hope to implement.

    For everyone who wanted a WINDOWS EXECUTABLE, I'm talking with someone who has offered to port my engine to windows. When that becomes available (I hope soon, cross my fingers) I'll post another IOTD on flipcode.

    I would let him port the current code, except that I posted my image to flipcode a week ago and the code is so different (and better) than it was that I want to finish my current modifications before I release another demo.

    I did something very strange, I can't believe the thought crossed my mind. I wrote a version of my engine without TEXTURING. Yep, I through textures away completely (at least for the landscape). The texture coordinate generation algorithm that I was so proud of I quit using (at least for now). Instead I increased my polygon count tremendously. The results are pretty cool. Instead of sending texture coordinates and textures I just send triangles with colors and normals. A WHOLE lot of triangles, and it looks as good as the texturing. Take a look at my homepage for some screenshots. I've been able to get 4 to 7 million triangles a second with this change.

    The other feature I want to add before I release another demo is real grass, rocks, and pebble. When you move close enough to a polygon I will generate blades of grass, small rocks, and tiny pebble on top of the triangles. I haven't started adding this code but I plan on doing it this week.

    Thanks for all the comments,

    Jack Strohm


    March 18, 2001, 08:14 PM

    It depends on the coherancy of the voxel set actually relative to the size - octree compression isn't that great, because if you want a structure you can walk fast, it takes up a reasonable amount of memory to have a 3 colour octree. But, on very coherant sets it can save you gobs of memory. But, you can still well bleed memory with complex high frequency objects and low spatial coherancy.

    In terms of high frequency objects with reasonable coherancy 4096x4096x2^32 is reasonably maintainable with good compression schemes. Although building them that big and compressing as you build is a BITCH.


    March 19, 2001, 10:21 AM

    > You mentioned new methods for speeding up ROAM on T&L machines. Care to point us to some docs?

    nope, they're not published yet. iirc, the one to look for is Alex A. Pomeranz masters thesis (uc davis) "ROAM Using Surface Triangle Clusters (RUSTiC)", whenever it gets on the web (I only have an early paper copy, doh!). he might share it if you find his email and ask nicely, but don't know him.

    the basic idea is to use ROAM as a chunk-based optimizer. the simplest method is to render each tri as an n*4 res patch (n*2 split levels, because given any continuous mesh, at every 2 split levels the junctions will line up naturally because each edge has been split once). so you could optimize say, a X-tri mesh, and then render X*4 (or 16, 64, 256) triangles. 6250*16 (or 1562*64 or 390*256) is 100,000. do that at 60fps, and you've got 6 mil tri/sec easy :). the granularity determines how big your chunks are (and thus how much faster you can render them), at a trade off of how accurate the result is (via how local the optimization is, eg, smaller chunks on a higher res mesh == more accurate, but likely slower).

    the more interesting (and correct) thing to do then is generate locally optimal chunk hierarchies to use instead of just boosting resolution uniformly. it's also possible to do something like local VIPM on the chunks as you go.

    thus, you can use ROAM to optimize on a higher level than individual triangles (which is what normally kills performance for super high res output).

    people tend to assume that because everything they've seen done with ROAM is simplistic or poor, it's the algorithms fault. this is demonstratably not so, and sooner or later someone (perhaps me) will proove it with a top-end public impl.


    David Olsson

    March 19, 2001, 01:48 PM

    I was so inspired by this IOTD that I started on my own voxel renderer. I am currently implementing Stan Melax's tessellation algorithm... that is damn boring. Not the algorithm itself but creating an array with triangles created for each 2x2x2 voxel layout.
    Before I continue with this which I suspect will take a few hours I'm just going to ask if you know somewhere I could my hands on such array or if you have some special trick when constructing that table.


    March 19, 2001, 01:57 PM

    I can give you my data file I created (all the triangles face the same direction, that took awhile to fix).
    What email would you like me to send it to you.

    David Olsson

    March 19, 2001, 02:32 PM


    March 22, 2001, 10:43 AM

    I have a small question regarding your perlin noise generated voxel cave thing. Im trying to do something similar (slowly) and I can't see how to implement dynamic LOD. My problem isnt the triangles - its the world itself. The simplest example I can come up with to explain it with is a floating rock which crosses the border between two LODs. If it is a small enough rock, it doesnt exist at the lower LOD and the triangles dont just change detail level - they cut off completely.
    This doesn't happen in a terrain because there is always something there... in a 3D surface sometimes there isn't.
    I had just given up and gone for constant LOD but if you've got a way round this please yell!


    March 22, 2001, 12:10 PM

    I use a vertex collapsing method to generate my LOD. Theoretically small peices of geometry (a small rock floating in space) might collaps to nothing, or actually to 2 points or less which would then be deleted. I haven't seen this situation occur so I don't know what would happen.

    To be honest I never thought much about it, but I will try playing with different models and see what happens at extreme loss of detail. I am pretty sure that the geometry will simply disappear if it isn't a surface and not a localized closed surface.

    Best of luck,

    Jack Strohm.


    March 24, 2001, 04:48 AM

    If anyone cares I added a screenshot to my hopepage of a test of dynamically generated grass on a terrain.

    go to:

    David Olsson

    March 24, 2001, 06:34 AM

    Looks damn cool !

    Is the grass polygon models or textures ?


    March 24, 2001, 12:52 PM

    What I am doing is I have an texture of grass shown from the side with alpha values. For each triangle that makes up my land I draw about 25 squares on top that have this texture.

    I only draw these textures quads when all three normals for the surface are positive. So it's pretty much massive bill boarding. It is VERY VERY beta but it shows promise.

    I hope to post another image to flipcode with grass and trees fully implemented. I have also found people who have agreed to port to the Mac and to Windows.

    David Olsson

    March 24, 2001, 01:25 PM

    It's pretty much the method I expected you to use only I didn't thought you were using that many "billboards".

    Btw, you don't use icq much, do you ?
    Or do I have the wrong icq# ?


    March 24, 2001, 01:55 PM

    I don't use ICQ much. I used to use it a very long time ago and I guess I still have an account. I may see about a linux client and install it in the future, I've had a few people ask me about it. I do answer emails very frequently. email me at until I get ICQ installed.


    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.