“Bounding proxies for shape approximation” by Calderon and Boubekeur
Conference:
Type:
Title:
- Bounding proxies for shape approximation
Session/Category Title: Being Discrete About Geometry Processing
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Many computer graphics applications use simpler yet faithful approximations of complex shapes to conduct reliably part of their computations. Some tasks, such as physical simulation, collision detection, occlusion queries or free-form deformation, require the simpler proxy to strictly enclose the input shape. While there are algorithms that can output such bounding proxies on simple input shapes, most of them fail at generating a proper coarse approximant on real-world complex shapes, which may contain multiple components and have a high genus. We advocate that, before reducing the number of primitives to describe a shape, one needs to regularize it while maintaining the strict enclosing property, to avoid any geometric aliasing that makes the decimation unreliable. Depending on the scale of the desired approximation, the topology of the shape itself may indeed have to be first simplified, to let the subsequent geometric optimization be free from topological locks.We propose a new bounding shape approximation algorithm which takes as input an arbitrary surface mesh, with potentially complex multi-component structures, and generates automatically a bounding proxy which is tightened on the input and can match even the coarsest levels of approximation. To sustain the nonlinear approximation process that may eventually abstract both geometry and topology, we propose to use an intermediate regularized representation in the form of a shape closing, computed in real time using a new fast morphological framework designed for efficient parallel execution. Once the desired level of approximation is reached in the shape closing, a coarse, tight and bounding polygonization of the proxy geometry is extracted using an adaptive meshing scheme. Our underlying representation is both geometry- and topology-adaptive and can be optionally controlled accurately by a user, through sizing and orientation fields, yielding an intuitive brush metaphor within an interactive proxy design environment. We provide extensive experiments on various kinds of input meshes and illustrate the potential applications of our method in scenarios that benefit greatly from coarse, tight bounding substitutes to the actual high resolution geometry of the original 3D model, including freeform deformation, physical simulation and level of detail generation for rendering.
References:
1. Marco Attene. 2010. A Lightweight Approach to Repairing Digitized Polygon Meshes. Vis. Comput. 26, 11 (2010), 1393–1406. Google ScholarDigital Library
2. Mirela Ben-Chen, Ofir Weber, and Craig Gotsman. 2009. Spatial Deformation Transfer. In Proc. SCA. 67–74. Google ScholarDigital Library
3. N. Bouaynaya, M. Charif-Chefchaouni, and D. Schonfeld. 2008. Theoretical Foundations of Spatially-Variant Mathematical Morphology Part I: Binary Images. Pattern Analysis and Machine Intelligence, IEEE Transactions on 30, 5 (2008), 823–836.Google ScholarDigital Library
4. V. Boulos, V. Fristot, D. Houzet, L. Salvo, and P. Lhuissier. 2012. Investigating performance variations of an optimized GPU-ported granulometry algorithm. In Design and Architectures for Signal and Image Processing (DASIP). 1–6.Google Scholar
5. Stephane Calderon and Tamy Boubekeur. 2014. Point Morphology. ACM Trans. Graph. 33, 4 (2014), 45:1–45:13.Google ScholarDigital Library
6. Jonathan Cohen, Amitabh Varshney, Dinesh Manocha, Greg Turk, Hans Weber, Pankaj Agarwal, Frederick Brooks, and William Wright. 1996. Simplification Envelopes. In Proc. SIGGRAPH. 119–128. Google ScholarDigital Library
7. David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. 2004. Variational Shape Approximation. In Proc. SIGGRAPH. 905–914. Google ScholarDigital Library
8. Olivier Cuisenaire. 2006. Locally adaptable mathematical morphology using distance transformations. Pattern Recognition 39, 3 (2006), 405 — 416. Google ScholarDigital Library
9. Zheng-Jie Deng, Xiao-Nan Luo, and Xiao-Ping Miao. 2011. Automatic Cage Building with Quadric Error Metrics. Journal of Computer Science and Technology 26, 3 (2011), 538–547. Google ScholarCross Ref
10. H. Edelsbrunner, D. Kirkpatrick, and R. Seidel. 1983. On the shape of a set of points in the plane. IEEE Transactions on Information Theory 29, 4 (1983), 551–559. Google ScholarDigital Library
11. Jihad El-Sana and Amitabh Varshney. 1998. Topology Simplification for Polygonal Virtual Environments. IEEE Trans. Vis. Comput. Graph. 4 (1998), 133–144. Google ScholarDigital Library
12. Noura Faraj, Jean-Marc Thiery, and Tamy Boubekeur. 2012. VoxMorph: 3-scale Freeform Deformation of Large Voxel Grids. Comput. & Graph. 36, 5 (aug 2012), 562–568. Google ScholarDigital Library
13. Michael Garland and Paul S. Heckbert. 1997. Surface Simplification Using Quadric Error Metrics. In Proc. SIGGRAPH. 209–216. Google ScholarDigital Library
14. J. Gil and M. Werman. 1993. Computing 2-D min, median, and max filters. Pattern Analysis and Machine Intelligence, IEEE Transactions on 15, 5 (1993), 504–507.Google ScholarDigital Library
15. Joseph (Yossi) Gil and Ron Kimmel. 2002. Efficient Dilation, Erosion, Opening, and Closing Algorithms. IEEE Trans. Pattern Anal. Mach. Intell. 24, 12 (2002), 1606–1617. Google ScholarDigital Library
16. H. Hedberg, P. Dokladal, and V. Öwall. 2009. Binary Morphology With Spatially Variant Structuring Elements: Algorithm and Architecture. Image Processing, IEEE Transactions on 18, 3 (2009), 562–572.Google ScholarDigital Library
17. Matthias Hopf and Thomas Ertl. 2000. Accelerating Morphological Analysis with Graphics Hardware. In Proc. Workshop on Vision, Modelling, and Visualization VMV fi00. 337–345.Google Scholar
18. Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. 1993. Mesh optimization. In Proc. SIGGRAPH 19–26. Google ScholarDigital Library
19. Paul T. Jackway and Mohamed Deriche. 1996. Scale-Space Properties of the Multiscale Morphological Dilation-Erosion. IEEE Trans. Pattern Anal. Mach. Intell. 18, 1 (1996), 38–51. Google ScholarDigital Library
20. Alec Jacobson, Zhigang Deng, Ladislav Kavan, and JP Lewis. 2014. Skinning: Real-time Shape Deformation. In ACM SIGGRAPH Courses.Google Scholar
21. G Jagannathan, R Subash, and K Senthil Raja. 2014. A Novel Open Source Morphology Using GPU Processing With LTU-CUDA. International Journal for Advance Research in Engineering and Technology 2, 1 (2014).Google Scholar
22. Pushkar Joshi, Mark Meyer, Tony DeRose, Brian Green, and Tom Sanocki. 2007. Harmonic Coordinates for Character Articulation. ACM Trans. Graph. 26, 3, Article 71 (2007). Google ScholarDigital Library
23. T. Ju, S. Schaefer, and J. Warren. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3 (2005), 561–566. Google ScholarDigital Library
24. B. Le and Z. Deng. 2017. Interactive Cage Generation for Mesh Deformation. In Proc. of ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (SI3D). 3:1–3:9. Google ScholarDigital Library
25. Hélène Legrand and Tamy Boubekeur. 2015. Morton Integrals for High Speed Geometry Simplification. In Proc. ACM SIGGRAPH/EUROGRAPHICS High-Performance Graphics. 105–112.Google ScholarDigital Library
26. Peter Lindstrom. 2000. Out-of-core simplification of large polygonal models. In Proc. SIGGRAPH. 259–262. Google ScholarDigital Library
27. Y. Lipman, D. Levin, and D. Cohen-Or. 2008. Green coordinates. ACM Trans. Graph. 27, 3 (2008), 1–10. Google ScholarDigital Library
28. Manish Mandad, David Cohen-Steiner, and Pierre Alliez. 2015. Isotopic Approximation Within a Tolerance Volume. ACM Trans. Graph. 34, 4 (2015), 64:1–64:12.Google ScholarDigital Library
29. Ravish Mehra, Qingnan Zhou, Jeremy Long, Alla Sheffer, Amy Gooch, and Niloy J. Mitra. 2009. Abstraction of Man-made Shapes. ACM Trans. Graph. 28, 5 (2009), 137:1–137:10.Google ScholarDigital Library
30. Ken Museth. 2013. VDB: High-resolution Sparse Volumes with Dynamic Topology. ACM Trans. Graph. 32, 3 (2013), 27:1–27:22.Google ScholarDigital Library
31. Laurent Najman and Hugues Talbot (Eds.). 2010. Mathematical Morphology: From Theory to Applications. Wiley.Google Scholar
32. Jarek Rossignac and Paul Borrel. 1993. Multi-resolution 3D approximations for rendering complex scenes. In Modeling in Computer Graphics. 455–465.Google Scholar
33. Christian Rössl, Leif Kobbelt, and Hans-Peter Seidel. 2000. Extraction of feature lines on triangulated surfaces using morphological operators. In AAAI Symp. Smart Graphics, Vol. 00–04. 71–75.Google Scholar
34. Leonardo Sacht, Alec Jacobson, Daniele Panozzo, Christian Schüller, and Olga Sorkine-Hornung. 2013. Consistent Volumetric Discretizations Inside Self-Intersecting Surfaces. Computer Graphics Forum 32, 5 (2013), 147–156. Google ScholarDigital Library
35. Leonardo Sacht, Etienne Vouga, and Alec Jacobson. 2015. Nested Cages. ACM Trans. Graph. 34, 6, Article 170 (2015), 170:1–170:14 pages.Google ScholarDigital Library
36. Pedro V. Sander, Xianfeng Gu, Steven J. Gortler, Hugues Hoppe, and John Snyder. 2000. Silhouette Clipping. In Proc. SIGGRAPH. 327–334. Google ScholarDigital Library
37. Michael Schwarz and Hans-Peter Seidel. 2010. Fast Parallel Surface and Solid Voxelization on GPUs. ACM Trans. Graph. 29, 6 (2010), 179:1–179:10.Google ScholarDigital Library
38. Jean Serra. 1983. Image Analysis and Mathematical Morphology. Academic Press, Inc.Google Scholar
39. Chen Shen, James F. O’Brien, and Jonathan R. Shewchuk. 2004. Interpolating and Approximating Implicit Surfaces from Polygon Soup. In Proc. SIGGRAPH. 896–904. Google ScholarDigital Library
40. A. Söderström and K. Museth. 2010. A Spatially Adaptive Morphological Filter for Dual-Resolution Interface Tracking of Fluids. In Eurographics. 5–8.Google Scholar
41. Pierre Soille, Edmond J. Breen, and Ronald Jones. 1996. Recursive Implementation of Erosions and Dilations Along Discrete Lines at Arbitrary Angles. IEEE Trans. Pattern Anal. Mach. Intell. 18, 5 (1996), 562–567. Google ScholarDigital Library
42. Marco Tarini, Nico Pietroni, Paolo Cignoni, Daniele Panozzo, and Enrico Puppo. 2010. Practical quad mesh simplification. Computer Graphics Forum 29, 2 (2010), 407–418. Google ScholarCross Ref
43. Jean-Marc Thiery, Émilie Guy, and Tamy Boubekeur. 2013. Sphere-Meshes: Shape Approximation Using Spherical Quadric Error Metrics. ACM Trans. Graph. 32, 6, Article 178 (2013), 178:1–178:12 pages.Google ScholarDigital Library
44. Matthew Thurley and Victor Danell. 2012. Fast morphological image processing open-source extensions for GPU processing with CUDA. IEEE Journal on Selected Topics in Signal Processing 6, 7 (2012), 849–855. Google ScholarCross Ref
45. Marcel van Herk. 1992. A Fast Algorithm for Local Minimum and Maximum Filters on Rectangular and Octagonal Kernels. Pattern Recogn. Lett. 13, 7 (1992), 517–521. Google ScholarDigital Library
46. Chuhua Xian, Hongwei Lin, and Shuming Gao. 2009. Automatic generation of coarse bounding cages from dense meshes. In IEEE SMI. 21–27.Google Scholar
47. Chuhua Xian, Hongwei Lin, and Shuming Gao. 2012. Automatic cage generation by improved OBBs for mesh deformation. The Visual Computer 28, 1 (2012), 21–33. Google ScholarDigital Library
48. Steve Zelinka and Michael Garland. 2002. Permission Grids: Practical, Error-bounded Simplification. ACM Trans. Graph. 21, 2 (2002), 207–229. Google ScholarDigital Library
