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


Submitted by Andrew Cox, posted on February 19, 2001




Image Description, by Andrew Cox



This is a picture of my volumetric sculpting tool Cavernosa in action. My work on it was sparked off by the voxel demo and paper released by Stan Melax of Bioware. His stuff is here. Since my goal in creating Cavernosa was to allow the modeling of expansive natural environments containing features such as caves that can't be represented by a heightmap, I've built it around a hierarchical voxel grid. This compressed representation allows grids of up to 2'097'152 x 2'097'152 x 2'097'152 voxels to be worked on.

Andrew


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

February 19, 2001, 03:02 PM

That's pretty wicked there. Very nice!

Ezra

 
z66831

February 19, 2001, 03:20 PM

Isn't there some sort of patent problem with using marching cubes like this? I haven't been to the Melax's tutorial in a while, but I remember him discussing that. Does anyone know of any alternatives for doing this type of spring mesh over voxels that's NOT encumbered?

-z

 
Squint

February 19, 2001, 04:44 PM

I am trying to make an engine that does things like that with 3D perlin noise ... its slightly irritating that someone just beat me to it, but maybe I can come up with a better texture ;)

Nice one, btw...

Now could someone tell me what marching cubes are please, coz if Im using those I am not going to be a happy bunny :/

 
Squint

February 19, 2001, 04:50 PM

Sorry, to clarify that: I've browsed down the paper you referenced and I'm using a similar but not identical technique ... the question should be "what precisely was patented?". Anyone know how to find out?

I would be nice to come up with an alternative that people can actually use!

 
MrSmiles121

February 19, 2001, 05:27 PM

I believe there's a bit about the marching cubes algorithm in the comp.graphics.algorithms newsgroup faq (sorry, can't remember the link, but it's easy to search for). That might help you out a little.

MrSmiles121

 
SigmundSEGV

February 19, 2001, 05:34 PM

VERY cool.

I've thought about trying to make something like this for awhile! One thing I wanted to be able to allow was deformation or alteration of the environment - such as blasting holes through walls or effectively making new tunnels in the cave system by kind of "eroding them with a blasting device." Is this something that the technique you're using could permit?

 
DirtyPunk

February 19, 2001, 05:54 PM

Looks good, but I bet that voxel size jumps dramatically when your sculpting gets complex - or if you fit the bounds of sculpt to the bounding box of your voxel set :)

Are you using a 3 colour octree or one of the more child per node representations?


 
Andrew Cox

February 19, 2001, 06:06 PM

There is a problem in that one of the two simultaneous originators went and patented it. I use the name Limit MCA since Melax does but as far as I am concerned, the tesselation is radicaly different and the letters MCA do not stand for Marching Cubes Algo. I'm also not sure precisely which part of the tesselation algo is called Marching Cubes, whether I even use it (never having tracked down the original two references) and how broad the patent is.

Anyway, I think the patent is fightable. Anyone hear about it being enforced ever?

Andrew

 
DirtyPunk

February 19, 2001, 06:08 PM

Well, this isn't 3d perlin noise - you couldn't get anywhere that level of compression on any sort of high detail noise - far too irregular. And you have still been beaten by many people may times on perlin noise in 3d. Most voxel compression techniques require fairly regular sets.

You would have to generate the noise analytically which would be virtually impossible to do realtime.

 
Andrew Cox

February 19, 2001, 06:08 PM

The checks in that texture line up with voxels when projected onto an axis perp plane which makes them useful when modeling. They also are a hard case for the mapping and blending algo and show up the distortion in mapping to a complex 3d surface (as oposed to a heightfield).

But yeah, it shouldn't be too hard to make something prettier :-).

Andrew

 
Andrew Cox

February 19, 2001, 06:12 PM

Yes, that is effectively what you do to model with Cavernosa. Once you have dug a little cave for yourself, you can fly towards one of it's walls and punch a hole in it. The mesh in that area will then spring into it's new shape over time.

I was originaly going to try to make a game out of this tech but it would have to be non-realistic since you can leave matter hanging in mid-air by cutting around it.

