Skeleton Extraction
Shape decomposition and skeletonization share many common properties and applications. However, they are generally considered as independent methods. In many applications, the detailed features of a model are not crucial and in fact considering them only may serve to obscure the important structural features and adds to the processing cost. In such cases, an approximate representation of the model, such as approximate convex decomposition (ACD), that captures the key structural features would be preferable. One important example is skeleton extraction. The skeleton is a low dimensional object which essentially represents the “shape” of the higher-dimensional target object. The process of generating such a skeleton is called skeleton extraction. ACD partitions a model into nearly convex components, has been shown to reveal important structural information and is used for shape decomposition in this paper. A skeleton of the model is then extracted from the convex hulls of these nearly convex components. The process of simultaneous shape decomposition and skeletonization iterates until the quality of the skeleton becomes satisfactory.
Skeletonization Extraction via Approximate Convex Decomposition
2D Polygon Examples
Original Mesh
Perturbed Mesh
3D Polyhdral Examples
Twisted Donut
Video: mpeg format
Images:
Buffalo
Original mesh
Video: mpeg format
Images:
Perturbed mesh
Video: mpeg format
Images:
Twisted X
Original mesh
Video: mpeg format
Images:
Perturbed mesh
Video: mpeg format
Images:
Simultaneous Shape Decomposition and Skeletonization Using Approximate Convex Decomposition
An example of co-evolution of shape decomposition and skeleton extraction.
The skeleton (shown in the lower row) evolves with the shape decomposition (shown in the upper row).
Robustness under pertubation and deformation
Robustness tests using perturbed and skeletal deformed meshes. The female, the horse and the triceratop models have 243,442, 39,694 and 5,660 triangles, respectively. DO is the graph edit distance between a skeleton extracted from a perturbed or deformed mesh and a skeleton extracted from the original mesh. D2 O is DO without counting operations on degree-2 nodes.
Application: Skeletal Deformation
Movie: baby boxing (divx, 6.8 MB)
An animation sequence obtained from applying the boxing motion capture data to the extracted skeleton from a baby model. The motion capture data (action number 13_17) is downloaded from the CMU Graphics Lab motion capture database. The first two figures in the sequence are the shape decomposition and the skeleton of the baby. Note the not all joints motions from the data are used because the extracted skeleton has fewer joints.
Publications
- Ghosh, M. , Thomas, S. , & Amato, N.M. (2020). Fast Collision Detection for Motion Planning Using Shape Primitive Skeletons. Algorithmic Foundations of Robotics XIII. Springer Proceedings in Advanced Robotics (SPAR). The 2018 Workshop on the Algorithmic Foundations of Robotics (WAFR) , 14 , 36-51. https://doi.org/10.1007/978-3-030-44051-0_3
- Ghosh, M. (2019). Geometric Approximations and Their Application to Motion Planning. Doctoral Dissertation, Texas A&M University. View publication
- Ghosh, M. , Thomas, S. , Morales, M. , Rodriguez, S. , & Amato, A.N.M. (2016). Motion Planning using Hierarchical Aggregation of Workspace Obstacles. In Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS) , 5716--5721. https://doi.org/10.1109/IROS.2016.7759841
- Ghosh, M. (2012). Fast Approximate Convex Decomposition. Texas A&M University. View publication
- Lien, J. & Amato, N.M. (2007). Approximate Convex Decomposition of Polyhedra. Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling (SPM 07) , 121–131. https://doi.org/https://doi.org/10.1145/1236246.1236265
- Lien, J. (2006). Approximate Convex Decomposition and its Applications. Doctoral dissertation, Texas A & M University , 69(01). https://doi.org/N/A
- Lien, J. , Keyser, J. , & Amato, N.M. (2006). Simultaneous Shape Decomposition and Skeletonization. In. Proc. of the 2006 ACM symposium on Solid and physical modeling , 219–228. https://doi.org/10.1145/1128888.1128919
- Lien, J. & Amato, N.M. (2004). Approximate Decomposition of Polygons. Proceedings of the Twentieth Annual Symposium on Computational Geometry (SOCG 04) , 17--26. https://doi.org/10.1145/997817.997823
- Lien, J. & Amato, N.M. (2004). Approximate Convex Decomposition. Proceedings of the Twentieth Annual Symposium on Computational Geometry (SOCG 04) , 457--458. https://doi.org/10.1145/997817.997889