Parameterization of triangle meshes over quadrilateral domains

ABSTRACT

We present a method for parameterizing irregularly triangulated input models over polyhedral domains with quadrilateral faces. A combination of center-based clustering techniques is used to generate a partition of the model into regions suitable for remeshing. Several issues are addressed: the size and shape of the regions, their positioning with respect to features of the input geometry, and the amount of distortion introduced by approximating each region with a coarse polygon. Region boundaries are used to define a coarse polygonal mesh which is quadrangulated to obtain a parameterization domain. Constraints can be optionally imposed to enforce a strict correspondence between input and output features. We use the parameterization for multiresolution Catmull-Clark remeshing and we illustrate two applications that take advantage of the resulting representation: interactive model editing and texture mapping.

REFERENCES

• 1: In http://www.alias.com. 1
• 2: In http://www.discreet.com. 1
• 3: In http://www.catia.ibm.com. 1
• 4: 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
• 5: 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
• 6: Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
• 7: M. W. Bern and D. Eppstein. Quadrilateral meshing by circle packing. Int. J. Comp. Geom. Appl., 10(4):347--360, 2000. 2
• 8: F. Bernardini and H. Rushmeier. The 3D model acquisition pipeline. Computer Graphics Forum, 21(2):149--172, 2002. 8
• 9: P.-T. Bremer, S. Porumbescu, B. Hamann, and K. I. Joy. Automatic semi-regular mesh construction from adaptive distance fields. In Proc. Curves and Surfaces 02, 2002. 2
• 10: E. Catmull and J. Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. CAD, 10(6):350--355, 1978. 1, 2
• 11: P. Cignoni, C. Rocchini, and R. Scopigno. Metro: Measuring error on simplified ssurfaces. CG Forum, 17(2): 167--174, 1998. 7
• 12: Jonathan Cohen , Marc Olano , Dinesh Manocha, Appearance-preserving simplification, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.115-122, July 1998 [doi>10.1145/280814.280832]
• 13: Qiang Du , Vance Faber , Max Gunzburger, Centroidal Voronoi Tessellations: Applications and Algorithms, SIAM Review, v.41 n.4, p.637-676, Dec. 1999 [doi>10.1137/S0036144599352836]
• 14: Qiang Du , Max D. Gunzburger , Lili Ju, Constrained Centroidal Voronoi Tessellations for Surfaces, SIAM Journal on Scientific Computing, v.24 n.5, p.1488-1506, 2002 [doi>10.1137/S1064827501391576]
• 15: Matthias Eck , Hugues Hoppe, Automatic reconstruction of B-spline surfaces of arbitrary topological type, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.325-334, August 1996 [doi>10.1145/237170.237271]
• 16: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 17: Michael Garland , Andrew Willmott , Paul S. Heckbert, Hierarchical face clustering on polygonal surfaces, Proceedings of the 2001 symposium on Interactive 3D graphics, p.49-58, March 2001 [doi>10.1145/364338.364345]
• 18: A. Gersho. Asymptotically optimal block quantization. IEEE Trans. Inf. Theory, 25(4):373--380, 1978. 3
• 19: Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 20: Xianfeng Gu , Shing-Tung Yau, Global conformal surface parameterization, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 21: Igor Guskov , Andrei Khodakovsky , Peter Schröder , Wim Sweldens, Hybrid meshes: multiresolution using regular and irregular refinement, Proceedings of the eighteenth annual symposium on Computational geometry, p.264-272, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513443]
• 22: K. Hormann and G. Greiner. MIPS: An efficient global parametrization method. In Curve and Surface Design, pages 153--162. 2000. 7
• 23: K. Hormann and G. Greiner. Quadrilateral remeshing. In Proc. Vision, Modeling, and Viz 2000, pages 153--162, 2000. 2
• 24: Andreas Hubeli , Markus Gross, Multiresolution feature extraction for unstructured meshes, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 25: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 26: Sagi Katz , Ayellet Tal, Hierarchical mesh decomposition using fuzzy clustering and cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 27: Youngihn Kho , Michael Garland, User-guided simplification, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California [doi>10.1145/641480.641504]
• 28: Andrei Khodakovsky , Nathan Litke , Peter Schröder, Globally smooth parameterizations with low distortion, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 29: 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]
• 30: Venkat Krishnamurthy , Marc Levoy, Fitting smooth surfaces to dense polygon meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.313-324, August 1996 [doi>10.1145/237170.237270]
• 31: Aaron Lee , Henry Moreton , Hugues Hoppe, Displaced subdivision surfaces, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.85-94, July 2000 [doi>10.1145/344779.344829]
• 32: Bruno Lévy , Sylvain Petitjean , Nicolas Ray , Jérome Maillot, Least squares conformal maps for automatic texture atlas generation, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 33: Michael Lounsbery , Tony D. DeRose , Joe Warren, Multiresolution analysis for surfaces of arbitrary topological type, ACM Transactions on Graphics (TOG), v.16 n.1, p.34-73, Jan. 1997 [doi>10.1145/237748.237750]
• 34: J. MacQueen. Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. Math Statistics and Prob., pages 281--297, 1967. 4
• 35: Matthias Müller-Hannemann , Karsten Weihe, Minimum strictly convex quadrangulations of convex polygons, Proceedings of the thirteenth annual symposium on Computational geometry, p.193-202, June 04-06, 1997, Nice, France [doi>10.1145/262839.262960]
• 36: Yutaka Ohtake , Alexander G. Belyaev , Ilia A. Bogaevski, Polyhedral Surface Smoothing with Simultaneous Mesh Regularization, Proceedings of the Geometric Modeling and Processing 2000, p.229, April 10-12, 2000
• 37: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 38: Robert Osada , Thomas Funkhouser , Bernard Chazelle , David Dobkin, Shape distributions, ACM Transactions on Graphics (TOG), v.21 n.4, p.807-832, October 2002 [doi>10.1145/571647.571648]
• 39: S. Owen, M. Staten, S. Canann, and S. Saigal. A survey of unstructured mesh generation technology. In Proc. 7th Int. Meshing Roundable, pages 239--267, 1998. 1, 2
• 40: Emil Praun , Hugues Hoppe, Spherical parametrization and remeshing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 41: K. Pulli and M. Lounsbery. Hierarchical editing and rendering of subdivision surfaces. Technical Report UW-CSE-97-04-07, Dept. of CS&E, Univ. of Washington, Seattle, WA, 1997. 6
• 42: C. Rocchini, P. Cignoni, C. Montani, and R. Scopigno. Acquiring, stitching and blending appearance attributes on 3D models. The Visual Computer, 18(3):186--204, 2002. 8
• 43: 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]
• 44: P. V. Sander , Z. J. Wood , S. J. Gortler , J. Snyder , H. Hoppe, Multi-chart geometry images, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 45: V. Surazhsky, P. Alliez, and C. Gotsman. Isotropic remeshing of surfaces: a local parameterization approach. In Proc. 12th Intl. Meshing Roundtable, 2003. 2
• 46: L. Velho. Quadrilateral meshing using 4-8 clustering. In Proc. CILANCE'00, pages 61--64, 2000. 2
• 47: D. Zorin, P. Schröder, T. DeRose, L. Kobbelt, A. Levin, and W. Sweldens. Subdivision for modeling and animation. SIGGRAPH'00 Course Notes, 2000. 1, 6
• 48: 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]