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


Submitted by Emmanuel ICART., posted on November 24, 2000




Image Description, by Emmanuel ICART.



Greetings, here is my IOTD submission. These pictures show my "work-in-progress" in Voxel rendering & manipulation methods.

The first 3 pictures show my heightfield renderer. Nothing really special compared to other voxel-based renderers, except that you can see my LiquidMorph algorithm in action. This algorithm simulates real-time fluid flowing over landscape areas. The first 2 pictures show what happens after I put a "Water ball" on the top of the mountain. LiquidMorph is based on a very basic concept of fluid dynamics, but is quite CPU-intensive (the screenshots here run at 17-18 FPS on my Celeron 433). The drawback of this algorithm is that the flowing process is a bit slow compared to real water flowing, but it is quite suitable for lava flowing. And the good point is that it is not limited to a particular area of the Heightfield, LiquiMorph acts on the whole landscape. So if you dig into the mountain, it can automaticaly initiate a flowing process.

The last picture shows my real-voxel rendering engine, ie 3D-sprite rendering algorithm. It is a basic ray-tracing algorithm, without any optimisation of the voxel data structure, so it is a bit slow (10 FPS at 320x240). But it allows realtime sclupting and painting on the shape.

The heightfield renderer will be used as a basis for my next game, probably a kind of 3D-Worms (where water kills !!). It will be a freeware Delphi Open-Source project, so if you are interested in this project please let me know.

Emmanuel ICART.


[prev]
Image of the Day Gallery
www.flipcode.com

[next]

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

November 24, 2000, 04:26 PM

Wow. I love the idea of using fluid dynamics in a game. Some sort of water version of "lemmings" would be cool, i.e. water would start flowing somewhere on the landscape, and you would have to guide it to a certain point by realtime "digging", whilst avoiding little villages from drowning or something. Could be a vulcano too.

 
Avulsion

November 24, 2000, 04:42 PM

Very cool, I love the idea of realtime water simulation. The game idea sounds great also. Keep up the good work!

 
Slade

November 24, 2000, 05:49 PM

Great Idea How about a god game drown people and stuff

 
Squint

November 24, 2000, 08:40 PM

There was such a thing. (2D on the Acorn Archimedes, ages ago)
Came out not long after lemmings (coincidence, eh?)

Don't remember the water flowing very realisitically, mind you ;)

 
DirtyPunk

November 24, 2000, 10:04 PM

What resolution is the voxel set in the true voxel tracer? And are you using trilerping on it?

 
malkia/eastern.analog

November 24, 2000, 11:06 PM

can we see a demo? sources?
please...

 
Kevin

November 25, 2000, 02:33 AM

Wow, really nice. I've been working on voxel stuff for some time. I'd really like to see a demo of your voxel object renderer. Please.

Kevin

 
Emmanuel ICART

November 25, 2000, 05:06 AM

Thanks for all your comments !

I've juste uploaded the true voxel source + exe on my web site, you can download it directly at

http://momorprods.homepage.com/tracy.zip (108 Kb)

It's a really basic Delphi2 project, just to test the rendering algorithm. Easily portable to C/C++ or Java.

DirtyPunk, the Voxel structure is a 128x128x128 shape.

I really thank you for all game ideas about the water feature. I'll very soon upload the heightfield engine
onto my web site (which has just been improved to support bilinear filtering and realtime shadows).

 
Emmanuel ICART

November 25, 2000, 05:25 AM

Oups, I forgot to mention that I also put a demo of the heightfield engine with water in action on
my site:

http://momorprods.homepage.com/heightfield.zip (500 Kb)

At first start, it will take a quite long time to generate a palette optimization file in the maps sub-folder.

If the rendering is too slow, you can modify the parameters in the config menu.

To dig the landscape, use the left mouse button.
To add a "water ball", use the right mouse button.

I hope you'll like it.

Emmanuel.

 
shrike

November 25, 2000, 06:40 AM

It would be cool if the water was able to erode the terrain.

 
malkia/eastern.analog

November 25, 2000, 06:45 AM

I've seen your raycast (I've used to be pascal programmer time ago - but i understand everything perfectly from your source!!)

I have an idea for speeding up the voxel caster,
but it requires preprocessing (which will stop eventually
doing some cool effects). The idea is following find
for each empty voxel what is the maximum sphere which can
be positioned on this voxel with maximum radius without
or nearly touching non-empty voxel. So you have for each
voxel one more byte for radius, and then you can skip not
one but many voxels (you skip the radius actually).

The offline process can be made using some distance
transform (Dave Eberly www.magic-software.com have some
code written). It's for 2D but can be adjusted and for
3D.

I'll pick your code and transfer to C and later to
pentium 3 assembler.

Thanx for the source!

 
James Matthews

November 25, 2000, 06:53 AM

