Approaches to Geometric Modeling (Basic Computer Graphics) Part 4

Parametric Representations

Many of the representations of solids rest on a representation of their boundaries. That was true even in the case of the csg-rep. Although the primitives were solids, in practice one only had equations or parameterizations for their surfaces, and the interior of the solid was not referenced explicitly. As far as parameterizations are concerned, there is no reason why we have to limit ourselves to parameterizations of two-dimensional objects. If we want access to interior points, we can define three-dimensional parameterizations just as easily. For example,

tmpc646979_thumb2_thumb

is a parameterization of a solid cylinder of radius 1 and height 2 with axis the z-axis. If we allowed such parameterizations, then we could also generate interior points of the object at will.Similarly, one could describe a corresponding basic collection of solids and their parameterizations. In other words, three-dimensional parameterizations are a representation scheme for solids. See [Mort85] for a discussion of what he calls a tricubic parametric solid. This is a space parameterized by a function p(u,v,w) of the form


tmpc646980_thumb2[2]

This is the most general cubic parameterization, but one can look at special cases such as Bezier or spline forms, just like in the surface case. See [HosL93].

Decomposition Schemes

Decomposition representation schemes represent objects as a union of quasi-disjoint pieces. These representations come in two flavors: object-based or space-based. The object-based versions present a subdivision of the object itself. The space-based versions, on the other hand, subdivide the whole space and then mark those pieces that belong to the object. The hatched cells in Figure 5.21(b) define a space-based decomposition representation of the object in Figure 5.21(a). Figure 5.21(c) shows an object-based decomposition of the same object.

Another distinction between decomposition schemes is whether they use a uniform or adaptive subdivision. The choice is driven by the geometry of the object. For example, at places where an object is very curved it would be advantageous to subdivide it more to get a more accurate representation. Object-based decomposition schemes tend to be adaptive.

Cell Decompositions. This is a very general object-based decomposition representation. Here the primitive pieces that an object is broken into can be arbitrary (curved) cells, typically triangles in the two-dimensional case or tetrahedra in the threedimensional one. The idea is to find triangular or tetrahedral pieces each of which has a relatively simple definition, something that presumably the whole object did not have. The representation is unambiguous but certainly not unique. Cell decompositions are an essential ingredient of finite element modeling.

Decomposition representations.

Figure 5.21. Decomposition representations.

Spatial occupancy representation.

Figure 5.22. Spatial occupancy representation.

Certain important topological properties can be computed relatively easily from a cell decomposition, such as answers to the questions

(1)    Is the object connected?

(2)    How many holes does it have?

The representation is also good for nonhomogeneous objects. See Section 7.2.4 in [AgoM04] for a general definition of a cell complex. Handle decompositions of manifolds (see Section 8.6 in [AgoM05]) are a special case of this type of representation.

Spatial Occupancy Enumeration. This space-based scheme represents objects by a finite collection of uniformly sized cells. Areas are divided into squares (pixels). Volumes are divided into cubical cells called voxels, an abbreviation for “volume elements.” There are two choices here in that one can either represent the object boundary or its interior. In the latter case, one can, for example, list the coordinates of the center of grid cells in the object. See Figure 5.22.

Spatial occupancy enumeration is an ambiguous representation. Furthermore, a big problem with this scheme is the amount of data that has to be stored. For that reason it was not used much for mechanical CAD or CAM (computer-aided manufacture) initially except for gross models to help with certain calculations such as collision checking and getting a rough estimate of volume. This has changed now that computers with gigabytes of memory have become a reality and voxel-based representation schemes for volumes have become very popular in certain parts of computer graphics. A more detailed discussion of this subject follows in the next section. Section 5.8.2 will describe the standard approach to cutting down on the amount of data one has to store.

Volume Modeling

Here are four terms and their definitions that usually appear in the same context:

Volumetric data:

The aggregate of voxels tessellating a volume.

Volume modeling:

The synthesis, analysis, and manipulation of sampled, computed, and synthetic objects contained within a volumetric data set.

Volume visualization:

A visualization method concerned with the representation, manipulation, and rendering of volumetric data.

Volume graphics:

The subfield of computer graphics that employs a volume buffer for scene representation and is concerned with synthesizing, manipulating, and rendering such scenes. Volume graphics is the three-dimensional counterpart of raster graphics.

