Approaches to Geometric Modeling (Basic Computer Graphics) Part 7

Converting Between Representations

The need for algorithms that convert from one representation to another exists not only because modelers using different representations may want to exchange geometric data but especially because modelers increasingly seem to maintain multiple representations internally. By in large, the problem seems to have only been dealt with in an ad hoc way. We begin by addressing the two classical CSG-to-b-rep and b-rep-to-CSG problems. We end with some comments about the IGES data exchange standard between modelers.

The CSG-to-b-rep problem is the boundary evaluation problem in CSG that was first studied systematically in [ReqV85]. An early algorithm for polyhedral objects can be found in [LaTH86].

Figure 5.43. A CSG-to-b-rep conversion example.

Ways to speed up the operation by only making computations for “active zones” (those parts of the CSG tree that actually affect the final answer) are described in [RosV89].

Let X be a CSG object. We clarify the basic approach to finding the boundary of X with the example in Figure 5.43(a) which is the union of a square (the intersection of four halfplanes defined by the edges a, b, c, and d) and the halfspace which is a disk. See [GHSV93].

Step 1: Determine the boundary of every CSG primitive halfspace Hi used in the

definition of X. In our example this gives us four lines and a circle.

Step 2: We know that dX c » 3Hj. Assuming that we have manageable definitions of the 3Hj, we now trim these boundaries against each other to get 3X. In our example, we would get four segments and three circular arcs. See Figure 5.43(b).

Step 3: To get a more compact representation one finally tries to merge adjacent faces into larger ones. In Figure 5.43(b) one would merge the three adjacent arcs into one arc.

The hard part in this algorithm is Step 2. We already mentioned some aspects of this problem in Section 5.3.3. We subdivide the step.

Step 2a: The points of each 3Hj are divided into three subsets which consist of those points that are either in, out, or on with respect to X. See Figure 5.43(b). Step 2b: The boundary dX consists of all those points which are on. This set is computed from the collection of in, out, and on sets using Boolean set operations together with some additional neighborhood information.

Essential to these computations is the point membership classification function, denoted by PMC. Assume that X is an r-set and p is a point. Define

 

 

 

Figure 5.44. An ambiguity in the on/on case for

One computes PMC by using the CSG structure of X. What this means is that

(1)    one has to know the value on the CSG primitives, and

(2)    one needs to be able to combine values for the various set operations, that is, if op is one of the operations such aswe    need to express PMC (p,X op Y) in terms of PMC (p,X) and PMC (p,Y).

As an example, here is the answer, in table form, to the combine operation (2) for the operation

X \ Y	in	on	out
in	in	on	out
on	on	on/out	out
out	out	out	out

There is a complication in the case where the point p is on both sets. Figure 5.44 shows the problem. We are unable to distinguish between the situations shown in Figure 5.44(a) and (b). To resolve this problem we need to store some neighborhood information N(p,X) whenever the point is on X. We therefore redefine the PMC function to

Describing the neighborhoods N(p,X) can get complicated in general, depending on the kind of primitive spaces one allows. However, as an extremely simple twodimensional example consider the case where the primitives are simply orthogonal rectangles. In that case it is possible to encode N(p,X) as a 4-tuple (a,b,c,d), where a, b, c, and d are T or F because the essential nature of a disk neighborhood of a point p on the boundary of X can be captured by considering the disk to be divided into quadrants and specifying which quadrant belongs to X. A quadrant is assigned a T if it belongs to X and an F, otherwise. See Figure 5.45. In Figure 5.44(a), we would have

Figure 5.45. Neighborhood classification of an on/on point.

Figure 5.46. The need for separating planes.

In Figure and N(p,Y) = (F,F,T,T). Simple Boolean operations on these representations would then determine the neighborhood of points in the on/on case. In a corresponding three-dimensional example of orthogonal blocks one would use an encoding based on octants. The reader is referred to [Tilo80] and [ReqV85] for a discussion of how one would handle more general cases.

Next, we consider the problem of converting from a b-rep to CSG, which is much more difficult than going in the opposite direction. The basic idea is to use the halfspaces associated to the faces of the b-rep to describe a CSG representation. Unfortunately, this may not work as the example in Figure 5.46(a) shows. The shaded region consisting of the three regions A, B, and C is our solid X and H and H2, the interiors of the horizontal and vertical ellipse, respectively, are the halfspaces associated to the faces of X. No CSG representation which only uses these two halfspaces will represent X because any space defined by such a representation that contains region C will also contain region D. We have to introduce some additional halfspaces, called separating planes. The separating plane and the halfplane H3 below it shown in Figure 5.46(b) will do the job for the space X. For example,

Therefore, before continuing, we need to answer the question: When can a space be described in terms of unions, intersections, and complements of halfspaces? Assume that we have a finite collection of halfspaces.

