An incremental approach to feature aligned quad dominant remeshing

ABSTRACT

In this paper we present a new algorithm which turns an unstructured triangle mesh into a quad-dominant mesh with edges aligned to the principal directions of the underlying geometry. Instead of computing a globally smooth parameterization or integrating curvature lines along a tangent vector field, we simply apply an iterative relaxation scheme which incrementally aligns the mesh edges to the principal directions. The quad-dominant mesh is eventually obtained by dropping the not-aligned diagonals from the triangle mesh. A post-processing stage is introduced to further improve the results. The major advantage of our algorithm is its conceptual simplicity since it is merely based on elementary mesh operations such as edge collapse, flip, and split. The resulting meshes exhibit a very good alignment to surface features and rather uniform distribution of mesh vertices. This makes them very well-suited, e.g., as Catmull-Clark Subdivision control meshes.

REFERENCES

• 1: 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
• 2: 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
• 3: Alliez, P., Ucelli, G., Gotsman, C., and Attene, M. 2005. Recent advances in remeshing of surfaces. Tech. rep., AIM@SHAPE Network of Excellence.
• 4: Marco Attene , Bianca Falcidieno , Jarek Rossignac , Michela Spagnuolo, Edge-sharpener: recovering sharp features in triangulations of non-adaptively re-meshed surfaces, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 5: Ioana Boier-Martin , Holly Rushmeier , Jingyi Jin, Parameterization of triangle meshes over quadrilateral domains, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057459]
• 6: Botsch, M., and Kobbelt, L. 2001. Resampling feature and blend regions in polygonal meshes for surface anti-aliasing. Computer Graphics Forum 20, 3, 402--410.
• 7: Mario Botsch , Leif Kobbelt, A remeshing approach to multiresolution modeling, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057457]
• 8: Canas, G. D., and Gortler, S. J. 2006. Surface remeshing in arbitrary codimensions. The Visual Computer 22, 9--11, 885--895.
• 9: David Cohen-Steiner , Jean-Marie Morvan, Restricted delaunay triangulations and normal cycle, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777839]
• 10: David Cohen-Steiner , Pierre Alliez , Mathieu Desbrun, Variational shape approximation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 11: Do Carmo, M. P. 1976. Differential Geometry of Curves and Surfaces. Prentice-Hall.
• 12: S. Dong , S. Kircher , M. Garland, Harmonic functions for quadrilateral remeshing of arbitrary manifolds, Computer Aided Geometric Design, v.22 n.5, p.392-423, July 2005 [doi>10.1016/j.cagd.2005.04.004]
• 13: Shen Dong , Peer-Timo Bremer , Michael Garland , Valerio Pascucci , John C. Hart, Spectral surface quadrangulation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 14: 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]
• 15: Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 16: Hertzmann, A., and Zorin, D. 2000. Illustrating smooth surfaces. ACM Transactions on Graphics 19, 3, 517--526.
• 17: Kälberer, F., Nieser, M., and Polthier, K. 2007. Quad-Cover - surface parameterization using branched coverings. Computer Graphics Forum 27, 3.
• 18: Yu-Kun Lai , Qian-Yi Zhou , Shi-Min Hu , Johannes Wallner , Helmut Pottmann, Robust Feature Classification and Editing, IEEE Transactions on Visualization and Computer Graphics, v.13 n.1, p.34-45, January 2007 [doi>10.1109/TVCG.2007.19]
• 19: 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]
• 20: Yang Liu , Helmut Pottmann , Johannes Wallner , Yong-Liang Yang , Wenping Wang, Geometric modeling with conical meshes and developable surfaces, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 21: Martin Marinov , Leif Kobbelt, Direct Anisotropic Quad-Dominant Remeshing, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, p.207-216, October 06-08, 2004
• 22: Marinov, M., and Kobbelt, L. 2006. A robust two-step procedure for quad-dominant remeshing. Computer Graphics Forum 25, 3, 537--546.
• 23: Nicolas Ray , Wan Chiu Li , Bruno Lévy , Alla Sheffer , Pierre Alliez, Periodic global parameterization, ACM Transactions on Graphics (TOG), v.25 n.4, p.1460-1485, October 2006 [doi>10.1145/1183287.1183297]
• 24: Ray, N., Vallet, B., Li, W.-C., and Levy, B. 2006. N-symmetry direction fields on surfaces of arbitrary genus. Tech. rep., INRIA, France.
• 25: 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
• 26: Thomas W. Sederberg , Jianmin Zheng , Almaz Bakenov , Ahmad Nasri, T-splines and T-NURCCs, ACM Transactions on Graphics (TOG), v.22 n.3, July 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: Surazhsky, V., Alliez, P., and Gotsman, C. 2003. Isotropic remeshing of surfaces: a local parameterization approach. In Proc. 12th Int'l Meshing Roundtable.
• 29: Tchon, K.-F., and Camarero, R. 2006. Quad-dominant mesh adaptation using specialized simplicial optimization. In Proc. 15th International Meshing Roundtable, 21--38.
• 30: Y. Tong , P. Alliez , D. Cohen-Steiner , M. Desbrun, Designing quadrangulations with discrete harmonic forms, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 31: Wan-Chiu Li , Nicolas Ray , Bruno Lévy, Automatic and interactive mesh to T-spline conversion, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 32: William Welch , Andrew Witkin, Variational surface modeling, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.157-166, July 1992
• 33: Andrew P. Witkin , Paul S. Heckbert, Using particles to sample and control implicit surfaces, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.269-277, July 1994 [doi>10.1145/192161.192227]
• 34: Yong-Liang Yang , Yu-Kun Lai , Shi-Min Hu , Helmut Pottmann, Robust principal curvatures on multiple scales, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy

INDEX TERMS

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

Keywords:
feature alignment, local updates, quad dominant remeshing