//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

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 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.

2.    Characteristics of solid modeling software

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

(1)     Feature-based modeling

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.

(2)     Constraint-based modeling

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.

Assignment 1

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.

(3)     Parametric modeling

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.

(4)     History-based modeling

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.

(5)     Associative modeling

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.

Assignment 2

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.

3.    Properties of representation schemes

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.

Assignment 3

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?

4.    Boundary Representation (B-rep)

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.

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 boundary models

Assignment 4

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 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.

4.3 Euler’s Law

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

4.4 Exact B-rep and faceted B-rep

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

Assignment 5

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 facetshence the name faceted B-rep.

Assignment 6

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 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 schememore 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.