User-controllable polycube map for manifold spline construction

ABSTRACT

Polycube T-spline has been formulated elegantly that can unify T-splines and manifold splines to define a new class of shape representations for surfaces of arbitrary topology by using polycube map as its parametric domain. In essense, The data fitting quality using polycube T-splines hinges upon the construction of underlying polycube maps. Yet, existing methods for polycube map construction exhibit some disadvantages. For example, existing approaches for polycube map construction either require projection of points from a 3D surface to its polycube approximation, which is therefore very difficult to handle the cases when two shapes differ significantly; or compute the map by conformally deforming the surfaces and polycubes to the common canonical domain and then construct the map using function composition, which is challenging to control the location of singularities and makes it hard for the data-fitting and hole-filling processes later on.

This paper proposes a novel framework of user-controllable polycube maps, which can overcome disadvantages of the conventional methods and is much more efficient and accurate. The current approach allows users to directly select the corner points of the polycubes on the original 3D surfaces, then construct the polycube maps by using the new computational tool of discrete Euclidean Ricci flow. We develop algorithms for computing such polycube maps, and show that the resulting user-controllable polycube map serves as an ideal parametric domain for constructing spline surfaces and other applications. The location of singularities can be interactively placed where no important geometric features exist. Experimental results demonstrate that the proposed polycube maps introduce lower area distortion and retain small angle distortion as well, and subsequently make the entire hole-filling process much easier to accomplish.

REFERENCES

