“Weighted averages on surfaces” by Panozzo, Baran, Diamanti and Sorkine-Hornung
Conference:
Type(s):
Title:
- Weighted averages on surfaces
Session/Category Title: Surfaces & Differential Geometry
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
