Split&Tweak schemes for Cubic Bspline, four-points, and Jarek subdivisions


Demo comparing uniform cubic Bspline (red), 4-point (blue), and Jarek (green) subdivisions.
Written by  Mark Luffel  as Project 1 in Prof. Jarek Rossignac's undergraduate graphics class.  

Click on control vertices and drag to move them. Click near edges and drag to insert new ones.
Press c, b, j, or f to show/hide control polygon, B-spline, Jarek, Four-point curves.
Press 1 through 5 to set level of subdivision.
Press space to reset.

Assume that the control polygon has vertices V0, V1,...Vn and that i+1=j=k-1.
All 3 schemes perform iterations that each combine a split and a tweak phase.
The split phase inserts a new vertex Mij in the middle of each edge between vertex Vi and Vj.
The tweak computes for each old vertex Vj a displacement vector Dj=Vi/8+Vk/8-Vj/4.
which is the half the displacemetn between Vj and the average of its two new neighbors.

For a uniform cubic B-spline, the tweak leaves Mij where they are and simply moves each old vertex Vj to Vj+Dj.  This is equivalent to moving Vj half-way towards the average of its new neighbors. Repeating this two phase process converges to the uniform cubic B-spline curve. Notice that the process shrinks convex parts of the curve.

For a four-point subdivision, the tweak leaves the orriginal vertices Vj where they are and simply moves each new vertex Mij by -(Di+Dj)/2. Notice that the four-point iteration is equivalent to first performing a B-spline iteration and then "expanding" the result by moving the old vertices back to their place before the iteration and by moving each new verttex by the average displacement of its two neighbors.  Notice that the limit curve interpolates the original control points but exhibits overshots when a short edge is adjacent to a long edge at a sharp angle.

For Jarek's subdivision make a compromise: Move each Vj by Dj/2 and each Mij by -(Di+Dj)/4. Notice that the limit curve of Jarek's subdivision lies between the B-spline and the Four-point curves. It is closer to the control polygons.  Jarek's scheme may be used to smoothen the control polygon, when preserving the area is important. Also, the original control polygon, or the results of m Split&Tweak iterations, are a better approximation for the limit curve for Jarek's subdivision than for the other two.

Jarek's subdivision and other examples of  teaching concepts of geometry processing are described in the following report, to appear in a special issue of the CAD Journal on CAD Education:
"Education-Driven Research in CAD", Jarek Rossignac. June 2003. GVU Tech. Report GIT-GVU-03-26.    
Source code
Built with Processing