Advanced Modeling 2
Katja Bühler, Andrej Varchola, Eduard Gröller
Institute of Computer Graphics and Algorithms Vienna University of Technology
Topics
Parametric curves and surfaces Polynomial curves
Rational curves
Tensor product surfaces
Triangular surfaces
Parametric Curves
regular.
are points
curve all
way that a
in ed parametriz be
can
regular
-
in regular
-
: ctor Tangent ve
-
in functions
able differenti
are
-
0 0
c c
o )
t(u )
c(u c
c(u) du
t(u) d
u , z(u)
x(u), y(u)
IR :I
a,b u
; z(u) y(u) x(u) c(u)
c:
Parametric Surfaces
regular.
are points
surface all
way that a
in ed parametriz be
can s
regular
s -
in regular s
-
: vector Normal
-
: plane Tangent
-
v and u
in functions
able differenti
are ,
, ,
-
IR :
, ,
) , (
; ) , (
) , (
) , ( )
, ( :
0 0 0
0
0 0 0
0 0
0
0 0 0
0 0
0 0
2
o n
s
s s
n
s s
s t
s
) ,v (u )
,v (u
) ,v (u )
,v (u )
,v (u
) ,v (u m
) ,v (u l
) ,v (u (l,m)
v) v), z(u v), y(u
x(u
J I
d c b
a v
u v
u z
v u y
v u x v
u s
v u
v u
Bézier Curves: The de Casteljau Algorithm
. point at
curve the
of line tangent the
determine and
points The
curve.
Bézier ing
correspond on the
point curve
a is Then
. :
with 1
: Set
. arbitrary
an and points
1 n Given
0 1
1 1
0 0
0 1
1 1
3 0
n n
n n
i i
r i r
i r
i
n
t -t)
(
IR t
IE ,...,
b b
b b
b b
b b
b
b b
1
2 1 0
2
3 0 1
1
2 0 0
1
1 0 0
0
b
b b
b b
b b
b b
Bézier Curves and Bernstein Polynomials
i i n n
i
n i n
i
i
i
t t) i (
(t) n B
(t) B
b b(t)
,...,n , i
b
1
0
0
: s polynomial Bernstein
: points
Bézier to
respect with
curve Bézier
Properties of Bézier Curves
Affine invariance
Convex hull property Endpoint interpolation Linear precision
Variation diminishing property Disadvantages
Only pseudo local control High degree
Important Algorithms for Bézier Curves
Degree elevation
to increase flexibility
Subdivision
to increase flexibility
to approximate the curve
The subdivision is a byproduct of the de Casteljau algorithm
Evaluation/Approximation of Bézier Curves
The de Casteljau algorithm is numerical stabil, but inefficient for evaluation
Horner scheme like evaluation is more efficient
Repeated subdivision gives in a fast way a good approximation of the curve
-t s
n t s n
s n t
s n t
n s
t ) ...) n n with 1
) 2 1
(...(( 0 )
( 0 1 2 2
b b b b
b
B-Spline Curves
B-Spline curves
are piecewise polynomial curves of degree k-1
have a degree (almost) independent of the number of control points
allow local control over the shape of a curve
B-Spline Curves: Definition
) ,...,u
(u U
,...,n , i
IE
k n i
0
3
0
vector knot
-
points control
1 n
-
: Given
d
k.
order of
functions basis
spline -
B the with
: curve spline
- B
) ( )
, [ ,
) ( )
( 0
0
u N
u u
u u
N u
k i k
n n
i
k i
i
ds
B-Spline Basis Functions
) ( )
( )
( :
0
) ,
[ 0
) 1 ( :
0
1 1 1
1 1
0 1
u u N
u
u u u
u N u
u u u
N k
sonst u u u u
N k
k i i
k i
k k i
i i
k i k i
i
i i i
) ,
[ 0
0
1
0
k i i k
i k
i
n
i
k i
u u u
(u) N
(u) N
(u) N
if
: support local
-
: positivity -
: unity of
partition -
: functions basis
the of
Properties
Properties of B-Spline Curves
Affine invariance
Strong convex hull property Variation diminishing property Local support
Knot points of multiplicity k are coincident with one of the control points.
A B-Spline curve of order k which has only knots of multiplicity k is a Bézier curve
Evaluating B-Spline Curves: The de Boor Algorithm
. :
: 1 :
) ,
[
1 2
2 1 1
0
1 1
1
0
0 3
0
k m k
m k
m k
m
i r
k i r i
i i
i
r i r i r
i r i r
i
k n
k n n
u u
u t )
- (
u u t
) ,...,u (u
U IE
,...,
b d
d
x d
d d
d d
d
d d
point at
curve the
of line tangent
the determine
and points
The
curve.
spline -
B
ing correspond the
on ] t , [t t
), (t for point the
is Then
and
with
Set
. arbitrary
an and
vector knot
a , points
control 1
n Given
1 m m 0
0
scheme Boor
de The
0 3
1 3
2 3 0
2
3 3 1
2 2 2 0
1 1 1 0 0
d d
d d
d d
d d
d d
Direct Evaluation of B-Spline Curves
Find the knot span [u
i,u
i+1) in which the parameter value t lies
Compute all non zero basis functions
Multiply the values of the nonzero basis
functions with the corresponding control points
Special B-Spline Curves open:
closed:
uniform:
) ) (
,...., ,
( u
0u
0d u
0n k d
U
k n n
k
k
u u u
u
u
0 ...
1 .... ...
) ,...,
,...., (
and
: ,...,
:
2 2 0
1 0
1
k n k
n
k k
n n
u u
u U
d d
d
d
Important Algorithms for B-Spline Curves
Knot insertion
to increase flexibility to compute derivatives
to split curves (subdivision algorithms) to evaluate the curve (see de Boor
algorithm)
to approximate the curve Degree elevation
to adapt curve degrees
Rational Curves
IR I
u u
z u y
u x
u w u
IR I
u u
z u y
u x u
u w
H
, ) (
) (
) (
) ( )
(
, ) (
) (
) ( )
( ) 1
(
c c
: tion representa
s Homogeneou
: curve Rational
2u b
) u (1- a
u 1 (u)
2u b
) u (1- a
u 1 (u) 1
section conic
: Example
2 2
2 2
cH
c
Rational Bézier Curves
n i
n i i H H
i
n i
n i i n
i
n i i i
w
IR I
u u
B u
,...,n , i
w
IR I
u u
B w
u B
u w
b b
b b
points Bézier
s homogeneou the
with
: tion representa
s Homogeneou
weights.
called are
The
as defined
is curve Bézier
rational A
, ) ( )
(
0 0
, ) (
) ) (
(
0 0 0
Rational Bézier Curves: Properties and Algorithms
Properties:
the same properties like polynomial curve, and projective invariance
the weights are an additional design parameter Algorithms
All algorithms of polynomial Bézier curves can be applied without any change to the
homogeneous representation of rational Bézier curves.
Non Uniform Rational B-Splines
k n n
i
k i i H H
i
k n n
i
k i i n
i
k i i i
k n
i
IR u
u u
u N
u
,...,n , i
w
IR u
u u
u N
w
u N
u w
) ,...,u
(u U
,...,n , i
d
n n
n d
points Spline
- B s homogeneou the
with
: tion representa
s Homogeneou
weights.
called are
The
as defined is
vector knot
the and
points control
the to
respect with
curve NURBS
A
) ,
[ ,
) ( )
(
0 0
) ,
[ ,
) (
) ) (
(
0
0 0
0 0
0
0
NURBS: Properties and Algorithms
Properties:
the same properties like polynomial curve, and
projective invariance
changing the weight wi affects only the interval [ui, ui+k)
Algorithms
All algorithms of B-spline curves can be applied without any change to the
homogeneous representation of NURBS curves.
Tensor-Product Surfaces
"A surface is the locus of a curve that is moving through space and thereby changing the shape"
0 0
, ) ( )
(
, ) ( )
(
IR J
v v
G v
IR I
u u
F u
m
j
j ij i
n
i
i i
a c
c f
surface product
- tensor a
yields both
Combining
yields points
control the
moving
curve a
Given
Tensor-Product Bézier Surfaces
surface.
the of
net control
the form
points Bézier
The
by given
is surface Bézier
product -
tensor A
ij n
i
m
j
m j n
i
ijB u B v u v I J IR
v u
b b
b 2
0 0
) , ( ,
) ( )
( )
,
(
Tensor-Product Bézier Surfaces Properties and Algorithms
Properties:
analogue to that of Bézier curves
Algorithms:
Apply algorithms for curves in two steps:
Apply to Apply to
n i
v B v
m
j
m j ij
i( ) ( ), 0,...,
0
b b
) ( ) ( )
, (
0
u B v v
u
n
i
n i
i
b b
Tensor-Product B-Spline Surfaces
surfaces.
product tensor
Bézier
for n descriptio the
to analogue are
s Algorithm and
Properties
surface.
the of
net control
the form
points control
The
by given is
vectors knot
the to
respect with
surface spline
- B uct tensorprod A
ij
l m k
n n
i
m
j
l j k
i ij
l m k
n
IR v
v u
u v
u v
N u N v
u
) ,...,v
(v ),V
,...,u (u
U
d d
d( , ) ( ) ( ), ( , ) [ 0, ) [ 0, ) 2.
0 0
0 0
Bézier Triangles
k j i n
ijk
k j i
n k j i
n ijk ijk
w v k u
j i w n
v u B
u,v,w
w v u B
w v u b
!
!
! ) !
, , (
) , , ( )
, , (
0 , ,
: s polynomial Bernstein
d Generalize
domain.
parameter triangular
the
of s coordinate c
barycentri are
The
by defined is
patch Bézier
triangular A
b
Bézier Triangles: Properties and Algorithms
Properties:
the same as in the univariate case
Algorithms:
De Casteljau:
Subdivision
Degree elevation
1 1 1
1 1
1
il jk ijl k ijkll
ijk
ub vb wb
b
Subdivision Surfaces
Polygon-mesh surfaces generated from a base
mesh through an iterative process that smoothes the mesh while increasing its density
Represented as functions defined on a parametric domain with values in R3
Allow to use the initial control mesh as the domain Developed for the purpose of CG and animation
Subdivision Surfaces: The Basic Idea
In each iteration
Refine the initial control mesh
Increase the number of vertices / faces
The mesh vertices converge to a limit surface
Loop’s Scheme (‘87)
Old vertex Edge vertex New vertex
8 3
8 1
8 3 8
1
1 5 3 2 2 2
8 8 8 cos
n n
1n
http://www.cs.technion.ac.il/~cs236716/
4
2 1
2
1 f f
e
v v
v
v v
4 4 1
1
i
i
f v
v
Catmull-Clark Scheme ’78
Face vertex
Vertex
Edge vertex
( 3)
2 p n
Q R
v n n n
Q – Average of face vertices
R – Average of edge vertices
v – new vertex
http://www.cs.technion.ac.il/~cs236716/
Comparison of the Loop and the Catmull-Clark Scheme
Loop subdivision scheme:
Catmull-Clark subdivision scheme:
