More Web Proxy on the site http://driver.im/

article

Mean value coordinates for arbitrary planar polygons

Authors:

Michael S. FloaterAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 25, Issue 4

Pages 1424 - 1441

https://doi.org/10.1145/1183287.1183295

Published: 01 October 2006 Publication History

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]

Arad, N., Dyn, N., Reisfeld, D., and Yeshurun, Y. 1994. Image warping by radial basis functions: Application to facial expressions. CVGIP: Graph. Models and Image Proc. 56, 2, 161--172.

[2]

Beatson, R. K., Light, W. A., and Billings, S. 2000. Fast solution of the radial basis function interpolation equations: Domain decomposition methods. SIAM J. Sci. Comput. 22, 5, 1717--1740.

[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]

Chai, J., Miyoshi, T., and Nakamae, E. 1998. Contour interpolation and surface reconstruction of smooth terrain models. In Proceedings of the Conference on Visualization. 27--33.

[7]

Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., and Stuetzle, W. 1995. Multiresolution analysis of arbitrary meshes. In Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques. 173--182.

[8]

Farin, G. 1990. Surfaces over Dirichlet tessellations. Computer Aided Geom. Des. 7, 1--4, 281--292.

[9]

Farin, G. 2002. Curves and Surfaces for CAGD: A Practical Guide, 5th ed. Morgan Kaufmann Series in Computer Graphics and Geometric Modeling. Morgan Kaufmann, San Francisco.

[10]

Floater, M. S. 1997. Parameterization and smooth approximation of surface triangulations. Comput. Aided Geom. Des. 14, 3, 231--250.

[11]

Floater, M. S. 2003. Mean value coordinates. Comput. Aided Geom. Des. 20, 1, 19--27.

[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]

Floater, M. S., Kós, G., and Reimers, M. 2005. Mean value coordinates in 3D. Comput. Aided Geom. Des. 22, 7, 623--631.

[14]

Glasbey, C. A. and Mardia, K. V. 1998. A review of image warping methods. J. Appl. Statistics 25, 2, 155--171.

[15]

Gross, L. and Farin, G. 1999. A transfinite form of Sibson's interpolant. Disc. Appl. Math. 93, 1, 33--50.

[16]

Hiyoshi, H. and Sugihara, K. 2000. Voronoi-Based interpolation with higher continuity. In Proceedings of the 16th Annual Symposium on Computational Geometry. 242--250.

[17]

Hormann, K. and Tarini, M. 2004. A quadrilateral rendering primitive. In Graphics Hardware 2004. T. Akenine-Möller and M. McCool, Eds. Eurographics Association, 7--14.

[18]

Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3, 561--566.

[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]

Lee, S., Chwa, K.-Y., Shin, S. Y., and Wolberg, G. 1995. Image metamorphosis using snakes and free-form deformations. In Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques. 439--448.

[22]

Lee, S., Wolberg, G., and Shin, S. Y. 1997. Scattered data interpolation with multilevel B-splines. IEEE Trans. Visual. Comput. Graph. 3, 3, 228--244.

[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]

Meyer, M., Lee, H., Barr, A. H., and Desbrun, M. 2002. Generalized barycentric coordinates on irregular polygons. J. Graph. Tools 7, 1, 13--22.

[28]

Milliron, T., Jensen, R. J., Barzel, R., and Finkelstein, A. 2002. A framework for geometric warps and deformations. ACM Trans. Graph. 21, 1, 20--51.

[29]

Möbius, A. F. 1827. Der Barycentrische Calcul. Johann Ambrosius Barth, Leipzig.

[30]

Nürnberger, G. and Zeilfelder, F. 2000. Developments in bivariate spline interpolation. J. Comput. Appl. Math. 121, 1--2, 125--152.

[31]

Pinkall, U. and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experim. Math. 2, 1, 15--36.

[32]

Ruprecht, D. and Müller, H. 1995. Image warping with scattered data interpolation. Comput. Graph. Applics. 15, 2, 37--43.

[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]

Wolberg, G. 1990. Digital Image Warping. IEEE Computer Society Press, Los Alamitos, CA.

Cited By

