Subdivision

Splines, Subdivision Surfaces and Fractal Mountains.: 

Splines, Subdivision Surfaces and Fractal Mountains. CS184 – Fall 2004

Outline: 

Outline Review Bézier Curves Subdivision Curves Subdivision Surfaces Quad mesh (Catmull-Clark scheme) Triangle mesh (Loop scheme) Fractal Mountains

Review of Bézier CurvesDeCastlejau Algorithm: 

Review of Bézier Curves DeCastlejau Algorithm V2 V4 V1 V3 Insert at t = ¾

Review of Bézier CurvesDeCastlejau Algorithm: 

Review of Bézier Curves DeCastlejau Algorithm 001 000 111 011 Insert at t = ¾ Ignore funny notation at vertices!

Review of Bézier CurvesDeCastlejau Algorithm: 

Review of Bézier Curves DeCastlejau Algorithm 001 000 111 011 00¾ ¾11 0¾1 Insert at t = ¾

Review of Bézier CurvesDeCastlejau Algorithm: 

Review of Bézier Curves DeCastlejau Algorithm 001 000 111 011 00¾ ¾¾1 ¾11 0¾1 0¾¾ Insert at t = ¾

Review of Bézier CurvesDeCastlejau Algorithm: 

Review of Bézier Curves DeCastlejau Algorithm 001 000 111 011 00¾ ¾¾1 ¾11 0¾1 0¾¾ ¾¾¾ Insert at t = ¾

Review of Bézier CurvesDeCastlejau Algorithm: 

Review of Bézier Curves DeCastlejau Algorithm 001 000 111 011 00¾ ¾¾1 ¾11 0¾1 0¾¾ ¾¾¾ Insert at t = ¾ Curve position and tangent for t = ¾

Review of Bézier CurvesDeCastlejau Algorithm: 

Review of Bézier Curves DeCastlejau Algorithm 001 000 111 011 00¾ ¾¾1 ¾11 0¾1 0¾¾ ¾¾¾ Insert at t = ¾ This also yields all control points for subdivision into 2 Bezier curves

Review of Bézier CurvesDeCastlejau Algorithm: 

Review of Bézier Curves DeCastlejau Algorithm 001 000 111 011 00¾ ¾¾1 ¾11 0¾1 0¾¾ ¾¾¾ Insert at t = ¾ Convex Hull Property!

Bézier Curves Summary: 

Bézier Curves Summary DeCastlejau algorithm is good for Evaluating position(t) and tangent(t), Subdividing the curve into 2 subcurves with their own control polygons. Subdivision of Bézier curves and their convex hull property allows for: Adaptive rendering based on a flatness criterion, Adaptive collision detection using line segment tests.

Outline: 

Outline Review Bézier Curves Subdivision Curves Subdivision Surfaces Quad mesh (Catmull-Clark scheme) Triangle mesh (Loop scheme) Fractal Mountains

Subdivision Curves: 

Subdivision Curves V20 V40 V10 V30 Subdivision is a recursive 2 step process Topological split Local averaging / smoothing Limit curve

Subdivision Curves: 

Subdivision Curves V20 V40 V10 V30 Subdivision is a repeated 2 step process Topological split Local averaging / smoothing E20 E40 E10 E30

Subdivision Curves: 

Subdivision Curves V20 V40 V10 V30 Subdivision is a repeated 2 step process Topological split Local averaging / smoothing E21 E41 E11 E31 V21 V11 V41 V31

Subdivision Curves: 

Subdivision Curves V20 V40 V10 V30 Subdivision is a repeated 2 step process Topological split Local averaging / smoothing E21 E41 E11 E31 V21 V11 V41 V31

Subdivision Curves: 

Subdivision Curves V20 V40 V10 V30 Subdivision is a repeated 2 step process Topological split Local averaging / smoothing E21 E41 E11 E31 V21 V11 V41 V31

Results in a Bspline Curve: 

