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: Pierre Alliez , Éric Colin de Verdière , Olivier Devillers , Martin Isenburg, Isotropic Surface Remeshing, Proceedings of the Shape Modeling International 2003, p.49, May 12-15, 2003
• 2: Burak Aksoylu , Andrei Khodakovsky , Peter Schröder, Multilevel Solvers for Unstructured Surface Meshes, SIAM Journal on Scientific Computing, v.26 n.4, p.1146-1165, 2005 [doi>10.1137/S1064827503430138]
• 3: Steven F. Ashby , Thomas A. Manteuffel , Paul E. Saylor, A taxonomy for conjugate gradient methods, SIAM Journal on Numerical Analysis, v.27 n.6, p.1542-1568, Dec. 1990 [doi>10.1137/0727091]
• 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: E. Cuthill , J. McKee, Reducing the bandwidth of sparse symmetric matrices, Proceedings of the 1969 24th national conference, p.157-172, August 26-28, 1969 [doi>10.1145/800195.805928]
• 8: James W. Demmel , Stanley C. Eisenstat , John R. Gilbert , Xiaoye S. Li , Joseph W. H. Liu, A Supernodal Approach to Sparse Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.720-755, July 1999 [doi>10.1137/S0895479895291765]
• 9: {DMA02} Desbrun M., Meyer M., Alliez P.: Intrinsic parameterizations of surface meshes. In Proceedings of Eurographics 02 (2002), pp. 209--218.
• 10: Mathieu Desbrun , Mark Meyer , Peter Schröder , Alan H. Barr, Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.317-324, July 1999 [doi>10.1145/311535.311576]
• 11: David R. Forsey , Richard H. Bartels, Hierarchical B-spline refinement, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.205-212, June 1988
• 12: David R. Forsey , Richard H. Bartels, Surface fitting with hierarchical splines, ACM Transactions on Graphics (TOG), v.14 n.2, p.134-161, April 1995 [doi>10.1145/221659.221665]
• 13: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 14: {GL89} Golub G. H., Loan C. F. V.: Matrix Computations. Johns Hopkins University Press, Baltimore, 1989.
• 15: Igor Guskov , Wim Sweldens , Peter Schröder, Multiresolution signal processing for meshes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.325-334, July 1999 [doi>10.1145/311535.311577]
• 16: Igor Guskov , Kiril Vidimče , Wim Sweldens , Peter Schröder, Normal meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.95-102, July 2000 [doi>10.1145/344779.344831]
• 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: Leif Kobbelt , Swen Campagna , Jens Vorsatz , Hans-Peter Seidel, Interactive multi-resolution modeling on arbitrary meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.105-114, July 1998 [doi>10.1145/280814.280831]
• 20: Leif Kobbelt , Jens Vorsatz , Hans-Peter Seidel, Multiresolution hierarchies on unstructured triangle meshes, Computational Geometry: Theory and Applications, v.14 n.1-3, p.5-24, Nov. 1999 [doi>10.1016/S0925-7721(99)00032-2]
• 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: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes: the art of scientific computing, Cambridge University Press, New York, NY, 1986
• 24: {PP93} Pinkall U., Polthier K.: Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 1 (1993), 15--36.
• 25: Nicolas Ray , Bruno Levy, Hierarchical Least Squares Conformal Map, Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, p.263, October 08-10, 2003
• 26: {SAG03} Surazhsky V., Alliez P., Gotsman C.: Isotropic remeshing of surfaces: In Proceedings of 12th International Meshing Roundtable (2003).
• 27: Vitaly Surazhsky , Craig Gotsman, Explicit surface remeshing, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 28: {TCR} Toledo S., Chen D., Rotkin V.: Taucs: A library of sparse linear solvers. http://www.tau.ac.il/stoledo/taucs.
• 29: J. Vorsatz , Ch. Rössl , H.-P. Seidel, Dynamic remeshing and applications, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781633]
• 30: Denis Zorin , Peter Schröder , Wim Sweldens, Interactive multiresolution mesh editing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.259-268, August 1997 [doi>10.1145/258734.258863]