“Weighted averages on surfaces” by Panozzo, Baran, Diamanti and Sorkine-Hornung

  • ©Daniele Panozzo, Ilya Baran, Olga Diamanti, and Olga Sorkine-Hornung




    Weighted averages on surfaces

Session/Category Title: Surfaces & Differential Geometry




    We consider the problem of generalizing affine combinations in Euclidean spaces to triangle meshes: computing weighted averages of points on surfaces. We address both the forward problem, namely computing an average of given anchor points on the mesh with given weights, and the inverse problem, which is computing the weights given anchor points and a target point. Solving the forward problem on a mesh enables applications such as splines on surfaces, Laplacian smoothing and remeshing. Combining the forward and inverse problems allows us to define a correspondence mapping between two different meshes based on provided corresponding point pairs, enabling texture transfer, compatible remeshing, morphing and more. Our algorithm solves a single instance of a forward or an inverse problem in a few microseconds. We demonstrate that anchor points in the above applications can be added/removed and moved around on the meshes at interactive framerates, giving the user an immediate result as feedback.


    1. Alexa, M. 2002. Linear combination of transformations. ACM Trans. Graph. 21, 3, 380–387. Google ScholarDigital Library
    2. Baran, I., Vlasic, D., Grinspun, E., and Popović, J. 2009. Semantic deformation transfer. ACM Trans. Graph. 28, 3. Google ScholarDigital Library
    3. Bonneel, N., van de Panne, M., Paris, S., and Heidrich, W. 2011. Displacement interpolation using lagrangian mass transport. ACM Trans. Graph. 30, 6. Google ScholarDigital Library
    4. Botsch, M., and Sorkine, O. 2008. On linear variational surface deformation methods. IEEE Trans. Visualization and Computer Graphics 14, 1, 213–230. Google ScholarDigital Library
    5. Botsch, M., Steinberg, S., Bischoff, S., and Kobbelt, L. 2002. OpenMesh – a generic and efficient polygon mesh data structure. In Proc. OpenSG Symposium.Google Scholar
    6. Boubekeur, T., and Alexa, M. 2008. Phong tessellation. ACM Trans. Graph. 27, 5, 141:1–141:5. Google ScholarDigital Library
    7. Buss, S. R., and Fillmore, J. P. 2001. Spherical averages and applications to spherical splines and interpolation. ACM Trans. Graph. 20, 2, 95–126. Google ScholarDigital Library
    8. Cartan, É. 1929. Groupes simples clos et ouverts et géométrie riemannienne. J. Math. Pures Appl. 8, 1–33.Google Scholar
    9. Chen, Y., and Medioni, G. 1991. Object modeling by registration of multiple range images. In Proc. IEEE International Conference on Robotics and Automation, 2724–2729.Google Scholar
    10. Cox, T. F., and Cox, M. A. A. 2000. Multidimensional Scaling, Second Edition. Chapman & Hall/CRC, Sept.Google Scholar
    11. Crane, K., Weischedel, C., and Wardetzky, M. 2013. Geodesics in heat. ACM Trans. Graph.. to appear.Google Scholar
    12. de Silva, V., and Tenenbaum, J. B. 2002. Global versus local methods in nonlinear dimensionality reduction. In Proc. NIPS, 705–712.Google Scholar
    13. Eckstein, I., Surazhsky, V., and Gotsman, C. 2001. Texture mapping with hard constraints. Comput. Graph. Forum 20, 3, 95–104.Google ScholarCross Ref
    14. Floater, M. S. 2003. Mean value coordinates. Computer Aided Geometric Design 20, 1, 19–27. Google ScholarDigital Library
    15. Fréchet, M. 1948. Les éléments alétoires de nature quelconque dans un espace distancié. Ann. Inst. H. Poincaré 10, 4, 215–310.Google Scholar
    16. Hofer, M., and Pottmann, H. 2004. Energy-minimizing splines in manifolds. ACM Trans. Graph. 23, 3, 284–293. Google ScholarDigital Library
    17. Hormann, K., and Sukumar, N. 2008. Maximum entropy coordinates for arbitrary polytopes. In Proc. SGP, 1513–1520. Google ScholarDigital Library
    18. Hormann, K., Polthier, K., and Sheffer, A. 2008. Mesh parameterization: Theory and practice. In SIGGRAPH ASIA 2008 Course Notes. Google ScholarDigital Library
    19. Jin, J., Garland, M., and Ramos, E. A. 2009. MLS-based scalar fields over triangle meshes and their application in mesh processing. In Proc. ACM I3D, 145–153. Google ScholarDigital Library
    20. Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3, 71:1–71:9. Google ScholarDigital Library
    21. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3, 561–566. Google ScholarDigital Library
    22. Karcher, H. 1977. Riemannian center of mass and mollifier smoothing. Communications on pure and applied mathematics 30, 5, 509–541.Google Scholar
    23. Kendall, W. 1990. Probability, convexity, and harmonic maps with small image I: uniqueness and fine existence. Proceedings of the London Mathematical Society 3, 2, 371.Google Scholar
    24. Kim, V. G., Lipman, Y., and Funkhouser, T. 2011. Blended intrinsic maps. ACM Trans. Graph. 30, 4. Google ScholarDigital Library
    25. Kobbelt, L., Vorsatz, J., and Seidel, H.-P. 1999. Multiresolution hierarchies on unstructured triangle meshes. Comput. Geom. Theory Appl. 14, 1–3, 5–24. Google ScholarDigital Library
    26. Kraevoy, V., and Sheffer, A. 2004. Cross-parameterization and compatible remeshing of 3D models. ACM Trans. Graph. 23, 3, 861–869. Google ScholarDigital Library
    27. Langer, T., Belyaev, A., and Seidel, H.-P. 2006. Spherical barycentric coordinates. In Proc. SGP, 81–88. Google ScholarDigital Library
    28. Lipman, Y., Kopf, J., Cohen-Or, D., and Levin, D. 2007. GPU-assisted positive mean value coordinates for mesh deformations. In Proc. SGP, 117–124. Google ScholarDigital Library
    29. Lipman, Y., Rustamov, R. M., and Funkhouser, T. A. 2010. Biharmonic distance. ACM Trans. Graph. 29, 3. Google ScholarDigital Library
    30. Loop, C. 1987. Smooth subdivision surfaces based on triangles. Master’s thesis, Department of Mathematics, University of Utah.Google Scholar
    31. Ovsjanikov, M., Mérigot, Q., Mémoli, F., and Guibas, L. J. 2010. One point isometric matching with the heat kernel. Comput. Graph. Forum 29, 5, 1555–1564.Google ScholarCross Ref
    32. Pálfia, M. 2009. The Riemann barycenter computation and means of several matrices. Int. J. Comput. Math. Sci. 3, 3, 128–133.Google Scholar
    33. Pennec, X. 1998. Computing the mean of geometric features: Application to the mean rotation. Rapport de Recherche RR–3371, INRIA – Epidaure project, Sophia Antipolis, France, March.Google Scholar
    34. Phong, B. 1975. Illumination for computer generated pictures. Communications of the ACM 18, 6, 311–317. Google ScholarDigital Library
    35. Ritschel, T., Thormählen, T., Dachsbacher, C., Kautz, J., and Seidel, H.-P. 2010. Interactive on-surface signal deformation. ACM Trans. Graph. 29, 4. Google ScholarDigital Library
    36. Rustamov, R., Lipman, Y., and Funkhouser, T. 2009. Interior distance using barycentric coordinates. Comput. Graph. Forum 28, 5. Google ScholarDigital Library
    37. Rustamov, R. 2010. Barycentric coordinates on surfaces. Comput. Graph. Forum 29, 5, 1507–1516.Google ScholarCross Ref
    38. Sander, P. V., Gu, X., Gortler, S. J., Hoppe, H., and Snyder, J. 2000. Silhouette clipping. In Proc. ACM SIGGRAPH, 327–334. Google ScholarDigital Library
    39. Schmidt, R., Grimm, C., and Wyvill, B. 2006. Interactive decal compositing with discrete exponential maps. ACM Trans. Graph. 25, 3, 605–613. Google ScholarDigital Library
    40. Schreiner, J., Asirvatham, A., Praun, E., and Hoppe, H. 2004. Inter-surface mapping. ACM Trans. Graph. 23, 3. Google ScholarDigital Library
    41. Sethian, J. A. 1996. A fast marching level set method for monotonically advancing fronts. In Proc. Nat. Acad. Sci, 1591–1595.Google ScholarCross Ref
    42. Sorkine, O., and Cohen-Or, D. 2004. Least-squares meshes. In Proc. Shape Modeling International, 191–199. Google ScholarDigital Library
    43. Sorkine, O., Cohen-Or, D., Goldenthal, R., and Lischinski, D. 2002. Bounded-distortion piecewise mesh parameterization. In Proc. IEEE Visualization, 355–362. Google ScholarDigital Library
    44. Sumner, R. W., and Popović, J. 2004. Deformation transfer for triangle meshes. ACM Trans. Graph. 23, 3, 399–405. Google ScholarDigital Library
    45. Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., and Hoppe, H. 2005. Fast exact and approximate geodesics on meshes. ACM Trans. Graph. 24, 3, 553–560. Google ScholarDigital Library
    46. Tzur, Y., and Tal, A. 2009. FlexiStickers: Photogrammetric texture mapping using casual images. ACM Trans. Graph. 28, 3. Google ScholarDigital Library
    47. Waldron, S. 2011. Affine generalised barycentric coordinates. Jaen Journal on Approximation 3, 2.Google Scholar
    48. Wallner, J., and Pottmann, H. 2006. Intrinsic subdivision with smooth limits for graphics and animation. ACM Trans. Graph. 25, 2, 356–374. Google ScholarDigital Library
    49. Xin, S.-Q., Ying, X., and He, Y. 2012. Constant-time all-pairs geodesic distance query on triangle meshes. In Proc. ACM I3D. Google ScholarDigital Library
    50. Yeh, I.-C., Lin, C.-H., Sorkine, O., and Lee, T.-Y. 2011. Template-based 3D model fitting using dual-domain relaxation. IEEE Trans. Vis. Comput. Graph. 17, 8, 1178–1190. Google ScholarDigital Library
    51. Zhou, K., Synder, J., Guo, B., and Shum, H.-Y. 2004. Isocharts: stretch-driven mesh parameterization using spectral analysis. In Proc. SGP, ACM, New York, NY, USA, 45–54. Google ScholarDigital Library

ACM Digital Library Publication: