Mean value coordinates for arbitrary planar polygons

ABSTRACT

Barycentric coordinates for triangles are commonly used in computer graphics, geometric modeling, and other computational sciences because they provide a convenient way to linearly interpolate the data that is given at the corners of a triangle. The concept of barycentric coordinates can also be extended in several ways to convex polygons with more than three vertices, but most of these constructions break down when used in the nonconvex setting. Mean value coordinates offer a choice that is not limited to convex configurations, and we show that they are in fact well-defined for arbitrary planar polygons without self-intersections. Besides their many other important properties, these coordinate functions are smooth and allow an efficient and robust implementation. They are particularly useful for interpolating data that is given at the vertices of the polygons and we present several examples of their application to common problems in computer graphics and geometric modeling.

REFERENCES

• 1: Nur Arad , Nira Dyn , Daniel Reisfeld , Yehezkel Yeshurun, Image warping by radial basis functions: applications to facial expressions, CVGIP: Graphical Models and Image Processing, v.56 n.2, p.161-172, March 1994 [doi>10.1006/cgip.1994.1015 ]
• 2: R. K. Beatson , W. A. Light , S. Billings, Fast Solution of the Radial Basis Function Interpolation Equations: Domain Decomposition Methods, SIAM Journal on Scientific Computing, v.22 n.5, p.1717-1740, 2000 [doi>10.1137/S1064827599361771]
• 3: Beatson, R. K. and Newsam, G. N. 1992. Fast evaluation of radial basis functions: I. Comput Math. Appl. 24, 12, 7--19.
• 4: Buhmann, M. 2000. Radial basis functions: The state-of-the-art and new results. Acta Numer. 9, 1--37.
• 5: Ceva, G. 1678. De lineis rectis se invicem secantibus, statica constructio. Ludovici Montiae, Mediolanum.
• 6: Jianyun Chai , Takaharu Miyoshi , Eihachiro Nakamae, Contour interpolation and surface reconstruction of smooth terrain models, Proceedings of the conference on Visualization '98, p.27-33, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 7: 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]
• 8: G. Farin, Surfaces over Dirichlet Tessellations, Computer Aided Geometric Design, v.7 n.1-4, p.281-292, Jun. 1990 [doi>10.1016/0167-8396(90)90036-Q ]
• 9: Gerald Farin, Curves and surfaces for CAGD: a practical guide, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 10: 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 ]
• 11: 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]
• 12: Floater, M. S., Hormann, K., and Kós, G. 2006. A general construction of barycentric coordinates over convex polygons. Adv. Comp. Math. 24, 1--4, 311--331.
• 13: Michael S. Floater , Géza Kós , Martin Reimers, Mean value coordinates in 3D, Computer Aided Geometric Design, v.22 n.7, p.623-631, October 2005 [doi>10.1016/j.cagd.2005.06.004]
• 14: Glasbey, C. A. and Mardia, K. V. 1998. A review of image warping methods. J. Appl. Statistics 25, 2, 155--171.
• 15: L. Gross , G. Farin, A transfinite form of Sibson's interpolant, Discrete Applied Mathematics, v.93 n.1, p.33-50, April 15, 1999 [doi>10.1016/S0166-218X(99)00004-9 ]
• 16: Hisamoto Hiyoshi , Kokichi Sugihara, Voronoi-based interpolation with higher continuity, Proceedings of the sixteenth annual symposium on Computational geometry, p.242-250, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336210]
• 17: Kai Hormann , Marco Tarini, A quadrilateral rendering primitive, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France [doi>10.1145/1058129.1058131]
• 18: Tao Ju , Scott Schaefer , Joe Warren, Mean value coordinates for closed triangular meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 19: Ju, T., Schaefer, S., Warren, J., and Desbrun, M. 2005. A geometric construction of coordinates for convex polyhedra using polar duals. In Geometry Processing 2005. M. Desbrun and H. Pottmann, Eds. Eurographics Association, 181--186.
• 20: Kounchev, O. 2001. Multivariate Polysplines: Applications to Numerical and Wavelet Analysis. Academic Press, Orlando, FL.
• 21: Seung-Yong Lee , Kyung-Yong Chwa , Sung Yong Shin, Image metamorphosis using snakes and free-form deformations, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.439-448, September 1995 [doi>10.1145/218380.218501]
• 22: Seungyong Lee , George Wolberg , Sung Yong Shin, Scattered Data Interpolation with Multilevel B-Splines, IEEE Transactions on Visualization and Computer Graphics, v.3 n.3, p.228-244, July 1997 [doi>10.1109/2945.620490 ]
• 23: Malsch, E. A. and Dasgupta, G. 2004a. Interpolations for temperature distributions: A method for all non-concave polygons. Int. J. Solids and Structures 41, 8, 2165--2188.
• 24: Malsch, E. A. and Dasgupta, G. 2004b. Shape functions for polygonal domains with interior nodes. Int. J. Numer. Method Eng. 61, 8, 1153--1172.
• 25: Malsch, E. A. and Dasgupta, G. 2005. Algebraic construction of smooth interpolants on polygonal domains. Mathematica J. 9, 3, 641--658.
• 26: Malsch, E. A., Lin, J. J., and Dasgupta, G. 2005. Smooth two dimensional interpolants: A recipe for all polygons. J. Graph. Tools 10, 2, 27--39.
• 27: Mark Meyer , Alan Barr , Haeyoung Lee , Mathieu Desbrun, Generalized barycentric coordinates on irregular polygons, Journal of Graphics Tools, v.7 n.1, p.13-22, November 2002
• 28: Tim Milliron , Robert J. Jensen , Ronen Barzel , Adam Finkelstein, A framework for geometric warps and deformations, ACM Transactions on Graphics (TOG), v.21 n.1, p.20-51, January 2002 [doi>10.1145/504789.504791]
• 29: Möbius, A. F. 1827. Der Barycentrische Calcul. Johann Ambrosius Barth, Leipzig.
• 30: G. Nürnberger , F. Zeilfelder, Developments in bivariate spline interpolation, Journal of Computational and Applied Mathematics, v.121 n.1-2, p.125-152, Sept. 1, 2000 [doi>10.1016/S0377-0427(00)00346-0 ]
• 31: Pinkall, U. and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experim. Math. 2, 1, 15--36.
• 32: Detlef Ruprecht , Heinrich Müller, Image Warping with Scattered Data Interpolation, IEEE Computer Graphics and Applications, v.15 n.2, p.37-43, March 1995 [doi>10.1109/38.365004 ]
• 33: Sibson, R. 1980. A vector identity for the Dirichlet tesselation. Math. Proc. Combridge Phil. Soc. 87, 151--155.
• 34: Sibson, R. 1981. A brief description of natural neighbour interpolation. In Interpolating Multivariate Data. V. Barnett, Ed. Wiley, New York, 21--36.
• 35: Sukumar, N. and Malsch, E. A. 2006. Recent advances in the construction of polygonal finite element interpolants. Arch. Comput. Meth. Eng. 13, 1, 129--163.
• 36: Wachspress, E. L. 1975. A Rational Finite Element Basis. Academic Press, New York.
• 37: Warren, J. 1996. Barycentric coordinates for convex polytopes. Advances in Comput. Math. 6, 2, 97--108.
• 38: Warren, J. 2003. On the uniqueness of barycentric coordinates. In Topics in Algebraic Geometry and Geometric Modeling. R. Goldman and R. Krasauskas, Eds. Contemporary Mathematics, vol. 334. American Mathematical Society, 93--99.
• 39: Warren, J., Schaefer, S., Hirani, A. N., and Desbrun, M. 2004. Barycentric coordinates for convex sets. Tech. Rep., Rice University.
• 40: George Wolberg, Digital Image Warping, IEEE Computer Society Press, Los Alamitos, CA, 1994

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Interpolation formulas

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Theory

Keywords:
Barycentric coordinates, interpolation