Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!ucsd!swrinde!mips!sgi!shinobu!fido.wpd.sgi.com!texas.asd.sgi.com!robert
From: robert@texas.asd.sgi.com (Robert Skinner)
Newsgroups: comp.graphics.visualization
Subject: Re: surface rendering of fuzzy cloud
Message-ID: <1991Apr30.182711.2223@fido.wpd.sgi.com>
Date: 30 Apr 91 18:27:11 GMT
References: <2594@amethyst.math.arizona.edu> <73521@eerie.acsu.Buffalo.EDU>
Sender: news@fido.wpd.sgi.com (Usenet News Admin)
Reply-To: robert@sgi.com
Distribution: usa
Organization: Silicon Graphics Inc., Advanced Systems Division
Lines: 67

In article <73521@eerie.acsu.Buffalo.EDU>, okeefe@cs.Buffalo.EDU (Paul O'Keefe) writes:
|> 
|> In article <2594@amethyst.math.arizona.edu>, winfree@.math.arizona.edu (Art Winfree) writes:
|> |> 
|> |> Does anybody know how to render the surface of a fuzzy 3D cloud of
|> |> data points? The "cloud" is actually supposed to be a 2D surface, but
|> |> the algorithm which generates it is not perfect, and typically
|> |> produces a sheet of points of variable thickness. In places, the
|> |> sheet is only 1 point thick.  We tried placing the cloud in a large
|> |> 3D array then hitting it with Marching Cubes-like surface finders,
|> |> but always with unsatisfactory results.  B-splining the surface points
|> |> was rejected because the points are totally unordered, and ordering
|> |> into rectangular array of control points is precluded by complex 
|> |> geometry of cloud.  Any suggestions?
|> |> 
|> |>       ATW
|> 
|> Mark LeVoy of UNC/Chapel Hill has an iso-value surface rendering algorithm
|> which is detailed in his widely cited article,
|> "The Display of Surfaces from Volume Data", IEEE CG&A, May 1988.
|> 
|> IMHO this algorithm is more suited than Marching Cubes for fuzzy surfaces,
|> however, it is slower.
|> 

For some time I've wanted to construct and visualize the surface of a
chaotic attractor, given an unordered list of points on the surface.

I've tried to do this using volume rendering techniques by first
converting the points into volume data.  I take the bounding box of the
points, then divide it into some number of 3D buckets.  If I count the
number of points that fall into each bucket I get a density volume.  If
I simply set each bucket to 1 that has any points in it, its as if I
have thresholded the density plot between 0 and 1.  If I run marching
cubes on either volume, I get holes and a very uneven surface.

I don't think any volume rendering technique can work reliably for this
kind of data.  Here's why:

(1)  The volume data quantizes the 3D region, and since memory use
grows as the cube of the quantization, its very expensive to quantize
any finer.  Hence the uneven surface.

(2)  (and the real killer)  The points do not evenly sample the
surface.  You can't expect a chaotic system to do so, can you?  So
there may be large areas of the surface that have no (computed) points
on them.  If you quantize finely to get a better surface, its likely
that there will be many buckets that the surface passes through, but
that had now points fall within them.

These two problems seem intertwined.  You can't solve one without being
killed by the other.

So I expect that the correct way to do this is by some triangulation
method (maybe start with a 3D voronoi representation), with some
heuristics to prune long edges that really reach across the surface.

I would like more discussion about how to construct a surface from a
list of points.  I'm sure that volume techniques won't work in all
cases.


-- 
Robert Skinner
robert@sgi.com

	How much sin can I get away with and still go to heaven?