Abstract
Ever since its introduction by Stam and Loop, the quad/triangle subdivision scheme, which is a generalization of the well-known Catmull–Clark subdivision and Loop subdivision, has attracted a great deal of interest due to its flexibility of allowing both quads and triangles in the same model. In this paper, we present a novel biorthogonal wavelet—constructed through the lifting scheme—that accommodates the quad/triangle subdivision. The introduced wavelet smoothly unifies the Catmull–Clark subdivision wavelet (for quadrilateral meshes) and the Loop subdivision wavelet (for triangular meshes) in a single framework. It can be used to flexibly and efficiently process any complicated semi-regular hybrid meshes containing both quadrilateral and triangular regions. Because the analysis and synthesis algorithms of the wavelet are composed of only local lifting operations allowing fully in-place calculations, they can be performed in linear time. The experiments demonstrate sufficient stability and fine fitting quality of the presented wavelet, which are similar to those of the Catmull–Clark subdivision wavelet and the Loop subdivision wavelet. The wavelet analysis can be used in various applications, such as shape approximation, progressive transmission, data compression and multiresolution edit of complex models.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bajaj, C., Schaefer, S., Warren, J., Xu, G.: A subdivision scheme for hexahedral meshes. Vis. Comput. 18(5–6), 343–356 (2002)
Ball, A., Storry, D.: A matrix approach to the analysis of recursively generated B-spline surfaces. Comput. Aided Des. 18, 437–442 (1986)
Beets, K., Claes, J., Van Reeth, F.: Optimizing Mesh Construction for Quad/Triangle Schemes. Lecture Notes in Computer Science, vol. 4035, pp. 711–718. Springer, Berlin (2006)
Bertram, M.: Biorthogonal Loop-subdivision wavelets. Computing 72(1–2), 29–39 (2004)
Bertram, M., Duchaineau, M., Hamann, B., et al.: Bicubic subdivision-surface wavelets for large-scale isosurface representation and visualization. In: Proceedings Visualization’2000, pp. 389–396 (2000)
Bertram, M., Duchaineau, M., Hamann, B., et al.: Generalized B-spline subdivision-surface wavelets for geometry compression. IEEE Trans. Vis. Comput. Graph. 10(3), 326–338 (2004)
Bonneau, G.: Multiresolution analysis on irregular surface meshes. IEEE Trans. Vis. Comput. Graph. 4(4), 365–378 (1998)
Catmull, E., Clark, J.: Recursively generated B-spline surfaces on arbitrary topological meshes. Comput. Aided Des. 10, 350–355 (1978)
Doo, D., Sabin, M.: Behavior of recursive division surfaces near extraordinary points. Comput. Aided Des. 10, 356–360 (1978)
Dyn, N., Levin, D., Gregory, J.: A butterfly subdivision scheme for surface interpolation with tension control. ACM Trans. Graph. 9(2), 160–169 (1990)
Eck, M., DeRose, T., Duchamp, T., et al.: Multiresolution analysis of arbitrary meshes. In: Proceedings of SIGGRAPH’1995, pp. 173–182 (1995)
Khodakovsky, A., Schröder, P., Sweldens, W.: Progressive geometry compression. In: Proceedings of SIGGRAPH’2000, New Orleans, Louisiana, USA, pp. 271–278 (2000)
Kobbelt, L.: Interpolatory subdivision on Open quadrilateral nets with arbitrary topology. Comput. Graph. Forum 15(3), 409–420 (1996) (Proceedings of Eurographics’96)
Kobbelt, L.: Root 3-subdivision. In: Proceedings of SIGGRAPH’2000, New Orleans, Louisiana, USA, pp. 103–112 (2000)
Kobbelt, L., Vorsatz, J., Labsik, U., et al.: A shrink wrapping approach to remeshing polygonal surfaces. Comput. Graph. Forum 18, C119–C130 (1999), Eurographics’99 issue
Labsik, U., Greiner, G.: Interpolatory root 3-subdivision. Comput. Graph. Forum 19(3), 131–138 (2000)
Lee, A., Sweldens, W., Schröder, P., et al.: MAPS: multiresolution adaptive parameterization of surfaces. In: Proceedings of SIGGRAPH’1998, Orlando, Florida, pp. 95–104 (1998)
Li, D., Qin, K., Sun, H.: Unlifted Loop subdivision wavelets. In: Proceedings of Pacific Graphics’2004, Seoul, Korea, pp. 25–33 (2004)
Li, G., Ma, W., Bao, H.: Root 2-subdivision for quadrilateral meshes. Vis. Comput. 20(2–3), 180–198 (2004)
Litke, N., Levin, A., Schröder, P.: Fitting subdivision surfaces. In: Proceedings of IEEE Visualization’2001, pp. 319–324 (2001)
Loop, C.: Smooth subdivision surfaces based on triangles. M.S. Thesis, Department of Mathematics, University of Utah (1987)
Lounsbery, M., DeRose, T., Warren, J.: Multiresolution analysis for surfaces of arbitrary topological type. ACM Trans. Graph. 16(1), 34–73 (1997)
Peters, J., Shiue, L.: Combining 4- and 3-direction subdivision. ACM Trans. Graph. 23(4), 980–1003 (2004)
Samavati, F., Bartels, R.: Multiresolution curve and surface editing: reversing subdivision rules by least-squares data fitting. Comput. Graph. Forum 18(2), 97–119 (1999)
Samavati, F., Mahdavi-Amiri, N., Bartels, R.: Multiresolution surfaces having arbitrary topologies by a reverse Doo subdivision method. Comput. Graph. Forum 21(2), 121–136 (2002)
Schaefer, S., Warren, J.: On C2 triangle/quad subdivision. ACM Trans. Graph. 24(1), 28–36 (2005)
Schröder, P., Sweldens, W.: Spherical wavelets: efficiently representing functions on the sphere. Comput. Graph. 161–172 (1995) (Proceedings of SIGGRAPH’95)
Sederberg, T., Zheng, J., Sewell, D., et al.: Non-uniform recursive subdivision surfaces. Comput. Graph. 387–394 (1998) (Proceedings of SIGGRAPH’98)
Stam, J., Loop, C.: Quad/triangle subdivision. Comput. Graph. Forum 22(1), 79–85 (2003)
Sweldens, W.: The lifting scheme: a custom-design construction of biorthogonal wavelets. Appl. Comput. Harmon. Anal. 3(2), 186–200 (1996)
Sweldens, W.: The lifting scheme: a construction of second generation wavelets. SIAM J. Math. Anal. 29(2), 511–546 (1997)
Valette, S., Prost, R.: Wavelet-based multiresolution analysis of irregular surface meshes. IEEE Trans. Vis. Comput. Graph. 10(2), 113–122 (2004)
Valette, S., Prost, R.: Wavelet-based progressive compression scheme for triangle meshes: Wavemesh. IEEE Trans. Vis. Comput. Graph. 10(2), 123–129 (2004)
Velho, L., Zorin, D.: 4–8 subdivision. Comput. Aided Geom. Des. 18(5), 397–427 (2001)
Wang, H., Qin, K., Tang, K.: Efficient wavelet construction with Catmull–Clark subdivision. Vis. Comput. 22(9–11), 874–884 (2006)
Wang, H., Qin, K., Sun, H.: Root 3-subdivision-based biorthogonal wavelets. IEEE Trans. Vis. Comput. Graph. 13(5), 914–925 (2007)
Wang, H., Tang, K., Qin, K.: Biorthogonal wavelets based on gradual subdivision of quadrilateral meshes. Comput. Aided Geom. Des. (2007), doi:10.1016/j.cagd.2007.11.002
Wu, J., Amaratunga, K.: Wavelet triangulated irregular networks. Int. J. Geograph. Inf. Sci. 17(3), 273–289 (2003)
Zorin, D., Schröder, P.: A unified framework for primal/dual quadrilateral subdivision schemes. Comput. Aided Geom. Des. 18(5), 429–454 (2001)
Zorin, D., Schröder, P., Sweldens, W.: Interpolating subdivision for meshes with arbitrary topology. In: Proceedings of SIGGRAPH’96, pp. 189–192 (1996)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, H., Tang, K. Biorthogonal wavelet construction for hybrid quad/triangle meshes. Vis Comput 25, 349–366 (2009). https://doi.org/10.1007/s00371-008-0300-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00371-008-0300-6