Boundary representation deformation in parametric solid modeling.
One of the major unsolved problems in parametric solid modeling is a robust update (regeneration) of the solid's boundary representation, given a specified change in the solid's parameter values. The fundamental difficulty lies in determining the mapping between boundary representations for solids in the same parametric family. Several heuristic approaches have been proposed for dealing with this problem, but the formal properties of such mappings are not well understood. We propose a formal definition for boundary representation. (BR-)deformation for solids in the same parametric family, based on the assumption of continuity: small changes in solid parameter values should result in small changes in the solid's boundary reprentation, which may include local collapses of cells in the  boundary representation. The necessary conditions that must be satisfied by any BR-deforming mappings between boundary representations are powerful enough to identify invalid updates in many (but not all) practical situations, and the algorithms to check them are simple. Our formulation provides a formal criterion for the recently proposed heuristic approaches to persistent naming, and explains the difficulties in devising sufficient tests for BR-deformation encountered in practice. Finally our methods are also applicable to more general cellular models of pointsets and should be useful in developing universal standards in parametric modeling.
consumer applications, probably has to do more with development and successful marketing of new parametric
("feature-based" and "constraint-based") user interfaces than with the mathematical soundness of solid
modeling systems. These parametric interfaces allow the user to define and modify solid models in terms of
high-level parametric definitions that are constructed to have intuitive and appealing meaning to the user
and/or application (see [16] for examples and references). The success of parametric solid modeling came at
a high price: the new solid modeling systems no longer guarantee that the parametric models are valid or
unambiguous, and the results of modeling operations are not always predictable.
Unpredictable behavior of the new systems is well documented in the literature [11, 13, 15, 34], and we
will consider some simple illustrative examples in the next section. The basic technical problem is that a
parametric solid model corresponds to a class of solids, but there is no formal definition or standard for what
Complete address: 1513 University Avenue, Madison, Wisconsin 53706, USA. Email: raghotha@cae.wisc.edu,
ParameterInstance
'persistent naming'
ParameterInstance

Figure

1: The role of persistent naming for a parametric family of solids
this class is [34]. As a result, different modeling systems employ incompatible, ad hoc, and often internally
inconsistent semantics for processing parametric models.
The lack of formal semantics manifests itself clearly through the so called "persistent naming" problem
[15, 34]. In modern systems, every edit of a parametric definition is followed by a regeneration (boundary
evaluation) of the boundary representation (b-rep) for the resulting solid. Since parametric definitions and
constraints explicitly refer to entities (faces, edges, vertices) in the boundary representation, every such
regeneration must also establish the correspondence between the pre-edit and post-edit boundary represen-
tations. The correspondence must persist over all valid edits, hence the term "persistent naming". But since
the semantics of a parametric family is not well-defined, neither is the required correspondence. All systems
seek to establish the correspondence that is consistent with the user's intuition, but no reliable methods for
achieving this goal are known today. The problem is illustrated in Figure 1. Every two instances of parametric
definition are related through a parametric edit of one or more parameters t; each instance has its
own b-rep(t), and the problem of persistent naming is to construct the map g between the two corresponding
b-reps.
Recently, several schemes for persistent naming have been proposed [10, 18, 25, 31] that appear to work
well in a variety of situations. But the proposed techniques are not always consistent between themselves
and none come with guarantees or with clearly stated limitations; they may be able to alleviate the observed
problems in today's systems, but not solve them - because the problems have not even been formulated.
1.2 Main contribution
The diagram in Figure 1 places no constraints on properties of the naming map g. A commonly cited
obstacle to such formal properties stems from the belief that in the most general case parametric edits do
not seem to preserve the basic structure of the boundary representation. For example, parametric edits
may lead to collapsed and expanded entities, (dis)appearance of holes, etc. Yet the naming mechanisms
proposed in [10, 18] clearly rely on the generic topological structure of the boundary representation as a
primary naming mechanism. Certainly we would expect that the naming problem should have a unique
solution when the parametric changes are small and the resulting boundary representation does not change
very much. Accordingly, we propose that any notion of a parametric family should be based on the following
principle of continuity :
ffl Throughout every valid parameter range, small changes in a solid's parameter values result in small
changes in the solid's representation.
This statement will be made precise in Section 2 of the paper. We argue that this essential requirement of continuity
eliminates much of the unpredictable and erratic behavior of modern systems as described in [15, 34].
In this paper, we use this principle of continuity to develop a formal definition for Boundary Representation
(BR-)deformation for solids in the same parametric family. Importantly, "small changes" may include limited
local collapsing of entities in boundary representations; in this case the resulting BR-deformation can actually
change the topology of the boundary representation. A special case of the topological BR-deformation
is a geometric BR-deformation that may modify the shape of the boundary cells, but the topology and the
combinatorial structure of the b-rep remains unchanged.
Our formulation does not solve the difficult problem of constructing the naming map g in Figure 1, but it
leads to necessary conditions that must be satisfied by any naming map g between boundary representations
in the same parametric family. Loosely, the oriented boundary of each cell in the pre-edit b-rep must be
mapped into the closure of the corresponding cell in the post-edit b-rep with the same orientation. These
conditions are powerful enough to identify invalid updates in many (but not all) practical situations, and
the algorithms to check them are simple. In particular, the identified conditions give formal justification to
the naming mechanisms proposed in [10, 18], but also identify techniques that are not acceptable, because
they do not satisfy the assumption of continuity. Finally, our definitions explain the difficulties of devising
sufficient conditions for BR-deformation and the associated naming map g.
A definition for BR-deformation is a prerequisite for extending informational completeness to parametric
solid modeling and for creating an industry-wide standard for data exchange of parametric models. To
our knowledge, there are no competing proposals. A notion of variational class is prominent in mechanical
tolerancing and robustness [29, 36]. Notably, Stewart proposed a definition of variational class in [36], which
was later used in study of polyhedral perturbations that preserve topological form in [3]. The assumptions of
continuity and continuous deformation are also mentioned informally in the naming techniques and discussion
of [11]. Our definitions are consistent with the earlier definitions, but are stronger and stated in algebraic
topological terms, which are more appropriate for dealing with boundary representations and the mappings
between them.
The proposed notion of parametric family and the principle of continuity are stated in terms of a particular
representation scheme (boundary representation in our case). But our formulation and results are applicable
to more general cellular representation of pointsets. In Section 5 we discuss briefly how our approach to
parametric modeling may be extended to deal with arbitrary parametric edits and other representations.
Applying similar principles of continuity to other representations would lead to different definitions of parametric
families, e.g. those based on small changes in CSG representations [30, 31, 34]. We do not consider
such families in this paper because most extant commercial systems are based on b-reps.
1.3 Examples
The following examples illustrate some of the erratic and inconsistent behavior that occurs during parametric
updates of a solid model. These examples were created in several versions of two leading commercial solid
modeling systems. 1
The simple solid S shown in Figure 2(a) is sufficient to illustrate many of the relevant issues. The shown
boundary representation was produced from a parametric definition of S. The parametric definition uses
a number of parameters, including parameters t and d that constrain the locations of features (slot and
hole) with respect to the solid's edges, as shown in the figure. The value of t determines the location of
which in turn determines the location of the hole constrained by parameter d. Consider what
happens during a parametric edit of t. Every time t is changed, the system attempts to regenerate the
boundary representation of the solid and establish which of the edges should be called
. The result of this
computation is easy to determine by simply observing what happens to the hole constrained by d, since it
explicitly references edge e 1
If the change in t is small enough not to produce any changes in the combinatorial structure of the
boundary representation, we would expect to see no abrupt changes resulting from the edit. In other words,
the hole and the constraint d should move continuously with changes in the value of t. Instead, Figure 2(b)
illustrates an example of situations that have been observed in earlier versions of some systems. In some
cases the hole jumps on the face f 0and in other situations the hole surprisingly jumps to the other side
of the edge e 0onto f 0. In either case, the observed behavior would indicate that e 1
was mapped to e 0; in
the latter case the placement of the hole was also affected by the orientation of the mapped edge e 0(which
is opposite to that of e 0with respect to face f 0). In both cases the assumption of continuity is violated,
even though the correct continuous mapping clearly exists. We will formally characterize such a mapping in
section 2.3 as geometrically deforming. Similar problems have been identified and illustrated with "jumping
blends" by Hoffmann [10]. The naming techniques proposed in [10, 11, 18], as well as the latest versions of
1 We do not identify the specific systems, because similar technical problems are easily identified in all parametric modeling
systems that rely on b-rep for internal representation of solids.
(a) Parameter t controls
the b-rep of the solid (b) Erratic behaviour
observed in earlier systems
(c) Continuous change
in t collapses face f1
(d) B-rep is not in
parametric family of (a)
d
d
d
d
d