Dieci LDifonzo FSukumar N(2024)Nonnegative moment coordinates on finite element geometriesMathematics in Engineering10.3934/mine.20240046:1(81-99)Online publication date: 2024
https://doi.org/10.3934/mine.2024004
Qin KZhou YYing CLi YDeng C(2024)C^0 Generalized Coons Patches for High-order Cage-based DeformationACM Transactions on Graphics10.1145/368797243:6(1-15)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687972
de Goes FDesbrun M(2024)Stochastic Computation of Barycentric CoordinatesACM Transactions on Graphics10.1145/365813143:4(1-13)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658131
Show More Cited By

Index Terms

Mean value coordinates for arbitrary planar polygons

Recommendations

Mean Value Coordinates for Closed Triangular Meshes
Seminal Graphics Papers: Pushing the Boundaries, Volume 2

Constructing a function that interpolates a set of values defined at vertices of a mesh is a fundamental operation in computer graphics. Such an interpolant has many uses in applications such as shading, parameterization and deformation. For closed ...
Mean value coordinates for closed triangular meshes

Constructing a function that interpolates a set of values defined at vertices of a mesh is a fundamental operation in computer graphics. Such an interpolant has many uses in applications such as shading, parameterization and deformation. For closed ...
Mean value coordinates for closed triangular meshes
SIGGRAPH '05: ACM SIGGRAPH 2005 Papers

Constructing a function that interpolates a set of values defined at vertices of a mesh is a fundamental operation in computer graphics. Such an interpolant has many uses in applications such as shading, parameterization and deformation. For closed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 25, Issue 4

October 2006

243 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1183287

Issue’s Table of Contents

Copyright © 2006 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2006

Published in TOG Volume 25, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

252
Total Citations
View Citations
1,699
Total Downloads

Downloads (Last 12 months)56
Downloads (Last 6 weeks)5

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dieci LDifonzo FSukumar N(2024)Nonnegative moment coordinates on finite element geometriesMathematics in Engineering10.3934/mine.20240046:1(81-99)Online publication date: 2024
https://doi.org/10.3934/mine.2024004
Qin KZhou YYing CLi YDeng C(2024)C^0 Generalized Coons Patches for High-order Cage-based DeformationACM Transactions on Graphics10.1145/368797243:6(1-15)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687972
de Goes FDesbrun M(2024)Stochastic Computation of Barycentric CoordinatesACM Transactions on Graphics10.1145/365813143:4(1-13)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658131
Ströter DThiery JHormann KChen JChang QBesler SMueller‐Roemer JBoubekeur TStork AFellner D(2024)A Survey on Cage‐based Deformation of 3D ModelsComputer Graphics Forum10.1111/cgf.1506043:2Online publication date: 30-Apr-2024
https://doi.org/10.1111/cgf.15060
Bunge ABukenberger DWagner SAlexa MBotsch M(2024)Polygon Laplacian Made RobustComputer Graphics Forum10.1111/cgf.1502543:2Online publication date: 30-Apr-2024
https://doi.org/10.1111/cgf.15025
Yu JLyu HXu ROuyang WLiu X(2024)Flow2Mesh: A flow-guided data-driven mesh adaptation frameworkPhysics of Fluids10.1063/5.018869036:3Online publication date: 8-Mar-2024
https://doi.org/10.1063/5.0188690
Nie XZou DChen KYi GKong X(2024)An improved high-precision polyhedron SBFEM with combinatorial interpolation strategiesEngineering Analysis with Boundary Elements10.1016/j.enganabound.2024.105991169(105991)Online publication date: Dec-2024
https://doi.org/10.1016/j.enganabound.2024.105991
Fuda CHormann K(2024)A new stable method to compute mean value coordinatesComputer Aided Geometric Design10.1016/j.cagd.2024.102310111:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.cagd.2024.102310
Huang ZLiu SFu X(2024)High-order shape interpolationComputer Aided Geometric Design10.1016/j.cagd.2024.102301111(102301)Online publication date: Jun-2024
https://doi.org/10.1016/j.cagd.2024.102301
Várady TSalvi PVaitkus M(2024)Genuine multi-sided parametric surface patches – A surveyComputer Aided Geometric Design10.1016/j.cagd.2024.102286110:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.cagd.2024.102286
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents