“Power coordinates: a geometric construction of barycentric coordinates on convex polytopes”
Conference:
Type(s):
Title:
- Power coordinates: a geometric construction of barycentric coordinates on convex polytopes
Session/Category Title: Tessellations
Presenter(s)/Author(s):
Abstract:
We present a full geometric parameterization of generalized barycentric coordinates on convex polytopes. We show that these continuous and non-negative coefficients ensuring linear precision can be efficiently and exactly computed through a power diagram of the polytope’s vertices and the evaluation point. In particular, we point out that well-known explicit coordinates such as Wachspress, Discrete Harmonic, Voronoi, or Mean Value correspond to simple choices of power weights. We also present examples of new barycentric coordinates, and discuss possible extensions such as power coordinates for non-convex polygons and smooth shapes.
References:
1. Arroyo, M., and Ortiz, M. 2006. Local maximum-entropy approximation schemes: a seamless bridge between finite elements and meshfree methods. Int. J. Num. Meth. Eng. 65, 13, 2167–2202. Cross Ref
2. Belyaev, A. 2006. On transfinite barycentric coordinates. In Symp. Geo. Processing, 89–99.
3. Ben-Chen, M., Weber, O., and Gotsman, C. 2009. Variational harmonic maps for space deformation. ACM Trans. Graph. 28, 3 (July), Art. 34.
4. Bruvoll, S., and Floater, M. S. 2010. Transfinite mean value interpolation in general dimension. Journal of Computational and Applied Mathematics 233, 7, 1631–1639.
5. Budninskiy, M., Liu, B., de Goes, F., Tong, Y., Alliez, P., and Desbrun, M. 2016. Optimal Voronoi tessellations with Hessian-based anisotropy. ACM Trans. Graph. 36, 6.
6. Busaryev, O., Dey, T., Wang, H., and Ren, Z. 2012. Animating bubble interactions in a liquid foam. ACM Trans. Graph. 31, 4, Art. 63.
7. CGAL. 2016. CGAL 4.8 User and Reference Manual. CGAL Editorial Board, http://www.cgal.org.
8. Cueto, E., Sukumar, N., Calvo, B., Martínez, M. A., Cegoňino, J., and Doblaré, M. 2003. Overview and recent advances in natural neighbour Galerkin methods. Archives of Computational Methods in Engineering 10, 4, 307–384. Cross Ref
9. Dasgupta, G., and Wachspress, E. L. 2008. Basis functions for concave polygons. Computers & Mathematics with Applications 56, 2, 459–468.
10. de Goes, F., Breeden, K., Ostromoukhov, V., and Desbrun, M. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 6, Art. 171.
11. de Goes, F., Alliez, P., Owhadi, H., and Desbrun, M. 2013. On the equilibrium of simplicial masonry structures. ACM Trans. Graph. 32, 4, Art. 93.
12. de Goes, F., Liu, B., Budninskiy, M., Tong, Y., and Desbrun, M. 2014. Discrete 2-tensor fields on triangulations. Comput. Graph. Forum 33, 5, 13–24.
13. de Goes, F., Memari, P., Mullen, P., and Desbrun, M. 2014. Weighted triangulations for geometry processing. ACM Trans. Graph. 33, 3, Art. 28.
14. de Goes, F., Wallez, C., Huang, J., Pavlov, D., and Desbrun, M. 2015. Power particles: An incompressible fluid solver based on power diagrams. ACM Trans. Graph. 34, 4, Art. 50.
15. Desbrun, M., Kanso, E., and Tong, Y. 2008. Discrete differential forms for computational modeling. In Discrete differential geometry. Birkhäuser Basel, 287–324.
16. Dyken, C., and Floater, M. S. 2009. Transfinite mean value interpolation. CAGD 26, 117–134.
17. Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., and Stuetzle, W. 1995. Multiresolution analysis of arbitrary meshes. In Proceedings of ACM SIGGRAPH, 173–182.
18. Floater, M. S., Kós, G., and Reimers, M. 2005. Mean value coordinates in 3D. CAGD 22, 7, 623–631.
19. Floater, M. S., Hormann, K., and Kós, G. 2006. A general construction of barycentric coordinates over convex polygons. Advances in Computational Mathematics 24, 1, 311–331. Cross Ref
20. Floater, M. S. 1997. Parametrization and smooth approximation of surface triangulations. CAGD 14, 3, 231 — 250.
21. Floater, M. S. 2003. Mean value coordinates. CAGD 20, 1, 19–27.
22. Floater, M. S. 2015. Generalized barycentric coordinates and applications. Acta Numerica 24 (5), 161–214. Cross Ref
23. Gillette, A., Rand, A., and Bajaj, C. 2016. Construction of scalar and vector finite element families on polygonal and polyhedral meshes. Computational Methods in Applied Math 19.
24. Glickenstein, D., 2005. Geometric triangulations and discrete Laplacians on manifolds. arXiv.org:math/0508188.
25. Gross, L., and Farin, G. 1999. A transfinite form of Sibson’s interpolant. Discrete Applied Mathematics 93, 1, 33–50.
26. Hiyoshi, H., and Sugihara, K. 1999. Two generalizations of an interpolant based on Voronoi diagrams. International Journal of Shape Modeling 05, 02, 219–231. Cross Ref
27. Hoff, K. E., Keyser, J., Lin, M., Manocha, D., and Culver, T. 1999. Fast computation of generalized Voronoi diagrams using graphics hardware. In Proceedings of ACM SIGGRAPH, 277–286.
28. Hormann, K., and Floater, M. S. 2006. Mean value coordinates for arbitrary planar polygons. ACM Trans. Graph. 25, 4, 1424–1441.
29. Hormann, K., and Sukumar, N. 2008. Maximum entropy coordinates for arbitrary polytopes. Comp. Graph. Forum 27, 5, 1513–1520.
30. Jacobson, A., Baran, I., Popović, J., and Sorkine, O. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4 (July), Art. 78.
31. Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3, Art. 71.
32. Ju, T., Schaefer, S., Warren, J., and Desbrun, M. 2005. A geometric construction of coordinates for convex polyhedra using polar duals. In Symp. Geo. Processing, 181–186.
33. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3, 561–566.
34. Ju, T., Liepa, P., and Warren, J. 2007. A general geometric construction of coordinates in a convex simplicial polytope. CAGD 24, 3, 161–178.
35. Klain, D. A. 2004. The Minkowski problem for polytopes. Advances in Mathematics 185, 2, 270–288. Cross Ref
36. Langer, T., and Seidel, H.-P. 2008. Higher order barycentric coordinates. Comp. Graph. Forum 27, 2, 459–466. Cross Ref
37. Langer, T., Belyaev, A., and Seidel, H.-P. 2006. Spherical barycentric coordinates. In Symp. Geo. Processing, 81–88.
38. Li, X.-Y., Ju, T., and Hu, S.-M. 2013. Cubic mean value coordinates. ACM Trans. Graph. 32, 4 (July), Art. 126.
39. Lipman, Y., Kopf, J., Cohen-Or, D., and Levin, D. 2007. GPU-assisted positive mean value coordinates for mesh deformations. In Symp. Geo. Processing, 117–123.
40. Lipman, Y., Levin, D., and Cohen-Or, D. 2008. Green coordinates. ACM Trans. Graph. 27, 3, Art. 78.
41. Liu, Y., Hao, P., Snyder, J., Wang, W., and Guo, B. 2013. Computing self-supporting surfaces by regular triangulation. ACM Trans. Graph. 32, 4.
42. Loop, C. T., and DeRose, T. D. 1989. A multisided generalization of Bézier surfaces. ACM Trans. Graph. 8, 3, 204–234.
43. Malsch, E. A., and Dasgupta, G. 2004. Shape functions for polygonal domains with interior nodes. International Journal for Numerical Methods in Engineering 61, 8, 1153–1172. Cross Ref
44. Malsch, E. A., and Dasgupta, G. 2005. Algebraic construction of smooth interpolants on polygonal domains. The Mathematica Journal 9, 3, 641–658.
45. Malsch, E. A., Lin, J. J., and Dasgupta, G. 2005. Smooth two-dimensional interpolations: A recipe for all polygons. Journal of Graphics, GPU, and Game Tools 10, 2, 27–39. Cross Ref
46. Manson, J., and Schaefer, S. 2010. Moving least squares coordinates. Comp. Graph. Forum 29, 5, 1517–1524. Cross Ref
47. Manson, J., Li, K., and Schaefer, S. 2011. Positive Gordon-Wixom coordinates. CAD 43, 11, 1422–1426.
48. Memari, P., Mullen, P., and Desbrun, M. 2012. Parametrization of generalized primal-dual triangulations. In International Meshing Roundtable. 237–253.
49. Meyer, M., Barr, A., Lee, H., and Desbrun, M. 2002. Generalized barycentric coordinates on irregular polygons. J. Graph. Tools 7, 1, 13–22.
50. Milbradt, P., and Pick, T. 2008. Polytope finite elements. Int. J. Num. Meth. Eng. 73, 12, 1811–1835. Cross Ref
51. Mullen, P., Memari, P., de Goes, F., and Desbrun, M. 2011. HOT: Hodge-optimized triangulations. ACM Trans. Graph. 30, 4.
52. Schaefer, S., Ju, T., and Warren, J. 2007. A unified, integral construction for coordinates over closed curves. CAGD 24, 8-9, 481–493.
53. Shepard, D. 1968. A two-dimensional interpolation function for irregularly-spaced data. In ACM National Conference, 517–524.
54. Sibson, R. 1981. A brief description of natural neighbor interpolation. In Interpolating Multivariate Data. John Wiley & Sons, ch. 2, 21–36.
55. Sukumar, N., and Bolander, J. 2009. Voronoi-based interpolants for fracture modelling. Tessellations in the Sciences.
56. Sukumar, N. 2004. Construction of polygonal interpolants: a maximum entropy approach. Int. J. Num. Meth. Eng. 61, 12, 2159–2181. Cross Ref
57. Varady, T., Salvi, P., and Kariko, G. 2016. A multi-sided Bézier patch with a simple control structure. Comp. Graph. Forum 35, 2, 307–317.
58. Wachspress, E. 1975. A Rational Finite Element Basis. Academic Press.
59. Warren, J., Schaefer, S., Hirani, A. N., and Desbrun, M. 2006. Barycentric coordinates for convex sets. Advances in Computational Mathematics 27, 3, 319–338. Cross Ref
60. Warren, J. 2003. On the uniqueness of barycentric coordinates. Contemporary Mathematics, 93–99.
61. Weber, O., and Gotsman, C. 2010. Controllable conformal maps for shape deformation and interpolation. ACM Trans. Graph. 29, 4, Art. 78.
62. Weber, O., Ben-Chen, M., and Gotsman, C. 2009. Complex barycentric coordinates with applications to planar shape deformation. Comp. Graph. Forum 28, 2. Cross Ref
63. Weber, O., Ben-Chen, M., Gotsman, C., and Hormann, K. 2011. A complex view of barycentric mappings. Comp. Graph. Forum 30, 5, 1533–1542. Cross Ref
64. Weber, O., Poranne, R., and Gotsman, C. 2012. Biharmonic coordinates. Comp. Graph. Forum 31, 8, 2409–2422.
65. Zhang, J., Deng, B., Liu, Z., Patanè, G., Bouaziz, S., Hormann, K., and Liu, L. 2014. Local barycentric coordinates. ACM Trans. Graph. 33, 6, Art. 188.