The definitions are taken from [KaCY93] and are an adequate representation of how these terms are usually used. The subject matter that is addressed by these terms is what this section is about. It really only dates back to the early 1980s and started in the context of tomography.

Although our main interest in this topic is on modeling geometric objects, volume modeling covers a much broader subject in that the "volumes" may have arisen in other ways. Volume modeling in its most general sense deals with scalar-valued functions defined on three-dimensional space. In that sense, it is not really a modeling scheme per se but has close connections with modeling. In the special case where the function takes on only two values, 0 and 1, we can, in fact, interpret the function as defining a space-based decomposition scheme generalizing the voxel-based spatial occupancy enumeration scheme. The voxel case is the uniform case, but the data set may have different geometries such as being composed of rectangular or curved cells. Cells might be different distances apart. On the other hand, the function could come from some arbitrary mathematical model. For example, one might want to display the temperature of a heated solid visually, perhaps by displaying the surfaces of constant temperature. We can think of volume modeling as modeling data that is acquired from appropriate instruments and then sampled to get the voxelization. The data could also be an "object" that is defined in terms of point samples. Volume rendering refers to the process of displaying such models. We shall have more to say about volume rendering in Section 10.4.

Foot with bones exposed ([ScML98]).

Figure 5.23. Foot with bones exposed ([ScML98]).

Volume modeling is beginning to make an impact on the more conventional CAD and CAGD. Here are some of its advantages:

(1)    One can “cut away” parts of an object and look at its interior. See Figure 5.23.

(2)    CSG can be implemented quite easily because at the voxel level the set operations are easy, especially if one has support for voxBlt (voxel block transfer) operations that are the analog of the bitBlt operations.

(3)    Rendering is viewpoint independent.

(4)    It is independent of scene and object complexity.

The author has felt for many years that it was advantageous to model the whole world and not just the objects within it. It gives one much more information. For example, to trace a ray, one simply marches through the volume and sees what one hits along the way, rather than having to check each object in the world for a possible intersection. Volume modeling is now making this possible.

Some disadvantages of volume modeling are:

(1)    A large amount of data has to be maintained.

(2)    The discretization causes loss of information.

(3)    The voxelization causes aliasing effects.

Volume modeling plays an important role in the visualization of scientific data. This is a big field in computer graphics. Although not the focus of this topic, it would not be right to omit mentioning some examples of it:

Medical Imaging. This was one of the first applications of volume modeling. See [StFF91] for an overview of early work. Physicians used MRI (magnetic resonance imaging) and CT (computed tomography) scanners to get three-dimensional data of a person’s internal organs. In tomography one gets two-dimensional slices of the object using X-rays. One projects X-rays through the body and measures their intensity with detectors on the other side of the body. The X-ray projector is rotated about the body and measurements are taken at hundreds of locations around the patient. A picture of the slice is then obtained from a reconstruction process applied to all this data. Radiologists were apparently good at seeing three-dimensional models from these two-dimensional slices, but surgeons and doctors were not. Fortunately, there exist algorithms that, when applied to a stack of such slices, produce a representation of the whole organ and volume rendering makes it possible to display it. One is able to remove uninteresting tissues to see those parts that one wants to see. At this point in time, three-dimensional medical graphics is not yet widely used, mainly because of the cost. Also, the slices are more accurate and have more information than the three-dimensional reconstruction, so that radiologists tend to refer to them more.

In another recent development, surgeons can now also use haptic systems to practice surgeries beforehand. "Haptic" means that one gets physical touch feedback from the system.

Modeling Natural Phenomena. Understanding the flow of air over an airplane wing is important for its design. A similar understanding is needed for designing intake or exhaust manifolds in engines. This is where fluid dynamics enters. Fluid dynamics deals with fluid flow, which is governed by a set of differential equations called the Navier-Stokes equations. These equations define the velocity and vorticity of the fluid. The vorticity describes the rotational part of the flow and is defined by a vector at each point of the fluid. Understanding vector-valued functions is not easy, but volume-rendering techniques have enabled scientists to get a better visual understanding of what happens inside a flow. Volume modeling has been helpful in modeling other phenomena such as ocean turbulence and hurricanes. Oil exploration has been greatly aided by the ability to use volume modeling to analyze geological data.

