Overview of
3D Object Representations
Thomas Funkhouser
Princeton University
C0S 597D, Fall 2003
3D Object Representations
What makes a good 3D object representation?
Stanford and
Hearn & Baker
3D Object Representations
What makes a good 3D object representation?
Intuitive specification
Guaranteed continuity
Guaranteed validity
Efficient rendering
Efficient boolean operations
Accurate
Concise
Structure
3D Reps for Computer Graphics
Raw data
Point cloud
Range image
Voxels
Polygon soup
Solids
Octree
BSP tree
CSG
High-level structures
Surfaces
Scene graph
Mesh
Subdivision
Parametric
Implicit
Point Cloud
Unstructured set of 3D point samples
Acquired from range finder, computer vision, etc
Hoppe
Hoppe
Range Image
Set of 3D points mapping to pixels of depth image
Acquired from range scanner
Range Image
Tesselation
Range Surface
Brian Curless
SIGGRAPH 99
Course #4 Notes
Voxels
Uniform grid of volumetric samples
Acquired from CAT, MRI, etc.
FvDFH Figure 12.20
Stanford Graphics Laboratory
Polygon Soup
Unstructured set of polygons
Created with interactive modeling systems?
Larson
3D Reps for Computer Graphics
Raw data
Point cloud
Range image
Voxels
Polygon soup
Solids
Octree
BSP tree
CSG
High-level structures
Surfaces
Scene graph
Mesh
Subdivision
Parametric
Implicit
Mesh
Connected set of polygons (usually triangles)
Efficient rendering
Stanford Graphics Laboratory
Subdivision Surface
Define surfaces as limit of refinement sequence
Guaranteed continuity, concise
Zorin & Schroeder
SIGGRAPH 99
Course Notes
Parametric Surface
Tensor product spline patchs
Intuitive specification?, guaranteed continuity?,
accurate?, concise
FvDFH Figure 11.44
Implicit Surface
Points satisfying: F(x,y,z) = 0
Guaranteed continuity, guaranteed validity, efficient
boolean operations, concise?
Polygonal Model
Implicit Model
Bill Lorensen
SIGGRAPH 99
Course #4 Notes
3D Reps for Computer Graphics
Raw data
Point cloud
Range image
Voxels
Polygon soup
Solids
Octree
BSP tree
CSG
High-level structures
Surfaces
Scene graph
Mesh
Subdivision
Parametric
Implicit
Octree
Binary space partition with solid cells labeled
Guaranteed validity, efficient boolean operations
FvDFH Figure 12.25
BSP Tree
Binary space partition with solid cells labeled
Guaranteed validity, efficient boolean operations
a
f
e
b
Object
d
c
e
b
6
f
d 7 c
c
3
Binary Spatial Partition
3
e
5
6
Binary Tree
Naylor
CSG
Hierarchy of boolean set operations (union,
difference, intersect) applied to simple shapes
Intuitive specification, guaranteed validity,
efficient boolean operations
FvDFH Figure 12.27
H&B Figure 9.9
3D Reps for Computer Graphics
Raw data
Point cloud
Range image
Voxels
Polygon soup
Solids
Octree
BSP tree
CSG
High-level structures
Surfaces
Scene graph
Mesh
Subdivision
Parametric
Implicit
Scene Graph
Union of objects at leaf nodes
Efficient rendering, high-level structure
Bell Laboratories
[Link]
3D Reps for Computer Graphics
Raw data
Point cloud
Range image
Voxels
Polygon soup
Solids
Octree
BSP tree
CSG
High-level structures
Surfaces
Scene graph
Mesh
Subdivision
Parametric
Implicit
10
Equivalence of Representations
Thesis:
Each fundamental representation has enough
expressive power to model the shape
of any geometric object
It is possible to perform all geometric operations with
any fundamental representation!
Analogous to Turing-Equivalence:
All computers today are turing-equivalent,
but we still have many different processors
Computational Differences
Efficiency
Combinatorial complexity (e.g. O( n log n ) )
Space/time trade-offs (e.g. z-buffer)
Numerical accuracy/stability (degree of polynomial)
Simplicity
Ease of acquisition
Hardware acceleration
Software creation and maintenance
Usability
Designer interface vs. computational engine
11
3D Reps for Computer Graphics
Intuitive specification
Guaranteed continuity
Guaranteed validity
Efficient boolean operations
Efficient rendering
Accurate
Concise
Structure
Display
Property
Editing
Different properties for different applications
Yes
Yes
Yes
Yes
Yes
Yes
?
Yes
No
No
No
No
Yes
Yes
?
Yes
3D Reps for Analysis & Retrieval
Analysis
Retrieval
Intuitive specification
Guaranteed continuity
Guaranteed validity
Efficient boolean operations
Efficient rendering
Accurate
Concise
Structure
Display
Property
Editing
Different properties for different applications
Yes
Yes
Yes
Yes
Yes
Yes
?
Yes
No
No
No
No
Yes
Yes
?
Yes
No
No
No
No
No
?
?
Yes
No
No
No
No
No
?
Yes
Yes
12
3D Reps for Analysis & Retrieval
Statistical examples
Moments
Wavelets
Extended Gaussian Image
Structural examples
Medial axis
Curve skeletons
Deformable models
Moments
Define shape by moments of inertia:
m pqr =
x p y q z r dxdydz
surface
Properties
Invertible
First-order moments give center of mass
Second-order moments give principal axes of rotation
13
Wavelets
Define shape with wavelet coefficients
16,000 coefficients
400 coefficients
100 coefficients
20 coefficients
Properties
Invertible
Multiresolution
Jacobs, Finkelstein, & Salesin 1995
Extended Gaussian Image
Define shape with histogram of normal directions
Invertible for convex objects
Spherical function
14
3D Reps for Analysis & Retrieval
Statistical examples
Moments
Wavelets
Extended Gaussian Image
Structural examples
Medial axis
Curve skeletons
Deformable models
Medial Axis
Define shape as union of centers of maximal balls
Nina Amenta
15
Curve Skeleton
Graph representing axis of local symmetry
Stanford Graphics Laboratory
Deformable Models
Represent model as union of part primitives
Robert Osada
16
Summary
Many possible 3D object representations
Most are turing equivalent
Different reps are more efficient for different tasks
Shape analysis & retrieval
Not same requirements as modeling and rendering
We will study several different reps in this course
17