A remeshing approach to multiresolution modeling

ABSTRACT

Providing a thorough mathematical foundation, multiresolution modeling is the standard approach for global surface deformations that preserve fine surface details in an intuitive and plausible manner. A given shape is decomposed into a smooth low-frequency base surface and high-frequency detail information. Adding these details back onto a deformed version of the base surface results in the desired modification. Using a suitable detail encoding, the connectivity of the base surface is not restricted to be the same as that of the original surface. We propose to exploit this degree of freedom to improve both robustness and efficiency of multiresolution shape editing.In several approaches the modified base surface is computed by solving a linear system of discretized Laplacians. By remeshing the base surface such that the Voronoi areas of its vertices are equalized, we turn the unsymmetric surface-related linear system into a symmetric one, such that simpler, more robust, and more efficient solvers can be applied. The high regularity of the remeshed base surface further removes numerical problems caused by mesh degeneracies and results in a better discretization of the Laplacian operator.The remeshing is performed on the low-frequency base surface only, while the connectivity of the original surface is kept fixed. Hence, this functionality can be encapsulated inside a multiresolution kernel and is thus completely hidden from the user.

References

1. {ACdVDI03} Alliez P., Colin de Verdière É., Devillers O., Isenburg M.: Isotropic surface remeshing. In Proceedings of Shape Modeling International (2003), pp. 49--58.
2. {AKS} Aksoylu B., Khodakovsky A., Schröder P.: Multilevel Solvers for Unstructured Surface Meshes. In review, SIAM J. Sci. Comput.
3. {AMS90} Ashby S. F., Manteuffel T. A., Saylor P. E.: A taxonomy for conjugate gradient methods. SIAM J. Numer. Anal. 27, 6 (1990), 1542--1568.
4. {BBC*94} Barrett R., Berry M., Chan T. F., Demmel J., Donato J., Dongarra J., Eijkhout V., Pozo R., Romine C., der Vorst H. V.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition. SIAM, Philadelphia, PA, 1994.
5. {BK03} Botsch M., Kobbelt L.: Multiresolution surface representation based on displacement volumes. In Proceedings of Eurographics 03 (2003), pp. 483--492.
6. {BK04} Botsch M., Kobbelt L.: An intuitive framework for real-time freeform modeling. In Proceedings of ACM SIGGRAPH 04 (2004).
7. {CM69} Cuthill E., McKee J.: Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 24th National Conference ACM (1969), pp. 157--172.
8. {DEG*99} Demmel J. W., Eisenstat S. C., Gilbert J. R., Li X. S., Liu J. W. H.: A supernodal approach to sparse partial pivoting. SIAM Journal on Matrix Analysis and Applications 20, 3 (1999), 720--755.
9. {DMA02} Desbrun M., Meyer M., Alliez P.: Intrinsic parameterizations of surface meshes. In Proceedings of Eurographics 02 (2002), pp. 209--218.
10. {DMSB99} Desbrun M., Meyer M., Schröder P., Barr A.: Implicit fairing of irregular meshes using diffusion and curvature flow. In Proceedings of ACG SIGGRAPH 99 (1999), pp. 317--324.
11. {FB88} Forsey D. R., Bartels R. H.: Hierarchical B-spline refinement. In Proceedings of ACM SIGGRAPH 88 (1988), vol. 22, pp. 205--212.
12. {FB95} Forsey D., Bartels R. H.: Surface fitting with hierarchical splines. ACM Transactions on Graphics 14, 2 (1995), 134--161.
13. {GL81} George A., Liu J. W.: Computer Solution of Large Sparse Positive Definite Matrices,. Prentice Hall, 1981.
14. {GL89} Golub G. H., Loan C. F. V.: Matrix Computations. Johns Hopkins University Press, Baltimore, 1989.
15. {GSS99} Guskov I., Sweldens W., Schröder P.: Multiresolution signal processing for meshes. In Proceedings of ACM SIGGRAPH 99 (1999), pp. 325--334.
16. {GVSS00} Guskov I., Vidimce K., Sweldens W., Schröder P.: Normal meshes. In Proceedings of ACM SIGGRAPH 00 (2000), pp. 95--102.
17. {Hac86} Hackbusch W.: Multi-Grid Methods and Applications. Springer Verlag, 1986.
18. {KBS00} Kobbelt L., Bareuther T., Seidel H.-P.: Multiresolution shape deformations for meshes with dynamic vertex connectivity. In Proceedings of Eurographics 00 (2000).
19. {KCVS98} Kobbelt L., Campagna S., Vorsatz J., Seidel H.-P.: Interactive multi-resolution modeling on arbitrary meshes. In Proceedings of ACM SIGGRAPH 98 (1998), pp. 105--114.
20. {KVS99} Kobbelt L., Vorsatz J., Seidel H.-P.: Multiresolution hierarchies on unstructured triangle meshes. Computational Geometry: Theory and Applications 14 (1999).
21. {Lév03} Lévy B.: Dual domain extrapolation. In Proceedings of ACM SIGGRAPH 03 (2003), pp. 364--369.
22. {MDSB03} Meyer M., Desbrun M., Schröder P., Barr A. H.: Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and Mathematics III, Hege H.-C., Polthier K., (Eds.). Springer-Verlag, Heidelberg, 2003, pp. 35--57.
23. {PFTV92} Press W. H., Flannery B. P., Teukolsky S. A., Vetterling W. T.: Numerical Recipes: The Art of Scientific Computing, 2nd ed. Cambridge University Press, 1992.
24. {PP93} Pinkall U., Polthier K.: Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1 (1993), 15--36.
25. {RL03} Ray N., Levy B.: Hierarchical Least Squares Conformal Map. In Proceedings of Pacific Graphics 03 (2003), pp. 263--270.
26. {SAG03} Surazhsky V., Alliez P., Gotsman C.: Isotropic remeshing of surfaces: In Proceedings of 12th International Meshing Roundtable (2003).
27. {SG03} Surazhsky V., Gotsman C.: Explicit surface remeshing. In Proceedings of the Eurographics/ACM SIGGRAPH symposium on Geometry processing (2003), pp. 20--30.
28. {TCR} Toledo S., Chen D., Rotkin V.: Taucs: A library of sparse linear solvers. http://www.tau.ac.il/stoledo/taucs.
29. {VRS03} Vorsatz J., Rössl C., Seidel H.-P.: Dynamic remeshing and applications. In Proceedings of Solid Modeling and Applications (2003), pp. 167--175.
30. {ZSS97} Zorin D., Schröder P., Sweldens W.: Interactive multiresolution mesh editing. In Proceedings of ACM SIGGRAPH 97 (1997), pp. 259--268.

• Computing methodologies

  • Computer graphics

• Theory of computation