Transcript Fair and Robust Circle Splines

SIGGRAPH 2003, San Diego
Fair and Robust Circle Splines
Carlo Séquin, EECS, UCB
Kiha Lee, ME, UCB
Motivation: Smooth Curves on a Sphere
 “Grand
Tour” camera movements
to look inward towards an object.
 Sculpture
Design:
“Viae Globi” (Pathways on a Sphere)
Sweep along a smooth curve on a sphere.
Concepts and Goals
Smooth Interpolating Curves on Sphere:

Sparse set of control points.

These get interpolated exactly.

All symmetries are maintained.

Produces round, pleasing looking curves.

If circles are possible, they will result.

 Like MVC*, but only local support.
* MVC = Minimum (Curvature) Variation Curve
Circle-Splines (“C-Splines”)
One simple scheme: …
in the plane,
on the sphere,
in 3D space,
Circle Splines: in the Plane (0)
Original data points and control polygon
Circle Spline Construction (1)
Original data points and control polygon
Focus on 4 consecutive points: A, B, C, D
B
D
A
C
Circle Spline Construction (2)
Original data points and control polygon
Focus on 4 consecutive points: A, B, C, D
LEFT CIRCLE thru A, B, C
B
D
A
C
Circle Spline Construction (3)
Original data points and control polygon
Focus on 4 consecutive points: A, B, C, D
LEFT CIRCLE thru A, B, C
RIGHT CIRCLE thru B, C, D
B
D
A
C
Circle Spline Construction (4)
Original data points and control polygon
Focus on 4 consecutive points: A, B, C, D
LEFT CIRCLE thru A, B, C
RIGHT CIRCLE thru B, C, D
B
D
A
C
BLEND CURVE between B and C
Local Support
STRAIGHT LINE
Pi–2
Pi–1
Pi+1
Pi+2
STRAIGHT LINE
Pi
PURE CIRCLE
B
D
A
BLEND
PURE CIRCLE
C
How to do the Blending ?
Left Circle thru: A, B, C; Right Circle thru: B, C, D.
D
B
A
?
C
Circle Blending: Previous Art (1)
Left Circle thru: A, B, C.
Right Circle thru: B, C, D.
n points on Left Circle.
n points on Right Circle.
D
Interpolate positions between
corresponding points.
C
B
Linearly weighted:
[ Wenz, 1996 ]
A
S
Circle Blending: Previous Art (2)
Trigonometrically weighted: Wu = Lu cos2(u p/2) + Ru sin2(u p/2)
[ Szilvasi-Nagy & Vendel, 2000 ]
WEIGHT
Curve clings to base circle
G2-continuity @ B
0
STEP u
D
1
C
B
A
S
STEP u
Circle Blending: Previous Art (3)
 Angle-based

blending [ Séquin & Yen, 2001 ]

Subdivision technique
(find mid-point only, and recurse)

Curves looked good

Could not formally prove continuity
2003: Sampled (Morph) Construction

Curves look even better!

Can formally prove G2-continuity

Can also obtain C2 with re-parameterization
Blending With Intermediate Circles (1)
Left Circle thru: A, B, C; Right Circle thru: B, C, D.
Draw Tangent Vectors for both circles at B and C.
D
B
A
C
Blending With Intermediate Circles (2)
Left Circle thru: A, B, C; Right Circle thru: B, C, D.
Draw Tangent Vectors for both circles at B and C.
Draw a bundle of regularly spaced Tangent Vectors.
D
B
A
C
Blending With Intermediate Circles (3)
Left Circle thru: A, B, C; Right Circle thru: B, C, D.
Draw Tangent Vectors for both circles at B and C.
Draw a bundle of regularly spaced Tangent Vectors.
Draw n equal-angle-spaced Circles from B to C.
D
B
A
C
Blending With Intermediate Circles (4)
Left Circle thru: A, B, C; Right Circle thru: B, C, D.
Draw Tangent Vectors for both circles at B and C.
Draw a bundle of regularly spaced Tangent Vectors.
Draw n equal-angle-spaced Circles from B to C.
Make n equal segments on each arc and
D
th
th
choose u point on u circle.
B
S
A
 G1-continuity @ B, C
C
Trigonometric Angle Blending (1)
Left Circle thru: A, B, C; Right Circle thru: B, C, D.
Draw Tangent Vectors for both circles at B and C.
Draw a bundle of trigonometrically spaced tangents.
D
ANGLE
B
A
C
STEP u
Trigonometric Angle Blending (2)
Left Circle thru: A, B, C; Right Circle thru: B, C, D.
Draw Tangent Vectors for both circles at B and C.
Draw a bundle of trigonometrically spaced Tangents.
Draw n trigonometrically-spaced Circles from B to C.
D
B
A
C
Trigonometric Angle Blending (3)
Left Circle thru: A, B, C; Right Circle thru: B, C, D.
Draw Tangent Vectors for both circles at B and C.
Draw a bundle of trigonometrically spaced Tangents.
Draw n trigonometrically-spaced Circles from B to C.
Blend curve “hugs” initial circles longer:  G2
B
S
A
D
C
Various Interpolation Schemes
Too sharp
Too “loopy”
Cubic
Polynomial
Subdivision
Trigonometrically
Position-Blended
Circular Arcs
( Szilvasi-Nagi )
“Just right”
Trigonometrically
Angle-Blended
C-Spline
NO CUSPS !
Comparing Interpolation Schemes

A simple control polygon
( Test case 2 )
Comparing Interpolation Schemes