Education. Volume modeling has been used to avoid having to use actual bodies in dissection experiments. As a result of the visible human project sponsored by the National Library of Medicine, there now exist models of a human male and female. If one tried to model a human in the more traditional way by means of facets, it would take millions of triangles to do so.

Nondestructive Testing. Volume modeling has been used to enable mechanical and materials engineers to find structural flaws in objects without having to take them apart.

This ends our brief overview of volume modeling. We return to the very interesting topic of volume rendering in Section 10.4. There is a large body of literature on volume modeling and the related subject of scientific visualization. A good place to begin more reading is [LiCN98], [ScML98], and various ACM SIGGRAPH course notes such as [Kauf98].

The Medial Axis Representation

In mathematics, when one tries to characterize or classify geometric objects, one first looks for coarse invariants (topology) and then successively refines the classification by adding metric criteria, differentiability criteria, etc. For example, at a very top level,a doughnut and a circle are similar because one can collapse the doughnut down to a circle. A double doughnut (two doughnuts attached to each other along a disk) is like a figure-eight curve. Therefore, since the circle is clearly a quite different shape from a figure-eight, one can see that the more complicated solids to which they are associated must also be fundamentally different shapes. This section is about a similar idea, namely, to facilitate dealing with objects by representing them by simpler (lowerdimensional) objects that nevertheless still capture the essence of the shape of the original object. The idea of using a “skeleton” of an object as a shape descriptor goes back to [Blum67] and [Blum73]. The fact that one gets a representation that has many attractive features has led to quite a bit of research activity on this subject. It should be noted, however, that the skeletal representation of an object is not a stand-alone representation for objects in practice. Mostly, it is intended to be used in conjunction with others, typically a boundary representation for continuous objects and a spatial occupancy enumeration representation based on pixels or voxels for discrete objects.

Skeletons come in two flavors, namely, continuous and discrete. We shall begin with definitions for the continuous case.

Definition. Lettmpc646984_thumb2[2]A maximal disk in X is a closed disktmpc646985_thumb2[2]contained    in    X with the property that it is not properly contained in any other closed disk in X.

Definition. Lettmpc646986_thumb2[2]The medial axis (MA) or skeleton or symmetric axis of X is the closure of the set of centers of maximal disks in X. The medial axis of a solid in R3 is sometimes called a medial surface. The real-valued function that assigns to each center of a maximal disk in X the radius of that disk extends to a continuous function on the medial axis called the radius function of that medial axis.

Note. Unfortunately, there is not complete agreement with regard to the terms medial axis, skeleton, and symmetric axis in the literature. For example, the medial axis in the continuous case is often also defined as the set of points equidistantly closest to at least two points in the boundary. The advantage of the definition given here with its closure condition is that if X is bounded then the medial axis will be a compact set.

Figure 5.24 shows the medial axis (indicated by solid lines) of a planar L-shaped bracket and a three-dimensional block. For a convex planar polygon it always con-sists of straight line segments but if the polygon is nonconvex there may be curved arcs as Figure 5.24(a) shows. There is a close relation between the medial axis and the Voronoi diagram of an object ([ShAR96]).

Medial axes.

Figure 5.24. Medial axes.

The medial axis for a polyhedron has a natural partition into cells. Determining the medial axis basically reduces to determining its cell decomposition. In two dimensions the cells are called arcs and junctions. For example, in Figure 5.24(a) BC and CD are arcs and the points A, B, and C are called junctions. In the nondegenerate case, junctions are the points where the maximal disk has three or more contact points with the boundary. The maximal disks at endpoints of arcs that lie in the boundary, like point D, have one contact point with the boundary. In three dimensions the cells are called sheets, seams, and junctions. The sheets are surface patches. These are further subdivided into wing sheets and body sheets. Wing sheets are those with points in their boundary where the maximal disk makes contact with the boundary at only one point, such as ABCD in Figure 5.24(b). Body sheets are the remaining sheets, such as ABEF. The seams are curves that typically are the intersection of two or more sheets where the maximal disk has three or more contact points with the boundary. Junctions are points that are the intersections of three or more sheets. See [BBGS99].

Next, consider discrete objects. We could give the same definitions because all that we need is a metric which we have. However, there are several natural metrics to choose from in this case and so it is possible to play around with the definition a bit and choose a variant which may be more suitable for a particular discrete problem. We follow [RosK76].

