//Logo Image
**Last updated: Yeh-Liang Hsu (2010-11-25).**

**Note: This is the course material for “ME550 Geometric modeling and
computer graphics,” Yuan Ze University. Part of this material is adapted from ***CAD/CAM
Theory and Practice*, by Ibrahim Zeid, McGraw-Hill, 1991. This material is
be used strictly for teaching and learning of this course.

# Solid modeling techniques and boundary representation

## 1.
Solid modeling techniques

## 2.
Characteristics of solid
modeling software

### (1)
Feature-based modeling

### (2)
Constraint-based modeling

**◇****Assignment 1**

### (3)
Parametric modeling

### (4)
History-based modeling

### (5)
Associative modeling

**◇****Assignment 2**

## 3.
Properties of representation
schemes

**◇****Assignment 3**

## 4.
Boundary Representation (B-rep)

### 4.1 Topologicl and geometrical information of B-rep

**◇****Assignment 4**

### 4.2 Primitives of B-rep

### 4.3 Euler’s Law

### 4.4 Exact B-rep and faceted B-rep

**◇****Assignment 5**

**◇****Assignment 6**

### 3.5 Advantages and disadvantages of B-rep

**Solid modeling techniques are based on informationally
complete, valid and unambiguous representations of objects.** Simply stated, **a complete geometric data representation of an object is one
that enables points in space to be classified relative to the object, if it is
inside, outside, or on the object**. This classification is sometimes called **spatial addressability**. Both
wireframe and surface models are incapable of handling spatial addressability
as well as verifying that the model is well formed. The latter meaning that
these models cannot verify whether two objects occupy the same space.

User input required
to create solid models on existing CAD/CAM systems depends on both the internal
representation scheme used by each system as well as the user interface. It is
crucial to distinguish between **the user interface and the internal data representation** of a given CAD/CAM system. The two are quite separate aspects of
the systems and can be linked together by software that is transparent to the
user. **For example,
a system that has a B-rep (boundary representation) internal data
representation may use a CSG (constructive solid geometry)-oriented user
interface**; that is, input a solid model by its
primitives. Most systems use the building-block approach (CSG oriented) and
sweep operations as the basis for user interface.

Solid modelers
store more information (geometry and topology) than wireframe or surface
modelers (geometry only). **Geometry** (sometimes called metric information) **is the actual dimensions that define the entities of the
object****.** The geometry that defines the
object shown in Figure1 is the lengths of lines *L*_{1}, *L*_{2} and *L*_{3},
the angles between the lines, and the radius *R* and the center **P**_{1} of the
half-circle. **Topology** (sometimes called combinatorial structure), on the other hand, **is the connectivity and associativity
of the object entities**. It has to do with the notion of neighborhood; that is, it determines the
relational information between object entities. The topology of the object
shown in Figure1(b) can be stated as follows: *L*_{1} shares a
vertex (point) with *L*_{2} and _{}; *L*_{2} shares a vertex with *L*_{1}
and _{}; *L*_{3} shares a vertex with *L*_{2}
and _{}; *L*_{1} and *L*_{3} do not
overlap; **P**_{1} lies outside the object.

Figure 1. Difference between geometry and topology
of an object

Based on these definitions, neither geometry
nor topology alone can completely model objects. **Wireframe and surface models deal only with geometrical
information of objects**, and are therefore considered incomplete and ambiguous. From a user
point of view, geometry is visible, and **topology is considered to be nongraphical relational
information that is stored in solid model databases and is not visible to users**.

Solid modeling software also has the following five characteristics to enhance the efficiency and productivity of the solid modeling process:

In feature-based modeling, a solid model is created and modified in a way that represents how geometries are created using common manufacturing processes. A base feature is a solid model that is roughly the size and shape of the part that is to be modeled. It can be thought of as the initial work block. All subsequent features reference the base feature either directly or indirectly. Additional features shape or refine the base feature.

Features in a part have a direct analogy to geometries that can be manufactured or machined. This gives the engineer the ability to easily create and modify common manufactured features. As a result, planning the manufacture of a part is facilitated by the correspondence between the features and the processes required to make them.

