skip to main content
article

Variational normal meshes

Published: 01 October 2004 Publication History

Abstract

Hierarchical representations of surfaces have many advantages for digital geometry processing applications. <i>Normal meshes</i> are particularly attractive since their level-to-level displacements are in the local normal direction only. Consequently, they only require scalar coefficients to specify. In this article, we propose a novel method to approximate a given mesh with a normal mesh. Instead of building an associated parameterization on the fly, we assume a globally smooth parameterization at the beginning and cast the problem as one of perturbing this parameterization. Controlling the magnitude of this perturbation gives us explicit control over the range between fully constrained (only scalar coefficients) and unconstrained (3-vector coefficients) approximations. With the unconstrained problem giving the lowest approximation error, we can thus characterize the error cost of normal meshes as a function of the number of nonnormal offsets---we find a significant gain for little (error) cost. Because the normal mesh construction creates a <i>geometry driven</i> approximation, we can replace the difficult geometric distance minimization problem with a much simpler least squares problem. This variational approach reduces magnitude <i>and</i> structure (aliasing) of the error further. Our method separates the parameterization construction into an initial setup followed only by subsequent perturbations, giving us an algorithm which is far simpler to implement, more robust, and significantly faster.

References

[1]
Aksoylu, B., Khodakovsky, A., and Schröder, P. 2005. Multilevel solvers for unstructured surface meshes. in review, SIAM J. Sci. Comput. To appear.
[2]
Burt, P. J. and Adelson, E. H. 1983. Laplacian Pyramid as a compact image code. IEEE Trans. on Commun. 31, 532--540.
[3]
Cignoni, P., Rocchini, C., and Scopigno, R. 1998. Metro: Measuring Error on Simplified Surfaces. Computer Graphics Forum 17, 2, 167--174.
[4]
Daubechies, I., Runborg, O., and Sweldens, W. 2004. Normal Multiresolution Approximation of Curves. Constructive Approximation.
[5]
Gu, X., Gortler, S. J., and Hoppe, H. 2002. Geometry Images. ACM Trans. Graph. 21, 3, 355--361.
[6]
Guskov, I., Vidimče, K., Sweldens, W., and Schröder, P. 2000. Normal Meshes. In Proceedings of SIGGRAPH 2000, 95--102.
[7]
Hoppe, H. 1996. Progressive Meshes. In Proceedings of SIGGRAPH 96, 99--108.
[8]
Jansen, M., Baraniuk, R., and Lavu, S. 2003. Multiscale Approximation of Piecewise Smooth Two-Dimensional Functions using Normal Triangulated Meshes. To appear.
[9]
Khodakovsky, A. and Guskov, I. 2002. Normal Mesh Compression. In Geometric Modeling for Scientific Visualization, G. Brunnett, B. Hamann, and H. Müller, Eds. Springer Verlag.
[10]
Khodakovsky, A., Litke, N., and Schröder, P. 2003. Globally Smooth Parameterizations With Low Distortion. ACM Trans. Graph. 22, 3, 350--357.
[11]
Lavu, S., Choi, H., and Baraniuk, R. 2003. Geometry Compression of Normal Meshes using Rate-Distortion Algorithms. In Proceedings of Symposium on Geometry Processing (Eurographics/ACM SIGGRAPH), 52--61.
[12]
Lee, A., Moreton, H., and Hoppe, H. 2000. Displaced Subdivision Surfaces. In Proceedings of ACM SIGGRAPH 2000, 85--94.
[13]
Lee, A. W. F., Sweldens, W., Schröder, P., Cowsar, L., and Dobkin, D. 1998. MAPS: Multiresolution Adaptive Parameterization of Surfaces. In Proceedings of SIGGRAPH 98, 95--104.
[14]
Lounsbery, M., DeRose, T. D., and Warren, J. 1997. Multiresolution Analysis for Surfaces of Arbitrary Topological Type. ACM Trans. Graph. 16, 1, 34--73.
[15]
Schreiner, J., Asirvatham, A., Praun, E., and Hoppe, H. 2004. Inter-surface mapping. ACM Trans. Graph. 23, 3, 870--877.
[16]
Schröder, P. and Sweldens, W., Eds. 1996. Wavelets in Computer Graphics. Course Notes. ACM SIGGRAPH.
[17]
Schröder, P. and Sweldens, W., Eds. 2001. Digital Geometry Processing. Course Notes. ACM SIGGRAPH.
[18]
Zorin, D., Schröder, P., and Sweldens, W. 1996. Interpolating Subdivision for Meshes with Arbitrary Topology. In Proceedings of SIGGRAPH 96, 189--192.
[19]
Zorin, D., Schröder, P., and Sweldens, W. 1997. Interactive Multiresolution Mesh Editing. In Proceedings of SIGGRAPH 97, 259--268.

Cited By

View all
  • (2021)Surface multigrid via intrinsic prolongationACM Transactions on Graphics10.1145/3450626.345976840:4(1-13)Online publication date: 19-Jul-2021
  • (2016)A Novel Approach for Semi-regular Mesh Based on Planar Proxies2016 13th International Conference on Computer Graphics, Imaging and Visualization (CGiV)10.1109/CGiV.2016.13(18-23)Online publication date: Mar-2016
  • (2015)Semi-Regular Triangle RemeshingComputer Graphics Forum10.1111/cgf.1246134:1(86-102)Online publication date: 1-Feb-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 23, Issue 4
October 2004
145 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/1027411
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2004
Published in TOG Volume 23, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. (semi-)regular meshes
  2. Hierarchy
  3. normal meshes
  4. resampling
  5. subdivision
  6. surface approximation

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)1
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)Surface multigrid via intrinsic prolongationACM Transactions on Graphics10.1145/3450626.345976840:4(1-13)Online publication date: 19-Jul-2021
  • (2016)A Novel Approach for Semi-regular Mesh Based on Planar Proxies2016 13th International Conference on Computer Graphics, Imaging and Visualization (CGiV)10.1109/CGiV.2016.13(18-23)Online publication date: Mar-2016
  • (2015)Semi-Regular Triangle RemeshingComputer Graphics Forum10.1111/cgf.1246134:1(86-102)Online publication date: 1-Feb-2015
  • (2012)Sparsity-based optimization of two lifting-based wavelet transforms for semi-regular mesh compressionComputers & Graphics10.1016/j.cag.2012.02.00436:4(272-282)Online publication date: Jun-2012
  • (2011)Normal Multi-scale Transforms for CurvesFoundations of Computational Mathematics10.5555/3115448.311562811:6(617-656)Online publication date: 1-Dec-2011
  • (2011)Normal Multi-scale Transforms for CurvesFoundations of Computational Mathematics10.1007/s10208-011-9104-611:6(617-656)Online publication date: 28-Oct-2011
  • (2011)A robust feature-preserving semi-regular remeshing method for triangular meshesThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-011-0555-127:9(811-825)Online publication date: 1-Sep-2011
  • (2010)Normal multi-scale transforms for surfacesProceedings of the 7th international conference on Curves and Surfaces10.1007/978-3-642-27413-8_34(527-542)Online publication date: 24-Jun-2010
  • (2010)Globally convergent adaptive normal multi-scale transformsProceedings of the 7th international conference on Curves and Surfaces10.1007/978-3-642-27413-8_19(296-310)Online publication date: 24-Jun-2010
  • (2009)Normal mesh based geometrical image compressionImage and Vision Computing10.1016/j.imavis.2008.06.01727:4(459-468)Online publication date: 1-Mar-2009
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media