Damn, that's really neat. It is something like dynamic fluids that games need to do some really cool stuff. For example, those areas in HalfLife where water drained out of the rooms really didn't look realistic, kinda killing the atmosphere of the game.

Running water, lava, whatever could create some kick-ass effects. Is this work pretty much unique to you, or are their papers on it?

I just finished downloading the demo - that is really sweet. I get a very decent framerate (PIII-933, 256 RAM, GeForce256 AGP 32Mb - so I suppose I would). You should work on having the surrounding moat move as well. If you dig by the waterfront, the water stays there.

That IR effect is neat too. Hey, I'm impressed :)

James.

 
remo

November 25, 2000, 06:59 AM

talking about a lemmings with water dynamics, if you want to see this sort of idea in practice, have a look at Clonk Planet (link). This game is similar to lemmings in some ways, but it involves building and fighting too. The fluid dynamics in it work well, and are an interesting part of the game, though it can get annoying when your clonks drown.

 
Emmanuel ICART

November 25, 2000, 08:25 AM

Hi again,

Shrike: That would be possible ...

Malkia: You are right, I saw a paper about this kind of data
optimization, but I was simply too lazy to implement it !!!
Moreover, I think this kind of structure could still allow
realtime sculpting ...
Tell me if you have a faster algo !!!

James: I thought about this algorithm about 3 years ago, but at this
time it did not provide very good results (lack of CPU power ).
I've never seen any paper about this, but to be honnest, it
is really a simple algorithm (the coding takes about 20 lines of pascal code !!!).

 
malkia/eastern.analog

November 25, 2000, 11:10 AM

a search on www.google.com

"volume" "distance transform"

should lead to what we need!

I found names like BORGEFORS (which I remmember time
ago reading bout this stuff - but can't rememmber
where I was reading - now back seeing your source
I'll try to find it again - I was lazy to code the
part you've done - i've done the other one but for
2D).

Nearly the same algorithm can be used for raycasting
just of heightfields, but instead of sphere one must
use inverted cones, each cone start vertex must be
located at each height field cell and to be with maximum
angle. By this way one can accelerate the raycasting

this is called "Height distributional distance
transform methods for height field ray tracing"

http://dev.acm.org/pubs/citations/journals/tog/1994-13-4/p376-paglieroni/

i'll continue my search - and probably will end
with some source (while trying to implement some
vertex buffers on DirectX8)

 
malkia/eastern.analog

November 25, 2000, 11:43 AM

it seems there are a lot of papers,
but one I found (now printing)
talks something about using this SPHERES
and doing ANTIALIASING at the same time
using them.

This have to be something very interresing

"Sphere Tracing: Simple Robust Antialiased Ren-
dering of Distance-Based Implicit Surfaces (1993)"

http://citeseer.nj.nec.com/hart93sphere.html

 
malkia/eastern.analog

November 25, 2000, 12:54 PM

further research points me to famous
KUIM library (i really forgot about it)

Emmanuel, take a look at

http://www.cim.mcgill.ca/~sasha/Web400/report.htm

and the bottom of the page are two sources,
one is for doing 3D Distant Transform, or
Volume Distant Transform

there is listed and the KUIM library

 
Emmanuel ICART

November 25, 2000, 01:44 PM

Thanks Malkia, I'll take a look at this.

 
Lourens Veen

November 25, 2000, 04:20 PM

Hey, great to see that there are more people doing voxels outside of the medical imaging world. Has anyone thought about compression yet? 128x128x128 greyscale yields 2MB of data, which is quite manageable, but 256x256x256 RGBA is 64MB already, not to mention larger datasets. I'm currently working on Haar-wavelet compression, which yields some interesting things like a partially precalculated volume gradient and octree-raycasting possibilities. Fractal compression is also in the picture.

Anyway, it's all in a very early stage and it's probably going to end up halfway done like all my projects, but still :-)

 
Andrew Cox

November 26, 2000, 12:57 AM

Hi Lourens,

yesterday I came across a couple of papers on Fractal Volume compression here: http://graphics.cs.uiuc.edu/~jch/papers/papers.html

I haven't read them yet myself but I thought I'd pass on the link.