Constraint-based modeling permits the engineer or designer to incorporate “intelligence” into the design. Often this is referred to as design intent. The initial sketch of a two-dimensional profile in constraint-based solid modeling does not need to be created with a great deal of accuracy. It just needs to represent the basic geometry of the cross section. The exact size and shape of the profile is defined through assigning enough parameters to fully “constrain” it. For example, if a hole is constrained to be at a certain distance from an edge, it will automatically remain at that distance from the edge, even if the edge is moved. If the edge were moved, the hole location would need to be respecified so that the hole remains the same distant from the edge. The advantage of constraint-based modeling is that the design intent of the engineer remains intact as the part is modified.

There are two primary types of constraints. Dimensional constraints are used to specify distances between items in a solid model. Geometric constraints define positional relationships between entities in the model in terms of the geometry. Examples of geometric constraints include tangency, parallelism, symmetry, concentricity, and so on. Typically, a combination of dimensional constraints and geometric constraints are used to fully “constrain” a part.

Create a simple solid model, a base feature with a
through hole for example, using your CAD software. Explore and describe the
feature-based and constraint-based modeling features in your CAD software. ◇

Parametric modeling means that parameters of the model may be modified to change the geometry of the model. A dimension is a simple example of a parameter. When a dimension is changed, the geometry of the part is updated. Thus, the parameter drives the geometry.

An additional feature of parametric modeling is that parameters can reference other parameters through relations or equations. The power of this approach is that when one dimension is modified, all linked dimensions are updated according to specified mathematical relations, instead of having to update all related dimensions individually.

The last aspect of solid modeling is that the order in which parts are created is critical. This is known as history-based modeling. For example, a hole cannot be created before a solid volume of material in which the hole occurs has been modeled. If the solid volume is deleted, then the hole is deleted with it. This is known as a parent-child relation. The child (hole) cannot exist without the parent (solid volume) existing first.

Parent-child relations are critical to maintaining design intent in a part. Most solid modeling software recognizes that if you delete a feature with a hole in it, you do not want the hole to remain floating around without being attached to the feature. Consequently, careful thought and planning of the base feature and initial additional features can have a significant effect on the ease of adding subsequent features and making modifications.

The associative character of solid modeling software causes modifications in one object to “ripple though” all associated objects. For instance, suppose that you change the diameter of a hole on the engineering drawing that was created based on your original solid model. The diameter of the hole will be automatically changed in the solid model of the part, too. In addition, the diameter of the hole will be updated on any assembly that includes that part. Similarly, changing the dimension in the part model will automatically result in updated values of that dimension in the drawing or assembly incorporating the part. This aspect of solid model software makes the modification of parts much easier and less prone to error.

Using the same solid model created in Assignment 1,
explore and describe the parametric, history-based feature-based (parent-child
relation) and associative modeling features in your CAD software. ◇

As a result of being feature based, constraint based, parametric, history based, and associative, modern solid modeling software captures “design intent”, not just the design. This comes about because the solid modeling software incorporates engineering knowledge into the solid model with features, constraints, and relationships that preserve the intended geometric relationships in the model.

The properties that a solid model or an abstract solid should capture mathematically can be stated as follows:

(1)
**Rigidity.** This implies that the shape of a solid model is invariant and does not
depend on the model location or orientation in space.

(2)
**Homogeneous three-dimensionality.** Solid boundaries must be in contact with the
interior. No isolated or dangling boundaries (see Figure2) should be permitted.

(3)
**Finiteness and finite describability.** The former property means that
the size of the solid is not infinite while the latter ensures that a limited
amount of information can describe the solid. The latter property is needed in
order to be able to store solid models into computers whose storage space is
always limited. It should be noted that the former property does not include
the latter and vice versa. For example, a cylinder that may have a finite
radius and length may be described by an infinite number of planar faces.

(4)
**Closure under rigid motion and regularized Boolean operations.** This property ensures that
manipulation of solids by moving them in space or changing them via Boolean
operations must produce other valid solids.

(5)
**Boundary determinism.** The boundary of a solid must contain the
solid and hence must determine distinctively the interior of the solid.

Figure 2. Example of isolated boundaries

Various
representation schemes have been designed and developed, with the above
properties in mind, to create solid models of real objects. Nine schemes can be
identified. Some of them are more popular than the others. These are
halfspaces, boundary representation (B-rep), constructive solid geometry (CSG),
sweeping, analytic solid modeling, cell decomposition, spatial enumeration,
octree encoding, and primitive instancing. **The three most popular schemes are B-rep, CSG, and
sweeping.**

