ABF++:Fast and Robust Angle Based FlatteningALLA SHEFFERUniversity of British ColumbiaBRUNO L´EVYINRIA LorraineandMAXIM MOGILNITSKY and ALEXANDER BOGOMYAKOVTechnionConformal parameterization of mesh models has numerous applications in geometry processing. Conformality is desirable forremeshing, surface reconstruction, and many other mesh processing applications. Subject to the conformality requirement, theseapplications typically benefit from parameterizations with smaller stretch. The Angle Based Flattening (ABF) method, presenteda few years ago, generates provably valid conformal parameterizations with low stretch. However, it is quite time-consumingand becomes error prone for large meshes due to numerical error accumulation. This work presents ABF++,ahighly efficientextension of the ABF method, that overcomes these drawbacks while maintaining all the advantages of ABF. ABF++ robustlyparameterizes 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 avoidsthe 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 parameterizationof models with millions of faces in seconds at the expense of a minor increase in parametric distortion. The parameterizationcomputed 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.Categories and Subject Descriptors: I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism—Color, shading,shadowing, and texture; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling; G.1.6 [Numerical Anal-ysis]: Optimization—Constrained optimization;J.6[Computer Aided Engineering]:General Terms: AlgorithmsAdditional Key Words and Phrases: Mesh processing, parameterization, conformality1. INTRODUCTIONWith recent advances in computer graphics hardware and digital geometry processing, parameterizedsurface meshes have become a widely used geometry representation. The parameterization defines aThis research was performed with the support of the AIM@SHAPE EU Network of Excellence and NSERC.Authors’ addresses: A. Sheffer, Department of Computer Science, University of British Columbia, Vancouver, BC, V6T 1Z4,Canada; email:[email protected]; B. Levy, INRIA Lorraine, 545000 Vandoeuvre, France; email: [email protected]; M. Mogilnitsky,Department of Computer Science, Technion, Haifa, 32000, Israel; A. Bogomyakov, Department of Computer Science, Technion,Haifa, 32000, Israel; email: [email protected] to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee providedthat copies are not made or distributed for profit or direct commercial advantage and that copies show this notice on the firstpage or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACMmust be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists,or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requestedfrom Publications Dept., ACM, Inc., 1515 Broadway, New York, NY 10036 USA, fax: +1 (212) 869-0481, or [email protected] 2005 ACM 0730-0301/05/0400-0311 $5.00ACM Transactions on Graphics, Vol. 24, No. 2, April 2005, Pages 311–330.312•A. Sheffer et al.correspondence between the surface mesh in 3D and a 2D domain, referred to as the parameter space.In the general case, the paramerizations are expected to be bijective, that is one-to-one. However formost practical applications, a weaker requirement of local bijectivity is sufficient. Local bijectivity isachieved when the planar mesh has no flipped (inverted) triangles. In the context of this article, theterm validity implies local bijectivity. The principal uses of parameterization are texture mapping andgeometry editing.— Texture mapping is the oldest application of parameterization. The parameter space is covered withan image which is then mapped onto the model through the parameterization. With the introduc-tion of programmable GPUs, more general attributes can be mapped onto the model in real time(e.g., BRDFs, bump maps, displacement maps, etc.). It is even possible to completely represent thegeometry of the model in parameter space, leading to the geometry images approach [Gu et al. 2002].— Geometry Editing is the second, increasingly popular, application domain. Using parameterization, itis possible to replace complex 3D algorithms operating on the surface with much simpler 2D compu-tations performed in parameter space. Applications that benefit from parameterized representationinclude multiresolution editing [Lee et al. 1998], surface fitting [Hormann and Greiner 2000], meshmorphing [Praun et al. 2001], remeshing [Alliez et al. 2003], and extrapolation [Levy 2003], to namejust a few.For all of these applications, the quality of the result depends heavily on the amount of deformationcaused by the parameterization. In the ideal case, areas and angles are preserved through the map-ping, that is the parameterization is isometric.Toreach this goal, the approach described in Maillotet al. [1993] minimizes a matrix norm of the deformation tensor. Unfortunately, only a small class ofsurfaces, that is developable surfaces, can be isometrically parameterized. Therefore, depending on theapplication, existing parameterization methods attempt to minimize different distortion components,such as angle deformation (conformal/harmonic parameterizations), length deformation (stretch), orarea deformation.1.1 Previous WorkFloater and Hormann [2004] provide an extensive survey of the state-of-the-art in parameterizationresearch. We briefly review the major techniques proposed for planar parameterization. We refer thereader to Floater and Hormann [2004] for a more detailed discussion of the numerous
View Full Document
Unlocking...