langston@omega.Central.Sun.COM (Jim Langston Sun ASE - MidWest ) (04/25/91)
Hi , Has anyone heard of the above mentioned ... It is my understanding that it done by GE Research, it is suppose to be a package, that will develop geometry for a Voxel. Anyone ????
rmr@tove.cs.umd.edu (Randy M. Rohrer) (04/25/91)
In article <3871@texsun.Central.Sun.COM> langston@omega.Central.Sun.COM (Jim Langston Sun ASE - MidWest ) writes: > >Has anyone heard of the above mentioned ... > >It is my understanding that it done by GE Research, >it is suppose to be a package, that will develop >geometry for a Voxel. > > Marching Cubes is a 3D iso-surface construction algorithm for volumetric data. Given a desired threshold, the algorithm constructs a representative iso-surface for that threshold by comparing adjacent slice pairs and interpolating between the sampled data. It produces a list of triangles (and normals) that represent the iso-surface. This list of triangles can then be passed on to any polygonal renderer for shaded display. Ref: "Marching Cubes: A High Resolution 3d Surface Construction Algorithm", William Lorenson and Harvey E. Cline, Computer Graphics (Proceedings of SIGGRAPH '87), Vol. 21, No. 4, July 1987, pp. 163 - 169. This technique for visualization is often called "surface rendering" as opposed to "volume rendering". Note that there is a companion algorithm called Dividing Cubes that generates 3D points to represent the iso-surface (this is mentioned in the above paper). Marching Cubes is pretty straight-forward and easy to understand and implement. Someone posted a public domain version last year in comp.graphics. The Ape system contains a module called "onion" that uses this algorithm. Hope this helps, Randy Rohrer
foo@titan.rice.edu (Mark Hall) (04/25/91)
In article <3871@texsun.Central.Sun.COM> langston@omega.Central.Sun.COM (Jim Langston Sun ASE - MidWest ) writes: ) )It is my understanding that it done by GE Research, )it is suppose to be a package, that will develop )geometry for a Voxel. ) @Article{LC:MCubes, author = "W. Lorenson and H. Cline", title = "Marching Cubes: A High Resolution 3D Surface Construction Algorithm", journal = siggraph, year = 1987, month = "August", volume = 21, number = 4, pages = "163--169" } - mark
stam@dgp.toronto.edu (Jos Stam) (04/25/91)
Talking about "marching cubes"... Does anyone had the same problem as me (and solved it !). I use the algorithm to display implicit surfaces (i.e. (x,y,z) such that F(x,y,z)=0). The problem I have is that my surfaces have "holes", i.e., certain triangles are not generated. This reminds me of problems I had when implementing "interval arithmetic"... Anyone has solved this, or is this just something one has to live with. cheers, Jos
payne@hyperion.loni.ucla.edu (Bradley Payne) (04/26/91)
I've also encountered the hole problem with marching cubes. This is caused by an ambiguous case in the cube classification table. One possible fix is to decompose each cube into tetrahedra (there are methods which give 5 or 6 per cube), and then tile the tetrahedra, which don't have any ambiguous cases. This does tend to give lumpier surfaces than marching cubes. For details, see Payne&Toga,"Surface Mapping Brain Function on 3D Models", CG&A vol 10 no 5, Sept 1990. I've seen mention of a tetrahedral approach in Siggraph course notes by Perlin, but I can't find the reference at the moment. Anybody patch this at the cube level? - Brad payne@loni.ucla.edu
favre@seas.gwu.edu (Jean M. Favre) (04/26/91)
In article <2551@lee.SEAS.UCLA.EDU> payne@hyperion.loni.ucla.edu (Bradley Payne) writes: > > >I've also encountered the hole problem with marching cubes. This is caused >by an ambiguous case in the cube classification table... . >Anybody patch this at the cube level? > > - Brad > payne@loni.ucla.edu I think that Alyn Rockwood has a "robust solution,...,handling singularities without introducing spurious rendering artifacts" (I quote from his abstract) in "Accurate Display of Tensor Product Isosurfaces", in the proceedings of Visualization 1990, San Francisco, pp.353-360. -- Jean M. Favre. EE&CS Dept. The George Washington University (202) 994 5917 favre@seas.gwu.edu
liberte@ncsa.uiuc.edu (Daniel LaLiberte) (04/26/91)
I implemented a marching cubes algorithm which decomposes each cube into 5 tetrahedrons. As Bradley Payne says, there are no ambiguities. My implementation is public domain (but I dont know whether it is different enough from the patented marching cubes algorithm to not infringe). You can get the code from NCSA DataSlice by anonymous ftp to ftp.ncsa.uiuc.edu. Dan LaLiberte National Center for Supercomputing Applications liberte@ncsa.uiuc.edu
slamont@network.ucsd.edu (Steve Lamont) (04/28/91)
In article <2551@lee.SEAS.UCLA.EDU> payne@hyperion.loni.ucla.edu (Bradley Payne) writes: > > >I've also encountered the hole problem with marching cubes. This is caused >by an ambiguous case in the cube classification table. One possible fix is >to decompose each cube into tetrahedra (there are methods which give 5 or 6 >per cube), and then tile the tetrahedra, which don't have any ambiguous cases. >This does tend to give lumpier surfaces than marching cubes. The problem with tetrahedra is effectively the same as the problem with cubes, they can both produce surfaces with holes in them. If you play around with the tetrahedral algorithm, you'll see what I mean. This was a topic of some discussion at the San Diego Workshop on Volume Visualization back in November 1990 (proceedings in Computer Graphics, V 24, No. 5). Jane Wilhelms and Allen Van Gelder suggested a fairly robust solution which essentially involves a surface fit in the ambiguous case (Topological considerations in isosurface generation [extended abstract]). A reasonable 'cheat' which may not work in all cases but works in the cases that I've encountered, is to use the averaging technique discussed in G. Wyvill, C. Mc Pheeters, and B. Wyvill, Data structures for soft objects, published in "The Visual Computer," 2(4):227-234, August 1986. spl (the p stands for polygons `r' me) -- Steve Lamont, SciViGuy -- (408) 646-2752 -- a guest at network.ucsd.edu -- NPS Confuser Center / Code 51 / Naval Postgraduate School / Monterey, CA 93943 "The only way to deal with exploiters is to terrorize the bastards." - The late Congressmember Phillip Burton
yamo@nas.nasa.gov (Michael Yamasaki) (04/30/91)
In article <5266@network.ucsd.edu> slamont@network.ucsd.edu (Steve Lamont) writes: > >The problem with tetrahedra is effectively the same as the problem with cubes, >they can both produce surfaces with holes in them. If you play around with >the tetrahedral algorithm, you'll see what I mean. > Uh, gee, I've played around with them quite a bit and still haven't run into that ambiguous case. And since there are only 2 real cases... + + /|\ /|\ - | - + | - \|/ \|/ - - There is a bit of a trick to decomposing the cubes into tetrahedra properly to avoid holes. If you are decomposing the cubes into 5 tetrahedra there are two possible outcomes (mirror symmetry). These two decompositions should alternate such that each laterally adjacent cube is a mirror image. In this way the edges of the tetrahedra "line up". Otherwise the edges cross and different values are used for the interpolations. In which case the surfaces are riddled with holes. Adjacent cubes should be like this: --------- _______ / /|\ /|\ / / | \ / | \ /________/ | \ / | \ \ \ | / \ | / \ \ | / \ | / \________\|/ \|/______ Not like this: --------- _______ / /|\ / \ / / | \ / \ /________/ | \ /_____\ \ \ | / \ / \ \ | / \ / \________\|/ \ /______ I would imagine there is a similar pattern for decomposing the cubes into 6 tetrahedra though I haven't worked with this method. -Yamo- yamo@wk209.nas.nasa.gov yamo@amelia.nas.nasa.gov {ncar, decwrl, hplabs, uunet}!ames!amelia!yamo
nataraja@hplabs.hpl.hp.com (Balas Natarajan) (05/01/91)
in regard to marching cubes and holes; there are two possible methods of fixing the holes. Method (1): use an ad hoc but consistent treatment of the ambiguities. this eliminates the holes, but can result in topologies that are different from the topology of the true isosurface of the trilinear interpolant of the data. an unfortunate side effect of the latter is that refining the data can cause drastic changes in topology. Method (2): analyze the true topology of the isosurface of the trilinear interpolant and report this topology. this eliminates the holes, and the refinement problem. the challenge here is to still report a small number of polygons for each voxel, unlike the method of "dividing cubes"; I have implementations of both methods. In method (1) I use a slight and "greedy" modification of the marching cubes case table. Method (2) involves a topological analysis of the trilinear interpolant in each voxel. My implementation of method (2) runs about 10% slower than marching cubes on the sample data i checked it on. --bkn
jd@pogo.WV.TEK.COM (John Dalrymple) (05/04/91)
If you have cycles to burn (:-) you may want to decompose a cube-like data
cell as follows:
Average the spatial coordinates of the 4 vertices of each face to
yield an interior vertex on each face. Average the data values
at the face vertices and assign the result to this "face-interior
vertex."
Average the spatial coordinates of all 8 vertices of the cell
to yield a vertex interior to the cell. Average all 8 cell-vertex
data values and assign the result to this "cell-interior vertex."
Tessellate the cell into 24 tetrahedra by connecting the
cell-interior vertex to all the other vertices, and by
connecting each face-interior vertex to its corresponding face
vertices.
Each tessellated face looks like this:
*-----*
|\ /|
| \ / |
| # | * = original vertex
| / \ | # = averaged face-interior vertex
|/ \|
*-----*
This gives a better polyhedral approximation to the isosurface inside
the cell than does a tessellation into five tetrahedra, and is also
independent of the cell's position in the overall mesh.
JD