3D Modeling
COS 426, Spring 2022
Princeton University
Felix Heide
1
Blender demo (musimduit)
` 2
Syllabus
I. Image processing
II. Modeling
III. Rendering
IV. Animation Rendering
(Michael Bostock, CS426, Fall99)
Image Processing
(Rusty Coleman, CS426, Fall99)
Modeling
(Denis Zorin, CalTech) Animation
(Angel, Plate 1)
3
What is 3D Modeling?
• Topics in computer graphics
• Imaging = representing 2D images
• Modeling = representing 3D objects
• Rendering = constructing 2D images from 3D models
• Animation = simulating changes over time
4
Modeling
• How do we ...
• Represent 3D objects in a computer?
• Acquire computer representations of 3D objects?
• Manipulate these representations?
Stanford Graphics Laboratory H&B Figure 10.46
5
Modeling Background
• Scene is usually approximated by 3D primitives
• Point
• Vector
• Line segment
• Ray
• Line
• Plane
• Polygon
6
3D Point
• Specifies a location
• Represented by three coordinates
• Infinitely small
typedef struct {
Coordinate x;
Coordinate y;
Coordinate z;
} Point; (x,y,z)
Origin
7
3D Vector
• Specifies a direction and a magnitude
• Represented by three coordinates
• Magnitude ||V|| = sqrt(dx ∙ dx + dy ∙ dy + dz ∙ dz)
• Has no location
typedef struct { (dx,dy,dz)
Coordinate dx;
Coordinate dy;
Coordinate dz;
} Vector;
8
3D Vector
• Dot product of two 3D vectors
• V1·V2 = ||V1 || || V2 || cos(Q)
(dx1,dy1,dz1)
Q
(dx2,dy2 ,dz2)
9
3D Orthogonality
• Dot product of two 3D vectors
• V1·V2 = ||V1 || || V2 || cos(p/2) = 0
(dx1,dy1,dz1)
90°
(dx2,dy2 ,dz2)
10
3D Vector
• Cross product of two 3D vectors
• V1 x V2 = vector perpendicular to both V1 and V2
• ||V1 x V2|| = ||V1 || || V2 || sin(Q)
(dx1,dy1,dz1)
Q
(dx2,dy2 ,dz2)
V1xV2
11
3D Vector
• Cross product of two 3D vectors
• V1 x V2 = vector perpendicular to both V1 and V2
• ||V1 x V2|| = ||V1 || || V2 || sin(Q)
(dx1,dy1,dz1)
Q
(dx2,dy2 ,dz2)
V1xV2
12
3D Line Segment
• Linear path between two points
• Parametric representation:
• P = P1 + t (P2 - P1), (0 t 1)
typedef struct {
Point P1;
Point P2;
} Segment; P2
P1
Origin
13
3D Ray
• Line segment with one endpoint at infinity
• Parametric representation:
• P = P1 + t V, (0 <= t < )
typedef struct {
Point P1;
Vector V;
} Ray;
P1
Origin
14
3D Line
• Line segment with both endpoints at infinity
• Parametric representation:
• P = P1 + t V, (- < t < )
typedef struct {
Point P1;
Vector V;
} Line;
V
P1
Origin
15
3D Plane
• Defined by three points in 3D space
P2 P3
P1
Origin 16
3D Plane
• A linear combination of three points
• Implicit representation:
• P·N - d = 0, or
• N· (P – P1)= 0, or N = (a,b,c)
• ax + by + cz + d = 0
typedef struct {
Vector N;
Distance d; P2 P3
} Plane;
• N is the plane “normal” P1
• Unit-length vector d
• Perpendicular to plane
Origin 17
3D Polygon
• Set of points “inside” a sequence of coplanar points
typedef struct {
Point *points;
int npoints;
} Polygon;
Points are in counter-clockwise order
18
3D Object Representations
How can this object be represented in a computer?
19
3D Object Representations
Solidworks
How about this one?
20
3D Object Representations
This one? FumeFx
21
3D Object Representations
• Points • Solids
• Range image • Voxels
• Point cloud • BSP tree
• CSG
• Surfaces • Sweep
• Polygonal mesh
• Subdivision • High-level structures
• Parametric • Scene graph
• Implicit • Application specific
22
Equivalence of Representations
• Thesis:
• Each representation has enough expressive power
to model the shape of any geometric object
• It is possible to perform all geometric operations
with any representation
• Analogous to Turing-equivalence
• Computers and programming languages are
Turing-equivalent, but each has its benefits…
23
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Manipulation
• Animation
→ Data structures determine algorithms
24
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Range Scanning
• Rendering
• Analysis
• Manipulation
• Animation
DGP course notes, Technion 25
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Computer Vision
• Rendering
• Analysis
• Manipulation
• Animation
USC
Indiana
University 26
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Tomography
• Rendering
• Analysis
• Manipulation
• Animation
DGP course notes, Technion
27
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Intersection
• Analysis
• Manipulation
• Animation
Autodesk
28
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Curvature,
smoothness
• Manipulation
• Animation
DGP course notes, Technion
29
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Fairing
• Manipulation
• Animation
DGP course notes, Technion
30
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Texture mapping
• Manipulation
• Animation
31
DGP course notes, Technion
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Reduction
• Manipulation
• Animation
DGP course notes, Technion 32
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Structure
• Manipulation
• Animation
DGP course notes, Technion
33
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Symmetry
detection
• Manipulation
• Animation
DGP course notes, Technion 34
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Correspondence
• Manipulation
• Animation
DGP course notes, Technion
35
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Segmentation
• Manipulation
• Animation
DGP course notes, Technion
36
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Manipulation
• Deformation
• Animation
IGL
37
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Manipulation
• Deformation
• Animation
DGP course notes, Technion
38
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Manipulation
• Healing
• Animation
DGP course notes, Technion
39
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Manipulation
• Animation
• Rigging
Animation
Buffet
40
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Manipulation
• Animation
• Simulation
Physically Based Modelling course notes, USC 41
Why Different Representations?
Efficiency for different tasks
• Acquisition
• Rendering
• Analysis
• Manipulation
• Animation
• Fabrication
DGP course notes, Technion 42
3D Object Representations
• Points • Solids
• Range image • Voxels
• Point cloud • BSP tree
• CSG
• Surfaces • Sweep
• Polygonal mesh
• Subdivision • High-level structures
• Parametric • Scene graph
• Implicit • Application specific
43
3D Object Representations
• Points • Solids
• Range image • Voxels
• Point cloud • BSP tree
• CSG
• Surfaces • Sweep
• Polygonal mesh
• Subdivision • High-level structures
• Parametric • Scene graph
• Implicit • Application specific
44
Range Image
Set of 3D points mapping to pixels of depth image
• Can be acquired from range scanner
Cyberware
Stanford
Range Image Tesselation Range Surface
Brian Curless
SIGGRAPH 99
Course #4 Notes 45
Point Cloud
Unstructured set of 3D point samples
• Acquired from range finder, computer vision, etc
Velodyne Lidar Scan
46
3D Object Representations
• Points • Solids
• Range image • Voxels
• Point cloud • BSP tree
• CSG
• Surfaces • Sweep
• Polygonal mesh
• Subdivision • High-level structures
• Parametric • Scene graph
• Implicit • Application specific
47
Polygonal Mesh
Connected set of polygons (often triangles)
Stanford Graphics Laboratory
48
Subdivision Surface
Coarse mesh & subdivision rule
• Smooth surface is limit of sequence of refinements
Zorin & Schroeder
SIGGRAPH 99
Course Notes 49
Parametric Surface
Tensor-product spline patches
• Each patch is parametric function
• Careful constraints to maintain continuity
v u
x = Fx(u,v)
y = Fy(u,v)
z = Fz(u,v)
FvDFH Figure 11.44
50
Implicit Surface
Set of all points satisfying: F(x,y,z) = 0
Polygonal Model Implicit Model
Bill Lorensen
SIGGRAPH 99
Course #4 Notes
51
3D Object Representations
• Points • Solids
• Range image • Voxels
• Point cloud • BSP tree
• CSG
• Surfaces • Sweep
• Polygonal mesh
• Subdivision • High-level structures
• Parametric • Scene graph
• Implicit • Application specific
52
Voxel grid
Uniform volumetric grid of samples:
• Occupancy
(object vs. empty space)
• Density
• Color
FvDFH Figure 12.20
• Other function
(speed, temperature, etc.)
• Often acquired via
simulation or from
CAT, MRI, etc.
Stanford Graphics Laboratory 53
Octree
The adaptive version of the voxel grid
• Significantly more space efficient
• Makes operations more cumbersome
Thomas Diewald 54
BSP Tree
Hierarchical Binary Space Partition with
solid/empty cells labeled
• Constructed from polygonal representations
a
b 1
1 a
a g 6 2
f c
f 3
e d 5 e d 7 c d 3
c 4 4 e
b 2 b
5 f
Object Binary Spatial Partition
6 7
Binary Tree
Naylor
55
CSG
Constructive Solid Geometry: set operations (union, difference,
intersection) applied to simple shapes
FvDFH Figure 12.27 H&B Figure 9.9
56
3D Object Representations
• Points • Solids
• Range image • Voxels
• Point cloud • BSP tree
• CSG
• Surfaces • Sweep
• Polygonal mesh
• Subdivision • High-level structures
• Parametric • Scene graph
• Implicit • Application specific
58
Application Specific
Apo A-1
(Theoretical Biophysics Group,
University of Illinois at Urbana-Champaign)
Architectural Floorplan
(CS Building, Princeton University)
59
Taxonomy of 3D Representations
3D Shape
Discrete Continuous
Voxels,
Point sets Combinatorial Functional
Topological Set Membership Parametric Implicit
Mesh BSP Tree Bezier Algebraic
Subdivision Cell Complex B-Spline
Naylor
60
Equivalence of Representations
• Thesis:
• Each representation has enough expressive power
to model the shape of any geometric object
• It is possible to perform all geometric operations
with any representation
• Analogous to Turing-equivalence
• Computers and programming languages are
Turing-equivalent, but each has its benefits…
61
Computational Differences
• Efficiency
• Representational complexity (e.g. surface vs. volume)
• Computational complexity (e.g. O(n2) vs O(n3) )
• Space/time trade-offs (e.g. tree data structures)
• Numerical accuracy/stability (e.g. degree of polynomial)
• Simplicity
• Ease of acquisition
• Hardware acceleration
• Software creation and maintenance
• Usability
• Designer interface vs. computational engine
62
Upcoming Lectures
• Points • Solids
• Range image • Voxels
• Point cloud • BSP tree
• CSG
• Surfaces • Sweep
• Polygonal mesh
• Subdivision • High-level structures
• Parametric • Scene graph
• Implicit • Application specific
63