Cubic polynomial subdivision scheme
[ Butterfly, Loop, Zorin ]
EXTREME
CURVATURE
Too sharp
Comparing Interpolation Schemes
 (Non-uniform)
Lagrange Interpolation
EXTREME
CURVATURE
Too sharp
Comparing Interpolation Schemes

Linearly position-blended circular arcs
[ Wenz, 1996 ]
Too “loopy”
Comparing Interpolation Schemes

Trigonometrically position-blended circular arcs
[ Szilvasi-Nagi and Vendel, 2000 ]
Too “loopy”
Comparing Interpolation Schemes

Angle-blended C-splines: C0 / G2
[ Séquin - Lee, 2003 ]
“Just right”
Comparing Interpolation Schemes

Angle-blended C-splines, reparameterized: C2 / G2
[ Séquin - Lee, 2003 ]
“Just right”
Comparing Circle-Blending Schemes
u=0
D
B
C
A
B
C
PARAMETER
LINES
INTERSECT
u=1
Positional interpolation
Szilvasi-Nagy & Vendel, 2000
Angle-based parametrization
(new)
SL
Comparison of Location of Midpoint S
SP
Linearly averaged
point position.
SA
Averaged circle,
based on angles !
SR
B
C
A
D
SL
Problem of Position Averaging
SP
It would be difficult
to reach tangent
direction at C
from mid-point SP
SA
SR
B
C
A
D
Key Points about Circle Splines
Going from Polynomial Splines
to Blended Circles:

Give up affine invariance

Give up linear precision

 Avoid cusps and hair-pin turns
 Get nicely rounded, loopy curves
 Approximate the behavior of the MVC
Bounded Curvature

For non-extreme control polygons,
the resulting curvature is bounded.
179° SWITCHBACK @ B
MAX. CURVATURE = 10
A
B
D
C
Circle-Splines on the Sphere
Examples from a prototype editor program.
We only need one small conceptual change …
Concept: Swivel Planes thru B,C
(u)
P(u)
3 consecutive
points define
a plane and
a circle on it.
A, B, C 
Left Plane.
A
B, C, D 
Right Plane.
Intermediate
planes / arcs
at <lin./trig.>
angle-steps.
Discrete Sample Points on Swivel Plane
“Trigonometric Swivel” for G2-continuity
C
B
B
C
D
A
END VIEW
A
SIDE VIEW
D
Circle-Splines in 3D Free Space

We want to have a seamless, unnoticeable
transition from sphere to plane:
 No “if” statements in the code
associated with a check for planarity !

In 2001, we had a very cumbersome way
to bring spheres and planes under one hat.

Today, the 3D case and the spherical case
naturally turn out to be the same !
Circle-Splines in 3D
Left Circle thru: A, B, C; Right Circle thru: B, C, D.
Mirror Tangent Vectors for both circles at B and C.
Draw a bundle of suitably spaced Tangent Vectors.
Corresponding tangent pairs define intermediate arcs.
D
MIRROR
C
B
Two different planes
A
Circle-Splines on Sphere
There is always at least one sphere through A, B, C, D.
Left Circle and Right Circle lie on that sphere;
The two tangent bundles are tangent to this sphere;
All intermediate arcs lie on sphere through A,B,C,D;
All generated points lie on sphere !
D
MIRROR
C
B
Tangent planes
A
A 3D Circle-Spline (Figure-8 Knot)
(Cross-eye stereo view)
Important Implementation Issues

Avoid calculations that explicitly involve
the centers of the circular arcs,
since these will go off to infinity,
when the arcs become straight.

Calculate points along arc (B,C)
as an offset from end point B.
P(u)
B
C
Linear steps, t(u)
Parametric Representation of Blend Curve
t(u)
B
P(u)
f(u)
f(u)
C
For: u = 0  1
 t(u) = ti cos2(u p/2) + ti+1 sin2(u p/2)
(Trigonometric angle parametrization)


f(u) = d sin(u t(u)) / sin(t(u))
f(u) = (1-u) t(u)
(Blend curve P(u) in polar coordinates)
How to Find Arc Through 3 Data Points ?
(We don’t really need arc, just need tangents!)
B
a
A
b
b
a
a
b
a
c
b
a
 Do
b
not try to find center, radius !
C
Key Insights
 The
typical polynomial spline
blends between the straight-line segments
of the control polygon.

Circle splines start with an overlapping
sequence of circular arc segments
and then blend between those.

The relevant parameter in this context
are ( turning / tangent ) angles.
Why This Works

We want to emulate a (loopy) MVC.

The ideal MVC result is a circle.
 If you want to see circles, start with circles !
 Affine
invariance  dimensional collapse.
 Circles
always consider problem in a 2D way,
giving equal weight to both coordinate axes.
Caveat
 These

curves are not MVC’s !
While they are G2 (C2) continuous, they
may possess unnecessary undulations.
BAD TANGENT
UNNECESSARY INFLECTION POINTS
A local scheme cannot compete with a global scheme !
Extensions

Extend range of local support to >3 points.

Better approximation to MVC:
Cornu spiral or clothoid
(curvature is linear with arc length).

In 3D also consider a helix
as a primitive.
 Issues are :

How to find robustly and efficiently
the (unique?) matching primitives ?

How to blend them ?
An “Evolutionary” Process…

From rulers…
Polynomial splines
with their linear interpolation
are reminiscent of straight edge rulers…
An Evolutionary Process…

From rulers…
 to
compasses…
Circle splines
capture the power of compasses…
QUESTIONS
?
An Evolutionary
Process…

From rulers…
 to

compasses…
to French Curves !