**Representations of solids are built and invoked via
algorithms.** An algorithm is a procedure that takes
certain input and produces a desired output. Algorithms can be classified into
three types according to their input and output.** ****Some algorithms take data and produce representations**; that is, *a*: data è rep
(reads as algorithm *a* is defined as taking data and producing
representation). Representation schemes mentioned above fall into this type. **The other type of algorithms compute
property values by taking a representation and producing data;** that is, *a*: rep è data.
All application algorithms belong to this type. For example, a mass property algorithm
takes a solid model representation and produces volume, mass, and inertial
properties. **Algorithms of
the third type take representations and produce representations;** that is, *a*: rep è rep.
For example, an algorithm that converts CSG to B-rep or one that simulates
(models) processes (such as motion or machining) on objects belongs to this
type. An algorithm might take a piece of stock and end up with a machined part.

Check out your CAD software. Are there any algorithms
compute property values by taking a representation and producing data? Are
there any algorithms take representations and produce representations? ◇

Boundary
representation is one of the two most popular and widely used schemes to create
solid models of physical objects. **A B-rep model or boundary model is based on the topological
notion that a physical object is bounded by a set of faces.** These faces are regions or subsets of **closed and orientable surfaces**.
A closed surface is one that is continuous without breaks. **An orientable surface is one in which
it is possible to distinguish two sides by using the direction of the surface
normal to point to the inside or outside of the solid model under construction****.** Each
face is bounded by edges and each edge is bounded by vertices. **Thus, topologically, a boundary model
of an object is comprised of faces, edges, and vertices of the object linked
together in such a way as to ensure the topological consistency of the model.**

The database of
a boundary model contains both its topology and geometry. **Topology is created by performing
Euler operations and geometry is created by performing Euclidean calculations.** Euler operations are used to create, manipulate, and edit the
faces, edges, and vertices of a boundary model as the set (Boolean) operations
create, manipulate, and edit primitives of CSG models. **Euler operators**, as Boolean operators, **ensure the integrity** (closeness, no
dangling faces or edges, etc.) **of boundary models.** **They offer a mechanism to check the
validity of these models.**** **Geometry includes coordinates of
vertices, rigid motion and transformation (translation, rotation, etc.), and
metric information such as distances, angles, areas, volumes, and inertia
tensors. It should be noted that topology and geometry are interrelated and
cannot be separated entirely. Both must be compatible otherwise nonsense
objects may result. Figure3 shows
a square which, after dividing its top edges by introducing a new vertex, is
still valid topologically but produces a nonsense object depending on the
geometry of the new vertex.

Figure 3. Effect of topology and geometry on boundary models

In your CAD software, can you build a block strictly using boundary representation? That is, define 8 vertices, connect them to form 12 edges, then define 6 closed, orientable surfaces to form the block. Render the block to show that your block is defined correctly. ◇

If a solid
modeling system is to be designed, the **domain** of its representation
scheme (objects that can be modeled) must be defined, **the basic elements** (primitives) needed to cover such modeling domain must be
identified, **the proper
operators** that enable the system users to build
complex objects by combining the primitives must be developed, and finally **a suitable data structure** must be designed to store all relevant data and information of the
solid model.

**Objects that are often encountered in engineering
applications can be classified as either polyhedral or curved objects.** A polyhedral object (plane-faced polyhedron) consists of planar
faces (or sides) connected at straight (linear) edges which, in turn, are
connected at vertices. A cube or a tetrahedron is an obvious example. A curved
object (curved polyhedron) is similar to a polyhedral object but with curved
faces and edges instead.

The reader might
have jumped intuitively to the conclusion that the primitives of a B-rep scheme
are faces, edges, and vertices. This is true if we can answer the following two
questions. First, what is a face, edge, or a vertex? Second, knowing the answer
to the first question,** **how can we know that when we
combine these primitives we would create valid objects?

**Polyhedral objects can be classified into four classes.** The first class is the simple polyhedra. The second class
(Figure4(b)) is similar to the first with the exception that a face may be
bounded by more than one loop of edges. The third class (Figure4(c)) includes
objects with holes that do not go through the entire object. The fourth and the
last class includes objects that have holes that go through the entire objects.
Topologically, these through holes are called handles.

