CS29413 HW3 Subdivision Surface
By FuChung 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 (CatmullClark Subdivision) has 3 major steps: split facet, split edge, join edge, as illustrated by the following figure


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.
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 
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 
Principal Direction for Kmax
and Kmin
Mid
Level Surface 
Kmax
Curvature 
Kmin
Curvature 
Smooth
Limit Surface 
A little bit about exact
evaluation
Here I tried to implement Jos Stam’s paper on “Exact Evaluation of CatmullClark 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.
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 BSpline 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 minmax 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 balllike shape.
3 level subdivision 
Mean, original 
optimized 
Optimized curvature 
Optimized smooth limit 
50 iteration 
100 iteration 
200 iteration 
500 iteration 
1000 iteration 