Graphics Reference
In-Depth Information
adaptive tiler
. As usual, one must be careful to make sure the cell partition is fine
enough so that our approximation is accurate, but not too fine so that we create too
much data. A review of implicit tilers can be found in [Kalv92], [NinB93], and
[Bloo97].
Algorithm 14.3.2 is an outline for the typical implicit tiler. We shall now explain
it in more detail. Our discussion will concentrate on surface tilers. Curve tilers are
similar but much easier. The first step is to divide space into cells. Bloomenthal
([Bloo97]) separates the approaches into three broad types: subdivision, enumeration,
and continuation.
In the
subdivision approach
one builds an octree representation of the object (a
quadtree for planar curves). The cells are usually cubes or tetrahedra because it is
easy to subdivide them into cells of the same type. The
enumeration approach
applies to volume modeling situations where one starts with a large three-dimensional
grid of data thought of as the values of some unknown function. The data could, for
example, come from MRI or CT scans. The grid is then searched to find all the cells
intersected by what would correspond to a contour surface of that function. This is
the kind of situation to which the marching cube algorithm applied. The
continua-
tion approach
is one based on incremental steps. One does not start out with a fixed
subdivision. Instead, one needs a starting point for each component of our surface.
One then marches out from that point generating an approximation to each compo-
nent. Predictor-corrector type methods often work fine for curves. In that case one
marches along the tangent line from the start point and uses some correction mech-
anism like the Newton-Raphson method to get back to the curve and a new point on
Step 1:
Partition space into cells
Methods:
subdivision - subdivide space and represent ob ject via a data structure
like a quadtree or octree
enumeration - get a predefined grid of values with the surface
corresponding to a contour
continuation - starting at certain points on the object expand the
subdivision of it into cells in an incremental way
Step 2:
Polygonize object
Method:
Find intersection of object with the boundary of each cell and then “fill in”
intersection with the interior of the cell.
Problem:
Ambiguity of the topology of the intersection with a particular cell.
Strategies to overcome the problem:
Topology inference, preferred polarity, or cell decomposition
Algorithm 14.3.2.
Outline for implicit tilers.