My own voxel modeling tool ( http://www.users.globalnet.co.uk/~acox/Cavernosa/index.html ) uses a hierarchical representation of a binary voxel grid to allow grids up to 16'777'216 on a side and I am happy with how that approach has worked out.

Andrew

 
Mark Friedenbach

November 26, 2000, 02:54 AM

Lourens - Well, you can store voxel information within an octree (or quadtree, depending on your needs), thus saving storage space for large open areas. This should reduce the amount of space required to store voxel data dramatically.

 
Lourens Veen

November 26, 2000, 07:50 AM

Andrew: Looks interesting, I'll read it soon if I can find the time.

Mark: yeah, I did that some time ago but as complexity increases you start saving less. Plus there is a the problem of having to store a pointer to each block, which can amount to a lot of memory being wasted on pointers, you need to compensate for that. All in all it's a lot like a 3d version of RLE. I think it's nice if you have a volume with values that are indices into an array of materials (since they have a great local coherence) but if you're just doing ARGB values then it's not much use I think, since they're likely to vary slightly from one voxel to the next.

 
Lourens Veen

November 26, 2000, 07:56 AM

Oh and Andrew: Cavernosa looks nice, but the resolution of the models is still very low. How much memory would a 16,777,216^3 volume take? And is it thus only a theoretical number?

 
Andrew Cox

November 26, 2000, 04:13 PM

Lourens,

about the looking nice comment, no it doesn't! I only stuck it up on the web because I didn't think I would have time to work on it for a while and I heard that the Python API of the free modeling package it optionaly acts as a plugin for ( www.blender.nl (Game Engine, polygons, nurbs, metaballs, other modeling stuff, rendering, animation, post-processing, ...check it out)) was going to be replaced soon just as I had written a long GUI script for it.

The 16'777'216 figure is not theoretical. Press '8' then 'u' (might be 'i' :-) ) you now have a full resolution grid to explore. You could leave a book resting on your mouse left button and something else on the 'v' key and go out to the shops. When you came back, you would find either a long trail of set voxels still being generated or your machine had run out of memory (but the camera should still be flying out into space). Performance should bog down however as there are a couple of hash maps in the implementation which do not yet have their tables resized.

Memory requirements increase approximately with surface area of the generated mesh and a grid which consisted of alternating solid/clear voxels would take around 20% more memory than a simple 3d array by my calculations. That is the very worst case. The .vox files saved by Cavernosa are small and show the typical space costs of the grid implementation.

The resolution of the models realy has to be low for real-time polygonisation as a volume of (say) 256*256*256 has an awful lot of voxels to visit every frame and results in a load of polygons too. The intended eventual application of Cavernosa is the rapid modeling of (ahem) cave-like environments where the whole environment (like: a cave system) would be much larger than the portion displayed at any one time and the polygons would be much larger than is usual for volume viz with marching cubes type algos. Check out the voxel demo on Stan Melax' homepage for an idea of what I am aiming for (but as a modeling tool and without the 128*128*16 grid limitation). It is here: http://www.cs.ualberta.ca/~melax/


Andrew

 
Lourens Veen

November 27, 2000, 11:36 AM

or your machine had run out of memory
The problem is that you run out of memory. If you made that 3d checkerboard pattern you'd have 5.7*10^21 voxels, which at the modest rate of 1 byte/voxel would be 6 billion terabyte of data. I don't know about you, but I don't have that much RAM :-). Ofcourse that's a worst-case scenario, but say that you have the (huge) compression ratio of 1:1000. Then you'd still have 4 million terabyte of data
I'm not trying to burn down your program, as I said I think it's pretty good. But what I wanted to make clear was that if you have a complex world then you have a huge amount of data. And that's a problem.

Those videos look cool, especially if you imagine some Phong shading and bumpmapping along with them. Could make for a very cool cave game thingy.

What I want to do with voxels is create more detailed worlds, in much the same way a bitmap image stores details much more efficiently than a vector representation of the same image, as long as it is complex enough. I realize that the trade-off point between a vector representation and a voxel representation is very likely to lie a fair bit beyond the capacity of today's hardware, but I'm doing this for fun so what the heck :-)

 
Emmanuel ICART

November 27, 2000, 04:40 PM

>> What I want to do with voxels is create more detailed worlds, in
>> much the same way a bitmap image stores details much more
>> efficiently than a vector representation of the same image, as
>> long as it is complex enough. I realize that the trade-off point
>> between a vector representation and a voxel representation is very
>> likely to lie a fair bit beyond the capacity of today's hardware,
>> but I'm doing this for fun so what the heck :-)

I perfectly agree with you, and I think that a kind of voxel tiling
system would allow such possibilities for a game's purposes. A bit
like we used to create large scrolling areas with some tiny bitmap
tiles a few years ago ... But this would lost the attractive feature
of being able to dig, erode, or paint the world.

 
Andrew Cox

November 27, 2000, 09:52 PM

>I perfectly agree with you, and I think that a kind of voxel tiling
>system would allow such possibilities for a game's purposes. A bit
>like we used to create large scrolling areas with some tiny bitmap
>tiles a few years ago ... But this would lost the attractive feature
>of being able to dig, erode, or paint the world.

About five years ago I had a whole scheme for an adaptive (as in less than one ray per pixel) ray-caster of tiled voxels worked out. I was pretty proud of my dweeby little self back then for working out that raycasting would win out over the standard pipeline at some point when screen resolution stopped increasing and scene complexity kept going. Anyway, it didn't get very far but left me susceptible when I came across a voxel related project this year. I still want to get back to direct rendering of true voxels at some point.

Andrew

 
This thread contains 27 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.