Leif Kobbelt
ABSTRACT
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.
- BLZ99.H. Biermann, A. Levin, D. Zorin, Piecewise smooth subdivision sur-faces with normal control, PreprintGoogle Scholar
- CC78.E. Catmull, J. Clark, Recursively generated B-spline surfaces on arbi-trary topological meshes, CAD 10 (1978), 350-355Google ScholarCross Ref
- CDM91.A. Cavaretta, W. Dahmen, C. Micchelli, Stationary Subdivision, Mem-oirs of the AMS 93 (1991), pp. 1-186 Google ScholarDigital Library
- DS78.D. Doo, M. Sabin, Behaviour of recursive division surfaces near ex-traordinary points, CAD 10 (1978), 356-360Google ScholarCross Ref
- DGL90.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 Google ScholarDigital Library
- Dyn91.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.Google Scholar
- GSS99.I. Guskov, W. Sweldens, P. Schr~ oder, Multiresolution signal processing for meshes, SIGGRAPH 99 Proceedings, 1999, pp. 325 - 334 Google ScholarDigital Library
- GvL96.G. Golub, C. van Loan, Matrix Computations, 3rd, Johns Hopkins Univ Press, 1996 Google ScholarDigital Library
- GZZ93.M. Griebel, C. Zenger, S. Zimmer, Multilevel Gauss-Seidel-Algorithms for Full and Sparse Grid Problems, Computing 50, 1993, pp. 127-148Google ScholarCross Ref
- Gus98.I. Guskov, Multivariate subdivision schemes and divided differences, Preprint, Princeton University, 1998Google Scholar
- Hac85.W. Hackbusch, Multi-Grid Methods and Applications, Springer, Berlin, 1985Google ScholarCross Ref
- HDD+94.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 Google ScholarDigital Library
- Kob96.L. Kobbelt, Interpolatory Subdivision on Open Quadrilateral Nets with Arbitrary Topology, Computer Graphics Forum 15 (1996), Eurographics '96 Conference Issue, pp. 409-420Google Scholar
- KDS98.L. Kobbelt, K. Daubert, H-P. Seidel, Ray-tracing of subdivision sur-faces, 9th Eurographics Workshop on Rendering Proceedings, 1998, pp. 69 - 80Google Scholar
- KCVS98.L. Kobbelt, S. Campagna, J. Vorsatz, H-P. Seidel, Interactive multires-olution modeling on arbitrary meshes, SIGGRAPH 98 Proceedings, 1998, pp. 105-114 Google ScholarDigital Library
- Lev99.A. Levin, Interpolating nets of curves by smooth subdivision surfaces, SIGGRAPH 99 Proceedings, 1999, pp. 57 - 64 Google ScholarDigital Library
- Loo87.C. Loop, Smooth subdivision surfaces based on triangles, Master The-sis, Utah University, USA, 1987Google Scholar
- Pra98.H. Prautzsch, Smoothness of subdivision surfaces at extraordinary points, Adv. Comp. Math. 14 (1998), pp. 377 - 390Google ScholarCross Ref
- Rei95.U. Reif, A unified approach to subdivision algorithms near extraordi-nary vertices, CAGD 12 (1995), pp. 153-174 Google ScholarDigital Library
- RP98.U. Reif, J. Peters, The simplest subdivision scheme for smoothing poly-hedra, ACM Trans. Graph. 16 (1998), pp. 420 - 431 Google ScholarDigital Library
- Sab87.M. Sabin, Recursive Division, in The Mathematics of Surfaces, Claren-don Press, 1986, pp. 269 - 282Google Scholar
- Sta98.J. Stam, Exact evaluation of Catmull/Clark subdivision surfaces at ar-bitrary parameter values, SIGGRAPH 98 Proceeding, 1998, pp. 395 - 404 Google ScholarDigital Library
- VG99.L. Velho, J. Gomes, Quasi-stationary subdivision using four directional meshes, PreprintGoogle Scholar
- VG00.L. Velho, J. Gomes, Semi-regular 4-8 refinement and box spline sur-faces, PreprintGoogle Scholar
- VT92.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 - 832Google Scholar
- Ver96.R. Verf~ urth, A review of a posteriori error estimation and adaptive mesh refinement techniques, Wiley-Teubner, 1996Google Scholar
- War00.J. Warren, Subdivision methods for geometric design, unpublished manuscript Google ScholarDigital Library
- ZSS96.D. Zorin, P. Schr~ oder, W. Sweldens, Interpolating Subdivision for Meshes with Arbitrary Topology, SIGGRAPH 96 Proceedings, 1996, pp. 189-192 Google ScholarDigital Library
- Zor97.D.Zorin, C k Continuity of Subdivision Surfaces, Thesis, California In-stitute of Technology, 1997Google Scholar
- ZSS97.D. Zorin, P. Schr~ oder, W. Sweldens, Interactive multiresolution mesh editing, SIGGRAPH 97 Proceedings, 1997, pp. 259-268 Google ScholarDigital Library
Index Terms
- √3-subdivision
Recommendations
√3-based 1-form subdivision
Proceedings of the 7th international conference on Curves and SurfacesIn this paper we construct an edge based, or <em>1-form</em>, subdivision scheme consistent with <InlineEquation ID="IEq2"><InlineMediaObject><ImageObject FileRef="978-3-642-27413-8_22_Chapter_TeX2GIF_IEq2.gif" Format="GIF" Color="BlackWhite" Type="...
Composite primal/dual √3-subdivision schemes
We present new families of primal and dual subdivision schemes for triangle meshes and √3-refinement. The proposed schemes use two simple local rules which cycle between primal and dual meshes a number of times. The resulting surfaces become very smooth ...
Combining 4- and 3-direction subdivision
4-3 direction subdivision combines quad and triangle meshes. On quad submeshes it applies a 4-direction alternative to Catmull-Clark subdivision and on triangle submeshes a modification of Loop's scheme. Remarkably, 4-3 surfaces can be <i>proven to be C<...
Comments