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 24, 2002, 01:03 PM

    First? Looks somekind of.... COOL !!!!!
    Good job!

    Headless Chicken

    April 24, 2002, 01:06 PM

    I've wanted to try this beauty out senc eI saw your last IOTD, I guess now I have the chance with a windows version. Gonna try it out tonight, nice work.


    April 24, 2002, 01:20 PM

    Sweet! I don't know much about Metaballs. I guess a trip to the bookstore or Google is in order. What do those here think of them, as opposed to splines?


    April 24, 2002, 01:23 PM

    Why compared to splines? Metaballs and splines have NOTHING in common apart from they both produces curvy stuff.


    April 24, 2002, 01:25 PM

    This looks really nice!
    I've implemented metaballs in my particle system (so you simply replace a particle with a metaball) so I'm very interested in what other applications there are for them.


    April 24, 2002, 02:10 PM


    My comment consists from following parts:


    "some people refered to it as green swiss cheese"
    "furry swiss cheese"

    NOTICED: strange love for cheese

    PART 2 (terrain)

    Every piece of rock can be terrain for ... bugs(not computer bugs;p). But for normal people its just piece of rock.
    I see few stones and I should call it terrain ?
    And hey... its not cheese. Its you shouldn't apply such texture for terrain.

    PART 3(odd structures)

    These structures are really odd

    PART 4 (downloads)

    Binary for linux is useless
    Binary for windows will crash (most likely)
    Source is useful

    PART 5 (longest project)

    congrats ... best project would sound better than longest

    PART 6 (question)

    What important feature shows two bottom objects ... I couldn't call it cheese or even stone. Its more like UFO


    April 24, 2002, 02:12 PM

    Your trees look like crap. And that doesn't even LOOK like a leopard! :-)

    Seriously though, that's a great concept! Very original thinking. And it has great applications that replace/simplify CSG.

    Good job!


    April 24, 2002, 02:37 PM

    Check out _Variational Implicit Splines_ by Greg Turk. You can use
    the thin-plate spline radial basis function to define an implicit
    spline which interpolates some given data.

    Sniper BoB

    April 24, 2002, 02:39 PM

    Extreamly cool!

    Unfortunatly it ran very slowly on my machine, the little star/sparkle things that show a pending transformation seemed to take anywhere from 20 to 60 seconds to calculate. That is far from real-time and somewhat spuratic. Excellent work on this inventive technquie though!


    My machine:
    AMD 1600xp+
    512 DDRam
    Geforce 3
    Windows XP Home


    April 24, 2002, 02:49 PM

    just shut up.
    because of people like you, i am getting tired of reading flipcode.

    btw, the iotd is great and it is a very different approach to terrain rendering, never seen anything like it. very innovative, congrats!


    April 24, 2002, 02:50 PM

    I have some issues with threading under windows I'm trying to figure out. On a regular sized mesh, I can do an edit under a second. [AMD 1.2 Ghz, 512 ram, GF3 Ti 200, Linux].

    The problem seems to be the way windows schedules theads. For some reason threads dont' get scheduled very often, but when they do they run for longer than under linux.. Notice in the windows version the LOD changes seem to come every once and awhile, and not smoothly. LOD get's calculated every time the thread runs thru it's loop.

    When I run under Linux it's extremely smooth, even on a slower machine. I can do very fast edits under linux on a Pentium III 866 with TNT2, but when I boot into XP it get's about 10 times slower.

    Any sugestions on Windows thread program would be appreciated.


    April 24, 2002, 02:51 PM

    I'll try to work on those trees :)


    April 24, 2002, 02:57 PM

    1) - Actually I don't like cheese much, it's okay, but it just seemed lot's of my models looked like blobby cheese or something like that. Just lots of metaballs stuck in random positions.

    2) - I'm not sure what you are trying to say here. . . sorry.

    3) - I'm not an artist, that's why the odd structures, they were simple to make.

    4) - Binary's are usefull for people who don't want to compile it, or don't know how, or don't want to install the development packages. Windows binary will probably crash, I only spent 3 hours porting the thing, but hey!, what app doesn't crash in windows? Hope you enjoy the source!

    5) - I guess it is my best project, but the fact that I've stuck with it so long probably made it my best project. So best and longest go together.

    6) - Again, I'm confused by this question, please explain in more detail.


    April 24, 2002, 03:05 PM

    It looks really cool ...

    Huh ... I don't know much about MetaBalls ... But, because it's really smooth ... Doesn't it take much memory ?(sorry for this question ...)

    But ... It's really odd ... Love it !!!


    April 24, 2002, 03:08 PM

    Looks very cool :)
    And the last feature is definetly the best :D

    Ben gosney.


    April 24, 2002, 03:10 PM

    thanx for response
    I mean that texture is not quite good for terrain


    April 24, 2002, 03:10 PM

    Here is an explanation about Metaballs:

    now about memory, Metaballs themselves don't take up much memory. For a simple ball you need a vector that is it's posiiton, a float that is the field strength, and a material identifier (in my case). Now depending on what resolution mesh you extract from them, the mesh can take a lot of memory. When I save a map, I save all the meshes I have calced (and cached), even the non-visible ones (LOD that aren't being displayed at that moment), so this makes my map files large. If I can get the mesh generation speed faster I can just recalc the mesh whenever I need it and only have the currently visible mesh calculated, so it won't take too much memory (still a lot more than the metaball data that the mesh was constructed from).

    On average a triangle takes about 50-100 bytes, a metaball takes about 20-50 bytes - hope that helps a bit.


    April 24, 2002, 03:11 PM

    ahh, yes I totally agree, but I thought it looked weird. I thought the mesh looked weird (not really terrain) so I used them together. I wasn't going for realism in this IOTD though. Maybe later I'll try for something more realistic.


    April 24, 2002, 03:11 PM

    i've got a question. in a situation with many, maybe hundreds of craters created by bomb impacts, each time a new metaball has to be added. won't it get slower and slower over time, even if the triangle count doesn't increase? in such a case, may be boolean operations could be faster, maybe i'm wrong...


    April 24, 2002, 03:12 PM

    Please do, they're at a completely wrong altitude for their botanical family. :-)

    I really like the possibilities you have here for deformable/interactive geometry. I'm very interested in seing what you'll be able to accomplish once your geometry deformation is completely real-time! That will be very interesting, indeed! However, I guess the relaly complicated issue at that point for a real-world gaming point of view would be how to handle the texturing. If you blow a hole in a grassy hill, the interior needs to look like dirt. Or if you blow a hole in a wall, the interior of the wall would need to look like brick/cement/whatever. But I'm sure you've got some ideas for that.


    April 24, 2002, 03:14 PM

    I need a better structure to store my metaball information, now I'm just using a list (yuck!), need some type of space partitioning structure so I can search thru and narrow down the metaballs that influence a given area of space.

    I also hope to add a simplification step that will look at the available metaballs and see if it can replace groups of metaballs with a large metaball that affects nearly the same area. That way the number of metaballs in a given area doesn't go crazy.

    For example a metaball at (0,0) with field strength 10, and one at (0,1) with field strength 10, might be replaced with one at (0,.5) with field strength 20 or so . . . not sure about that but you get my point right?

    Sniper BoB

    April 24, 2002, 03:15 PM

    I believe you need to create the threads within the same application space. (Or something like that, maybe I am thinking Application Domains from .NET) Then make sure that you change the thread priorities to high or some other setting. Look into that.

    Lastly, if your calculation thread works iteratively you can figure out some way to loop while the function has been running for less than X milliseconds. When that time is exceeded, stop iterating and complete the calculations the next frame or over the next few frames.



    April 24, 2002, 03:16 PM

    Yeah, I hear ya! I've had similar problems with threading in Windows. My problem has been that if I set the thread priority to one setting, it eats up all the CPU and leaves too little to other processes. And then if I lower the thread priority just a single notch, suddenly, it C...R...A...W...L...S but the other thread runs smoothly. Since there's no in-between priority setting, I'm at a loss.


    April 24, 2002, 03:20 PM

    i'm not very into metaballs rendering anyway.. but maybe it would be possible to check if a metaball changes the surface of your mesh, and if it doesnt, you throw it away. this way, you would not have any negative metaballs hanging in empty air and doing nothing besides wasting processing time.

    Sniper BoB

    April 24, 2002, 03:21 PM

    That won't work because you will have to create a larger meatball to encapsolate the smaller ones, that would result in loss of detail on the outtershape and make it a smooth sphere. The only removals you can do are the removals of meatballs that are completely contained within another meatball. Maybe you can order your list of meatballs by size and then check the current meatball against those of greater size to see if the meatball is entirely contained. If it is, remove it.


    Sniper BoB

    April 24, 2002, 03:23 PM

    the hanging in empty air 1 isnt what "that wont work" replys to... i was talking about the combinding meat balls


    April 24, 2002, 03:27 PM

    Are you using a metaball (MEATball, haha) function that extends to infinity? There are plenty of good ones that go to zero at a defined radius, thus allowing you to ignore their influence on most of the grid. It seems like you could speed up calculations by only recalculating the area affected by the new metaball.


    April 24, 2002, 03:31 PM

    The linux binary doesn't run on my debian system. When I attempt to execute it I get the following.

    geek relocation error: ./geek: undefined symbol: __dynamic_cast_2

    The Makefiles in the source code distribution are including Mandrake header files

    make: *** No rule to make target '/usr/lib/gcc-lib/i586-mandrake-linux-gnu/2.96/include/stddef.h', needed by 'demo/main.o'. Stop.

    Would it be possible to set up an autoconf script so it will be easier to build on other distributions?


    I look forward to trying out the demo.

    Sniper BoB

    April 24, 2002, 03:34 PM

    hahaha yea i read it meatball the first time....and it was to much thought to call it metaball after i laughed my ass off when i realized i screwed it up :-P my mind gets stuck on shit like that, i have been known to spell variable names wrong just so i dont have to compile and have it come up with errors like "Symbol 'Grafics' undefined"


    Just a little crazyness from your friend


    April 24, 2002, 03:38 PM

    extra ordinary elite mega monsgter IOTD, this is like NEW stuff.. Tho ive seen it running on an Amiga 1230 for loots of years ago .. like almost 10 years ago ;D

    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.