Approaches to Geometric Modeling (Basic Computer Graphics) Part 6

Functions and Algorithms

In addition to modeling objects, modelers must also be able to perform a variety of operations on the objects that they have modeled. As indicated in the introduction, modeling involves modeling maps as well as objects. Here is a sample of some queries users may want to make and actions they may want to perform:

(1) Find physical propertie of objects:

center of mass, moments of inertia, area, volume, . . .

(2) Find geometrical properties of objects:

distances between objects, collision detection, intersections and other Boolean set operations, . . .

(3) Perform geometrical operations:

rigid motions, . . .

(4) Numerical control related operations:

milling, lathing, . . .

Relationship between functions and algorithms.

Figure 5.35. Relationship between functions and algorithms.


In a modeler mathematical functions get replaced by algorithms. We want a commutative diagram as shown in Figure 5.35. Some issues that arise are:

(1)    A “correct” algorithm must perform the “correct” action on all valid inputs.

This is a serious issue in the context of computers because  of round-off errors.

For example, finding the intersection of two rectangles should work if they  only touch along a face.

(2)    If an input to an algorithm is meaningless or invalid the algorithm should

(a)    inform the user, and

(b)    still return some answer which will not cause the system to crash

(3)    An algorithm should be efficient. If objects have several representations it should be smart enough to pick the best one for its task.

(4)    An algorithm should be as general as possible to allow extensions.

We can see from this discussion that modelers must deal with many tasks that fall into the field of computational geometry, which deals with finding geometric algorithms and analyzing them. In this regard we should mention the relatively new but growing area of research into genetic algorithms. These algorithms are a class of search algorithms that are proving to be very useful in the complex optimization problems encountered by modelers. An overview of this topic can be found in [RenE03].

Data Structures

Data Structures for Boundary Representations

Anyone interested in implementing a geometric modeling program will quickly face the problem of choosing appropriate data structures for the geometry that is to be modeled. As usual, one wants data structures that will be efficient in both space and execution times of algorithms. This section will briefly look at this issue in the case where we use a boundary representation for linear polyhedra. The next section will look at what one can do in the case of volume rendering.

Rendering linear polyhedra, or cell complexes in general, involves two parts: the abstract structure of the complex and the actual data. To describe the structure means describing various adjacency relations between the cells of the space.

Definition. A d-dimensional cell is said to be adjacent to an e-dimensional cell if

tmp3038-16_thumb[2][2]

In our discussion here we shall restrict ourselves to two-dimensional complexes. Algorithms dealing with such complexes typically need adjacency information such as the set of edges of a face or the set of faces that contain a given vertex. We shall use the following notation:

tmp3038-17_thumb[2][2]

In the context of this notation, capital letters such as X and Y will be one of the types V (vertex), E (edge), or F (face). IXI will denote the number of objects of type X. We shall refer to ^tmp3038-18_thumb[2][2]as    an adjacency relation.

The nine possible types of adjacency information between vertices, edges, and faces are shown in Figure 5.36. If a data structure contains one of these adjacency relations explicitly, then we shall say that one has direct access to that information. For example, the notationtmp3038-19_thumb[2][2]means that each edge has direct access to both of

its vertices andtmp3038-20_thumb[2][2]means    that    each    vertex    has    direct access to all of the vertices adjacent to it. Call a relationtmp3038-21_thumb[2][2]a self-relation.

Two questions which need to be addressed when choosing a data structure are:

(1)  Does the data structure adequately describe the topology of the spaces that are represented? If so, then we shall say that it is topologically adequate.

(2) What is the complexity of determining the truth oftmp3038-22_thumb[2][2]or    computing    some tmp3038-23_thumb[2][2]given the adjacency relations defined explicitly by the data structure.

[Weil85] has an extensive discussion of question (1). The topologically adequate adjacency relationships are identified and proved to be that. We shall not repeat those arguments here but simply refer the interested reader to that paper.

Possible face-edge-vertex adjacency data.

Figure 5.36. Possible face-edge-vertex adjacency data.

Computing the inverse adjacency relation

Algorithm 5.8.1.1. Computing the inverse adjacency relationtmp3038-32_thumb[2][2]

Rather, we want to concentrate on the answer to (2) and summarize the main results of [NiBl94]. It should be noted however, that all the adjacency relations that we mention later on as having the best complexity properties are also topologically adequate.

First of all, as Ni and Bloor point out, we need to distinguish between complexity in the context of a particular implementation and complexity at the abstract data structure level. [NiBl94] analyze the latter, which is implementation independent, and give answers in terms of the number of direct accesses of information and the number of set operations, such as union, intersection, etc., that are needed. A discussion of the costs involved in the context of some specific implementations, in particular, edge-based ones, can be found in [Weil85].

As an example of how one can compute the implementation independent cost of an adjacency relation that may be needed for an algorithm, suppose that a single non-self-relationtmp3038-33_thumb[2][2]__ is given. Algorithm 5.8.1.1 computes the inverse adjacency relationtmp3038-34_thumb[2][2]The    cost    of    this    algorithm    is    IXI    direct    accesses, IXI set membership tests, and at most IXIIYI unions for a total oftmp3038-35_thumb[2][2]steps. Ni and Bloor analyze in a similar way the costs of all the other possible queries for any given set of adjacency relations. One relation, namely, thetmp3038-36_thumb[2][2]relation, is treated as a special case. Sometimes data structures are used that do not store all objects adjacent to a given object. For historical reasons, due to the influential papers [Baum72] and [Baum75], the edge-edge adjacency relation has come to denote a more restricted relation in that only two of the edges adjacent to a given edge are listed.