Although there is an infinite number of ways that these spaces can be combined with the regular operatorsthe following  is  true: 5.9.1 Theorem. All possible combinations of the halfspaces in H using the operatorswill generate only a finite number of regular spaces X and each of these can be represented by a unique expression in the form

and each hj is either

As an example of this theorem, consider the space X in Figure 5.46(b) again. The unique decomposition of X guaranteed by the theorem is the one below:

(The decomposition in equation (5.5) does not have the right structure.)

In general, let us call any space like Πί in equations (5.6) a canonical intersection term for the collection of halfspaces H. Note that the interior of every canonical intersection term is the intersection of the interior of the halfspaces that defined that canonical intersection. This leads to the main theorem about when a space admits a CSG representation based on a given set of halfspaces.

5.9.2 Theorem. Letbe    a    collection    of    halfspaces.    A solid X with the property thatadmits    a    CSG    representation based on H if and only if the interior of every canonical intersection term based on H is either entirely contained in X or entirely outside of X.

Theorem 5.9.2 explains why the two halfspaces in Figure 5.46(a) were inadequate to describe the space X: the canonical intersectionis    half    in X and half outside of X.

We clarify our discussion with another example. We desire a b-rep-to-CSG conversion for the solid X in Figure 5.47(a) ([GHSV93]). The b-rep of our solid X specifies five halfspaces associated to each face in the boundary: four halfplanes and one disk. Figure 5.47(b) shows the in/out classification of the canonical intersections for our halfspaces. We see that the regions A and B in the figure that belong to the same canonical intersection have a different in/out classification. They are both in the square and outside the disk, but one is inside our solid and the other is outside it. By Theorem 5.9.2 this means that X cannot be obtained from the given halfplanes and disk by standard set operations. We need more halfspaces and the separating halfspace shown in Figure 5.47(c) resolves our problem.

Figure 5.47. A b-rep to CSG conversion example.

We are now ready to describe the steps in a general b-rep-to-CSG conversion.

Step 1: We use the b-rep of our solid X to specify halfspaces associated to each face in the boundary.

Step 2: Since the halfspaces we get from Step 1 may not be adequate to describe X in a CSG way, we may have to introduce additional separating halfspaces. This is the hardest part of the conversion. What we do is to compute the canonical intersections of the halfspaces derived in Step 1. They divide the whole Euclidean space into a collection of cells. These cells and their interiors do not need to be connected. (See Figures 5.46 and 5.47.) Heavy use of the point membership classification function enables us to determine the in/out classification of these components. This classification tells us whether we need separating planes and is also used to find such planes if they are needed.

Step 3: The CSG decomposition is gotten from the cells in Step 2 by taking a union of all the cells that consisted of in points.

Step 4: The CSG decomposition we get in this way may not be very efficient and so as a last step one may try to perform some optimization which either minimizes the number of primitives or the number of set operations.

For more details see [ShaV91a], [ShaV91b], and [ShaV93]. [GHSV93] has a nice overview of the generic representation conversion process and the general principles that are involved. Step 4 above points to one of the stumbling blocks to having a nice theory of conversions between different representations. The answer may not be well-defined. In the b-rep-to-CSG case, we do not have a clear idea of which of the many possible primitives that one can use are best.

As we have seen, converting between different representations is potentially a hard problem. There is another related problem. Two modelers may use basically the same representation scheme but have implemented them differently. This is hardly surprising since each had a different team of programmers. What we have here is an implementation conversion problem. Because there are many commercial modeling systems in use, this is a real problem since many businesses are not able to assume that all needed data will be generated internally and there is a need to transfer data from one system to another. IGES (Initial Graphics Exchange Specification) was developed to solve this problem and enable different systems to exchange data between themselves. To use IGES, a modeling system must have translators that convert from their representations to those of IGES and vice versa. A person wishing to transfer data from system A to system B would then first use system A’s IGES translator to translate the system A data into the IGES format and write this to a file. That file would then be read by system B’s IGES translator that would convert the IGES data into system B’s own internal format.

IGES is not perfect and it is easy to complain about its constraints. There is another more advanced data exchange format STEP that allows for much more high-level descriptions than the relatively simple annotated geometry formats of IGES, but we refer the reader to [ShaM95] for that. Nice features of a modeling system can get lost in the translation to and from IGES. A direct translation from one system’s data structure into the other’s would usually be more efficient. The latter approach would therefore be the way to go in certain dedicated situations. However, it is certainly much simpler to write one translator (for IGES) than writing many (one for each external modeling system). Writing translators is a nontrivial task. Furthermore, modeling systems continue to evolve and one would have to keep updating any direct translators. IGES also continues to change with the times, but at least only one update has to be written if one uses it. The bottom line is that IGES is a cost-effective solution to the geometric data transfer problem that works.