Definition. Lettmpc646991_thumb2[2]The    medial axis (MA) or skeleton or symmetric axis of X with respect to U is the set of points whose distances from the complement U – X are a local maximum, that is, no neighboring point has a greater distance to the complement. The distance function for the medial axis is the real-valued function that assigns to each point of the medial axis its distance to U – X.

In practice, the "universe" U is a rectangle when n = 2 (the pixel case) and a rectangular box when n = 3 (the voxel case). Figure 5.25 shows the medial axes for a 7 x 8 discrete rectangle in Z2. In Figure 5.25(a) we used the taxicab metric and in Figure 5.25(b), the max metric. The medial axes are the numbered points with the numbers giving the distance of the point to the complement.

Discrete medial axes.

Figure 5.25. Discrete medial axes.

Definition. The medial axis representation or medial axis transform (MAT) of an object consists of its medial axis together with the associated radius function in the continuous case and the distance function in the discrete case.

One can show that an object is completely specified by its medial axis representation. See [Verm94] and [RosK76]. Furthermore, in the continuous case the envelope of the maximal disks is just the boundary of the object. One nice thing about the medial axis representation is that it depends on the geometry of the object and not on the choice of coordinate axes like the quadtree or octree representation for discrete objects defined by pixels or voxels.

Algorithms that compute medial axes divide into two types based on whether they apply to discrete or continuous objects. The basic thinning algorithm for computing the discrete medial axis is often referred to as the “grassfire” algorithm. If a fire started at the boundary of the object were to burn into the object at a constant rate, then it would meet in the medial axis. One starts on the boundary of the object and strips away one layer of pixels or voxels after another until one reaches points that the fire reaches from two directions. See [RosK76] and [WatP98] for thinning of twodimensional discrete sets. Similar arguments work in three dimensions.

In describing algorithms for finding the medial axis of continuous objects we shall concentrate on three-dimensional objects. Such algorithms can be classified by the specific approach that is used: volume thinning, tracing of seams and sheets, Voronoi diagrams, or Delaunay triangulation. See [BBGS99] for advantages and disadvantages for various schemes. [CuKM99] also describes previous work.

Volume Thinning. One voxelizes the object and then computes the discrete medial axis that is then polygonized. An additional extra pass is required at the end to determine the radius function. Of course, this will only determine an approximation to the medial axis and one must be careful that it is accurate.

Tracing Approaches. One tracing approach is described in [ShPB95]. One starts at a known junction like a vertex of the polyhedron and then traces along an adjacent seam, defined as the zero set of some functions, until one gets to another junction. At that point one repeats this process for each seam that ends at that new junction. Polygonal approximations to the seams are computed. The main difficulty is determining the next junction. A similar approach is used in [CuKM99] but is claimed to be more accurate because it uses exact arithmetic.

Voronoi Diagrams. A number of algorithms use Voronoi diagrams because of their close connection to the medial axis problem since they also deal with equidistant sets of points. See Section 17.7 for a definition of Voronoi diagrams and some of their properties. The idea is to use a suitable sample of points in the boundary and compute their Voronoi diagram. See [Bran92], [ShPB95], or [ShPB96]. [CuKM99] describes an algorithm for polyhedra via Voronoi diagram and exact arithmetic.

Delaunay Triangulations. See Section 17.8 for a definition of a Delaunay triangulation of a set of points. A Delaunay triangulation is the geometric dual to the Voronoi diagram. [ShAR95] and [ShAR96] generate a domain Delaunay triangulation consisting of a set of tetrahedra based on an adaptive collection of boundary points. The medial axis is obtained from this triangulation.

Interior and exterior skeletons.

Figure 5.26. Interior and exterior skeletons.

Most algorithms are basically discrete algorithms. One exception is the algorithm described in [Hoff94] for CSG objects. In this regard, see also [LBDW92]. The authors describe how one can obtain an approximation to a variant of the Voronoi diagram for CSG objects. Sometimes bisectors of surfaces are rational. See [ElbK99]. In case of polyhedra, the medial surface consists of bisectors that are planes or quadric surfaces. An algorithm for planar regions with curved boundaries can be found in [RamG03].