Figure

2: Parametric edits of a simple solid
many commercial systems, are now able to establish the appropriate mapping in this simple case, but not
in many more general situations.

Figure

2(c) shows another parametric update of the same solid, where the value of t is equal to the radius
of the cylindrical slot, and the edge e 1 becomes coincident with e 3 . Few (if any) of the latest commercial
systems can handle such an update in a consistent and uniform fashion. A typical response in one system is
shown in Figure 2(d), which indicates again that e 1
was mapped to e 0; another system simply signaled an
error indicating that it could not locate the proper edge (the naming map could not be found). When the
slot was constructed as a "hole," the latter system signals no error and simply maps e 1
to e 0, with the smaller
hole reappearing on the other side of e 0(outside the solid). Yet another system might delete the constraint
(and the hole) with an appropriate warning message. Again, intuitively it is clear that continuous change in
should lead to the collapse of face f 1
and identification of edges e 1
and e 3
to e 0. We will characterize such
collapsing maps in section 2.3 as topologically deforming.
These simple examples clearly show that the naming map is usually developed in ad hoc fashion, is
dependent on the way the solid is created, and may be internally inconsistent across different features
and representation schemes. The matching methods proposed in [10, 18] will not always properly handle
collapsing maps, although it appears that the techniques in [10] could be further adapted.
One may also start with the solid shown in Figure 2(d), i.e., create the hole and constrain it with
respect to e 0, and then increase the value of parameter t. One would then expect the face f 0and the hole to
gradually move to the right; we will call the corresponding mapping between pre-edit and post-edit boundary
representations expanding. Unfortunately, a more typical response from a system is the one shown in Figure
2(a), and the result will certainly differ from version to version and from system to system.
(a) Original solid's b-rep K (b) Modified solid's b-rep L

Figure

