“Approximate convex decomposition and transfer for animated meshes”
Conference:
Type(s):
Title:
- Approximate convex decomposition and transfer for animated meshes
Session/Category Title: Nets, cages and meshes
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Many geometric quantities can be computed efficiently for convex meshes. For general meshes, methods for approximate convex decomposition have been developed that decompose a static, non-convex object into a small set of approximately convex parts. The convex hulls of those parts can then be used as a piecewise convex approximation to the original mesh.While previous work was only concerned with static meshes, we present a method for decomposing animated 3D meshes into temporally coherent approximately convex parts. Given a mesh and several training frames—that is, different spatial configurations of its vertices—we precompute an approximate convex decomposition that is independent of any specific frame. Such a decomposition can be transferred in real-time to novel, unseen frames. We apply our method to a variety of pre-animated meshes as well as a 3D character interactively controlled by a user’s body pose. We further demonstrate that our method enables real-time physics simulations to interact with animated meshes.
References:
1. Shmuel Asafi, Avi Goren, and Daniel Cohen-Or. 2013. Weak Convex Decomposition by Lines-of-sight. In Proceedings of the Eleventh Eurographics/ACMSIGGRAPH Symposium on Geometry Processing (SGP ’13). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 23–31. Google ScholarDigital Library
2. Marco Attene, Michela Mortara, Michela Spagnuolo, and Bianca Falcidieno. 2008. Hierarchical Convex Approximation of 3D Shapes for Fast Region Selection. In Proceedings of the Symposium on Geometry Processing (SGP ’08). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 1323–1332. Google ScholarDigital Library
3. O. Kin-Chung Au, Y. Zheng, M. Chen, P. Xu, and C. Tai. 2012. Mesh Segmentation with Concavity-Aware Fields. IEEE Transactions on Visualization and Computer Graphics 18, 7 (July 2012), 1125–1134. Google ScholarDigital Library
4. Stéphane Calderon and Tamy Boubekeur. 2017. Bounding Proxies for Shape Approximation. ACM Trans. Graph. 36, 4 (July 2017), 57:1–57:13. Google ScholarDigital Library
5. S. Cameron. 1997. Enhancing GJK: computing minimum and penetration distances between convex polyhedra. In Proceedings of International Conference on Robotics and Automation, Vol. 4. 3112–3117 vol.4.Google ScholarCross Ref
6. Bernard M. Chazelle. 1981. Convex Decompositions of Polyhedra. In Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing (STOC ’81). ACM, New York, NY, USA, 70–79. Google ScholarDigital Library
7. Fernando de Goes, Siome Goldenstein, and Luiz Velho. 2008. A Hierarchical Segmentation of Articulated Bodies. In Proceedings of the Symposium on Geometry Processing (SGP ’08). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 1349– 1356. Google ScholarDigital Library
8. Mukulika Ghosh, Nancy M Amato, Yanyan Lu, and Jyh-Ming Lien. 2013. Fast approximate convex decomposition using relative concavity. Computer-Aided Design 45, 2 (2013), 494–504. Google ScholarDigital Library
9. E. G. Gilbert, D. W. Johnson, and S. S. Keerthi. 1988. A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Journal on Robotics and Automation 4, 2 (April 1988), 193–203.Google ScholarCross Ref
10. S. Gottschalk, M. C. Lin, and D. Manocha. 1996. OBBTree: A Hierarchical Structure for Rapid Interference Detection. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’96). ACM, New York, NY, USA, 171–180. Google ScholarDigital Library
11. P. M. Hubbard. 1995. Collision detection for interactive graphics applications. IEEE Transactions on Visualization and Computer Graphics 1, 3 (Sept. 1995), 218–230. Google ScholarDigital Library
12. Wenzel Jakob. 2010. Mitsuba renderer. http://www.mitsuba-renderer.org.Google Scholar
13. Doug L. James and Dinesh K. Pai. 2004. BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models. ACM Transactions on Graphics 23 (July 2004). Google ScholarDigital Library
14. Doug L. James and Christopher D. Twigg. 2005. Skinning Mesh Animations. In ACM SIGGRAPH 2005 Papers (SIGGRAPH ’05). ACM, New York, NY, USA, 399–407. Google ScholarDigital Library
15. Oliver Van Kaick, Noa Fish, Yanir Kleiman, Shmuel Asafi, and Daniel Cohen-OR. 2014. Shape Segmentation by Approximate Convexity Analysis. ACM Trans. Graph. 34, 1 (Dec. 2014), 4:1–4:11. Google ScholarDigital Library
16. Evangelos Kalogerakis, Aaron Hertzmann, and Karan Singh. 2010. Learning 3D Mesh Segmentation and Labeling. In ACM SIGGRAPH 2010 Papers (SIGGRAPH ’10). ACM, New York, NY, USA, Article 102, 12 pages. Google ScholarDigital Library
17. L. Kavan and J. Žára. 2005. Fast Collision Detection for Skeletally Deformable Models. Computer Graphics Forum 24, 3 (2005), 363–372.Google ScholarCross Ref
18. J. T. Klosowski, M. Held, J. S. B. Mitchell, H. Sowizral, and K. Zikan. 1998. Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Transactions on Visualization and Computer Graphics 4, 1 (Jan. 1998), 21–36. Google ScholarDigital Library
19. AF Koschan. 2003. Perception-based 3D triangle mesh segmentation using fast marching watersheds. In Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on, Vol. 2. IEEE, II–II.Google ScholarCross Ref
20. V. Kreavoy, D. Julius, and A. Sheffer. 2007. Model Composition from Interchangeable Components. In 15th Pacific Conference on Computer Graphics and Applications (PG’07). 129–138. Google ScholarDigital Library
21. Lubor Ladicky, SoHyeon Jeong, Barbara Solenthaler, Marc Pollefeys, and Markus Gross. 2015. Data-driven fluid simulations using regression forests. ACM Transactions on Graphics (TOG) 34, 6 (2015), 199. Google ScholarDigital Library
22. Tong-Yee Lee, Ping-Hsien Lin, Shaur-Uei Yan, and Chun-Hao Lin. 2005. Mesh decomposition using motion information from animation sequences. Computer Animation and Virtual Worlds 16, 3–4 (2005), 519–529. Google ScholarDigital Library
23. Bin Liao, Chunxia Xiao, Meng Liu, Zhao Dong, and Qunsheng Peng. 2012. Fast hierarchical animated object decomposition using approximately invariant signature. The Visual Computer 28, 4 (2012), 387–399. Google ScholarDigital Library
24. Jyh-Ming Lien and Nancy M Amato. 2004. Approximate convex decomposition of polygons. In Proceedings of the twentieth annual symposium on Computational geometry. ACM, 17–26. Google ScholarDigital Library
25. Jyh-Ming Lien and Nancy M Amato. 2007. Approximate convex decomposition of polyhedra. In Proceedings of the 2007 ACM symposium on Solid and physical modeling. ACM, 121–131. Google ScholarDigital Library
26. Guilin Liu, Zhonghua Xi, and Jyh-Ming Lien. 2016. Nearly convex segmentation of polyhedra through convex ridge separation. Computer-Aided Design 78 (2016), 137–146. Google ScholarDigital Library
27. Rong Liu and Hao Zhang. 2007. Mesh Segmentation via Spectral Embedding and Contour Analysis. Computer Graphics Forum 26, 3 (Sept. 2007), 385–394.Google ScholarCross Ref
28. Khaled Mamou. 2016. Volumetric Hierarchical Approximate Convex Decomposition. In Game Engine Gems 3, Eric Lengyel (Ed.). A K Peters, 141–158.Google Scholar
29. Khaled Mamou and Faouzi Ghorbel. 2009. A simple and efficient approach for 3D mesh approximate convex decomposition. In Image Processing (ICIP), 2009 16th IEEE International Conference on. IEEE, 3501–3504. Google ScholarDigital Library
30. Zhou Ren, Junsong Yuan, Chunyuan Li, and Wenyu Liu. 2011. Minimum near-convex decomposition for robust shape representation. In 2011 International Conference on Computer Vision. 303–310. Google ScholarDigital Library
31. Idan Shatz, Ayellet Tal, and George Leifman. 2006. Paper craft models from meshes. The Visual Computer 22, 9 (2006), 825–834. Google ScholarDigital Library
32. Shymon Shlafman, Ayellet Tal, and Sagi Katz. 2002. Metamorphosis of polyhedral surfaces using decomposition. In Computer graphics forum, Vol. 21. Wiley Online Library, 219–228.Google Scholar
33. Jean-Marc Thiery, Émilie Guy, Tamy Boubekeur, and Elmar Eisemann. 2016. Animated mesh approximation with sphere-meshes. ACM Transactions on Graphics (TOG) 35, 3 (2016), 30. Google ScholarDigital Library
34. Jianhua Wu and Leif Kobbelt. 2005. Structure recovery via hybrid variational surface approximation. In Computer Graphics Forum, Vol. 24. Wiley Online Library, 277–284.Google Scholar
35. Stefanie Wuhrer and Alan Brunton. 2010. Segmenting animated objects into near-rigid components. The Visual Computer 26, 2 (2010), 147–155. Google ScholarDigital Library
36. J. Zunic and P. L. Rosin. 2004. A new convexity measure for polygons. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 7 (July 2004), 923–934. Google ScholarDigital Library