Baumgart’s Winged Edge Representation. In this representation each face is assumed to be bounded by a set of disjoint edge cycles. One of these is the outside boundary, and the others are holes in the face.

Winged edge representation.

Figure 5.37. Winged edge representation.

In terms of implementing this, one uses a face table that consists of a list of edges where one has taken one edge from each edge cycle. Each vertex belongs to a circularly ordered set of edges. These sets are represented by one edge that is chosen from each. For each edge one lists

(1)    the incident vertices,

(2)    the left and right face,

(3)    the preceding and succeeding edge in clockwise (cw) order with respect to the exterior of the solid, and

(4)    the preceding and succeeding edge in counter-clockwise (ccw) order with respect to the exterior of the solid

Figure 5.37(b) shows the relations which are involved, although tmp3038-43_thumb[2][2]are only partial relations in this case.

Weiler ([Weil85]) showed that although the Baumgart structure represents the topology completely, certain algorithms for querying the data structure became complicated if self-looping edges were allowed (the two endpoints are the same point). He defined three improvements. One added a little to the structure and the other two split the edge structure into two.

Returning to [NiBl94], one finds the following conclusions:

(1)    The best single relations aretmp3038-44_thumb[2][2]These relations are also adequate to describe the topology completely provided that the setstmp3038-45_thumb[2][2]are ordered in a circularly coherent manner.

(2)    When one is given a pair of adjacency relations, this is the first time that one can, with an appropriate choice,answer all possible adjacency queries. The best pair of relations istmp3038-46_thumb[2][2]

(3)    The two adjacency relation combinations shown in Figure 5.38(a) are the best combinations when one uses three adjacency relations.

(4)    Figure 5.38(b) shows the best combination of four adjacency relations. This relation was discovered by [WooT85].

(5)    The winged data structure shown in Figure 5.37(b) and some of its variants are worse than the combination in Figure 5.38(b).

Optimal combinations of adjacency relations.

Figure 5.38. Optimal combinations of adjacency relations.

Another useful adjacency relation.

Figure 5.39. Another useful adjacency relation.

See [NiBl94] for additional observations. The authors point out that in some situations, the face-edge-vertex structure shown in Figure 5.39 is one worth considering because the algorithms used with it are simpler than the corresponding ones one would use with the related winged-edge representation.

Of course, as our final observation, in general the way one chooses a data structure for an algorithm is by first seeing what operations are needed by the algorithm and then choosing an optimal data structure for these operations. In the discussion above we evaluated data structures in terms of efficiency with respect to all possible adjacency queries which were possible with a given set of adjacency relations. In a particular context one may not need to answer all such queries however.

Data Structures for Volume Modeling

Encoding techniques based on tree structures have been used to cut down on the amount of data one needs when objects are represented by pixels or voxels. The recursive step in the basic algorithm for the general (n-dimensional) volume case is the following:

(1)    If the volume is empty or completely covered by the object, then no further subdivision is necessary. Mark the volume as EMPTY or FULL, respectively.

(2)    Otherwise, subdivide the volume and recursively repeat these two steps on each of the subvolumes.

 Quadtree examples.

Figure 5.40. Quadtree examples.

Quadtree structure.

Figure 5.41. Quadtree structure.

The binary nature of the algorithm suggests a binary tree structure, but this is not as efficient as the quadtree in the two-dimensional case and octree in the threedimensional case.

Quadtrees. Assume that a planar region is contained in a rectangle. For example, consider the shaded region R in Figure 5.40(a). Now change the general algorithm above to the following:

(1)    If the region covers the current rectangle or is disjoint from it, then stop subdividing and return that fact; otherwise,

(2)    divide the rectangle into four equal parts and repeat these two steps for each of the subrectangles.

For the region R in Figure 5.40(a) we shall end up with a subdivision as indicated in the figure. The region can therefore be represented by a tree structure, called a quadtree, where each node has up to four nonempty subtrees. If we label the four subrectangles of a rectangle as indicated in Figure 5.41(a), then the Figure 5.41(b) shows the tree structure for R.

Quadtrees can also be used to represent curved regions as shown in Figure 5.40(b) by modifying the criteria for when one quits subdividing in one of two ways:

Octree subdivision.

Figure 5.42. Octree subdivision.

(1)    We could specify a cutoff depth below which we do not subdivide, or

(2)    rather than requiring that the region either misses or covers a rectangle completely, we can quit if it “almost” misses or quits, that is, one uses thresholds on the percentage of area covered.

Octrees. Octrees are the three-dimensional generalization of quadtrees. In the case of octrees we divide a cube into eight octants. See Figure 5.42. We can then encode objects with trees where each node has up to eight nonempty subtrees. Octrees are generated for objects analogous to how quadtrees are generated.

One can show that the number of nodes in a quadtree or octree are typically proportional to the size of the object’s boundary, although it is possible to create some worse cases. The intuitively obvious reason for that is that the only time one needs to subdivide is when a cell is crossed by the boundary.

The quadtree and octree representations for objects have many nice properties and they have been studied extensively in order to store and process them efficiently. Boolean set operations are relatively easy. One traverses both trees in parallel and takes the appropriate steps at each corresponding pair of nodes. Algorithms exist for finding a pixel or voxel or finding neighboring pixels or voxels in the tree. These are operations that one often needs. Some simple transformations, such as rotations by 90 degrees, scaling by powers of 2, and reflections are easy. Other transformations are not. Aliasing is a big problem when performing these transformations. For more details see the references in the spatial data structure section of the bibliography.

Next post:

Previous post: