Hierarchical Convex Approximation of 3D Shapes for Fast Region Selection

dc.contributor.authorAttene, Marcoen_US
dc.contributor.authorMortara, Michelaen_US
dc.contributor.authorSpagnuolo, Michelaen_US
dc.contributor.authorFalcidieno, Biancaen_US
dc.date.accessioned2015-02-21T17:32:26Z
dc.date.available2015-02-21T17:32:26Z
dc.date.issued2008en_US
dc.description.abstractGiven a 3D solid model S represented by a tetrahedral mesh, we describe a novel algorithm to compute a hierarchy of convex polyhedra that tightly enclose S. The hierarchy can be browsed at interactive speed on a modern PC and it is useful for implementing an intuitive feature selection paradigm for 3D editing environments. Convex parts often coincide with perceptually relevant shape components and, for their identification, existing methods rely on the boundary surface only. In contrast, we show that the notion of part concavity can be expressed and implemented more intuitively and efficiently by exploiting a tetrahedrization of the shape volume. The method proposed is completely automatic, and generates a tree of convex polyhedra in which the root is the convex hull of the whole shape, and the leaves are the tetrahedra of the input mesh. The algorithm proceeds bottom-up by hierarchically clustering tetrahedra into nearly convex aggregations, and the whole process is significantly fast. We prove that, in the average case, for a mesh of n tetrahedra O(n log2 n) operations are sufficient to compute the whole tree.en_US
dc.description.number5en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume27en_US
dc.identifier.doi10.1111/j.1467-8659.2008.01271.xen_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages1323-1332en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2008.01271.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltden_US
dc.titleHierarchical Convex Approximation of 3D Shapes for Fast Region Selectionen_US
Files