Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!husc6!rice!titan!foo
From: foo@titan.rice.edu (Mark Hall)
Newsgroups: comp.graphics
Subject: Re: Blobbly Polygons
Keywords: meta-ball, blobby molecules
Message-ID: <2642@kalliope.rice.edu>
Date: 19 Feb 89 20:16:24 GMT
References: <439@celia.UUCP> <2607@kalliope.rice.edu>
Sender: usenet@rice.edu
Reply-To: foo@titan.rice.edu (Mark Hall)
Distribution: usa
Organization: Rice University, Houston
Lines: 75

In article <2607@kalliope.rice.edu> foo@titan.rice.edu (Mark Hall) writes:
>In article <439@celia.UUCP> celia!charlie@tis.llnl.gov (Charlie Gibson) writes:
>>Can anyone recommend some references for "Meta-Sphere" or "Blobby Molecule"
>>algorithms that create a tesselated 3-d geometry? 
>>-- 
>>Charlie Gibson                                | What IS the secret powder
>>Rhythm & Hues, Inc.                           | that makes "Orange Julius"
>


   I left a few things unclear in my posting of references in polygonalizing
 implicit surfaces, among which are the "blobby molecules". 

   If you want a copy of the paper I co-authored, send an email request
 with a physical mail address. The figures and photos in the paper do 
 not travel by email very well. At least, I don't have that capability. 

   The "tricky" part of Bloomenthal's polygonalization algorithm is in 
 the adaptive part. If you don't care about adaptively polygonalizing
 his algorithmic approach is quite straightforward.(If you are rendering
 "blobby molecules", for instance, there will probably not be large flat
 portions on your surface, so adaptivity will probably not buy you much).
 
   Note that Lorenson & Cline's method presupposes a fixed grid of values
 that the algorithm is presented with. Lots of scientific data comes in
 this form. The other algorithms show their graphics origins in that they
 can take advantage of (or require) the ability to generate density 
 information at arbitrary locations. This allows much smaller amounts of 
 data to be sufficient. If you are concerned with a single connected 
 structure, it is often possible to "walk" along the surface, generating
 data only in a small area just inside and outside the surface. (see 
 Bloomenthal's paper)

   A previous article mentioned that Lorenson and Cline's method can cause
 holes to appear at saddle points of the surface. That is the problem that 
 Duurst mentioned. However, I feel that the holes are a symptom of a more
 general and underlying problem. The real problem is that the lookup table 
 method they use can cause data on a single face to be interpreted differently
 by the two cubes which share the face.

   A quick note: All these methods are point-sampling methods, and are therefore
 subject to the problems of undersampling just as in signal processing.
 Therefore it is impossible to know that you have sampled the volume closely
 enough unless you can determine the maximum "frequency" and sample twice
 that closely. All these methods can be "fooled" by data with a high enough
 frequency component. Lorenson and Cline's method has the additional problem that 
 two cubes may differently interpret how the surface crosses their shared face.

             in           out         in           out
                * * * * * *             * *.* * * *
                *      .  *             * .       *
                *.      . *             *.       .*
                * .      .*             *       . *
                *  .      *             *      .  *
                * * * * * *             * * * * * *
             out          in         out            in

   (the above is supposed to be two squares with a pair of diagonal 
    lines in each. )

   Consider the 2D case: you have 4 data values at the corners of a square
 (or rectangle). Consider the case where diagonally opposite corners match
 as to "inside/outside"edness. There are 2 ways to interpret the data for 
 simple functions. (1) the 2 corners that are "inside" are connected to 
 each other or (2) they are unconnected on this face. The two 
 interpretations will lead to a different set of polygon edges on the
 face. 

   In 3D, the above scenario happens on a face shared by two abutting cubes.
 If the two cubes interpret the shared face inconsistently, problems
 arise. One is the creation of holes at saddle points. All the other
 methods insure consistency in the interpretation of shared faces and so 
 not have the same problems. 

   - mark