ABF++: fast and robust angle based flattening

ABSTRACT

Conformal parameterization of mesh models has numerous applications in geometry processing. Conformality is desirable for remeshing, surface reconstruction, and many other mesh processing applications. Subject to the conformality requirement, these applications typically benefit from parameterizations with smaller stretch. The Angle Based Flattening (ABF) method, presented a few years ago, generates provably valid conformal parameterizations with low stretch. However, it is quite time-consuming and becomes error prone for large meshes due to numerical error accumulation. This work presents ABF++, a highly efficient extension of the ABF method, that overcomes these drawbacks while maintaining all the advantages of ABF. ABF++ robustly parameterizes meshes of hundreds of thousands and millions of triangles within minutes. It is based on three main components: (1) a new numerical solution technique that dramatically reduces the dimension of the linear systems solved at each iteration, speeding up the solution; (2) a new robust scheme for reconstructing the 2D coordinates from the angle space solution that avoids the numerical instabilities which hindered the ABF reconstruction scheme; and (3) an efficient hierarchical solution technique. The speedup with (1) does not come at the expense of greater distortion. The hierarchical technique (3) enables parameterization of models with millions of faces in seconds at the expense of a minor increase in parametric distortion. The parameterization computed by ABF++ are provably valid, that is they contain no flipped triangles. As a result of these extensions, the ABF++ method is extremely suitable for robustly and efficiently parameterizing models for geometry-processing applications.

REFERENCES

• 1: 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]
• 2: Pierre Alliez , David Cohen-Steiner , Olivier Devillers , Bruno Lévy , Mathieu Desbrun, Anisotropic polygonal remeshing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 3: Degener, P., Meseth, J., and Klein, R. 2003. An adaptable surface parametrization method. In 12th International Meshing Roundtable. 201--213.
• 4: 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]
• 5: Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic parameterizations of surface meshes. In Proceedings of Eurographics. 209--218.
• 6: Matthias Eck , Tony DeRose , Tom Duchamp , Hugues Hoppe , Michael Lounsbery , Werner Stuetzle, Multiresolution analysis of arbitrary meshes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.173-182, September 1995 [doi>10.1145/218380.218440]
• 7: Michael S. Floater, Parametrization and smooth approximation of surface triangulations, Computer Aided Geometric Design, v.14 n.3, p.231-250, April 1997 [doi>10.1016/S0167-8396(96)00031-3]
• 8: Michael S. Floater, Mean value coordinates, Computer Aided Geometric Design, v.20 n.1, p.19-27, March 2003 [doi>10.1016/S0167-8396(02)00002-5]
• 9: Floater, M. S. and Hormann, K. 2004. Surface parameterization: A tutorial and survey. In Advances on Multiresolution in Geometric Modelling. M. S. F. N. Dodgson and M. Sabin, Eds. Springer-Verlag, Heidelberg.
• 10: Graphite. 2003. http://www.loria.fr/levy/Graphite/index.html.
• 11: Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 12: Gu, X. and Yau, S.-T. 2002. Computing conformal structures of surfaces. Comm. Inform. Syst. 2, 121--146.
• 13: Hormann, K. 2001. Theory and applications of parameterizing triangulations. Ph.D. thesis, Department of Computer Science, University of Erlangen.
• 14: Hormann, K. and Greiner, G. 2000. MIPS: An efficient global parametrization method. In Curve and Surface Design: Saint Malo 1999. P.-J. Laurent, P. Sablonniëre, and L. Schumaker, Eds. Vanderbilt University Press, 153--162.
• 15: Aaron W. F. Lee , Wim Sweldens , Peter Schröder , Lawrence Cowsar , David Dobkin, MAPS: multiresolution adaptive parameterization of surfaces, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.95-104, July 1998 [doi>10.1145/280814.280828]
• 16: Bruno Lévy, Dual domain extrapolation, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 17: Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps. ACM Trans. Graph. (SIGGRAPH). 362--371.
• 18: Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2003. http://www.loria.fr/levy/erratum.html.
• 19: Liesen, J., de Sturler, E., Sheffer, A., Aydin, Y., and Siefert, C. 2001. Preconditioners for indefinite linear systems arising in surface parameterization. In Proceedings of the 11th International Meshing Roundtable. 71--81.
• 20: Peter Lindstrom , Greg Turk, Fast and memory efficient polygonal simplification, Proceedings of the conference on Visualization '98, p.279-286, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 21: Jérôme Maillot , Hussein Yahia , Anne Verroust, Interactive texture mapping, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.27-34, September 1993 [doi>10.1145/166117.166120]
• 22: Mogilnitsky, M. 2004. Efficient, low distortion, conformal parameterization of large meshes. MS thesis, Technion.
• 23: Nocedal and Wright. 2000. Numerical Optimization. Springer.
• 24: Pinkall, U. and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experiment. Math. 2, 15.
• 25: Emil Praun , Wim Sweldens , Peter Schröder, Consistent mesh parameterizations, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.179-184, August 2001 [doi>10.1145/383259.383277]
• 26: 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
• 27: Pedro V. Sander , Steven J. Gortler , John Snyder , Hugues Hoppe, Signal-specialized parametrization, Proceedings of the 13th Eurographics workshop on Rendering, June 26-28, 2002, Pisa, Italy
• 28: Pedro V. Sander , John Snyder , Steven J. Gortler , Hugues Hoppe, Texture mapping progressive meshes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.409-416, August 2001 [doi>10.1145/383259.383307]
• 29: Sheffer, A. and de Sturler, E. 2001. Parameterization of faceted surfaces for meshing using angle based flattening. Engin. Comput. 17, 326--337.
• 30: Alla Sheffer , John C. Hart, Seamster: inconspicuous low-distortion texture seam layout, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 31: Olga Sorkine , Daniel Cohen-Or , Sivan Toledo, High-pass quantization for mesh encoding, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 32: Strang, G. 1988. Linear Algebra and Its Applications. 3rd Ed., Harcourt Brace Jovanovich, San Diego.
• 33: Robert W. Sumner , Jovan Popović, Deformation transfer for triangle meshes, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 34: Tutte, W. 1960. Convex representation of graphs. In Proceedings of the London Mathematical Society Vol. 10.
• 35: A Fast and Simple Stretch-Minimizing Mesh Parameterization, Proceedings of the Shape Modeling International 2004 (SMI'04), p.200-208, June 07-09, 2004 [doi>10.1109/SMI.2004.2]
• 36: Zayer, R., Roessl, C., and Seidel, H. P. 2004. Variations on angle based flattening. Proceedings of Mingle Workshop.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms

Keywords:
Mesh processing, conformality, parameterization