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

Submitted by Jack Strohm, posted on April 24, 2002

Image Description, by Jack Strohm

NOTE - Not a terrain engine, but it can do terrain.

These are some shots from an engine I've been working on for about 2 years. I've still got a long way to go before it's finished, but since I finally got a windows version up and running I decided to post an IOTD.

I originally posted an IOTD quite awhile back, some people refered to it as green swiss cheese. I've decided to call the top left image furry swiss cheese (I'm using animal skin textures for my test now). The top right image is the left image in wireframe. The bottom left shows the top side of a smooth cube with some odd structures on it. The bottom right shows a few seconds later with some edits applied. The edits are near-realtime.

Originally the engine was supposed to be a voxel engine, inspired from some work by Stan Melax. But as I kept working on it I ended up switching it to metaballs. It seems to me that voxels are kinda like a degenerate form of metaballs anyway, at a certain area one unit squared they have a field value of infinity and everywhere else they are zero. Metaballs have some nice properties that voxels don't give you like simple normal calculation and reduced memory overhead.

Well now the engine takes a whole lot less memory than before and I've gotten edits much faster. This demo allows you to edit in one of two ways. You can fire (spacebar) a bullet that hits the terrain and destroys it (actually adds negative metaballs). You can also move to a spot and hit 'E' and deposit a positive metaball in your location. Both of these will be quickly calced and added to the new scene, on a fast system in less than a second. Please read the readme.txt before you run the program.

I've got ideas to build a game, that allows real-time deformation of the terrain (grenades, bombs, etc!). Also when I add the physics system I can use the field values from the metaballs to calculate gravity so that you can walk over the surface of the metaball structure. Think of the game "Tribes" in space, fighting on deformable metaballs.

It supports LOD using a modified binary triangle tree algorithm. The BTT seemed a bit slow, sending single triangles to the screen at a time, so instead of a triangle being a leaf node in the BTT, a large group of triangles are the leaf node of the BTT. Also LOD only occurs in the XY plane. Z LOD always stays the same. The meshes that exist in the leaf nodes of the BTT are optimized for the Geforce vertex cache.

