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

 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 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.

 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