Results in a Bspline Curve 4 1 3 2 1 4 3 2 4 Knots:

Subdivision Curve Summary: 

Subdivision Curve Summary Subdivsion is a recursive 2 step process: Topological split at midpoints, Local averaging/smoothing operator applied. Doubles the number of vertices at each step Subdivision curves are nothing new Suitable averaging rules can yield uniform Bspline curves.

Outline: 

Outline Review Bézier Curves Subdivision Curves Subdivision Surfaces Quad mesh (Catmull-Clark scheme) Triangle mesh (Loop scheme) Fractal Mountains

Subdivision Overview: 

Subdivision Overview Subdivision is a two part process: Topological split Local averaging / smoothing Control Mesh Topological Split Averaging Limit Surface

Subdivision Overview: 

Subdivision Overview Repeated uniform subdivisions of the control mesh converge to the limit surface. Limit surface can be calculated in closed form for stationary schemes (averaging mask does not change). Control Mesh Generation 1 Generation 2 Generation 3

Outline: 

Outline Review Bézier Curves Subdivision Curves Subdivision Surfaces: Quad mesh (Catmull-Clark scheme) Triangle mesh (Loop scheme) Fractal Mountains

Bspline Surfaces: 

Bspline Surfaces A single Bspline surface patch is controlled by a regular 4x4 grid of control points

Bspline Surfaces: 

Bspline Surfaces 2 adjacent patches share 12 control points and meet with C2 continuity

Bspline Surfaces: 

Bspline Surfaces Requires a regular rectangular control mesh grid and all valence-4 vertices to guarantee continuity.

Catmull-Clark Subdivision Surfaces: 

Catmull-Clark Subdivision Surfaces Yields smooth surfaces over arbitrary topology control meshes. Closed control mesh  closed limit surface. Quad mesh generalization of Bsplines C1 at non-valence 4 vertices, C2 everywhere else (Bsplines). Sharp corners can be tagged Allows for smooth and sharp features, Allows for non-closed meshes.

Catmull-Clark Subdivision: 

Catmull-Clark Subdivision Extraordinary vertices are generated by non-valence-4 vertices and faces in the input mesh. No additional extraordinary vertices are created after the first generation of subdivision. Gen 0 Gen 1 Gen 2

Catmull-Clark Averaging: 

Catmull-Clark Averaging (simple averaging) n = valence

Outline: 

Outline Review Bézier Curves Subdivision Curves Subdivision Surfaces Quad mesh (Catmull-Clark scheme) Triangle mesh (Loop scheme) Fractal Mountains

Loop Subdivision Surfaces: 

Loop Subdivision Surfaces Gen 0 Gen 1 Gen 2 n = valence

Summary: 

Summary Subdivision is a 2 step recursive process: Topological split, Local averaging / smoothing. It is an easy way to make smooth objects of irregular shape of topologies other than rectangular (torus). Available in SLIDE !

Outline: 

Outline Review Bézier Curves Subdivision Curves Subdivision Surfaces Quad mesh (Catmull-Clark scheme) Triangle mesh (Loop scheme) Fractal Mountains

Fractals: 

Fractals Self-similar recursive modeling operators: Sierpinski Triangle Koch Snowflake

Linear Fractal Mountains: 

Linear Fractal Mountains 2-step recursive process: Subdivide chain by creating edge midpoints, Randomly perturb midpoint positions (proportional to subdivided edge length). Gen 0: Gen 1: Gen 2: Gen 3:

Fractal Mountain Surfaces: 

Fractal Mountain Surfaces 2-step recursive process: Subdivide triangles at edge midpoints, Randomly perturb midpoint positions. Gen 0 Gen 1 Gen 2

Fractal Mountains Summary: 

Fractal Mountains Summary 2-step recursive process: Topological split at edge midpoints, Random perturbation of midpoint positions. Triangle topological split maintains a water-tight connected mesh. Useful to make uneven, “natural” terrain. Often a low-order subdivision is good enough to control terrain following vehicles.