With the above
physical insight, let us define the primitives of a B-rep scheme. **A vertex**
is a unique point (an ordered triplet) in space. **An edge** is a finite,
non-self-intersecting, directed space curve bounded by two vertices that are
not necessarily distinct. **A face** is defined as a finite
connected, non-self-intersecting, region of a closed oriented surface bounded
by one or more loops. **A loop** is an ordered alternating
sequence of vertices and edges. A loop defines a non-self-intersecting, piecewise,
closed space curve which, in turn, may be a boundary of a face. In Figure4(a),
each face has one loop while the top and the right side faces of the object
shown in Figure4(b) have two loops each (one inner and one outer). **A handle**
(or through hole) is defined as a passageway that pierces the object
completely. **The
topological name for the number of handles in an object is genus.** The last item to be defined is **a body** (sometimes called a
shell). It is a set of faces that bound a single connected closed volume. Thus
a body is an entity that has faces, edges, and vertices. A minimum body is a
point. Topologically this body has one face, one vertex, and no edges. The
object on the right of Figure4(c) has two bodies (the exterior and interior
cubes) and any other object in Figure4 has only one body.

Figure 4. Types of polyhedral objects

Faces of boundary models possess certain essential properties and characteristics that ensure the regularity of the model; that is, the model has an interior and a boundary. Faces are two-dimensional homogeneous regions so they have areas and no dangling edges. In addition, a face is a subset of some underlying closed oriented surface. At each point on the face, there is a surface normal N that has a sign associated with it to indicate whether it points into or away from the solid interior.

In traversing loops, the edges of the face outer loop is traversed, say, in a counterclockwise direction and the edges of the inner loops are traversed in the opposite direction, say the clockwise direction.

Euler (in 1752) proved that polyhedra are topologically valid if they satisfy the following equation:

_{} (1)

where* F*,*
E*,* V*,* L*,* B*,
and *G* are the number of faces, edges,
vertices, faces’ inner loop, bodies, and genus respectively. Eq.(1) is known as
the **Euler or Euler-Poincare law**.

Open objects satisfy the following Euler’s law:

_{} (2)

Figure 5. Open polyhedral objects

The boundary
model of a sphere has one face and one vertex. We now turn from polyhedral
objects to curved objects such as cylinders and spheres. As shown in Figure 6,
the boundary model of a cylinder has three faces (top, bottom, and cylindrical
face itself), two vertices, and three edges connecting the two vertices. The
other “edges” are for visualization purposes. They are called **silhouette** edges.

Figure 6. Exact B-rep of a cylinder and a sphere

Make a table to list *F*,*
E*,* V*,* L*,* B*,
and *G* of the 9 objects in Figure 4. Show
that all 9 objects of Figure 4 satisfy the Euler law in Equation (1). Make a
table to list *F*,*
E*,* V*,* L*,* B*,
and *G* of the objects in Figure 5 and
6. Show that all objects of Figure 5 and 6 satisfy the Euler law in Equation
(2). ◇

If the curved
objects are represented by storing the equations of the underlying curves and
surfaces of the object edges and faces respectively, the resulting boundary
scheme is known as an** ****exact B-rep scheme**. Another
alternative is the approximate or faceted B-rep. In this scheme, any curved
face is divided into planar facets－hence the name **faceted B-rep**.

Can you construct a solid object that contains a B-spline
surface using your CAD software? Display this object and discuss whether it’s
an exact B-rep or a faceted B-rep. ◇

Figure 7. Faceted B-rep of a cylinder and a sphere

The B-rep scheme
is very popular and has a strong history in computer graphics because **it is closely related to traditional
drafting**. Its main advantage is that** ****it is very appropriate to construct solid models of
unusual shapes** that are difficult to build using
primitives.

Another major
advantage is that **it is relatively simple to convert a B-rep model into a
wireframe model** because the model's boundary
definition is similar to the wireframe definition.

One of the major
disadvantages of the boundary model is that **it requires large amounts of storage** because it stores the explicit definition of the model boundaries. **It is also a verbose scheme**－more verbose than CSG. The model is
defined by its faces, edges, and vertices which tend to grow fairly fast for
complex models. If B-rep systems do not have a CSG-compatible user interface,
then **it becomes
slow and inconvenient to use Euler operators in a design and production
environment**.