AML710 CAD

LECTURE 31

Solid Modeling Techniques

Half Spaces Boundary Representation (B-rep)

Half Spaces
Half spaces form a basic representation scheme for bounded solids.

A half space is a regular point set in E3 and is given by:

H = {P : P E 3 and f ( P) < 0}
A planar half space is represented as:

H = {( x, y, z ) : z < 0}
YL XL

ZL

Planar Half Space

Classification: Unevaluated boundary based, spatial based

Half Spaces
A cylindrical Half Space is a given by:

H = {( x, y, z ) : x 2 + y 2 < R 2 }

YL
R

XL

ZL

Cylindrical Half Space

Half Spaces
A spherical Half Space is a given by:

H = {( x, y, z ) : x 2 + y 2 + z 2 < R 2 }

YL
R

XL

ZL Spherical Half Space

Half Spaces
A conical Half Space is a given by:

H = {( x, y, z ) : x 2 + y 2 < (tan( / 2) z ) 2 }

YL XL

ZL

Conical Half Space

Half Spaces
A toroidal Half Space is a given by:
2 2 H = {( x, y, z ) : ( x 2 + y 2 + z 2 R2 R12 < 4 R2 ( R12 z 2 )}

YL
R1 R2

XL

ZL

Toroidal Half Space

Constructing Solids with Half Spaces

Complex objects can be modeled by combining Half Space using set operations

n S = U H I i i =0

Constructing solids with Half Space

Advantages and Disadvantages of Half Spaces

Advantages: The main advantage is its conciseness of representation compared to other modeling schemes. It is the lowest level representation available for modeling a solid object

Disadvantages: The representation can lead to unbounded solid models as it depend on user manipulation of half spaces The modeling scheme is cumbersome for ordinary users / designers

Boundary Representation (B-rep)

Closed Surface: One that is continuous without breaks. Orientable Surface :One in which it is possible to distinguish two sides by using surface normals to point to the inside or outside of the solid under consideration. Boundary Model :Boundary model of an object is comprised of closed and orientable faces, edges and vertices. A database of a boundary model contains both its topology and geometry. Topology :Created by Euler operations Geometry :Includes coordinates of vertices, rigid motions and transformations

Boundary Representation (B-rep)

Involves surfaces that are
closed, oriented manifolds embedded in 3-space

A manifold surface:
each point is homeomorphic to a disc

A manifold surface is oriented if:

any path on the manifold maintains the orientation of the normal

An oriented manifold surface is closed if:

it partitions 3-space into points inside, on, and outside the surface

A closed, oriented manifold is embedded in 3space if:

Geometric (and not just topological) information is known

Adjacency Topology in B-rep

VV VE VF

EV

EE

EF

FV

FE

FF

Topological Atlas and Orientability

The simplest data structure keeps track of adjacent edges. Such a data structure is called an atlas.
A

Topological Atlas of a Tetrahedron

Topological Atlas and Orientability

The orientability indicated with arrows or numbers as shown below. We see that the orienation preserving arrows are in two opposite rotational directions i.e., clockwise and anticlockwise. While orienation reversing arrows are in the same rotational directions.
1 2 3 4 5 6 1 2 3 4 5 6

1 2 3 4 5 6 Orientation Preserving

6 5 4 3 2 1 Orientation Reversing

Schlegel Diagrams
A common form of embedding graphs on planar faces is called Schlegel Diagram. It is a projection of its combinatorial equivalent of the vertices, edges and faces of the embedded boundary graph on to its surface. Here the edges may not cross except at their incident vertices and vertices may not coincide.
e5 e9 e1 e8 e4 e3 e12 e7 Schlegel Diagram of a Cube e11 e2 e6 e10

Atlas of Cube
An atlas of a cube can also be given by the arrangement of its faces as shown below

1 0 2 3 4 3 5 2 1

Atlas of Cube

Some Examples of Atlases

While orienation reversing arrows are in the same rotational directions.

Cylinder

Mobius Strip

Can you think of the atlases of Torus ? Klein bottle ?

Boundary Representation (B-rep)

Non-manifold surfaces

Non-oriented Manifolds

Moebius strip

Klein bottle

Object Modeling with B-rep

Both polyhedra and curved objects can be modeled using the following primitives
Vertex: A unique point (ordered triplet) in space. Edge :A finite, non-selfintersecting directed space curve bounded by two vertices that are not necessarily distinct. Face :Finite, connected, non-selfintersecting region of a closed, orientable surface bounded by one or more loops. Loop :An ordered alternating sequence of vertices and edges. A loop defines non-self intersecting piecewise closed space curve which may be a boundary of a face. Body :An independent solid. Sometimes called a shell has a set of faces that bound single connected closed volume. A minimum body is a point (vortex) which topologically has one face one vortex and no edges. A point is therefore called a seminal or singular body. Genus :Hole or handle.

Boundary Representation
E=4 V =4 F =1
Original object

E =5 V =5 F =1

E =5 V =5 F =1

Nonsense object Euler Operations (Euler Poincare Law): The validity of resulting solids is ensured via Euler operations which can be built into CAD/CAM systems. Volumetric Property calculation in B-rep: It is possible to compute volumetric properties such as mass properties (assuming uniform density) by virtue of Gauss divergence theorem which converts volume integrals to surface integrals.

Modified objects

10

Leonhard Euler (1707 1783) Henri Poincar (1854 1912)

Euler-Poincare Law
Euler (1752) a Swiss mathematician proved that polyhedra that are homomorphic to a sphere are topologically valid if they satisfy the equation:

F E + V L = 2( B G ) F E +V = 2 F E +V L = B G
F=Face B=Bodies E=Edge L=Faces inner Loop

General Simple Solids Open Objects

V=Vertices G=Genus

11

Euler Operations
A connected structure of vertices, edges and faces that always satisfies Eulers formula is known as Euler object. The process that adds and deletes these boundary components is called an Euler operation Applicability of Euler formula to solid objects:
At least three edges must meet at each vertex. Each edge must share two and only two faces All faces must be simply connected (homomorphic to disk) with no holes and bounded by single ring of edges. The solid must be simply connected with no through holes

Validity Checking for Simple Solids

F E + V = 2 Simple Solids
E = 10 V =6 F =6 6 10 + 6 = 2
E = 12 V =8 F =6 6 12 + 8 = 2

E =8 V =5 F =5 58+5 = 2
E = 24 V = 16 F = 10 10 24 + 16 = 2

12

Validity Checking for Simple Solids

F E + V = 2 Simple Solids

E =3 V =2 F =3 33+ 2 = 2

E=2 V =2 F =2 22+2 = 2

E=2 V =2 F =2 22+2 = 2

Loops (rings),Genus & Bodies

Genus zero

Genus one

Genus two

One inner loop

13

Validity Checking for Polyhedra with inner loops

F E + V L = 2( B G )
E = 36 F = 16 V = 24 L=2 B =1 G=0 16 36 + 24 2 = 2(1 0) = 2

General

Validity Checking for Polyhedra with holes

F E + V L = 2( B G )
E = 24 F = 12 V = 16 L=0 B=2 G=0 12 24 + 16 0 = 2(2 0) = 4

General

Interior hole (void)

E = 24 V = 16 B =1
Surface hole

F = 11 L =1 G=0

11 24 + 16 1 = 2(1 0) = 2

14

Validity Checking for Polyhedra with through holes (handles)

F E + V L = 2( B G )
E = 24 F = 10 V = 16 L=2 B =1 G =1 10 24 + 16 2 = 2(1 1) = 0

General

Through hole Handles/through hole Wireframe polyhedra Lamina polyhedra

E = 48 F = 20 V = 32 B =1 L=4 G =1

20 48 + 32 4 = 2(1 1) = 0

Validity Checking for Open Objects

F E +V L = B G

Shell polyhedra

Open three dimensional polyhedra

15

Exact Vs Faceted B-rep Schemes

Exact B-rep: If the curved objects are represented by way of equations of the underlying curves and sufraces, then the scheme is Exact B-rep. Approximate or faceted B-rep :In this scheme of boundary representation any curved face divided into planar faces. It is also know as tessellation representation.

Exact B-rep: Cylinder and Sphere

Faceted cylinder and sphere

Data structure for B-rep models

F E + V L = 2( B G )
Topology Object Body Genus Face Loop Edge Vertex Underlying curve equation Point coordinates Underlying surface equation Topology

General

16

Winged Edge Data structure

All the adjacency relations of each edge are described explicitly. An edge is adjacent to exactly two faces and hence it is component in two loops, one for each face. Successor 1 Predecessor 2
v2

F1 F1 E F2

F2

v1

Predecessor 1

Successor 2

As each face is orientable, edges of the loops are traversed in a given direction. The wingded edge data structure is efficient in object modifications (addition, deletion of edges, Euler operations).

Building Operations
F E + V L = 2( B G )
Operation Initiate Database and begin creation Create edges and vertices Create edges and faces Operator MBFV MEV MEKL MEF MEKBFL MFKLG KFEVMG KFEVB MME ESPLIT KVE Complement KBFV KEV KEML KEF KEMBFL KFMLG MFEVKG MFEVB KME ESQUEEZE

General
Description Make Body Face Vertex Make Edge Vertex Make Edge Kill Loop Make Edge Face Make Edge Kill Body, Face Loop Make Edge Kill Loop Genus Kill Face Edge Vertex Make Genus Kill Face Edge Vertex Body Make Multiple Edges Edge Split Kill Vertex Edge

The basis of the Euler operations is the above equation. M and K stand for Make and Kill respectively.

Glue Composite Operations

17

Transition States of Euler Operations

F E + V L = 2( B G ) General
While creating B-rep models at each stage we use Euler operators and ensure the validity.
Operator MBFV MEV MEKL MEF MEKBFL MFKLG KFEVMG KFEVB MME ESPLIT KVE F 1 0 0 1 -1 1 -2 -2 0 0 -(n-1) E 0 1 1 1 1 0 -n -n n 1 -n V 1 1 0 0 0 0 -n -n n 1 -1 L 0 0 -1 0 -1 -1 0 0 0 0 0 B 1 0 0 0 -1 0 0 -1 0 0 0 G 0 0 0 0 0 -1 1 0 9 9 9

F E + V L = 2( B G )
MBFV

Euler Operations

MEV KEV MEKL KEML

MEF KEF

18

F E + V L = 2( B G )
MEKBFL KEMBFL

Euler Operations

MFKLG KFMLG

GLUE(KFEVMG) UNGLUE(MFEVKG)

F E + V L = 2( B G )
GLUE(KFEVB)

Euler Operations

B
UNGLUE(MFEVB)

MME KME MME KME KVE

19

Building operations
MME

MBFV

MEF

MME

MEF, MEF, MEF, MEF, MEF

Merits and Demerits of Euler Operations

If the operator acts on a valid topology and the state transition it generates is valid, then the resulting topology is a valid solid. Therefore, Eulers law is never verified explicitly by the modeling system. Merits:
They ensure creating valid topology They provide full generality and reasonable simplicity They achieve a higher semantic level than that of manipulating faces, edges and vertices directly

Demerits :
They do not provide any geometrical information to define a solid polyhedron They do not impose any restriction on surface orientation, face planarity, or surface self intersection

20

Advantages and Disadvantages of B-rep

Advantages:
It is historically a popular modeling scheme related closely to traditional drafting It is very appropriate tool to construct quite unusual shapes like aircraft fuselage and automobile bodies that are difficult to build using primitives It is relatively simple to convert a B-rep model into a wireframe model because its boundary definition is similar to the wireframe definitions In applications B-rep algorithms are reliable and competitive to CSG based algorithms

Disadvantages :
It requires large storage space as it stores the explicit definitions of the model boundaries It is more verbose than CSG Faceted B-rep is not suitable for manufacturing applications

21