3: Discontinuous update allowed by the parametric modeling system
Our final example is shown in Figure 3. Parameter t controls the location of the cylindrical feature that
is unioned to the cubical body, and one of the intersection edges is blended. 2 The change in the value of t
moves the cylinder from one side of the block to the other. The system matches the blended edge e 1
with
the edge e 0in the post-edit b-rep as shown. Is there a way to determine if this update is correct? Notice
that there exists a continuous map between pre-edit and post-edit boundary representations: it is a simple
rigid body motion that flips S upside-down. But this map is not consistent with the parametric change in
t, which requires that face f 1
is mapped into face f 0. While some of the proposed naming techniques will
allow such edits, we will see in section 3.4 that no change continuous in t could produce such a boundary
representation.
All boundary representations are cell complexes, and their formal properties, including validity, are rooted
in algebraic topology [14, 27]. Algebraic topology is also the proper setting for formulating BR-deformation.
Below we use a number of standard concepts (complexes, chains, continuous maps, etc.) that can be found
in many textbooks [1, 5, 17, 22]. For brevity, we only state few critical definitions and results that are
necessary for formulating and understanding the concept of BR-deformation.
Blends provide a convenient way to track the names of the edges [10]. Throughout the paper we will ignore the geometric
changes in b-rep resulting from blended edges.
2.1 Boundary representation as a cell complex
The boundary of a 3-dimensional solid is an orientable, homogeneously 2-dimensional cell complex. Internally,
every b-rep consists of an abstract (unembedded) cell complex, that captures all combinatorial relationships
between cells (vertices, edges, and faces), and geometric information that specifies the embedding for every
cell in E 3 . We do not deal with specific data structures in this paper, and therefore it is not necessary to
distinguish between the abstract cell complex and its embedding. Thus, we will assume that the boundary
of a solid S is represented by an embedded complex K (the b-rep of S).
Many different cell complexes have been used for boundary representations, including simplicial, polyhe-
dral, and CW (with cells homeomorphic to disks). Our discussion, definitions, and results are not affected
by any particular choice of a cell complex. As the example in Figure 2 illustrates, b-reps of many commercial
systems may contain more general cells, such as faces with holes, circular edges, and so on; such cell
complexes are also natural from the user's point of view. The corresponding formal definition, which we also
adopt in this work, is given by Rossignac and O'Connor in [23]: a Selective Geometric Complex (SGC) is
composed of cells that are relatively open connected submanifolds of various dimension and are assembled
together to satisfy the usual conditions of a cell complex:
1. The cells in K are all disjoint; and
2. The relative 3 boundary boe of each p-cell oe is a finite union of cells in K.
Both SGCs and our definitions are valid in n-dimensions, but for the purposes of solid modeling, we will
assume that each p-cell oe of K is a p-dimensional subset of E 3 with 3. The union of all embedded
cells is the underlying space jKj of the complex K. In particular, the set of points b(S) of every solid S is
the underlying space of some boundary representation K.
The boundary of a homogeneously p-dimensional complex K can be also characterized algebraically, as
an algebraic topological chain @C(K). The precise difference and the significance of this distinction will be
become apparent in section 3.
2.2 Cell maps and cell homeomorphisms
The cellular structure of b-reps implies the proper mechanism for defining the notion of a variational class:
we will consider the effect of a parametric change on the b-rep cell by cell. Informally, if K is the pre-edit b-
and L is the post-edit b-rep(t 1
), then the naming map g seeks to establish a correspondence between
cells in K and cells in L. So for example, when t 1
, we have and it is natural that g should be
a cell-by-cell identity mapping. When the difference t 1
is so small that none of the cells collapse, the
correspondence between the cells does not change, even though some cells may continuously change their
shapes. For example, in Figure 2(a), small changes in t correspond to a small movement of the hole on face
f 2 and therefore to a change in the shape of f 2 in the post-edit boundary representation. As the difference
larger, so does the difference between the shapes of the corresponding cells; and eventually some
cells may actually continuously collapse into some other cells. This is exactly the case in Figure 2(c) where
face f 1 and all of its bounding edges collapsed into the edge e 3 and its bounding vertices.
In other words, the cells in the post-edit b-rep L are images of continuous variations of the corresponding
cells in the pre-edit b-rep K. This cell-by-cell continuous variation is captured by the notion of a continuous
cell map (modified from [17]).
and L be two b-reps. Map called a continuous cell map
from K to L if:
1. for each cell oe 2 K, g(oe) is a cell in L;
2. dimension(g(oe)) - dimension(oe);
3. for every oe 2 K, g restricted to the closure of oe is continuous.
3 The relative boundary of a cell oe is defined as the set difference between the closure of oe and oe itself [23].
The first two conditions capture the notion of a cell-by-cell map. The third condition implies that g is a
continuous map on every cell that can also be extended to the continuous map on the whole
boundary of the solid [1, 22, 24]. By definition, continuity of g requires that g(closure(oe)) ae closure(g(oe))
for every cell oe [21]. But since K and L are finite, and jKj and jLj are closed and bounded, the stronger
condition
can be shown to hold [22, p.215].
In keeping with the common practice in topology literature, a cell map g is used to denote both a map
between two b-reps and a map between their underlying spaces, depending on the context in which it is used.
In the same spirit, we will at times abuse the notation and use oe to denote both the cell or its underlying
space, again depending on the context. Thus, cell map g plays a dual role: on the one hand, it acts as a
"naming" map and establishes the correspondence between the cells of two boundary representations; on the
other hand it guarantees the continuity of variation in the underlying space (the solid's boundary).
Before we go any further, it may be instructive to check whether naming maps can be constructed for
the examples of the previous section that are also cell maps. Consider the naming map g between the two
boundary representations of the solids in Figure 2(a) and 2(c) defined by:
and so on, i.e. the rest of the cells in Figure 2(a) map to their implied images in Figure 2(c). It is easy to
verify that g is a cell map, because it satisfies all three conditions of the definition given above: every cell
in (a) is continuously mapped to a cell in L of the same or lower dimension (note that face f 1 is mapped to
edge e 0) and the continuity condition is satisfied for every cell. In particular, note that the boundary set of
the collapsed face f 1 is mapped into the closure of e 1 .
Now consider the mapping of the same boundary representation in (a) to the one shown in Figure 2(d):
and the rest of the cells in (a) map to their appropriate images in (d). It is easy to check that g is not a
cell map; for example, the closure of face f 1
contains the edge e 1
, while e 0= g(e 1
) is not in the closure of
Referring to Figure 3, consider the mapping g given by:
where n is the number of faces and m is the number of edges respectively in the boundary representation.
This map g trivially satisfies all three required conditions and is therefore a cell map. However, there is also
another cell map h between the two boundary representations:
This cell map h maps the loop of edges around face f 1 into the loop of edges around f 2 and vice versa,
and corresponds to a rigid body rotation of 180 degrees about the shown x-axis. Thus, given two boundary
representations K and L there may be more than one valid cell map between them.
For sufficiently small parameter changes, we expect that none of the cells in the boundary representation
collapse and that there is also a one-to-one correspondence between cells in K and L. In this case, we can
strengthen the definition of a cell map:
bijective cell map called a cell homeomorphism
between jKj and jLj [22].
Notice that when g is a cell homeomorphism, the second condition in the definition of the cell map can
also be strengthened: the dimension of g(oe) must be equal to that of oe for every cell in K. For example,
both cell maps g and h, constructed above for the transformation in Figure 3, are cell homeomorphisms.
2.3 Topological and geometric deformations
In order for boundary representation L to be in the parametric family of boundary representation K, there
must exist a (not necessarily unique) cell map g from K to L. Furthermore, the principle of continuity
postulated in section 1.2 implies that when two boundary representations are in the same parametric range,
one must be continuously deformable into the other, as illustrated in Figure 4. Unfortunately, the existence
of a cell map from K to L alone is not sufficient to assure that K is deformable into L.
(a)

Figure

4: Continuous deformation from K to L
For example, even though the two boundary representations in Figure 3 are related by a cell homeomorphism
g, K cannot be deformed into L without leaving E 3 , because L is a reflection of K. We will see in
section 4 that such cell maps can be characterized and detected in a straightforward fashion. A more difficult
situation is illustrated in Figure 5. The boundary representation of two linked tori is related to the boundary
representation of the two unlinked tori by a cell homeomorphism; yet it is not possible to deform one into
another without leaving E 3 , because the continuity principle is violated for some intermediate values of the
shown parameter t. If K is a b-rep(t 0
and L is a b-rep(t 1
), then the continuity principle requires that, as t
changes from t 0 to t 1 , K continuously deforms into L. These observations motivate the following definition.
(a) Original cell complex K (b) Modified cell complex L

Figure

5: K is homeomorphic to L, but K cannot be deformed into L without leaving E 3
Definition 3 (BR-deformation) Let K, L be two boundary representations. A map
called a Boundary Representation deformation or BR-deformation of K to L if:
1. F (jKj;
2. F (jKj;
3. F (jKj; t) is a cell map that is also continuous in t 2 [0; 1].
Without loss of generality, we use symbol I in the above definition to denote the closed interval [0; 1], which
corresponds to the normalized range of valid values for the parameter t. In standard algebraic topological
terms, BR-deformation F is a homotopy [1, 17] and can be also viewed as a continuous family of cell maps
F t , for every value t 2 I. In particular, F 0 is the identity cell map and F 1 is the cell (naming) map g from
K to L.
BR-deformation captures the spirit of the postulated requirement of continuity and appears to be the
weakest possible condition. The obvious BR-deformation can be found by examination in Figure 4 for the
parametric updates shown in Figures 2. Let us consider again the typical situation illustrated in Figure 1
with pre-edit b-rep(t 0
denoted by K and post-edit b-rep(t 1
denoted by L. Only the map g between the two
boundary representations is known, and the problem is to determine whether an appropriate BR-deformation
F exists or not. If BR-deformation does exists, then we say that g is a BR-deforming map.
Definition 4 (BR-deforming map) A map g from boundary representation K to boundary representation
L is called BR-deforming if F (jKj; BR-deformation F .
If one accepts the principle of continuity and the implied definitions proposed above, then it may be
reasonable to require that a naming map g for solids in the same parametric family must be BR-deforming.
We constructed the appropriate BR-deformation in Figure 4 by examination, and it is easy to see that
no BR-deformation exists for the example in Figure 5. But our definition of BR-deformation involves
conditions not only on K and L but also on all the b-reps in the parametric range
which are typically
not known. Furthermore, such a BR-deformation need not be (and usually is not) unique. Is there a
general method for checking if a given map g is BR-deforming? For example, it may not be clear why no
appropriate BR-deformation exists for the parametric update shown in Figure 3. We will delay discussing
the sufficient conditions for existence of BR-deformation until section 5. In the next section, we discuss
necessary conditions for the existence of BR-deformation and show through examples how they can be used
in practice to distinguish b-reps which belong to the same parametric family from b-reps which do not.
Observe that boundary representations in Figures 4(a), (b) and (c) are related by a continuous family
F t of cell homeomorphisms. This corresponds to a special but common and important case of geometric
BR-deformation F . The combinatorial structure of the boundary representation K, including the dimension
of all cells, is preserved under geometric BR-deformation. On the other hand, the further deformation of the
solid in Figure 4(d) is not geometric BR-deformation, because one of the faces is continuously collapsed into
the adjacent edge and the combinatorial structure of the resulting b-rep has changed. It should be clear that
geometric BR-deformation is a special case of the more general topological BR-deformation. We shall see in
the next section that the necessary conditions for geometric BR-deformation are simpler and are easier to
test.
Necessary Conditions for BR-Deformation
3.1 Combinatorial closure and star conditions
The third condition in definition 1 of cell map g requires that g restricted to the closure of every cell is
continuous. We already used this condition to test whether the maps for the examples of section 1 are cell
maps. The closure of a cell oe in a complex K consists of oe itself and all lower dimensional cells incident on
oe. Thus, the closure of a two-dimensional face includes its bounding edges (which are often represented by
intersection of surfaces), and the closure of a vertex is the vertex itself.
To facilitate development of more convenient algorithmic tests, we now restate this condition in alternative
combinatorial terms, using the Cauchy's definition of continuity in terms of open neighborhoods [2]. The
combinatorial equivalent of a cell's open neighborhood is the star of the cell. The following definition is
modified from [9, 22] and is also consistent with definitions in [23].
Definition 5 (Star of a cell) The star of a cell oe in a complex K, denoted St(oe), is the union of oe and
all cells in K that contain oe in their boundary.
In other words, the star of a cell is the union of the cell with its neighboring higher-dimensional cells.
For example the star of the edge e 1 of the solid shown in Figure 2(a) is the union of cells
g. The
star of a vertex is a union of the vertex with all its adjacent faces and edges. The star of a face is just the
face itself, as there are no three-dimensional cells in boundary representations.
We can now restate the requirement that g restricted to the closure of oe is continuous, originally expressed
by the condition (1), to mean that every neighboring cell of oe is mapped to a neighboring cell of the image
cell g(oe) or to g(oe) itself. Remembering that some cells oe may collapse into lower-dimensional cells g(oe),
this requirement translates into a simple condition that must be satisfied by every cell[2, 22]:
The strict inclusion applies when the cell oe is mapped to a lower dimensional cell, while condition (2) becomes
an equality when the dimension of oe remains the same under the map g. In the latter case, this condition
simply means that adjacency of all cells is also preserved under the map g.
Let us consider the examples of the previous section to see how the star condition can be verified. The
naming map between solids in Figure 2(a) and Figure 2(c) takes the star of e 1
into the union of their
respective image cells fe 0; f 0g. The star of e 0is the union of cells fe 0; f 0g and the other (hidden) adjacent
face of e 0. This clearly shows that g(St(e 1 )). The star condition (2) is easily verified to hold for
other cells as well.
Now consider the mapping of the same boundary representation in Figure 2(a) to the one shown in

Figure

2(d). We already concluded earlier that this map is not a cell map because the closure condition is
violated, and this can be easily verified by the star condition. The star of e 1 is the union of cells
which are mapped to cells fe 0; e 0; f 0g. Since the star of g(e 1 ) is the union of fe 0; f 0; f 0g, it is clear that
)), and g cannot be a cell map.
3.2 Oriented cell maps
As we have seen above, the requirement on g to be a cell map is a necessary but very weak condition for
BR-deformation. The difficulty with the example in Figure 3 is that the proposed cell map from K to L does
not preserve the relative orientation between certain cells. A simpler two-dimensional example is shown in

Figure

6. A cell map defined by g(oe
0 takes the cell complex (triangle) K into its reflected copy L;
however it is not possible to continuously deform K into L without leaving E 2 .
(a) Original cell complex K (b) Modified cell complex L
f

Figure

Cell map between K and L does not preserve orientation
In order to take advantage of the orientation information, we need to slightly modify the definitions of
a cell complex and a cell map by requiring that all cells are oriented, which is usually the case in most
boundary representations. Orientation of a cell oe 2 K can be visualized as a (positive or negative) sense
of direction. More specifically, every 0-cell (vertex) can be oriented positively or negatively, orientation of
every 1-cell (edge) bounded by two vertices s and t is determined by the order of s and t, and 2-cells (faces)
can be oriented either counterclockwise (positive) or clockwise (negative). Cyclic edges that do not have
vertices can be also directed in one of two ways. Oriented cell complexes are shown in Figures 3 and 6. We
can now modify the definition of the cell map to account for orientation.
Definition 6 (Oriented Cell Map) A map is an oriented cell map if it is a cell map and
for every oriented cell oe 2 K, g(oe) is an oriented cell in L.
It can be shown that orientation is a homotopy invariant and is automatically preserved through continuity
[5], which means that every BR-deforming map is orientation preserving . In other words, the sense of
direction must be preserved at every point of the solid's boundary, and we need to assure this condition in
a cell-by-cell fashion.
Since boundary representation of every solid is orientable [14, 27], the above condition is easily enforced
on 2-cells by requiring that all faces are oriented positively (counterclockwise); we will also postulate that
all 0-cells (vertices) have positive orientation. It is more difficult to state what it means to preserve the
orientation on 1-cells; note however that orientation of a face induces orientation in its bounding edges, and
an edge orientation induces orientation in its bounding vertices. For example, in Figure 6(a) the assumed
orientation of edge e 2 is consistent with the orientation of e 2 induced by the face f . By contrast, in Figure
6(b) the orientation induced in e 0by f is opposite to the assumed orientation of e 0. A similar situation can
be observed in Figure 3 for the edges bounding face f 3 . Additional discussion and examples of assumed and
induced orientation can be found in most texts on algebraic topology, e.g. in [1].
3.3 Induced orientation condition
Informally, orientation of a cell complex K is preserved under a cell map g if g maps the oriented boundary
of every non-collapsed cell oe 2 K into the oriented boundary of the image cell g(oe) 2 L. The sole purpose of
this section is to express this statement precisely and in a computationally convenient form, using algebraic
topological chains. Given a cell complex K; a p-dimensional chain, or simply p-chain, is a formal expression
a an oe n ;
where oe i are p-dimensional cells of K and a i are integer coefficients. Two p-chains on the same cell complex
can be added together by collecting and adding coefficients on the same cells. The collection of all p-chains
on K is a group denoted by C p (K) for 3. Using chains we can replace incidence, adjacency, and
orientation computations with a simple algebra. In particular, we define the (algebraic) oriented boundary
operation in terms of chains using only three coefficients from the set f\Gamma1; 0; +1g: (Such chains are often
called elementary chains [1, 12].)
Definition 7 (Boundary of a cell) The boundary of a p-cell oe is the (p \Gamma 1)-chain consisting of all (p \Gamma 1)
cells that are faces of oe with coefficient +1 if the orientation of oe is consistent with the orientation of the
face and \Gamma1 otherwise. 4
The coefficients are the simple algebraic means to compare the assumed orientation of a cell oe with the
orientation induced in oe by an adjacent higher-dimensional cell (in the star of oe). For example, the oriented
boundary of the 1-cell e 1
in

Figure

6 is a 0-chain: @e 1
which implies that edge e 1
starts at vertex v 1
and ends at vertex v 2
. The boundary of an oriented 2-cell f in the same figure is a 1-chain:
which tells us that the directions of edges e 1
and e 2
are consistent with the counter-clockwise direction of
the face f; while the direction of the edge e 3
is not. The face f 2
in

Figure

7 has a hole and its boundary is
also a 1-chain: @f convention, the boundary of a 0-cell is defined to be 0.
(a) Top view of K (b) Top view of L
v3 v2 v8 v7

Figure

7: Top view of oriented boundary representation of the solid in Figure 2.
The definition of boundary for an individual cell oe extends linearly to the boundary of any p-chain, i.e.
an oe n is a p-chain, then it's boundary is a (p \Gamma 1)-chain
with the usual rules of chain addition. In other words, the boundary operator is a linear function @ :
4 Here we rely on standard terminology in algebraic topology: 'face of oe' refers to any lower-dimensional cell incident on cell
oe.
The above definitions give precise characterization to the informal concept of "oriented boundary of every
cell" as a chain. But the naming map g is a cell map and technically cannot be applied to chains; to see
what g does to boundaries of cells, we need to extend g to maps on chains.
Intuitively, a chain map g p takes individual p-cells (which are elementary p-chains) in K into individual
p-cells in L - just as the cell map g does when the dimension p of the cells stays the same. But g may also
collapse some p-cell oe 2 K onto a lower dimensional cell in L; since these lower dimensional cells do not
belong to any p-chains on L, the chain map is instructed to simply ignore them by setting g p
once again, we require that the action of a chain map on individual cells must extend linearly to arbitrary
p-chains. 5 Together these three conditions give the usual definition of a chain map [17]:
be a orientation preserving cell map. For each dimension p,
define a chain map
1. if oe is a p-cell in K and g(oe) is a p-cell in L, g p
2. if
3. an oe n an
Thus, any BR-deforming naming cell map g induces a family of chain maps g p in every dimension
2. It is also known [1, 5, 17] that every such family of induced chain map satisfies the following
commutative diagram:
\Gamma! C p (L)
Since an oriented cell oe can be viewed as a chain with 0 coefficients attached to all other cells in the cell
complex, the above commutative diagram can be enforced in a cell-by-cell fashion. Specifically, given an
orientation preserving cell map g, the following simple condition is satisfied for each oriented p-cell oe 2 K:
We will refer to this condition as the orientation condition, which is a precise restatement of the requirement
that g maps the oriented boundary of every non-collapsed cell oe 2 K into the oriented boundary of the
image cell g(oe) 2 L.
3.4 Examples revisited
Consider once again the examples from section 1. Technically, every naming map g consists of the vertex,
edge, and face maps. For brevity, we will only specify the action of g on those cells that are necessary for
the presentation purposes. For example, below we assume that vertices are mapped to their implied images
with a positive orientation and omit explicit description of the vertex map, even though the (chain of the)
oriented boundary of every mapped edge is determined by the vertex map.
Consider the naming map between the solids in Figure 2(a) and (c). The cells in the top view of the two
solids are shown in Figure 7. The semantics of the update collapses the face f 1
and its boundary into the
single edge e 0and its vertices. This deformation is reflected in the topological BR-deforming naming map g
as follows:
Notice that g is many-to-one and can be characterized as collapsing map. We already know from section
2.2 that g satisfies the star condition (2). Let's check if it also satisfies the necessary condition (3) in terms
of induced chains maps g 1
and
5 In other words, chain map gp is a homomorphism [17].
A simple check shows that the necessary condition (3) @(g
The rest of the cells remain topologically invariant under the naming map, and it is easy to check that the
necessary condition (3) holds for all other cells in the boundary representation.
Observe that the inverse map g \Gamma1 from the solid in Figure 2(c) to (a) is not BR-deforming; in fact it is
not a valid cell map because it maps a one-dimensional edge e 0to a two-dimensional face f 1
. Nevertheless,
such maps appear useful and are allowed in many systems. Therefore we will say that a one-to-many relation
g is a expanding map if its inverse is a collapsing BR-deforming map.
Now consider the apparent naming map between the solids in Figure 2(a) and (d):
We already know that this map g is not BR-deforming (because it is not a cell map), and it is easy to verify
that the necessary condition (3) does not hold either. The induced chain maps are:
and the left and the right hand side of the equation (3) evaluate to different chains:
Clearly, g is not collapsing map and the inverse map g \Gamma1 cannot be an expanding map.
Next consider the example in Figure 3. We described two distinct naming cell maps g and h in section
2.2 that satisfy the star condition (2). We also argued that neither of them is appropriate - but for different
reasons. We claimed that the naming map g computed by a commercial system is not BR-deforming because
it is not orientation preserving. Indeed, g k (oe) = g(oe) for all cells in the boundary representation, because no
cells have been collapsed, and in fact there is a one-to-one correspondence between the pre-edit and post-edit
boundary representations. Yet, checking the necessary condition (3) for face f 3
, we see that
Thus, @(g 2
same relation can be verified for all other faces in the boundary represen-
tation; this shows that g is orientation reversing and is not BR-deforming.
But now consider the necessary condition (3) for the second naming map h for the same solids:
and so on. Notice that h reverses the assumed orientation of all edges connecting f 1
. Checking the
necessary condition (3) on this oriented cell map:
Similarly, one can check that map h does satisfy the necessary condition (3) for all other cells in the boundary
representation and is a BR-deforming map associated with the 180 degree rotation of the solid about the
X-axis. Furthermore, h is a cell homeomorphism and is geometrically BR-deforming because it preserves
the combinatorial structure of the boundary representation, even though it may alter the geometry of some
cells. Unfortunately, this particular BR-deformation is not consistent with the intended semantics of the
parametric edit. In fact in this example, due to symmetry, there are many other geometric BR-deforming
maps (e.g. rotation about Z-axis by 90 degrees). The guarantee of BR-deformation should not be confused
with the guarantee of the correct semantics of the parametric update.
Persistent naming
4.1 Sufficient conditions for an orientation preserving cell map
In the typical scenario described in section 1, a pre-edit b-rep K and a post-edit b-rep L are given, and the
system attempts to match the cells in K with the cells in L, i.e. to construct the naming map
The matching process may or may not succeed. In terms of our definitions, there are at least three reasons
why matching may fail:
1. A BR-deforming map g may not exist, because L does not belong to the same parametric family defined
by K;
2. A BR-deforming map g does exist, but the system is not able to find it;
3. A BR-deforming map is not unique, and the system is not able to determine which map captures the
semantics of the edit. 6
Whatever the outcome of the matching may be, the correctness of the result depends critically on the
system's ability to determine if a constructed naming map is in fact BR-deforming. The formal machinery
developed above is sufficient to determine if a given map g is an orientation preserving cell map, which
is in turn a necessary condition for g to be BR-deforming. As our examples above have illustrated, these
conditions are powerful enough to detect many (but not all) invalid edits in parametric solid modeling. To
summarize, a map preserving cell map if and only if:
1. K and L are oriented consistently;
2. g is an oriented cell map;
3. if maps the oriented boundary of cell oe 2 K into the oriented boundary
of the image cell g(oe) 2 L.
The first requirement is enforced by assuming positive orientation for all vertices and faces (oriented
counter-clockwise). The second requirement reduces to either the combinatorial closure condition (1) or
the star condition (2). The third requirement is expressed by the orientation condition (3) which enforces
the relative orientation between edges, vertices, and faces. All required conditions can be easily checked
for a given map g; but it is important to understand the applicability and the limitations of the proposed
conditions.
Examples of Figures 3 and 6 may suggest that the orientation condition (3) is unnecessarily complicated
because it detects only "global" orientation reversals as shown above. But imagine the solid in Figure 3 to
be attached to a planar face of another solid (base), and now we can easily construct a local orientation
reversing map which reflects a portion of the solid's boundary. Our experience suggests that such local
reversals in orientation occur frequently in commercial systems, apparently due to partial and incremental
updates in boundary representations. Enforcing the orientation condition for all cells would eliminate this
type of invalid edit.
The orientation condition (3) may appear to imply the star condition (2), since the closure of every cell
includes its boundary points. To see why this is false, let us assume that g is an arbitrary (not necessarily
cell) map that satisfies the first two conditions of the cell map (Definition 1). We can still use g to induce
chain maps g p and use the boundary operator as before. Suppose we determine that the orientation condition
(3) holds. Does this mean that g is an orientation preserving cell map? More specifically, does this mean
that the star condition (2), or equivalently the combinatorial closure condition (1), is satisfied as well? Not
necessarily. Consider the case when g collapses a p-cell oe 2 K to a lower dimensional cell g(oe) 2 L. By
definition of a chain map, g p irrespectively of what g(oe) may be. Therefore,
it is easy to construct a map g such that condition (3) is satisfied and yet g is not a cell map. Thus, it should
be clear that the star condition and the orientation condition are not redundant for BR-deforming maps.
On the other hand, suppose that dim(oe) for all cells in K. Since g preserves the dimension
of every cell oe 2 K, the orientation condition (3) implies that 1-cells bounding every 2-cell oe 2 are in 1-to-1
6 In some cases, this is in fact the correct answer, because semantics of some edits has not been defined unambiguously.
correspondence with 1-cells bounding g(oe 2 ), and 0-cells bounding every 1-cell oe 1 are in 1-to-1 correspondence
with 0-cells bounding g(oe 1 ). In other words, g takes the closure of every cell in K to the closure of the
corresponding cell in L, which implies the closure condition in the definition of cell map and the equivalent
star condition (2).
Furthermore, recall that when none of the cells are collapsed, the (geometrically) BR-deforming map g
is a cell homeomorphism. It follows that the star condition (2) is redundant for geometrically BR-deforming
maps. Thus, to check if a map is geometrically BR-deforming, it is only necessary that none of the cells are
mapped to the cells of lower dimension and that the orientation condition (3) is satisfied for every cell.
4.2 Comparison with previously proposed naming methods
Several heuristic methods have been proposed for constructing the naming maps g [10, 11, 18, 25, 31] in a
variety of situations, including those where BR-deforming maps may not exist. A thorough analysis of all
methods would not be practical in this paper, but it is instructive to check if the proposed techniques are
consistent with our definitions when they do apply.
The naming techniques proposed by Kripac[18] and Hoffmann et al [10, 11] rely on several common
methods for naming cells in boundary representations. In particular, both start with the names of the
primitive surfaces appearing in the parametric definition and construct the names for individual cells using:
ffl the list of adjacent cells in the boundary representation;
ffl the relative orientation of the cell with respect to the adjacent cells.
In general, these two techniques are not sufficient to uniquely match cells in the two b-reps, and a number
of additional techniques must be employed. For example, [18] also uses the history of editing to distinguish
between cells, while [10] uses extended adjacency information and directional information associated with
the particular solid construction method. The two naming techniques used by both [18] and [10] intuitively
correspond respectively to the two types conditions that ensure an orientation preserving cell map. The use
of adjacent cells is a means for extending the continuity of the naming map to the whole boundary of the
solid, which relies on the combinatorial closure condition (1) and/or star condition (2). The matching of
relative orientation of cells is basically equivalent to our orientation condition (3).
On closer examination, it appears that [18] may map a cell oe 2 K to g(oe) 2 L when all cells adjacent
to oe are mapped into cells adjacent to g(oe), without considering the orientation information. But as is
clearly shown by example in Figure 3, such a naming map does not have to preserve orientation and may
not be BR-deforming. By contrast, [11] matches oe to g(oe) only if the adjacent cells also preserve orientation.
This method of naming will never result in orientation-reversing naming map. Both methods will find the
geometrically BR-deforming map, if it exists and every cell has a unique name. It is not clear whether
geomtric BR-deformation is always enforced when heuristic methods are used to resolve multiple matches
between cells with the same names.
Neither of the above methods are able to handle collapsing maps in general as defined in this paper,
because both [18] and [11] require exact match of the adjacent cells, which in turn corresponds to the
special case of exact equality in the star condition (2). For example, edge e 1
in

Figure

2(a) is adjacent
to faces f 1
and f 3
, while face f 1
is no longer present in the post-edit boundary representation of Figure
2(c). Thus, the proposed naming methods will never match e 1
to e 0, as they don't allow the strict inclusion
relation implied by condition (2). More generally, all of the proposed methods assume that the dimension of
the mapped cells will always be preserved, which is not the case for collapsing and expanding maps. Based
on our results, it seems to make sense to redefine the adjacency conditions to correspond to the star condition
(2).
Rossignac observed that when every cell in a b-rep can be represented by a Boolean (set-theoretic)
expression on primitive surfaces and halfspaces, the expression can be used as a persistent name for the
cells [31]. In fact, it appears that some commercial systems use this method of naming in simple cases with
limited success. 7 Boolean set-theoretic representations place no restrictions on the topology of the resulting
7 Constructing Boolean expressions for every cell in boundary representation is not trivial and may require a difficult construction
known as separation [33].
boundary representations, imply a very different parametric family [34], and do not provide a mechanism
for enforcing or even checking BR-deformation.
A common method of matching cells in pre-edit and post-edit b-reps, which can be observed in some
commercial systems, combines Boolean naming with the sequential ordering of the entities with respect to
some external direction. For example, a system may attempt to distinguish between edges e 1
and e 2
in

Figure

2(a) by indexing them along the length of the face (x-axis in the Figure). This method is most likely
responsible for producing the solid in Figure 2(d) instead of (c): the identification of e 1
with e 3
changes the
adjacency information so that e 0appears to be the "first" edge to fit the new name of e 1
5 Conclusion
5.1 Significance and limitations
We have argued that the proposed principle of continuity and the implied notion of BR-deformation should
be accepted as the basis for formally defining the semantics of a parametric family. Notice, however, that
BR-deformation is not an equivalence relation: it is generally not true that boundary representation K can be
deformed into L and vice versa. Thus, a parametric family of boundary representations can be defined in more
than one way. For example, we could define a parametric family to include all those boundary representations
that can be obtained by deforming one special 'master' boundary representation K. Alternatively, we could
define two boundary representations to be in the same parametric family whenever one of them can be
deformed into another. The latter definition may be more appealing because it does specify an equivalence
class of solids, but deciding membership in such a class algorithmically appears to be nontrivial.
The proposed formalism allows precise formulation and partial solution for a number of problems in
parametric modeling. For example, the problem of "persistent naming" amounts to deciding whether two
boundary representations K and L can be related by a BR-deforming map g that is consistent with the
semantics of the parametric edit, and constructing such a map.
A key computational utility for enforcing BR-deformation is the ability to decide if a given naming map
between two b-reps K and L is BR-deforming. We have argued that any such g must satisfy the following
two easily computable necessary conditions for every named (mapped) cell oe:
ffl the combinatorial adjacency (star or closure) conditions expressed by (1) and (2); and
ffl the orientation condition g p\Gamma1
Our formulations and the implied conditions do not completely solve the above problem, but they are
the strongest possible, in the sense that the formulated problem could be solved only if solid modeling
representations are enhanced with additional information that is not being used today. The main difficulty
lies in the need to know what happens to the boundary representation not only for parameter values t 0
and
, but also for all the values of t in the interval [t
]. For example, it is impossible to decide that the
two boundary representations in Figure 5 do not belong to the same parametric range without considering
the deformation process in E 3 . This is the very reason why we defined BR-deformation as a family of maps
F t from E 3 into E 3 , even though the naming map
takes jKj into jLj. To guarantee that a given
naming map g is BR-deforming, we must show that g is an orientation preserving cell map and that it can
be extended to a continuous map on the whole of E 3 . To be more precise, g will satisfy all the requirements
of BR-deforming map if there exists a continuous orientation preserving map h from E 3 to E 3 , such that h
restricted to jKj is a cell map g from jKj to jLj [1].
This sufficient condition for BR-deformation cannot be verified by considering only the structure of
the two-dimensional boundary representations. Possible approaches to constructing BR-deforming maps
include constructing the corresponding map h as a cell map on the three-dimensional decomposition of E 3
as suggested in [32, 34], or ensuring the properties of h by further restricting how g modifies individual cells
[4, 36].
Other criteria for membership in a parametric family are possible. For example, one could require only
that two boundary representations are related by an orientation preserving cell map. This would significantly
enlarge the parametric family and would immediately establish computable sufficient conditions for persistent
naming. These advantages would come at a considerable sacrifice: the loss of the physical principle of
continuous deformation between solids in the same family. Nevertheless, this may be a reasonable and
pragmatic compromise, given the difficulties of establishing BR-deformation as defined in section 2.
5.2 Semantics of more general edits
It may appear that accepting the principle of continuity and BR-deformation as a basis for parametric
modeling is too limiting because a number of practically important parametric edits cannot be described by
BR-deformation. These include merging and splitting entities in boundary representations, (dis)appearance
of holes, and common edits such as shown in Figure 8: as the slot moves to the left, the edge e 1 collapses into
vertex v 1 . But this edit cannot be described by a cell map unless the edge bounded by vertices v 1 and v 3 is
split into two edges, e 2 and e 3 , as shown in Figure 8(a). This would allow constructing a proper cell map
that takes v 5 into v 0, v 4 into v 0, and so on. But of course, vertex v 2 would not be present in most boundary
representations that rely on maximal faces [35]. Below we explain how our approach may be extended to
formally define arbitrary parametric edits.
(a) Original solid's b-rep K (b) Modified solid's b-rep L

Figure

8: A parametric edit is defined by a splitting followed by a collapse
While the notion of BR-deformation is not applicable to splitting and merging of faces and edges (such
as needed in the example of Figure 8), recall that the main purpose of an orientation-preserving cell map
was to enforce the continuity of the map in a cell-by-cell fashion; a natural extension of this
principle would allow structural changes in the cells of K and L. In particular, subdividing or merging cells
in a solid's boundary representation, e.g. as proposed in [23], has no effect on the boundary set itself (the
underlying space). Thus, it seems reasonable that we can define a more general edit that preserves the spirit
of continuous deformation by a sequence of splits, merges, and BR-deforming maps. Importantly, such edits
include significant topological changes, including elimination of holes. Figure 9 illustrates a possible two-step
procedure. First the collapsing map g takes the boundary of the hole c to a vertex c the resulting
cell complex has a 2-cell that contains an isolated 0-cell in its interior. Then the subsequent merging step
eliminates the 0-cell, without changing the underlying space.
Finally, recall that the expanding map is not BR-deforming (only its inverse is), because it is one-to-
many and is not a continuous cell map. Yet it appears that useful parametric edits require using such a
collapse merge
c c'

Figure

9: Holes can be eliminated as a two-step procedure: collapse followed by a merge
map. It may be feasible to define such edits by a sequence of maps such that each map in the sequence is
collapsing, expanding, splitting, or merging. This approach may provide great flexibility in formally defining
the semantics of parametric edits in a piecewise continuous fashion. For example, the reverse sequence of
events shown in Figure 9 would allow the introduction of holes as a two-step procedure consisting of a split
followed by an expanding map. This may also allow formally defining the semantics of feature attachment
operations without using boolean operations.
5.3 Deformations of other representations
The assumptions of continuity and continuous deformations make sense from an engineering point of view
and can serve as a starting point for developing universal standards in parametric modeling. The proposed
definition of BR-deformation and the implied necessary conditions can be employed in numerous other
applications, including shape optimization, tolerancing, and constraint solving. For example, some heuristic
methods proposed in [6] for identifying the correct solutions in constraint solving resemble the necessary
conditions implied by our definitions, and the use of homotopy was also proposed in [19].
The principle of continuity is stated in terms of a particular representation scheme for solids. The
same principle of continuity could be used to develop notions of parametric families with respect to other
representation schemes. For example, it may be feasible to define a parametric family with respect to CSG
representations [34], in which case the Boolean naming [31] may indeed correspond to a class of appropriately
defined continuous deformations.
The obvious and useful extension of our work is to general n-dimensional cellular models of pointsets,
such as those represented by Selective Geometric Complexes [23] and more recently advocated by others
[8, 26]. It should be intuitively clear that such cellular structures can be constructed and transformed
into each other by combinations of expanding, collapsing, splitting, and merging maps. The cellular data
structures (including boundary representations) are commonly supported by a number of so-called Euler
operators [7, 20] that create, modify, and eliminate cells or collection of cells (loops, shells, rings, wedges,
etc. Though the Euler operators are assumed to operate continuously on the underlying space of the cell
complex, the continuity conditions are rarely enforced. The concepts of continuity, orientation preserving
cell map, continuous deformation, and chain map apply to all cellular models without any modifications.
Furthermore, the identified necessary conditions for deformation, including the star condition (2) and the
orientation condition (3), hold as well.

Acknowledgements

This research is supported in part by the National Science Foundation CAREER award DMI-9502728 and
grant DMI-9522806. The authors are grateful to Tom Peters, Malcolm Sabin, Neil Stewart, and Victor
Zandy for reading the earlier drafts of this paper and suggesting numerous improvements.


--R

Algebraic Topology.
Combinatorial Topology
Polyhedral perturbations that preserve topological form.

Basic Topology.
A geometric constraint solver.
Stepwise construction of polyhedra in geometric modeling.
A geometric interface for solid modeling.
Introductory Topology.
Generic naming in generative
On editability of feature-based design
Dover Publications
A road map to solid modeling.
Morgan Kaufman
On semantics of generative geometry representations.
Parametric and Variational Design.
Topology of Surfaces.
A mechanism for persistently naming topological entities in history-based parametric solid models
Solving geometric constraints by homotopy.
An Introduction to Solid Modeling.
Topology A First Course.
Elements of Algebraic Topology.
SGC: A dimension independent model for pointsets with internal structures and incomplete boundaries.
Lectures in Algebraic Topology.
Breps as displayable-selectable models in interactive design of families of geometric objects
The generic geometric complex (GGC): a modeling scheme for families of decomposed pointsets.
Mathematical models of rigid solid objects.
Representations for rigid solids: Theory
Representation of tolerances in solid modeling: Issues and alternative approaches.
Issues in feature-based editing and interrogation of solid models
CSG formulations for identifying and for trimming faces of CSG models.
Maintenance of geometric representations through space decompositions.
Separation for boundary to CSG conversion.
What is a parametric family of solids?
Alternative definitions of faces in boundary representations of solid objects.
Sufficient condition for correct topological form in tolerance specification.
--TR
Introduction to Solid Modeling
Geometric and solid modeling: an introduction
Separation for boundary to CSG conversion
What is a parametric family of solids?
Solving geometric constraints by homotopy
Polyhedral perturbations that preserve topological form
The generic geometric complex (GGC)
Representations for Rigid Solids: Theory, Methods, and Systems
A Road Map To Solid Modeling

--CTR
Hilderick A. van der Meiden , Willem F. Bronsvoort, Solving topological constraints for declarative families of objects, Computer-Aided Design, v.39 n.8, p.652-662, August, 2007
Frank Y. Shih , Vijayalakshmi Gaddipati, Geometric modeling and representation based on sweep mathematical morphology, Information SciencesInformatics and Computer Science: An International Journal, v.171 n.1-3, p.213-231, 4 March 2005
Hilderick A. van der Meiden , Willem F. Bronsvoort, Tracking topological changes in feature models, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
Hilderick A. van der Meiden , Willem F. Bronsvoort, Solving topological constraints for declarative families of objects, Proceedings of the 2006 ACM symposium on Solid and physical modeling, June 06-08, 2006, Cardiff, Wales, United Kingdom
Srinivas Raghothama , Vadim Shapiro, Models and representations for families of parts, From geometric modeling to shape modeling, Kluwer Academic Publishers, Norwell, MA, 2002
Thomas Convard , Patrick Bourdot, History based reactive objects for immersive CAD, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
K. Y. Lee , C. G. Armstrong , M. A. Price , J. H. Lamont, A small feature suppression/unsuppression system for preparing B-rep models for analysis, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.113-124, June 13-15, 2005, Cambridge, Massachusetts
David Marcheix , Guy Pierra, A survey of the persistent naming problem, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrcken, Germany
Srinivas Raghothama, Constructive topological representations, Proceedings of the 2006 ACM symposium on Solid and physical modeling, June 06-08, 2006, Cardiff, Wales, United Kingdom
Srinivas Raghothama , Vadim Shapiro, Consistent updates in dual representation systems, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.65-75, June 08-11, 1999, Ann Arbor, Michigan, United States
Guillaume Caumon , Charles H. Sword, Jr. , Jean-Laurent Mallet, Constrained modifications of non-manifold B-reps, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
Srinivas Raghothama , Vadim Shapiro, Topological framework for part families, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrcken, Germany
parametric editing;boundary deformation;cell complex;algebraic topology;persistent naming;soild modeling;boundary representation