• 1: Carner, C., Jin, M., Gu, X., and Qin, H. 2005. Topology-driven surface mappings with robust feature alignment. In IEEE Visualization
• 2: Chow, B., and Luo, F. 2003. Combinatorial Ricci flows on surfaces.J. Differential Geom. 63, 1, 97--129.
• 3: 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]
• 4: 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
• 5: Floater, M. S., and Hormann, K. 2005. Surface parameterization: a tutorial and survey. In Advances in multiresolution for geometric modelling, N. A. Dodgson, M. S. Floater, and M. A. Sabin, Eds. Springer Verlag, 157--186.
• 6: Steven J. Gortler , Craig Gotsman , Dylan Thurston, Discrete one-forms on meshes and applications to 3D mesh parameterization, Computer Aided Geometric Design, v.23 n.2, p.83-112, February 2006 [doi>10.1016/j.cagd.2005.05.002]
• 7: Craig Gotsman , Xianfeng Gu , Alla Sheffer, Fundamentals of spherical parameterization for 3D meshes, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 8: Cindy M. Grimm , John F. Hughes, Modeling surfaces of arbitrary topology using manifolds, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.359-368, September 1995 [doi>10.1145/218380.218475]
• 9: Gu, X., and Vemuri, B. C. 2004. Matching 3d shapes using 2d conformal representations. In MICCAI(1), 771--780.
• 10: 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
• 11: Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 12: Gu, X., Wang, Y., Chan, T. F., Thompson, P. M., and Yau, S.-T. 2004. Genus zero surface conformal mapping and its application to brain surface mapping. IEEE Transactions on Medical Imaging 23, 8 (Aug.), 945--958.
• 13: Xianfeng Gu , Ying He , Hong Qin, Manifold splines, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.27-38, June 13-15, 2005, Cambridge, Massachusetts [doi>10.1145/1060244.1060249]
• 14: Xianfeng Gu , Ying He , Miao Jin , Feng Luo , Hong Qin , Shing-Tung Yau, Manifold splines with single extraordinary point, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China [doi>10.1145/1236246.1236258]
• 15: Steven Haker , Sigurd Angenent , Allen Tannenbaum , Ron Kikinis , Guillermo Sapiro , Michael Halle, Conformal Surface Parameterization for Texture Mapping, IEEE Transactions on Visualization and Computer Graphics, v.6 n.2, p.181-189, April 2000 [doi>10.1109/2945.856998]
• 16: Hamilton, R. S. 1988. The Ricci flow on surfaces. Mathematics and general relativity 71, 237--262.
• 17: He, Y., Jin, M., Gu, X., and Qin, H. 2005. A C¹ globally interpolatory spline of arbitrary topology. In LNCS, vol. 3752, 295--306.
• 18: He, Y., Gu, X.-F., and Qin, H. 2006. Automatic shape control of triangular B-splines of arbitrary topology. J. Comput. Sci. Technol. 21, 2, 232--237.
• 19: He, Y., Wang, K., Wang, H., Gu, X., and Qin, H. 2006. Manifold T-spline. In Proceedings of Geometric Modeling and Processing, 409--122.
• 20: Henle, M. 1979. A Combinatorial Intorduction to Topology. W. H. Freeman and Co.
• 21: Hoppe, H. 1998. Efficient implementation of progressive meshes. Computers & Graphics 22, 1, 27--36.
• 22: Miao Jin , Yalin Wang , Shing-Tung Yau , Xianfeng Gu, Optimal Global Conformal Surface Parameterization, Proceedings of the conference on Visualization '04, p.267-274, October 10-15, 2004 [doi>10.1109/VIS.2004.75]
• 23: Miao Jin , Feng Luo , Xianfeng Gu, Computing surface hyperbolic structure and real projective structure, Proceedings of the 2006 ACM symposium on Solid and physical modeling, June 06-08, 2006, Cardiff, Wales, United Kingdom [doi>10.1145/1128888.1128904]
• 24: Jost, J., and Simha, R. R. 1997. Compact Riemann Surfaces: An Introduction to Contemporary Mathematics. Springer-Verlag Telos.
• 25: Kälberer, F., Nieser, M., and Polthier, K. 2007. Quad-cover - surface parameterization using branched coverings. Computer Graphics Forum 26, 375--384.
• 26: Kharevych, L., Springborn, B., and Schröder, P. 2005. Cone singularities to the rescue: Mitigating area distorsion in discrete conformal. In ACM SIGGRAPH/Eurographics Symposium on Geometry Processing.
• 27: Liliya Kharevych , Boris Springborn , Peter Schröder, Discrete conformal mappings via circle patterns, ACM Transactions on Graphics (TOG), v.25 n.2, p.412-438, April 2006 [doi>10.1145/1138450.1138461]
• 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: Bruno Lévy , Sylvain Petitjean , Nicolas Ray , Jérome Maillot, Least squares conformal maps for automatic texture atlas generation, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 30: 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
• 31: 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, August 02-06, 0093, Anaheim, CA [doi>10.1145/166117.166120]
• 32: Xinlai Ni , Michael Garland , John C. Hart, Fair morse functions for extracting the topological structure of a surface mesh, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 33: Perelman, G. 2002. The entropy formula for the ricci flow and its geometric application.
• 34: Perelman, G. 2003. Finite extinction time for the solutions to the ricci flow on certain three-manifolds.
• 35: Perelman, G. 2003. Ricci flow with surgery on three-manifolds.
• 36: Emil Praun , Hugues Hoppe, Spherical parametrization and remeshing, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 37: 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]
• 38: Rodin, B., and Sullivan, D. 1987. The convergence of circle packings to the Riemann mapping. J. Differential Geom. 26, 2, 349--360.
• 39: 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
• 40: Thomas W. Sederberg , David L. Cardon , G. Thomas Finnigan , Nicholas S. North , Jianmin Zheng , Tom Lyche, T-spline simplification and local refinement, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 41: Hans-Peter Seidel, An Introduction to Polar Forms, IEEE Computer Graphics and Applications, v.13 n.1, p.38-46, January 1993 [doi>10.1109/38.180116]
• 42: Sheffer, A., and De Sturler, E. 2001. Parameterization of faceted surfaces for meshing using angle-based flattening. Eng. Comput. (Lond.) 17, 3, 326--337.
• 43: Alla Sheffer , Bruno Lévy , Maxim Mogilnitsky , Alexander Bogomyakov, ABF++: fast and robust angle based flattening, ACM Transactions on Graphics (TOG), v.24 n.2, p.311-330, April 2005 [doi>10.1145/1061347.1061354]
• 44: Alla Sheffer , Emil Praun , Kenneth Rose, Mesh parameterization methods and their applications, Foundations and Trends® in Computer Graphics and Vision, v.2 n.2, p.105-171, January 2006 [doi>10.1561/0600000011]
• 45: Stephenson, K. 2005. Introduction to circle packing. Cambridge University Press, Cambridge. The theory of discrete analytic functions.
• 46: Vitaly Surazhsky , Craig Gotsman, Explicit surface remeshing, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 47: Marco Tarini , Kai Hormann , Paolo Cignoni , Claudio Montani, PolyCube-Maps, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 48: Thurston, W. 1982. Hyperbolic geometry and 3-manifolds. In Low-dimensional topology (Bangor, 1979), vol. 48 of London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, 9--25.
• 49: 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
• 50: Wang, Y., and Zheng, J. 2006. Control point removal algorithm for T-spline surfaces. In GMP, 385--396.
• 51: Wang, L., Gu, X., Mueller, K., and Yau, S.-T. 2005. Uniform texture synthesis and texture mapping using global parameterization. The Visual Computer 21, 8--10, 801--810.
• 52: Hongyu Wang , Ying He , Xin Li , Xianfeng Gu , Hong Qin, Polycube splines, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China [doi>10.1145/1236246.1236281]
• 53: Lexing Ying , Denis Zorin, A simple manifold-based construction of surfaces of arbitrary smoothness, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 54: Jianmin Zheng , Yimin Wang , Hock Soon Seah, Adaptive T-spline surface fitting to z-map models, Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, November 29-December 02, 2005, Dunedin, New Zealand [doi>10.1145/1101389.1101468]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Keywords:
T-splines, affine atlas, manifold splines, polycube map, shape computing, solid modeling