“Interpolating Subdivision for meshes with arbitrary topology” by Zorin, Schröder and Sweldens

Subdivision is a powerful paradigm for the generation of surfaces of arbitrary topology. Given an initial triangular mesh the goal is to produce a smooth and visually pleasing surface whose shape is controlled by the initial mesh. Of particular interest are interpolating schemes since they match the original data exactly, and play an important role in fast multiresolution and wavelet techniques. Dyn, Gregory, and Levin introduced the Butterfly scheme, which yields C1 surfaces in the topologically regular setting. Unfortunately it exhibits undesirable artifacts in the case of an irregular topology. We examine these failures and derive an improved scheme, which retains the simplicity of the Butterfly scheme, is interpolating, and results in smoother surfaces.

1. Ball, A. A., and Storry, D. J. T. Conditions for tangent plane continuity over recursively generated B-spline surfaces. ACM Transactions on Graphics 7, 2 (1988), 83-102.
2. Catmull, E., and Clark, J. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design 10, 6 (1978), 350-355.
3. Dahmen, W., Micchelli, C. A., and Seidel, H.-P. Blossoming begets B-splines bases built better by B-patches. Mathematics of Computation 59, 199 (1992), 97-115.
4. Doo, D. A subdivision algorithm for smoothing down irregularly shaped polyhedrons. In P~vceedings on Interactive Techniques in Computer Aided Design (Bologna, 1978), pp. 157-165.
5. Doo, D., and Sabin, M. Analysis of the behaviour of recursive division surfaces near extraordinary points. Computer Aided Design 10, 6 (1978), 356-360.
6. Dubuc, S. Interpolation through an iterative scheme. J. Math. Anal. Appl. 114 (1986), 185-204.
7. Dyn, N., Gregory, J. A., and Levin, D. A four-point interpolatory subdivision scheme for curve design. Computer Aided Geometric Design 4 (1987), 257-268.
8. Dyn, N., Hed, S., and Levin, D. Subdivision schemes for surface interpolation. In Workshop in ComputationaIGeometry (1993), A. C. et al., Ed., World Scientific, pp. 97-118.
9. Dyn, N., Levin, D., and Gregory, J. A. A butterfly subdivision scheme for surface interpolation with tension control. ACM Transactions on Graphics 9, 2 (1990), 160-169.
10. Dyn, N., Levin, D., and Micchelli, C. A. Using parameters to increase smoothness of curves and surfaces generated by subdivision. Computer Aided Geometric Design 7 (1990), 129-140.
11. Halstead, M., Kass, M., and DeRose, T. Efficient, fair interpolation using catmullclark surfaces. In Computer Graphics P1vceedings (1993), Annual Conference Series, ACM Siggraph, pp. 35-44.
12. Hoppe, H., DeRose, T., Duchamp, T., Halstead, M., Jin, H., McDonald, J., Schweitzer, J., and Stuetzle, W. Piecewise smooth surface reconstruction. In Computer Graphics P1vceedings (1994), Annual Conference Series, ACM Siggraph, pp. 295-302.
13. Kobbelt, L. Interpolatory subdivision on open quadrilateral nets with arbitrary topology. In Computer Graphics Forum (1996), vol. 15, Eurographics, Basil Blackwell Ltd. Eurographics ’96 Conference issue.
14. Loop, C. Smooth subdivision surfaces based on triangles. Master’s thesis, University of Utah, Department of Mathematics, 1987.
15. Loop, C. Smooth spline surfaces over irregular meshes. In Computer Graphics P1vceedings (1994), Annual Conference Series, ACM Siggraph, pp. 303-310.
16. Lounsbery, M., DeRose, T. D., and Warren, J. Multiresolution surfaces of arbitrary topological type. Department of Computer Science and Engineering 93-10-05, University of Washington, October 1993. Updated version available as 93-10-05b, January, 1994.
17. Nasri, A. H. Surface interpolation on irregular networks with normal conditions. Computer Aided Geometric Design 8 (1991 ), 89-96.
18. Peters, J. C1 surface splines. SIAMJ. Numer. Anal. 32, 2 (1995), 645-666.
19. Peters, J. Curvature continuous spline surfaces over irregular meshes. Computer Aided Geometric Design (to appear).
20. Reif, U. A unified approach to subdivision algorithms near extraordinary points. Computer Aided Geometric Design 12 (1995), 153-174.
21. Sabin, M. The use of Piecewise Fo1~s for the NumericaI Representation of Shape. PhD thesis, Hungarian Academy of Sciences, Budapest, 1976.
22. Schr/Sder, R, and Sweldens, W. Spherical wavelets: Efficiently representing functions on the sphere. In Computer Graphics P~vceedings (1995), Annual Conference Series, ACM Siggraph, pp. 161-172.
23. Sweldens, W. The lifting scheme: A construction of second generation wavelets. Tech. Rep. 1995:06, Industrial Mathematics Initiative, Department of Mathematics, University of South Carolina, 1995.
24. Warren, J. Subdivision methods for geometric design. Unpublished manuscript, November 1995.
25. Zorin, D., Schr/3der, R, and Sweldens, W. Interpolating subdivision for meshes of arbitrary topology. Tech. Rep. CS-TR-96-06, Caltech, Department of Computer Science, Caltech, 1996.