To use the medial axis representation effectively one needs to know not only how to compute it but also how one can reconstruct the original object from it. The latter task is often referred to as refleshing. Algorithms for refleshing divide into direct and implicit approaches.

The direct approach to refleshing tries to reconstruct the boundary surface of the original object directly using the given radius or distance function. This amounts to constructing the surface from a variable offset type surface. See [GelD95]. Selfintersections are a problem with offsets and the exterior skeleton has been used here to help prevent these. See [STGLS97]. The exterior skeleton or exoskeleton of an object is the skeleton of the complement of the object. The ordinary skeleton is sometimes called the interior skeleton or endoskeleton. The exterior skeleton comes in handy at those places where the boundary of the object is concave. See Figure 5.26.

The implicit approaches to refleshing try to define the boundary surface implicitly as the zero set of a suitable function. They can be further subdivided into those that use a distance function and those that use convolution methods. See [BBGS99] for a more detailed discussion of this along with references. The paper also describes a new distance function approach. This involves triangulating the medial axis and defining a local distance function for each triangular facet. The global distance function is then the minimum of all the local ones. To give the reader a flavor of how a local distance function is constructed, we sketch the construction in the case where the radius function is constant over a facet. The local distance function is a composite of functions defined over regions that are related to the Voronoi cells associated to the facet, its edges, and its vertices. See Figure 5.27, which shows a triangular facet with vertices pi, p2, and p3 and its associated Voronoi cells whose boundaries are obtained by sweeping a vector orthogonal to the edges of the facet orthogonally to the plane of the facet. Let fsi be the local distance function for point pi determined by the sphere labeled spherei.

The regions used to define a local distance function for a facet.

Figure 5.27. The regions used to define a local distance function for a facet.

Lettmp3038-3_thumbbe the local distance function associated to the cylinder labeled cylij that is centered on the edge from pi to pj and meets the spheres labeled spherei and spherej tangentially. Lettmp3038-4_thumbbe the local distance function associated to the planes that meet the spheres labeled spherei tangentially. Then the local distance function f(p) associated to the facet is defined by

tmp3038-7_thumb

If the radius is not constant over a facet but varies linearly over it, then a similar construction works using cones rather than cylinders. In the end, the refleshed object is defined as the halfspace of a (distance) function. The implicitly defined boundary (the zero set of the function) can then be polygonized by some standard method if this is desired.

One goal of the medial axis representation is to make modeling easier for the user. For one thing, we have reduced the dimension by one. An example of this is the representation of an object by orthogonal projections. See [Bloo97], [STGLS97], and [BBGS99] for how a user might edit an object using its medial axis. In [BBGS99] the basic approach to editing a solid was

(1)    Compute the medial axis and radius function for the solid.

(2)    Allow the user to interactively edit the skeleton and radii.

(3)    Reflesh to obtain the edited solid.

(4)    Polygonize the boundary of the solid so that the user can use the b-rep for other purposes.

The allowed editing operations were

(1)    Stretching: The user picks skeletal vertices and a translation vector.

(2)    Bending: The user picks a joint and specifies a rotation by clicking with the mouse on one side of a separating plane through the rotation axis.

(3)    Rounding: At sharp convex edges the wing sheets meet the boundary of the object and the disk radii go to zero. The user can either remove the wing sheets or change the disk radii.

(4) Editing disk radii: This allows a user to round, thicken, or thin parts of the object in uniform or nonuniform ways.

The bending operation in particular shows why the medial axis representation has an advantage over a b-rep. With a b-rep such an operation can produce tears if one is not careful. Although bending the medial axis may produce tears or intersections, the refleshing operation removes all that.

Medial axis computations have many applications. Just to list a few topics and references, they are used in finite element mesh generation ([STGLS97]), shape optimization and robot path planning ([GelD95]), and pattern analysis and shape recognition ([FarR98]). See [Nack82] for relationships between the curvature of a surface and curvature functions associated to its medial axis representation.

Finally, related to the medial axis are the level sets of [LazV99] and the Reeb graph of [ShKK91] and [ShiK91]. With level sets the goal was to describe both the topology and geometry of the object, whereas with the Reeb graph the goal was to encode the topology. Both of these approaches are based on the handle decomposition of manifolds that is central to the classification of manifolds.

Next post:

Previous post: