“√3-subdivision” by Kobbelt

A new stationary subdivision scheme is presented which performs slower topological refinement than the usual dyadic split operation. The number of triangles increases in every step by a factor of 3 instead of 4. Applying the subdivision operator twice causes a uniform refinement with tri-section of every original edge (hence the name √3-subdivision) while two dyadic splits would quad-sect every original edge. Besides the finer gradation of the hierarchy levels, the new scheme has several important properties: The stencils for the subdivision rules have minimum size and maximum symmetry. The smoothness of the limit surface is C2 everywhere except for the extraordinary points where it is C1. The convergence analysis of the scheme is presented based on a new general technique which also applies to the analysis of other subdivision schemes. The new splitting operation enables locally adaptive refinement under built-in preservation of the mesh consistency without temporary crack-fixing between neighboring faces from different refinement levels. The size of the surrounding mesh area which is affected by selective refinement is smaller than for the dyadic split operation. We further present a simple extension of the new subdivision scheme which makes it applicable to meshes with boundary and allows us to generate sharp feature lines.

1. H. Biermann, A. Levin, D. Zorin, Piecewise smooth subdivision sur-faces with normal control, Preprint
2. E. Catmull, J. Clark, Recursively generated B-spline surfaces on arbi-trary topological meshes, CAD 10 (1978), 350-355
3. A. Cavaretta, W. Dahmen, C. Micchelli, Stationary Subdivision, Mem-oirs of the AMS 93 (1991), pp. 1-186
4. D. Doo, M. Sabin, Behaviour of recursive division surfaces near ex-traordinary points, CAD 10 (1978), 356-360
5. N. Dyn, J. Gregory, D. Levin, A Butterfly Subdivision Scheme for Sur-face Interpolation with Tension Controll, ACM Trans. Graph. 9 (1990), pp. 160-169
6. N. Dyn, Subdivision Schemes in Computer Aided Geometric Design, Advances in Numerical Analysis II, Wavelets, Subdivisions and Radial Functions, W.A. Light ed., Oxford University Press, 1991, pp: 36-104.
7. I. Guskov, W. Sweldens, P. Schr~ oder, Multiresolution signal processing for meshes, SIGGRAPH 99 Proceedings, 1999, pp. 325 – 334
8. G. Golub, C. van Loan, Matrix Computations, 3rd, Johns Hopkins Univ Press, 1996
9. M. Griebel, C. Zenger, S. Zimmer, Multilevel Gauss-Seidel-Algorithms for Full and Sparse Grid Problems, Computing 50, 1993, pp. 127-148
10. I. Guskov, Multivariate subdivision schemes and divided differences, Preprint, Princeton University, 1998
11. W. Hackbusch, Multi-Grid Methods and Applications, Springer, Berlin, 1985
12. H. Hoppe, T. DeRose, T. Duchamp, M. Halstead, H. Jin, J. McDonald, J. Schweitzer, W. Stuetzle, Piecewise smooth surface reconstruction, SIGGRAPH 1994 Proceedings, 1994, pp. 295-302
13. L. Kobbelt, Interpolatory Subdivision on Open Quadrilateral Nets with Arbitrary Topology, Computer Graphics Forum 15 (1996), Eurographics ’96 Conference Issue, pp. 409-420
14. L. Kobbelt, K. Daubert, H-P. Seidel, Ray-tracing of subdivision sur-faces, 9th Eurographics Workshop on Rendering Proceedings, 1998, pp. 69 – 80
15. L. Kobbelt, S. Campagna, J. Vorsatz, H-P. Seidel, Interactive multires-olution modeling on arbitrary meshes, SIGGRAPH 98 Proceedings, 1998, pp. 105-114
16. A. Levin, Interpolating nets of curves by smooth subdivision surfaces, SIGGRAPH 99 Proceedings, 1999, pp. 57 – 64
17. C. Loop, Smooth subdivision surfaces based on triangles, Master The-sis, Utah University, USA, 1987
18. H. Prautzsch, Smoothness of subdivision surfaces at extraordinary points, Adv. Comp. Math. 14 (1998), pp. 377 – 390
19. U. Reif, A unified approach to subdivision algorithms near extraordi-nary vertices, CAGD 12 (1995), pp. 153-174
20. U. Reif, J. Peters, The simplest subdivision scheme for smoothing poly-hedra, ACM Trans. Graph. 16 (1998), pp. 420 – 431
21. M. Sabin, Recursive Division, in The Mathematics of Surfaces, Claren-don Press, 1986, pp. 269 – 282
22. J. Stam, Exact evaluation of Catmull/Clark subdivision surfaces at ar-bitrary parameter values, SIGGRAPH 98 Proceeding, 1998, pp. 395 – 404
23. L. Velho, J. Gomes, Quasi-stationary subdivision using four directional meshes, Preprint
24. L. Velho, J. Gomes, Semi-regular 4-8 refinement and box spline sur-faces, Preprint
25. M. Vasilescu, D. Terzopoulos, Adaptive meshes and shells: Irregular triangulation, discontinuities and hierarchical subdivision, Proceedings of the Computer Vision and Pattern Recognition Conference, 1992, 829 – 832
26. R. Verf~ urth, A review of a posteriori error estimation and adaptive mesh refinement techniques, Wiley-Teubner, 1996
27. J. Warren, Subdivision methods for geometric design, unpublished manuscript
28. D. Zorin, P. Schr~ oder, W. Sweldens, Interpolating Subdivision for Meshes with Arbitrary Topology, SIGGRAPH 96 Proceedings, 1996, pp. 189-192
29. D.Zorin, C k Continuity of Subdivision Surfaces, Thesis, California In-stitute of Technology, 1997
30. D. Zorin, P. Schr~ oder, W. Sweldens, Interactive multiresolution mesh editing, SIGGRAPH 97 Proceedings, 1997, pp. 259-268