If you want to do something similar, you should definitely check out the paper by Stan. It will at least give you something to work from. I have a few other links as well I can pass on.

Andrew

 
Andrew Cox

February 19, 2001, 06:40 PM

Memory consumption stays in proportion to the surface area of the generated mesh. If you filled space with a lattice structure or similar, memory consumption would exceed that of an equivalently sized 3d bit-array by approx 20%. Doing that would require impractical artist effort for a grid of any size though so isn't ever going to happen (I wonder how big the grid would have to be before generating such a lattice would take more artist-hours than a human lifespan. Not that big I'd guess).

The voxel state of the outside of the grid is special-cased and stored as solid or clear in the file format to avoid generating a mesh around the outside of a solid grid. You're right that not doing so would lead to a fairly large mesh ;-).

I'm not using an octree at all. An octree would have 21 levels for the largest grid I can handle. Also, since I only store one bit per voxel, the data structure memory overheads would dominate.

My core data structure is based around several hash maps.

Andrew

 
The Wolf

February 19, 2001, 08:09 PM

very nice, excellent work, haven't seen much on this subject in a while.
Are you using an Octree for spacial partitioning? looks like it from the grid lines.

 
Andrew Cox

February 19, 2001, 09:21 PM

Thanks. I don't use an octree although I considered it when I started out. See this previous reply.

 
NinjaCross

February 20, 2001, 03:41 AM

Hey, really amazing work !!
Only al little thing... why did you chioce that texture ? it doesn't allow to see clearly all the particulars of the scene.

 
Qiller

February 20, 2001, 06:40 AM

I've did some research on MC patent some time ago (since I'm writing commercial project this is important to me). See this posting: metaballs algorithms

 
merak

February 21, 2001, 08:06 AM

Andrew, can you pass other links that you have? I mean, where we can find similar info. Thanks.

 
Andrew Cox

February 21, 2001, 10:05 AM

Stan's paper is the only source I have that is specifically about voxel-based deformable environments.

I did come across some work on volumetric sculpting which is interesting and involves a compression scheme that is worth reading about. Check out the paper Practical Volumetric Sculpting by Eric Ferley Marie-Paule Cani, and Jean-Dominique Gascuel.

There is lots of info on implicit surfaces that is relevent.

Paul Bourke has code for marching cubes and tetras and pyrimids:
http://www.swin.edu.au/astronomy/pbourke/
Brian Sharp's fluid demo has source:
http://www.gdmag.com/
Jeff Lander wrote at least one article on 'metagoop' which is at gamasutra.

There is also info in books that you might have:
Graphics Gems IV has a chapter on implicit surface polygonisation.
One of the few code listings in AART is a Marching Cubes implementation.

Andrew

 
Catfish

February 21, 2001, 05:57 PM

Hmmm....that's quite funky. What hardware do you have it running on? Similar engines that I've seen (about a year ago) were a lot blockier - that looks very smooth...

Catfish

 
Andrew Cox

February 21, 2001, 09:22 PM

Celeron@400 :-).

That's running through the SGI software OpenGL.

From your 'smooth' comment it sounds like you think the voxels are rendered directly. They are actualy used as the basis for a surface tessellation. There is a link to a paper in my description at the top of the page if you are interested.

Andrew

 
Squint

February 22, 2001, 03:30 PM

Well, this isn't 3d perlin noise - you couldn't get anywhere that level of compression on any sort of high detail noise - far too irregular.

Actually drawing 3D perlin noise would require a representation of 4D space. Im drawing a 3D shape which is calculated from it, and it probably could be compressed. I may try, if i can first prove that it works...

And you have still been beaten by many people may times on perlin noise in 3d. Most voxel compression techniques require fairly regular sets.

I am aware that i am not the first person to do perlin noise in 3D!
I need to put bigger smileys in , dont I, when I'm not being entireley serious?
;)
that better?

It's a very nice picture and the compression is very impressive. If it's ever open source I will be sure to try to learn from it. For now, I will be delighted if I can display a 100x100x100 grid!

Incedently, how do you light it? or dont you? There's no sensible way to do it like sunlight on a terrain and I havent thought of an alternative...

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