winfree@.math.arizona.edu (Art Winfree) (04/29/91)
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?
ATWokeefe@cs.Buffalo.EDU (Paul O'Keefe) (04/29/91)
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. A color and opacity is assigned to each voxel, then the volume is raytraced. The assignment of opacities is the only difference between LeVoy's surface and full volume rendering algorithms. The apE module `opac` is the only widely available implementation of which I`m aware. Caveat, opac too slow for volumes larger than 32^3, since it doesn't use octtree encoding or other speed-up method. Paul O'Keefe SUNY at Buffalo
bstewart@bnlux1.bnl.gov (Bruce Stewart) (04/30/91)
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 By what criteria were the results of marching surface finders unsatisfactory?
rick@pangea.Stanford.EDU (Rick Ottolini) (04/30/91)
In article <1991Apr29.204526.11197@bnlux1.bnl.gov> bstewart@bnlux1.bnl.gov (Bruce Stewart) 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 One idea is to leave the points as points, but add a normal for lighting models. The visualization toolkit called SunVision (from Sun) contains this technique. You could probably estimate the normal from the best fitting surface or ellipsoid.
robert@texas.asd.sgi.com (Robert Skinner) (05/01/91)
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?
stam@dgp.toronto.edu (Jos Stam) (05/01/91)
(Rick Ottolini) writes: >>(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 >One idea is to leave the points as points, but add a normal for lighting >models. The visualization toolkit called SunVision (from Sun) contains this >technique. You could probably estimate the normal from the best fitting >surface or ellipsoid. One possibility is to interpolate your data, this will give you a smooth function from which you can calculate normals. There is a huge choice of interpolators. You'll probably only need to consider data points within a small neighbourhood to calculate your interpolator. If you think this might help you and you want more info, e-mail me at: stam@dgp.toronto.edu cheers, Jos
okeefe@cs.Buffalo.EDU (Paul O'Keefe) (05/02/91)
|> In article <73521@eerie.acsu.Buffalo.EDU>, okeefe@cs.Buffalo.EDU (Paul O'Keefe) writes: |> |> 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. A few amendments: 1) That's Levoy, not LeVoy, and he's now Assistant Professor of Computer Science at Stanford. 2) For rendering clouds, volume rendering is not the correct approach. For one thing, the spatial location of the points in a cloud are not restricted to a grid as is volume data. 3) At SIGGRAPH `91, there will be a course called, "Photo-realistic Volume Modeling and Rendering Techniques". The lectures include James Kajiya of CalTech and Ken Perlin of NYU. Topics include "volume tracing techniques for rendering atmospheric effects and laminar flame model; volume rendering of soft objects". Get a copy of the course notes at SIGGRAPH. 4) Consult the publications of Kajiya, Blinn, Perlin and others for tips on rendering fuzzy clouds. Paul O'Keefe SUNY at Buffalo
bstewart@bnlux1.bnl.gov (Bruce Stewart) (05/02/91)
In article <1991Apr30.182711.2223@fido.wpd.sgi.com> robert@sgi.com writes: >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 > >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. > IMHO this is an excellent example of a problem which needs some thought as to how the problem should be posed before attempting to find a solution. "The surface of a chaotic attractor" may or may not be a well-defined concept, depending on the attractor. In some cases, notably systems with very strong dissipation (= area or volume contraction rate), a chaotic attractor may be very close to a branched manifold; the Lorenz system and the Roessler band are examples. In other cases, fractal structure is a prominent feature of an attractor; Ueda has made high resolution pictures of some in this category, see for example D. Ruelle's article in the Math. Intelligencer 1980, pp.126-137; the Japanese attractor illustrated therein is in some sense equivalent to a disk, but I doubt if any general algorithm would produce anything close to a circle as an outer boundary of this object, and I would mistrust any algorithm which did give such an answer. (I am assuming that the outer boundary - whatever that is - of this two-dimensional attractor is analogous to what is sought by the poster for a three-dimensional attractor.) Better to ask why one would want to look at the "surface of a chaotic attractor." One might want to give a simple characterization of the ensemble of phase space points which may be visited, for example to give a convenient engineering bound on the maximum displacement (or velocity or energy or strain or ...) which can be expected. This might lead to a formulation which would point to an algorithm or class of algorithms. However, approaching this via any finite sample of points would be very dangerous, since even simple attractors like the Lorenz attractor visit their outer limits extremely rarely. If one wants to "get an idea of the shape and structure" of an attractor, the right way to proceed is to understand the dynamics: find the unstable periodic points or unstable periodic orbits of lowest period, and construct their unstable manifolds (outsets). This is not always a cookbook procedure: for example the Lorenz attrator has unstable periodic orbits AND unstable fixed points; the two spiral points are not within the attractor, but they are inside any simply connected hull, and they are probably the objects whose outsets are most informative. On the other hand, this approach is not (as it might seem) limited to chaos techno-freaks with specialized software; one purpose of my interactive software for Iris workstations (and the accompanying documentation and tutorial exercises) is to show that fixed points and invariant manifolds can be constructed via primitive phase-space-geometric operations. (End of advertisement.) I apologize for all this babble, which may be of little or no intrinsic interest to many in this newsgroup. It was merely intended to put some kind of fig leaf on the following opinion: Looking for the surface of a chaotic attractor is probably a misguided enterprise, and I would be wary of any conlcusions reached in the process of trying to accomplish this. It appears that the question originally posted by Art Winfree IS based on a well-posed problem, but it might have been useful to give a more complete description of how the problem arose and how a solution is judged good or not. -Bruce Stewart
uselton@nas.nasa.gov (Samuel P. Uselton) (05/03/91)
In article <74189@eerie.acsu.Buffalo.EDU> okeefe@cs.Buffalo.EDU (Paul O'Keefe) writes: > >|> In article <73521@eerie.acsu.Buffalo.EDU>, okeefe@cs.Buffalo.EDU (Paul O'Keefe) writes: >|> >|> 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. > >A few amendments: > >1) That's Levoy, not LeVoy, and he's now Assistant Professor of Computer > Science at Stanford. > >2) For rendering clouds, volume rendering is not the correct approach. > For one thing, the spatial location of the points in a cloud are not > restricted to a grid as is volume data. > As discussed fairly extensively at the San Diego Volume Visualization Workshop (December 1990), there is a lot of volume data that is NOT defined on regular grids. Fluid dynamics uses warped grids; finite element analysis and other fields use "grids" in which cells may have more or fewer than six faces. None the less, these applications may profit from volume rendered display of their data. It is just harder to do. ( :-) ) >3) At SIGGRAPH `91, there will be a course called, > "Photo-realistic Volume Modeling and Rendering Techniques". > The lectures include James Kajiya of CalTech and Ken Perlin of NYU. > Topics include "volume tracing techniques for rendering > atmospheric effects and laminar flame model; volume rendering of soft > objects". Get a copy of the course notes at SIGGRAPH. > >4) Consult the publications of Kajiya, Blinn, Perlin and others for tips > on rendering fuzzy clouds. > >Paul O'Keefe >SUNY at Buffalo Sam Uselton uselton@nas.nasa.gov employed by CSC working for NASA (Ames) speaking for myself volume rendering vector fields on warped grids!
rick@pangea.Stanford.EDU (Rick Ottolini) (05/03/91)
In article <1991May1.205240.28361@bnlux1.bnl.gov> bstewart@bnlux1.bnl.gov (Bruce Stewart) writes: >In article <1991Apr30.182711.2223@fido.wpd.sgi.com> robert@sgi.com writes: >>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 >> >>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. Many of the current graphics representation techniques using the concept of a lighting model to project an illusion of 3-D. The lighting models are either reflective- a light source in front of the object that reflects to the viewpoint- or transmissive- goes through an object of various degrees of opacity. Now consider the reflective lighting model. It requires some idea of surface tangency (the normal is the perpendicular). A tangency is only well-defined if the object is differentiable. Many chaotic or fractal datasets are not differentiable. Graphics people cheat sometimes and assume a smooth connection between sampled points for the purpose of rendering.