Transcript Solid Modeling - TAMU Computer Science Faculty Pages

Solid Modeling
Dr. Scott Schaefer
1
Solid Modeling Representations
Constructive Solid Geometry
 Octrees
 Boundary Representations
 Implicit Representations

2/58
Constructive Solid Geometry
Combine simple primitives together using set
operations
 Union, subtraction, intersection
 Intuitive operations for
building more complex
shapes

3/58
Constructive Solid Geometry
Combine simple primitives together using set
operations
 Union, subtraction, intersection
 Intuitive operations for
building more complex
shapes

Image taken from “Feature-Sensitive Subdivision and Isosurface Reconstruction”
4/58
Constructive Solid Geometry
Typically represented as binary tree
 Leaves store solids (sphere, cylinder, …)
 Interior nodes are operations
union
(union, subtraction, …) or
transformations
subtraction
rotation

sphere
cylinder
cylinder
5/58
Ray Tracing CSG Trees

Assume we have a ray R and a CSG tree T

If T is a solid,
 compute all intersections of R with T
 return parameter values and normals
If T is a transformation
 apply inverse transformation to R and recur
 apply inverse transpose of transformation to normals
 return parameter values
Otherwise T is a boolean operation
 recur on two children to obtain two sets of intervals
 apply operation in T to intervals
 return parameter values.



Display closest intersection point
6/58
Inside/Outside Test for CSG Trees

Given a point p and a tree T, determine if p is inside/outside the solid defined by T

If T is a solid
 Determine if p is inside T and return
If T is a transformation
 Apply the inverse transformation to p and recur
Otherwise T is a boolean operation
 Recur to determine inside/outside of left/right children
 If T is Union
 If either child is inside, return inside, else outside
 If T is Intersection
 If both children are inside, return inside, else outside
 If T is Subtraction
 If p is inside left child and outside right child, return inside, else outside


7/58
Application: Computing Volume
Monte Carlo method
 Put bounding box around object
 Pick n random points inside the box
 Determine if each point is inside/outside
the CSG Tree
# inside
 Volume  vol(box)
n

8/58
Octrees
Models space as a tree with 8 children
 Nodes can be 3 types
 Interior Nodes
 Solid
 Empty

9/58
Octrees
Models space as a tree with 8 children
 Nodes can be 3 types
 Interior Nodes
 Solid
 Empty

10/58
Building Octrees
If cube completely inside, return solid node
 If cube completely outside, return empty
node
 Otherwise recur until
maximum depth reached

11/58
Octrees


Advantages
 Storage space proportional to surface area
 Inside/Outside trivial
 Volume trivial
 CSG relatively simple
 Can approximate any
shape
Disadvantages
 Blocky appearance
12/58
Octrees


Advantages
 Storage space proportional to surface area
 Inside/Outside trivial
 Volume trivial
 CSG relatively simple
 Can approximate any
shape
Disadvantages
 Blocky appearance
13/58
Boundary Representations

Stores the boundary of a solid
 Geometry: vertex locations
 Topology: connectivity information
 Vertices
 Edges
 Faces
14/58
Boundary Representations

Constant time adjacency information
 For each vertex,
 Find edges/faces touching vertex
 For each edge,
 Find vertices/faces touching edge
 For each face,
 Find vertices/edges touching face
15/58
Half Edge Data Structure
NHE
face
HE E Flip
PHE
V
16/58
Half Edge Data Structure
HalfEdge {
HalfEdge next, prev, flip;
Face face;
Vertex origin;
Edge edge;
}
Face {
HalfEdge edge; // part of this face
}
Vertex {
HalfEdge edge; // points away
}
Edge {
HalfEdge he;
}
NHE
face
HE E Flip
PHE
V
17/58
Half Edge Data Structure
Given a face, find all vertices touching that
face
 Given a vertex, find all
edge-adjacent vertices
NHE
 Given a face, find all
Flip
face
adjacent faces
HE

E
PHE
V
18/58
Building a Topological Data Structure
Must connect adjacent edges/faces/vertices
 Edges are critical in most data structures


Use a hash table indexed by
two vertices
NHE
face
HE E Flip
PHE
V
19/58
Boundary Representations
Advantages
 Explicitly stores neighbor information
 Easy to render
 Easy to calculate volume
 Nice looking surface
 Disadvantages
 CSG very difficult
 Inside/Outside test hard

20/58
Implicit Representations of Shape

Shape described by solution to f(x)=c
f ( x, y)  x 2  y 2  9
21/58
Implicit Representations of Shape

Shape described by solution to f(x)=c
f ( x, y)  x 2  y 2  9
22/58
Implicit Representations of Shape

Shape described by solution to f(x)=c
f ( x, y)  x 2  y 2  9
- - - 23/58
Implicit Representations of Shape

Shape described by solution to f(x)=c
f ( x, y)  x 2  y 2  9
+
+
+
+
- - - +
+
+
+
24/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
 CSG operations

25/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
 CSG operations
+
+ 
+
+
- - +
+
+
+
26/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
 CSG operations

27/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
 CSG operations
 Union

28/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
 CSG operations
 Union

29/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
 CSG operations
 Union
+
+

+
+
-
-
+
+
30/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
+
 CSG operations
+  Union

+
-
+
-
-
-
+
+
31/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
+
 CSG operations
+ -+
 Union
+

+
+
-+
-
+
-
- - -
-
+
+
+ +
32/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
 CSG operations
-+
 Union

+
-
-
+
- -- +
- --
+
+
33/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
+
+
 CSG operations
+
 Union
+ +
+
 Intersection
+ +
- + +
+
+

34/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
 CSG operations
+
 Union
+
 Intersection

+
-
+
35/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
+
+
 CSG operations
+
 Union
+ +
+
 Intersection
+ +
 Subtraction
- + +
+
+

36/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
 CSG operations
+
+
 Union
+
+
+
 Intersection
+
+
+
+
 Subtraction
+
+
+

-
37/58
Advantages
No topology to maintain
 Always defines a closed surface!
 Inside/Outside test
 CSG operations
 Union
+
 Intersection
+
 Subtraction
+

-
+
-
+
38/58
Disadvantages
Hard to render - no polygons
 Creating polygons amounts to root finding
 Arbitrary shapes hard to represent as a
function

39/58
Non-Analytic Implicit Functions

Sample functions over grids
40/58
Non-Analytic Implicit Functions

Sample functions over grids
41/58
Data Sources
42/58
Data Sources
43/58
Data Sources
44/58
Data Sources
45/58
Data Sources
46/58
Data Sources
47/58
2D Polygon Generation
48/58
2D Polygon Generation
49/58
2D Polygon Generation
50/58
2D Polygon Generation
51/58
2D Polygon Generation
52/58
3D Polygon Generation
53/58
3D Polygon Generation
54/58
Fun Examples
55/58
Fun Examples
56/58
Fun Examples
57/58
Fun Examples
58/58