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
Solid modeling techniques
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.
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 L1, L2 and L3,
the angles between the lines, and the radius R and the center P1 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: L1 shares a
vertex (point) with L2 and ; L2 shares a vertex with L1
and ; L3 shares a vertex with L2
and ; L1 and L3 do not
overlap; P1 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.
Characteristics of solid
software also has the following five characteristics to enhance the efficiency
and productivity of the solid modeling process:
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.
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”
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. ◇
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
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
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.
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.
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.
Properties of representation
that a solid model or an abstract solid should capture mathematically can be
stated as follows:
Rigidity. This implies that the shape of a solid model is invariant and does not
depend on the model location or orientation in space.
Homogeneous three-dimensionality. Solid boundaries must be in contact with the
interior. No isolated or dangling boundaries (see Figure2) should be permitted.
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.
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.
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
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
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 (B-rep)
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.
4.1 Topologicl and geometrical information of B-rep
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
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. ◇
4.2 Primitives of B-rep
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
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
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.
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.
4.3 Euler’s Law
Euler (in 1752)
proved that polyhedra are topologically valid if they satisfy the following
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.
satisfy the following Euler’s law:
Figure 5. Open polyhedral objects
4.4 Exact B-rep and faceted B-rep
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
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
3.5 Advantages and disadvantages of B-rep
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
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