AML710 CAD
LECTURE 30
Solid Modeling
Concepts
Evolution of Geometric Modeling
A wireframe representaion of an object is done using edges (lines curves) and vertices. Surface representation then is the logical evolution using faces (surfaces), edges and vertices. In this sequence of developments, the solid modeling uses topological information in addition to the geometrical information to represent the object unambiguously and completely.
Wireframe Model
Solid Model
Advantages of Solid Models
Unlike wireframes and surface representations which contain only geometrical data, the solid model uses topological information in addition to the geometrical information to represent the object unambiguously and completely. Solid model results in accurate design, helps to further the goal of CAD/ CAM like CIM, Flexible manufacturing leading to better automation of the manufacturing process. Geometry: The graphical information of dimension, length, angle, area and transformations Topology: The invisible information about the connectivity, neighborhood, associatively etc Is a solid model just a shaded image? Three dimensional addressability? Suitable for automation? Wireframe Model Solid Model
Geometry Vs Topology
Geometry:
Metrics and dimensions of the solid object. Location of the object in a chosen coordinate system
Topology:
Combinatorial information like connectivity, associativity and neighborhood information. Invisible relationship information.
L1 L2 P1 R1 L2 L1 R1 P1
L3
L3
Same geometry and different Topology
Manifold Vs Non-manifold
Two Manifold Representations:
Two manifold objects are well bound, closed and homomorphic to a topological ball.
Non-manifold Representations:
When restrictions of closure and completeness are removed from the solid definition, wireframe entities can coexist with volume based solids.
Dangling face
Two-Manifold Object
Dangling edge
Non-Manifold Representation
Disadvantages of Wireframe Models
Ambiguity Subjective human interpretation Complex objects with many edges become confusing Lengthy and verbose to define Not possible to calculate Volume and Mass properties, NC tool path, cross sectioning etc
Definition of a Solid Model
A solid model of an object is a more complete representation than its surface (wireframe) model. It provides more topological information in addition to the geometrical information which helps to represent the solid unambiguously.
Wireframe Model
Solid Model
History of Geometric Modeling
Year 1972 1973 1973 1975 1975 Modeler PAP, PADL-I, PADL2 Build-I Build-II TIPS-I GLIDE-I Euler Ops Winged Edge, B-rep Romulus Developer Univ. of Rochester, Voelcker & Requicha Braids CAD Group in Cambridge, UK Hokkaido University, Japan Eastmans Group in CMU, USA Baumgart, Stanford Univ., USA
1981
Evans and Sutherland, 1st commercial
Geometric Modeling - Primitives
Primitives and Instances
PRIMITIVES Instancing: An instance is a scaled / transformed replica of its original. The scaling may be uniform or differential. It is a method of keeping primitives in their basic minimum condition like unit cube and unit sphere etc. INSTANCES
Solid Primitives: Ready starting objects
Y L P B Z Y H D X R Z X Y
BLOCK WEDGE
CYLINDER SPHERE
X
P D B
R Z
Origin of MCS: P
Orientation
Topology and shape
Dimension (size) L,B,H.D,R
Perspective on/off
Solid Primitives: Ready starting objects
Y TORUS X P R Z Ri Ro Z R X H CONE Y
PERSPECTIVE OFF
PERSPECTIVE ON
Operation on Primitives
A desired solid can be obtained by combining two or more solids When we use Boolean (set) operations the validity of the third
(rusulting) solid is ensured
3 Dimensional UNION: BLOCK
CYLINDER
A B
Operation on Primitives
A desired solid can be obtained by combining two or more solids When we use Boolean (set) operations the validity of the third
(rusulting) solid is ensured
UNION: BLOCK
CYLINDER
A B
Operation on Primitives
A A B B B
A- B
INTERSECTION: BLOCK
CYLINDER A B
BLOCK
B- A
DIFFERENCE:
- CYLINDER
Simple Polyhedron Eulers Formula
Eulers formula gives the relation amongst faces, edges and vertices of a simple polyhedron. V-E+F=2. This formula tells us that there are only 5 regular polyhedra Consider polyhedra with every face having h edges, k edges emanating from each vertex and each edge sharing exactly 2 faces, then we can write an invariant for the solid as: hF=2E=kV Substituting this in Eulers formula we get
2E 2E 1 1 1 1 E+ =2 = + k h E h k 2
Five Regular Polyhedra
2E 2E E+ =2 k h 0< 1 1 1 1 = + E h k 2
We notice that for a polyhedron h,k3 What happens if h=k=4 ? If we take h=3, then 3k5 Then by symmetry, if k=3 then 3h5 Thus the possible polyhedra can be symbolically given as: (h,k,E)=(3,3,6), (3, 4, 12), (4,3,12), (5, 3, 30) and (3, 5, 30); tetrahedron, octahedron, cube, dodecahedron, icosahedron
Solid Representation
The solid representation of an object is based on the idea that a physical object divides an n-dimensional space En into two regions: interior and exterior separated by the object boundaries (two-manifold objects) From this point of view any solid model is defined mathematically as a point set S in the three dimensional Euclidean space E3
S = iS U bS
where iS is the interior point set and bS the boundary set. The universal set is now defined as Where cS is the complementary set of iS U bS
W = iS U bS U cS
Interior, Exterior and Closure
The following example will illustrate the concepts of interior, boundary, closure and exterior. Consider a unit sphere Its interior is Its Boundary is Solid sphere is Its closure
x2 + y2 + z 2 < 1 x2 + y2 + z 2 = 1 x2 + y2 + z 2 1
Whatever is outside of this closure is exterior
Geometric Closure
The universal set is now defined as
W = iS U bS U cS
where cS is the complementary set of iS U bS The interior of the solid is geometrically closed by its boundaries S = kS = iS U bS
cS W E3
iS
U bS
= S
Wireframe models lack closure propery Curve in E3 is one dimensional in parametric space A surface in E3 is two dimensional in parametric space
10
Properties of Solid Models
Rigidity: Shape of the solid is invariant w.r.t location/orientation Homogeneous 3-dimensionality: The solid boundaries must be in contact with the interior. No isolated and dangling edges are permitted.
Dangling face
Dangling edge
Non-Manifold Representation
Properties of Solid Models
Finiteness and finite describability: Size is finite and a finite amount of information can describe the solid model. Closure under rigid motion and regularised Boolean operations: Movement and Boolean operations should produce other valid solids. Boundary determinism: The boundary must contain the solid and hence determine the solid distinctly. Any valid solid must be bounded, closed, regular and semi-analytic subsets of E3
11
Properties of Solid Models
The regularized point sets which represent the resulting solids from Boolean operations are called r-sets (regularized sets. R-sets can be imagined as curved polyhedra with well behaved boundaries.
Properties of Solid Modeling Schemes
The schemes operate on r-sets or point sets to produce the desired solid model, which is automatically a valid solid For unambiguous, complete and unique representation the scheme maps points form point set (Euclidian) into a valid model to represent the physical object.
Unlimited Point set , W UCU O
Representation Scheme
Model space , S AIN P O1 O 2 P
Unambiguous, complete, unique
UCN
P1 P2
Unambiguous, complete, non-unique
Ambiguous, incomplete, non-unique
12
Common Features of Modeling Schemes
Domain: The type of objects that can be represented or the geometric coverage. Validity: The resulting solid model when subjected to algorithms should succeed as valid solid. Completeness and Unambiguousness. Uniqueness: Positional and Permutational uniqueness. a b b a
S=A U B U C S=C U B U A
A B
C B
Positionally non-unique
Permutationally non-unique
Desirable Properties of Modeling Schemes
Conciseness, ease of creation and efficiency in application. Conciseness means compact database to represent the object. Ease of operation implies user-friendliness. Most of the packages use CSG approach to create the solids The representation must be usable for later operations like CAM / CNS etc
13
Classification of Solid Modeling
Boundary based or Volume based Object based or spatially based Evaluated or unevaluated
Unevaluated Evaluated
Spatial
Boundary |
Volume
Half space Octree
Object
Euler Ops
CSG
Unevaluated Evaluated Boundary based Spatial based Object Volume based Based
Spatial
Boundary Cell Enum Cell Enum Boundary Rep Nonparametic
Object
Major Modeling Schemes
1. Half Spaces. 2. Boundary Representation (B-Rep) 3. Constructive Solid Geometry (CSG) 4. Sweeping 5. Analytical Solid Modeling (ASM) 6. Cell decomposition 7. Spatial Ennumeration 8. Octree encoding 9. Primitive Instancing The 3 most popular schemes: B-rep, CSG,Sweeping
14
Conversion Among Representations
Some representations can be converted to other representations. CSG to B-REP (but not B-rep to CSG) B-Rep 2. Sweep CSG Cell Decomposition
Some Solid Modelers in Practice
Modeler
CATIA GEOMOD / I-DEAS PATRAN-G PADL-2 SOLIDESIGN UNISOLIDS / UNIGRAPHICS PRO-E SOL. MOD. SYS
Developer
IBM SDRC/EDS PDA ENGG. CORNELL UNI. COMPUTER VISION McDONELL DOUGLAS PARAMETRIC INTERGRAPH
Primary Scheme
CSG BREP ASM CSG BREP CSG BREP BREP
User Input
BREP+CSG BREP+CSG
HYPERPATCHES+CSG
CSG BREP+CSG BREP+CSG BREP+CSG BREP+CSG
15
Algorithms in Solid Modelers
Three types of algorithms are in use in many solid modelers according to the kind of input and output
1. a; data -> representation
Data Algorithm Representation
most common build, maintain, manage representations
Algorithms in Solid Modelers
Some algorithms operate on existing models to produce data. 2. a; representation -> data
Representation Algorithm Data
E.g.. Mass property calculation
16
Algorithms in Solid Modelers
Some representations use the available representations to produce another representation.
3. a: representation -> representation
Representation Algorithm Representation
E.g. Conversion from CSG to B-rep
Closure and Regularized set Operations
The interior of the solid is geometrically closed by its boundaries
S = kiS = iS U bS
iS
U bS
= S
If the closure of the interior of a given set yields that same given set then the set is regular Mathematically a given set is regular if and only if:
S = kiS = iS U bS
P *Q = ki( P Q);
P *Q = ki( P Q) c * Q = ki(cQ)
P *Q = ki( P Q);
17
Regularized set Operations
The interior of the solid is geometrically closed by its boundaries
A *B
A B
A *B A *B =
Set Membership Classification
The process by which various parts of a candidate set X (points, lines or solids) are assigned to (is tested) with a reference set iS, bS or cS is called set membership classification.
M [ X , S ] = ( X in S , X on S , X out S )
X the candidate set S reference set
Input Line Arguments Segment 6 5
1 2 Test Result
L out S L in S L out S L in S L on S
L out S
4 3 2 1 S
3 4 5 6
18
