PDA

View Full Version : Marching Cubes

Satanic Dogus
09-21-2001, 12:05 PM
I have to create a surface, actually an electron density map. I'm currently using the marching cubes alg., but I really don't get it. I would like to speed up the rendering, and since it's only a wire frame mesh, shouldn't it be fast? Also, how do I make the surface a translucent solid surface?
Thanks!

09-22-2001, 02:24 AM
Well the drawing is not the bottleneck...

Just think about the marchingcubes algo... it is a O(N^3) function for creating the triangles... So if you have a width of 100 on the cube for the its beeing executed 100^3 1000000 times. Thats gonna be pretty damn slow, dont ya think so?

Tone
09-23-2001, 09:49 AM
Also, if you have an Nvidia GeForce video card, drawing in wireframe is always going to be slower than drawing the same thing with polygons. I guess Nvidia did this so people would actually have a reason to buy their Quadro line of cards.

Satanic Dogus
09-23-2001, 01:52 PM
So what should I use to get a surface which renders really quick?
thanks!

ffish
09-23-2001, 04:12 PM
Perform marching cubes as a preprocessing step which outputs an array of triangles and an array of indices. Then use probably vertex_array_range to render them. That way your program takes a long time to load but minimal time to render (but you still have to watch your number of triangles - can be huge). Also look at various decimation algorithms for reducing triangle count. The two main methods are edge collapsing or vertex collapsing.

Hope that helps.

Bob
09-23-2001, 10:44 PM
A preprocessing step requires the field to be static. If it is, it a great way of dealing with the problem of trianglulation speed. If it's a dynamic field, preprocessing isn't going to work very well.

If it' is dynamic, you must retrianglulate the field every time. A way of doing this, can be to to a recursive triangulator, maybe using octtrees. I haven't looked much into this, but as far as I understand, this is not an easy task.

Satanic Dogus
09-24-2001, 01:15 PM
thanks ffish and bob!
Okay....when I load the electron density map, I can do a one time preprocessing step, which in fact I am kinda doing, then dump the results into a matrix, use a triangle reduction alg, then draw them?
That's what you're saying?
The density map doesn't change, but it's orientation in space does and the complexity of the map also changes as a userdefined variable, in the menu.

chrisATI
09-24-2001, 05:43 PM
Originally posted by Satanic Dogus:
thanks ffish and bob!
Okay....when I load the electron density map, I can do a one time preprocessing step, which in fact I am kinda doing, then dump the results into a matrix, use a triangle reduction alg, then draw them?
That's what you're saying?
The density map doesn't change, but it's orientation in space does and the complexity of the map also changes as a userdefined variable, in the menu.

This demo does not use the marching cubes algorithm but rather spherical shells... perhaps you may find it useful anyway.

ffish
09-24-2001, 05:55 PM
Satanic Dogus, you're on the right track. It doesn't matter if the orientation of the whole map changes, as long as the data you're marching on doesn't change. As I mentioned, fastest rendering will come from using VAR or ATI's new equivalent (forgot the name).

What do you mean by complexity of the map? If you mean number of triangles, that can be a user-defined choice, but be aware that the decimation algorithms are also resource intensive and probably won't work in real-time depending on the size of your data. The method I'd use is probably the same technique Hugues Hoppe uses. Search on google for his site at Microsoft Research. He's also done many SIGGRAPH papers if you can get old conference proceedings (they're online somewhere).

Out of interest, check out this site:
http://astronomy.swin.edu.au/pbourke/modelling/polygonise/

for some code and hints on marching cubes. One of the source code links at the top has a GLUT application (with source) that demonstrates some simple marching cubes.

One last thing, be aware that the marching cubes algorithm is covered by a patent held by General Electric so you probably should investigate that if you're doing this for a commercial app.

Hope that helps.

Satanic Dogus
09-27-2001, 01:13 PM
Thanks a bunch......

Okay...about the complexity....it's like a threshold....but yeah....you only have to calculate them once, and store them, and reconnect them differently to increase complexity....though I'm having some problems with clipping planes....

About triangle reduction...I'm drawing a blank..I've been snooping around looking for some info....but haven't been really successful.

Thanks!

ffish
09-27-2001, 08:38 PM
Originally posted by Satanic Dogus:
About triangle reduction...I'm drawing a blank..I've been snooping around looking for some info....but haven't been really successful.
Here's a coupla:
http://citeseer.nj.nec.com/schroeder92decimation.html http://citeseer.nj.nec.com/hoppe93mesh.html http://www.research.microsoft.com/~hoppe/

The citeseer links have paper downloads in the top right, plus heaps of links to other papers. Just look around a bit. Check out Hugues Hoppe's papers starting with Progressive Meshes (1993). He follows up on that with several others all in the same theme. These are the kinds of articles you find in SIGGRAPH proceedings, so if you can find a library with those, check them out. Most SIGGRAPH articles are available online somewhere though, you just have to do a bit of digging.

Hope that helps.

[This message has been edited by ffish (edited 09-27-2001).]

Satanic Dogus
10-09-2001, 09:46 AM
I hate sounding dumb, but where can I get source codes from?
Thankx

ffish
10-09-2001, 07:38 PM
Dunno, I would just write it out myself from reading the papers. I once did a vertex based decimation algorithm as a project with another guy, but I can't find it now, and it wasn't meant to be used with OpenGL anyway.

clunis_immensus
10-11-2001, 07:06 PM
Originally posted by Satanic Dogus:
I hate sounding dumb, but where can I get source codes from?
Thankx

VTK includes an implementation of Marching Cubes.