CS294-13 HW3 Subdivision Surface

By Fu-Chung Huang

Basic Subdivision Surface

For the project I use CGAL half edge data structure for basic design (note I only use its data structure, the rest is implemented by myself.)

CGAL half edge data structure support basic Euler Operator, e.g., divide facet, joint facets, and etc.

The process I subdivide surface using primal method (Catmull-Clark Subdivision) has 3 major steps: split facet, split edge, join edge, as illustrated by the following figure

Procedure

1.      Create center vertex by split facet

2.      Create vertices (on boundary edges) by splitting triangular facets

3.      Merge diagonal half edge pairs to form new rectangular facets.

4.      Remember to update the vertices position, and we are done.

 

 

Here is two simple example of the subdivision results, my program generally support quad mesh (in .obj format) without boundary.

Ring_Ori

Original_Cube

Ring_Smooth

Cube_Level2_Control_Smooth

 

 

Feature Tagging

Here the tagging algorithm I used is that for each time of subdivision, decrement sharpness value s by 1, and when s = 0, it follows the normal subdivision rule, otherwise a separate rule for edges (not using facet points) and vertices (c is number of sharp edge around vertex, and rules are defined for c > 2, c = 2, and c < 2 respectively) are used.

Tagging sharpness s = Inf at edges of bottom and top face

Tagging at bottom face only

Tagging s = 1 for top face, and s = Inf at bottom

Tagging only 2 edges s = Inf

Tag2_orig

Tag3_Orig

Tag1_Orig

Tag4_orig

Tag2_smooth

Tag3_smooth

Tag1_Smooth

Tag4_smooth

 

Gauss and Mean Curvature Plot

Here for each vertex I collect its local one ring to compute the PCA, and extract the Kmax and Kmin.

Mean curvature is compute by (Kmax + Kmin)/2, where Gauss curvature is (Kmax*Kmin).

The curvature is normalized to [0,1] for visualization purpose, so note that the negative value for Kmin multiply by large value Kmax will result in very small value(negative).

Control Polygon

Mid Level Surface

Mean Curvature

Gauss Curvature

Limit Smooth Surface

corner1_orig

Corner2_smooth

Corner2_mean

Corner2_Gauss

Corner1_smooth

 

 

Principal Direction for Kmax and Kmin

Mid Level Surface

Kmax Curvature

Kmin Curvature

Smooth Limit Surface

L_flat

L_kmax

L_kmin

L_smooth

Ring_flat

Ring_kmax

Ring_kmin

Ring_Smooth

Sphere_flat

Sphere_kmax

Sphere_kmin

Sphere_Smooth

 

 

A little bit about exact evaluation

Here I tried to implement Jos Stam’s paper on “Exact Evaluation of Catmull-Clark Subdivision Surface At Arbitrary Parameter Values.” The problem is divided into two parts, one for ordinary regular patches (derived from original control quad facet), and patches that contain extraordinary point.

Here is the preview for the patch parameterization: for extraordinary patches I use the ordering notion as described in the paper, i.e. direction u from v1->v6, and direction v from v1->v4, and use one ring clockwise neighborhood for numbering vertices.

On the middle image is the local patch subdivision surface. For the center extraordinary point, its 3 connecting patches have strict ordering rules, blue direction is +u and orange is +v.

Cube_Level2_Control

Cube_Level2_Parameterization

Center_Ordering

Cube_Level2_Control_Smooth

Control polygon, 2 level subdivisions from cube.

Local patch parameterization.

Extraordinary point neighbor ordering

Smooth limit surface

For the regular patches, I use standard Bicubic B-Spline evaluation at (u,v) using 16 control points, which is pretty straightforward and interpolate nicely.

Unfortunately I ran into some trouble about evaluating the value at extraordinary patches.

Florian told me there is some hidden secret (?) about formula as described in the paper, but I don’t have enough time to figure out them before the deadline, so I will just stop here.

 

Optimization

For optimization I basically use simulated annealing by randomly chose a control point and jitter it slightly.

If the error energy goes down or increase by less than 1% (avoid local minima), then I will accept the configuration.

This method doesn’t run particular fast. In particular it doesn’t compute the Jacobian toward the minimum energy direction.

The error energy I use is the maximum mean curvature as guide, so the optimization is guaranteed to produce min-max curvature, and here is the result.

Note that the curvature plots are normalized each time. The colors are matched to normalized [0, 1] range, so it looks like error are not decreasing.

However when look into the shape for a while, it tells that curvature is minimized when it evolve to certain ball-like shape.

3 level subdivision

Mean, original

optimized

Optimized curvature

Optimized smooth limit

50 iteration

100 iteration

200 iteration

500 iteration

1000 iteration