×

4–8 Subdivision. (English) Zbl 0969.68157

Summary: We introduce 4-8 subdivision, a new scheme that generalizes the four-directional box spline of class \(C^{4}\) to surfaces of arbitrary topological type. The crucial advantage of the proposed scheme is that it uses bisection refinement as an elementary refinement operation, rather than more commonly used face or vertex splits. In the uniform case, bisection refinement results in doubling, rather than quadrupling of the number of faces in a mesh. Adaptive bisection refinement automatically generates conforming variable-resolution meshes in contrast to face and vertex split methods which require a postprocessing step to make an adaptively refined mesh conforming. The fact that the size of faces decreases more gradually with refinement allows one to have greater control over the resolution of a refined mesh. It also makes it possible to achieve higher smoothness while using small stencils (the size of the stencils used by our scheme is similar to Loop subdivision). We show that the subdivision surfaces produced by the 4-8 scheme are \(C^{4}\) continuous almost everywhere, except at extraordinary vertices where they are is \(C^{1}\)-continuous.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Biermann, H.; Levin, A.; Zorin, D., Piecewise smooth subdivision surfaces with normal control, (Proceedings of SIGGRAPH 2000 (2000))
[2] Borouchaki, H.; Frey, P.; George, P., Unstructured triangular-quadrilateral mesh generation (1996)
[3] Catmull, E.; Clark, J., Recursively generated B-spline surfaces on arbitrary topological meshes, Computer-Aided Design, 10, 350-365 (1978)
[4] Cavaretta, A. S.; Dahmen, W.; Micchelli, C. A., Stationary subdivision, Mem. Amer. Math. Soc., 12, 453 (1991) · Zbl 0741.41009
[5] de Boor, C.; Hollig, D.; Riemenschneider, S., Box Splines (1994), Springer-Verlag: Springer-Verlag New York
[6] de Boor, C.; Höllig, K.; Riemenschneider, S., Box Splines (1993), Springer-Verlag: Springer-Verlag New York · Zbl 0814.41012
[7] Doo, D.; Sabin, M., Behaviour of recursive division surfaces near extraordinary points, Computer-Aided Design, 10, 356-360 (1978)
[8] Duchaineau, M.; Wolinsky, M.; Sigeti, D.; Miller, M.; Aldrich, C.; Mineev-Weinstein, M., Roaming terrain: Real-time optimally adapting meshes, (IEEE Visualization ’97 (1997)), 81-88
[9] Evans, W.; Kirkpatrick, D.; Townsend, G., Right triangular irregular networks (1997), Technical Report 97-0, University of Arizona · Zbl 0984.65014
[10] Feauveau, J. C., Wavelets and their Applications (chapter: Wavelets for the Quincunx Pyramid) (1992), Jones and Bartlet · Zbl 0792.94003
[11] Gritz, L.; Hahn, J. K., BMRT: A global illumination implementation of the renderman standard, J. Graphics Tools, 1, 3, 29-47 (1996)
[12] Grünbaum, B.; Shephard, G., Tilings and Patterns (1987), W.H. Freeman · Zbl 0601.05001
[13] Habib, A.; Warren, J., Edge and vertex insertion for a class of
((C^1\) subdivision surfaces, Computer Aided Geometric Design, 16, 4, 223-247 (1997), Previously available as a TR, Rice University, August 1997 · Zbl 0916.68151
[14] Hebert, D. J., Cyclic interlaced quadtree algorithms for quincunx multiresolution, J. Algorithms, 27, 97-128 (1998) · Zbl 0919.68050
[15] Von Herzen, B.; Barr, A. H., Accurate triangulations of deformed, intersecting surfaces, Computer Graphics (Proceedings of SIGGRAPH 87), 21, 4, 103-110 (1987), Held in Anaheim, CA
[16] Jury, E. I., Theory and Applications of the \(z\)-Transform Method (1964), Wiley: Wiley New York
[17] Kobbelt, L., Interpolatory subdivision on open quadrilateral nets with arbitrary topology, Computer Graphics Forum, 15, 3, 409-420 (1996)
[18] Kobbelt, L., Interpolatory subdivision on open quadrilateral nets with arbitrary topology, (Computer Graphics Forum (Proc. EUROGRAPHICS ’96), 15(3) (1996)), 409-420
[19] Kobbelt, L., \(3\) subdivision, (SIGGRAPH 2000 Conference Proceedings (2000))
[20] Lane, J.; Riesenfeld, R., A theoretical development for the computer generation and display of piecewise polynomial surfaces, IEEE Trans. Pattern Analysis Machine Intell., 2, 1, 35-46 (1980) · Zbl 0436.68063
[21] Lawton, W.; Lee, S. L.; Shen, Z., Stability and orthonormality of multivariate refinable functions, SIAM J. Math. Anal., 28, 4, 999-1014 (1997) · Zbl 0872.41003
[22] Levy, S.; Munzner, T.; Phillips, M., Geomview (1991), Geometry Center, University of Minnesota
[23] Lindstrom, P.; Koller, D.; Ribarsky, W.; Hughes, L. F.; Faust, N.; Turner, G., Real-time, continuous level of detail rendering of height fields, (SIGGRAPH 96 Conference Proceedings (1996)), 109-118
[24] Loop, C., Smooth subdivision for surfaces based on triangles. Master’s Thesis (1987), University of Utah
[25] Peters, J.; Reif, U., The simplest subdivision scheme for smoothing polyhedra, ACM Transactions on Graphics, 16, 4, 420-431 (1997)
[26] Reif, U., A unified approach to subdivision algorithms near extraordinary vertices, Computer Aided Geometric Design, 12, 2, 153-174 (1995) · Zbl 0872.65007
[27] Rivara, M. C., Mesh refinement processes based on the generalized bisection of simplices, SIAM J. Numer. Anal., 21, 3, 604-613 (1984) · Zbl 0574.65133
[28] Stam, J., Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values, (SIGGRAPH 98 Conference Proceedings (1998)), 395-404
[29] Velho, L., Using semi-regular 4-8 meshes for subdivision surfaces, J. Graphics Tools (2001) · Zbl 0971.68176
[30] Velho, L.; Gomes, J., Hierarchical \(4- k\) Meshes: Concepts and Applications. Computer Graphics Forum (2000)
[31] Zorin, D., A method for analysis of
((C^1\)-continuity of subdivision surfaces, SIAM J. Numer. Anal., 37, 4 (2000) · Zbl 0959.65021
[32] Zorin, D., Smoothness of subdivision on irregular meshes, Constructive Approximation, 16, 3 (2000) · Zbl 0965.65024
[33] Zorin, D.; Schröder, P.; Sweldens, W., Interactive multiresolution mesh editing, (SIGGRAPH 97 Conference Proceedings (1997)), 259-268
[34] Zorin, D., Schröder, P. (Eds.) 2000. Subdivision for modeling and animation. Course notes of Siggraph 2000, ACM SIGGRAPH; Zorin, D., Schröder, P. (Eds.) 2000. Subdivision for modeling and animation. Course notes of Siggraph 2000, ACM SIGGRAPH
[35] Zorin, D.; Duchamp, T.; Biermann, H., Smoothness of subdivision surfaces on the boundary (2000), Technical report, New York University, Dept. of Computer Science, In preparation
[36] Zwart, P. B., Multivariate splines with nondegenerate partitions, SIAM J. Numer. Anal., 10, 4, 665-673 (1973) · Zbl 0261.65011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.