Ok, now for my feature list:
  • Underlying data structure are metaballs.
  • Dynamically Generated Mesh and Texture coordinates.
  • Terrain doesn't have to be flat. It can have holes and caves in it easily.
  • Allows modifying of the metaballs which in turn causes all affected meshes to be recalculated (very fast!).
  • Real time editing (now it's fast, but it will get MUCH faster!) LOD implemented using a variation of binary triangle trees.
  • Saving and Loading of all data structures.
  • Console can change most system variables while the app is running.
  • Implemented in C++ and OpenGL under Linux, ported to Windows using Borland C++ (only tested under XP). Currently only tested on TNT2, Geforce2MX, Geforce2 GTS(thanks Zelcious).
  • Multithreaded (A little jerky under windows, still working on figuring that out).
  • The longest project I've ever been able to concentrate on without getting distracted (Hey that's a very cool feature!)
  • To download the source code, linux binary, or windows executable go to Larger screenshots are also available. Prebuilt maps are available as a seperate download (they aren't very fancy!).

    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.

    April 25, 2002, 01:06 AM

    woops - that last one got added twice.


    April 25, 2002, 01:24 AM

    Patents are evil, man, evil.

    What's a metaball? I'm developing my own gfx engine, to be made part of a game (and hopefully sold), and the last thing I wanna do is accidentally implement something that's patented..


    April 25, 2002, 02:04 AM

    cant MCBAXTON be banned then?



    April 25, 2002, 02:06 AM

    Here is a good description of metaballs and it also covers marching cubes (a patented algorithm). Metaballs are not patented. You will have to create an account to read this article, but it is free and well worth it because they have lot's of other good articles.

    As for patents being evil, I disagree, but I can understand why you would say so. But in this case I think the patent is stupid. They basically patented using a lookup 256 entry lookup table to generate polygon data from a 8 voxels. They take the binary values of the corners of a cube (8 1 bit values, zero if density is below a threshhold, one if density is above threshhold, so a 256 number). You take that number and lookup in a table a list of polygons that fits that configuration. The article explains it much better.

    This is such a simple algorithm, it would be like patenting a binary search or something . . . . that is stupid. But I do feel sometimes patents have there place, to protect truly original ideas.


    April 25, 2002, 03:30 AM

    Sorry I should have read all the instructions :)

    'make depend','make clean',make got the build process past the mandrake dependency, but now I seem to have a compiler problem. I have gcc 2.95.4 which it is using. I also gave gcc-3.0 version 3.0.4 installed.

    In file included from common/CQuaternion.h:7,
    from engine/CActor.h:22,
    from engine/CPlayer.h:19,
    from demo/CDemoWindow.cpp:12:
    common/CMatrix4X4.h:33: anonymous class type not used to declare any objects
    common/CMatrix4X4.h:37: anonymous class type not used to declare any objects
    common/CMatrix4X4.h: In method `class CMatrix4X4 & CMatrix4X4::operator =(const CMatrix4X4 &)':
    common/CMatrix4X4.h:57: `xx' undeclared (first use this function)
    common/CMatrix4X4.h:57: (Each undeclared identifier is reported only

    Mathias R

    April 25, 2002, 03:56 AM

    Wow... that dual contouring stuff really looks cool. I wonder what you can do with it. In a game, could you drill holes into walls with it? Could you make a pit, and when somebody falls into it, seal it? The possibilities seem endless. ;)


    April 25, 2002, 03:58 AM

    Nice, thanks!
    Will check it out!


    April 25, 2002, 05:05 AM

    Dunno if this would work with your method, but you could try the slope lighting method discussed in a previous IOTD.


    April 25, 2002, 05:39 AM

    Hey guys - I am tired of such 'forum defenders' like you, just shut up please. Because of the poster's name is 'MC BAXTON' does not mean you MUST reply with 'shut up'-forum pattern!


    April 25, 2002, 05:43 AM

    Gee, I have seen that before... The 'what is *engine*-shut up' pattern by Polstrat and Ron Frazier et al.


    April 25, 2002, 06:25 AM

    The way I do it is to make 2 vectors using the 4 points around the point you are looking at (ie: Up-Down, Left-Right) and do a cross product on them to find the normal.

    I think that's the way I do it anyway... It's been a long time since I touched my terrain engine.

    Ron Frazier

    April 25, 2002, 07:30 AM

    Well, I just thought if he's going to copy and past the same question, I would just copy and paste him the same answer :)


    April 25, 2002, 07:59 AM

    I'm using gcc version 2.96 20000731 (Mandrake Linux 8.2 2.96-0.76mdk). That peice of code I copied from a quaternion exaple on the web, it's using anonymous unions (or something like that), which I'd never seen before and didn't know you could do. So apperantly you can't on all compilers. Well gcc 2.96 and Borland C++ seems to like it. I'll look at rewriting it sometime so that they aren't anonymous, sorry about that. Thanks for the info!


    April 25, 2002, 07:59 AM

    do you remember which IOTD?


    April 25, 2002, 08:00 AM

    yeah, that's what I was thinking about.


    April 25, 2002, 08:20 AM

    I think people are just messed up.. runs perfectly fine on my WinXP machine... I shoot the thingy out.. hits the terrain, flashes the lines, and bam, it's deformed.

    Athlon XP 1600
    128 megs PC2100
    Geforce2 MX (original)
    Windows XP Proffesional

    (Maybe you guys have something set differently, like giving priority to tasks up front instead of background processes, or something stupid like that).

    Billy -


    April 25, 2002, 08:32 AM

    Okay I'll post this in the main thread, but I implemented a simple MetaHeightField and posted screenshots on my webpage (It's pretty fast, but many optimizations I can do on it) here is the direct link:

    Thanks everyone!!!


    April 25, 2002, 08:35 AM

    Thanks to some ideas from the guys here I posted some screenshots showing a test I did. I added a new metafunction called a MetaHeightField which is a function whose values are calculated from simple height field data.

    The reason this is cool, is that in areas that only contain this function, I can change my render code from a generic metaball renderer to a much faster height field renderer. So when I get it fully implemented you will get the speed of height fields plus the flexibility of metaballs.

    Thanks for all the suggestions everyone and please if anyone has more ideas post em here or email them to me! I love new ideas!

    The new screenshots are on my home page or you can jump directly to them:


    April 25, 2002, 08:51 AM

    There's an article about it on gamedev I think. I dunno whether it's any good though.


    April 25, 2002, 08:55 AM

    you advocate a system where people who are unpopular or say unpopular things should be removed from the system?

    what if you decide you don't like this post? you going to call for me to be banned?

    i'd prefer to see people like you banned, but i'd be a hypocrite to call for anyone to be banned, wouldn't i?


    April 25, 2002, 09:55 AM

    Or could it be that someone needs to adjust their monitor's horizontal and virtical phase and position? ;-)


    April 25, 2002, 10:00 AM

    Hey, how are you transitioning from one texture to another like that? Two passes?


    April 25, 2002, 10:06 AM

    One pass puts down all non alpha blended surfaces, then blending is enabled an any texture that was on top of other textures is blended into the scene. So at the most a triangle is rendered 3 times if it has 3 seperate textures merging at it. But usually just 1 pass or 2 pass. I haven't added multitexturing support, but when I do this should be very fast, most of the work could be done in 1 pass ( Geforce can do 2 Textures at a time which is usually what I need, while the ATI can do 3, which will also help). Also when I add detail textures this will possibly double the passes for nearby meshes.


    April 25, 2002, 11:10 AM

    Is there any delay? Does the LOD change frequently or does it take a few seconds for each LOD change? If not, I wonder why it runs smooth on yours and not on any other windows machine . .. hmmm . . . , You must have that SET RUN_SMOOTHLY=true flag turned on in your system.ini file.


    April 25, 2002, 02:32 PM

    Last time you posted you had ditched the idea of using textures, and you were using differetn coloured triangles. Now you have not only brought them back but starting merging them together!

    They look nice, btw, but what projection are you using to avoid stretching them? They _seem_ to be coping with, for example, an arbitrary cave structure, without getting mismatched edges, and I never could think of a way of doing that that didn't involve long streaky patches in awkward spots . . .

    The best I ever came up with, in fact, was 3 textures, one projected along each major axis, and blended together, and you already said you aren't doing that ;)

    Sniper BoB

    April 25, 2002, 02:37 PM

    Sick! I love it!

    Great work, and so fast to! Can't wait to see the finished improvements and for you to solve that little threading problem.

    Gook Luck


    April 25, 2002, 04:17 PM

    woops, yeah I go back and forth on ideas, and while previously I found a way to generate texture coordinates for arbitrary meshes, I've decided it was just too processor intensive to work with (actuallyit wasn't that slow, but it had some quality issues).

    Believe it or not, but I'm using the 3 Texture projected along each major axis now. It was easy to implement, but I think I'm going to change this and move to cube mapping where supported by hardware. I'll probably just give you the choice of mappings. Right now I support planer projection or what I call cross project (3 texture on each major axis).

    It looks good for most textures.


    April 25, 2002, 04:21 PM

    The simple version was easy to implement and looks pretty good (If you've looked at my screenshots I took this morning). The design of my app allows me to plug in new meta functoins easily so I just wrote a metafunction that is defined by a height map. I've got a lot of work to do, but hopefully I'll have a new version on my web page in a few weeks.

    I've gotten so many ideas from peoples responses on flipcode, I'm gonna have a lot of work to do (I like having stuff to do!). If you get any more ideas please email em to me!!!


    April 27, 2002, 12:48 PM

    Runs alright on my computer. Crashed the 3rd time I closed it, nothing major. My system didn't hang at all. I turned of FSAA and put the res down to 640 and no speed difference. Must not be fill rate limited.

    My system (laptop):

    Pentium III 1GHz
    256MB RAM
    nVidia Geforce2 GO
    WinXP Professional


    April 27, 2002, 01:59 PM

    Very cool, I've been wanting to get a laptop with a 2GO on it. Yeah, the basic maps aren't fill rate limited (yet!).

    Also, I have a frame rate limiter, anything above 30fps and sleeps (this is so that the background thread can do more processing)

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