Deforming Objects
• Non-Uniform Scale
• Global Deformations
Deformation Techniques • Skeletal Deformations
• Grid Deformations
CMPT 466 • Free-Form Deformations (FFDs)
Computer Animation • Morphing
Torsten Möller • 3D Shape Interpolation
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Examples Deforming Objects
• Changing an object’s shape
– Non-simulated algorithms
– User guidance
!"#$%&'()#$*#+$*$,,*-
• Easiest when topology is preserved
– Topology = number of faces, vertices, edges,
holes !
– Define the movements of vertices
.%$/$%01",*#'&'(',2
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Non-Uniform Scale Non-Uniform Scale (2)
sx 0 0 0
0 sy 0 0
0 0 sz 0
0 0 0 1
Transformation matrix - diagonal elements
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Global Deformations Moving Vertices
• Transformations elements - functions of • Cannot define trajectory of all vertices
coordinates • Work on seed vertices
• Effect nearby vertices
34562678 ,4562678
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Moving Vertices Defining Vertex Functions
• If vertex i is displaced by (x, y, z) units
– Displace each neighbor, j, of i by
• (x, y, z) * f(i, j)
• f(i,j) is typically a function of distance
– Euclidean distance
– Number of edges from i to j
– Distance along surface
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Vertex Displacement Function Vertex Displacement Function
• i is the (shortest) distance (in number of
edges) from j
• n is the max number of edges affected
• (k=0) = linear; (k<0) = rigid; (k>0) = elastic
• Figure 3.55 k +1
& i #
f (i ) = 1.0 ' $ ! ;k ( 0
% n +1"
' k +1
& & i ##
f (i ) = $$1.0 ' $ ! !! ;k < 0
% % n +1""
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Global Deformations Global Deformations - taper
• Alan Barr, SIGGRAPH ’84
• A 3x3 transformation matrix affects all
vertices
– P’=M(P)P
• M(P) can taper, twist, bend…
• Figure 3.63 - 3.66
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Global Deformations - taper Global Deformations - Twist
x’ = x*cos(f(y)) – z*sin(f(y))
y’ = y
z’ = x*sin(f(y)) + z*cos(f(y))
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Global Deformations - Bend Global Deformations - Bend
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Global Deformations -
Grid Deformation
Compound
2D technique used in the film HUNGER
• Overlay 2D grid on top of object
• Map object vertices to grid cells (create
local coordinate system)
• User distorts 2D grid vertices
• Object vertices are remapped to local
coordinate system of 2D grid by using
bilinear interpolation
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Grid Deformation (2) Grid Deformation (3)
• For each vertex
• Identify cell
• Local u,v coordinate
0.8
0.5
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Grid Deformation (4) P11
Grid Deformation (5)
Pu1
P01
P00
• Bilinear interpolation Pu0
• Pu0 = (1-u)*P00 + u*P10 P01
• Pu1 = (1-u)*P01 + u*P11
• Puv = (1-v)*P0u + v*P1u
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Grid Deformation (5) Skeletal Deformation
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Skeletons - NOT these type! Skeletons
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Skeletal Deformation (2) Skeletal Deformation (3)
• Interior angle bisectors • Get object
• Perpendiculars at end points L
• Draw polyline
• Map vertices to polyline
• Warp polyline s
• Reposition vertices
d
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Skeletal Deformation (4) Free-Form Deformation (FFD)
• Sederberg, SIGGRAPH ’86
• Position geometric object in local
coordinate space
• Build local coordinate representation
• Deform local coordinate space and thus
deform geometry
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
FFD (2) FFD (3)
• Similar to 2-D grid deformation • Define local coordinate system for
• Define 3-D lattice surrounding geometry deformation
• Move grid points of lattice and deform • (not necessarily mutually perpendicular)
geometry accordingly
T
• Use local coordinate system
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
FFD - register point in cell Trilinear Interpolation
• Let S, T, and U (with origin P0) define local
coord axes of bounding box that encloses
geometry
. : • A vertex P’s coordinates are:
P # P0 P = P0 + s ! S + t ! T + u !U
s = (T " U ) !
(T " U ) ! S T (TxU) . (P-P0)
((TxU) . S)
; P # P0
t = (U " S ) ! P
(U " S ) ! T TxU U
9 P # P0
u = (S " T ) !
© Möller/Parent/Machiraju
( S " T ) !U © Möller/Parent/Machiraju
S P0
Volumetric Control Points FFD - move and reposition
• S, T, and U axes subdivided by control • Move control grid points
points • Usually tri-cubic
• Lattice of control points constructed interpolation is used with FFDs
• Bezier interpolation of CPs • Originally Bezier interpolation was used.
define new vertex positions • B-spline and Catmull-Rom interpolation
i j k have also been used (as well as tri-linear
Pijk = P0 + ! S + ! T + !U
l m n interpolation)
l
&l # & m &m# & n &n# ##
P( s, t , u ) = ) $$ !!(1 ' s ) l 'i s i ( $ ) $$ !!(1 ' t ) m ' j t j ( $$ ) $$ !!(1 ' u ) n ' k u k Pijk !! !
$ ! http://www.dgp.utoronto.ca/~rudy/teapot.html
i =0 % i " % j =0 % j " % k =0 % k " ""
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Examples FFD - extensions
• Hierarchical FFDs
• Animated FFD
• Static FFD that object moves through
• Non-parallelpiped FFD
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Using FFDs to Animate FFDs @ Work
• Control point lattice smaller than geometry
• Move lattice through geometry so it affects
different regions in sequence
• Creepy crawlers under your skin
• Figure 3.74
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
FFDs @ Work Using FFDs to Animate
• Build FFD lattice that is larger than
geometry
• Translate geometry within lattice so new
deformations affect it with each move
• Change shape of object to move along a
path
• Figure 3.75
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Animating the FFD
• Create interface for efficient manipulation
of lattice control points over time
– Connect lattices to rigid limbs of human
skeleton
– Figure 3.77
– Physically simulate control points
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Animating the FFD FFD - films and video
• examples
– Boppin’ in Bean Town by John Chadwick
– Facit demo by Beth Hofer
– Balloon Guy by Chris Wedge
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
(2D) Morphing Morphing
• image post-processing technique • 2D image metamorphosis
• transfer source into target image – Coordinate Grid Approach
• user need to specify corresponding elements – Feature-Based Approach
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Coordinate Grid Morph Coordinate Grid
• create intermediate grid • Source and destination images
• warp source images to intermediate grid – Overlay upon both a 2-D lattice of points
– first in x then in y • Points along edges must remain on edges
• Internal points can be in different positions
• cross-dissolve images • Same number of points in both
• Points define movement of pixels
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Two-pass Rendering Morphing Images to
Overview Intermediate
• Figure 3.79 • First stretch in x direction and then in y
direction
– Auxiliary lattice has x
coordinates from
source and y
coordinates from
intermediate lattice
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Morphing Images Intermediate Feature-Based Morphing
• Use scanline method to • Simplest case: user
compute what pixels from draws one ray on
source image map to a source and
particular pixel of destination images to
intermediate image define morph
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Local Coordinate Systems Local Coordinate Systems
• Root of feature line in source image is
coordinate system origin
• Feature line in source image correspond to
v axis (unit length)
• Construct perpendicular to this ray for u
axis
• Every pixel (x, y) of image now mapped to
(u, v) using projection to u/v axes
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Local Coordinate Systems Mapping Destination to Source
• Perform similar local coordinate system • (x, y) dest --- (s, t)
computation for destination image • (s, t) --- (u, v)
– Build s/t axes • (u, v) --- (x, y)source
• Color (x, y)dest with (x, y)source
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Necessary Details Necessary Details
• More than one line • Mapping from destination to pixel to source
– Perform mapping for all line segments pixel will not land on pixel centers
– Weight each line segment’s contribution to – Aliasing results…
averaged color value – Use quadrilateral centered at source (u, v)
• Q2 – Q1 = distance of line
b
location to sample multiple pixels and average
segment & Q2 ' Q1 p #
• dist is distance from pixel w=$ !
to line $ a + dist !
% "
• a and b are user specified
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
3D Shape Interpolation Matching Topology
• still being researched • same vertex-edge topology
• map between topologically equal objects • easy problem, just interpolate the (x,y,z)
• [easier] map between objects with same position of corresponding vertices
(geometric) topology
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Star-Shaped Polyhedra Axial Slices
• find a vertex in the core of each polyhedra • do the same as before but for 3D object on a
• send rays / discretize polyhedra per slice basis
© Möller/Parent/Machiraju © Möller/Parent/Machiraju
Map To Sphere
• works for genus 0 topologies
• create mapping to sphere
• sphere is an “intermediate” surface, which
lets us find a correspondence between the 2
objects
© Möller/Parent/Machiraju
