Geometric models composed of millions (or more) of facets are common today due to improved technologies for generating high-resolution complex models. The large size makes it infeasible to perform some fundamental geometric operations on these models. For instance, more than 1.4 billion geometric union operations are required to compute the Minkowski sum of the David model. Re-designing existing algorithms for large models would require significant time and effort, and may not always be possible. This project is investigating approximate convex decomposition (ACD), an alternative representation for large geometries that approximately represents the original model using a set of convex objects. By using the much smaller convex approximation in place of the original model, ACD allows existing (inefficient) methods and software to perform efficiently for large geometries without designing and implementing new algorithms. An important goal of this project is to develop simple algorithms that not only allow efficient reconstruction but also allow practical implementation.
This project will make significant contributions to fundamental problems in geometric computing, such as Minkowski sum, continuous motion collision detection, general penetration depth estimation, and swept volume. Beyond these fundamental geometric operations, this project will provide new ways to handle geometric problems in several areas of robotics (e.g., environment/map representation, motion planning and grasp planning), in pattern recognition (e.g., structural salient feature recognition, visual-based part decomposition and motif identification in protein structures), and in computer graphics (e.g., data compression, physically-based simulation and skeletonization). The software developed by this project will be provided to the public domain.
Models composed of millions of polygons are common today and making it infeasible to perform some fundamental geometric operations, such as Minkowski sum, continuous motion collision detection, penetration depth estimation, and swept volume. The main objective of this project is to approximately represent the original model using a set of convex objects. This representation provides new ways to handle geometric problems in several areas of robotics (e.g., environment/map representation and motion planning), in pattern recognition (e.g., structural salient feature recognition, and visual-based part decomposition), and in computer graphics (e.g., data compression, and physically-based simulation). Consequently, this representation provides unique functionality that is not available from existing shape approximations, such as surface simplification. During the course of this project, our research team explored several approaches to address various issues related to convex approximation and its applications in Minkowski sum computation and motion planning. Our results are summarized below. First, we investigated the issues related to efficiency. We proposed a new method called Fast Approximate Convex Decomposition (FACD) that improves the quality of decomposition and reduces the computational cost for both 2D and 3D models using the idea of relative concavity. Second, we investigated the issues related to parameters. The majority of existing shape-approximation methods require many user-defined parameters to control the quality of the approximation. These parameters are usually problem specific and are not intuitive to the users. We proposed an approach called α-decomposition that is designed to take as few as just a single parameter. In α-decomposition, we explored a space of decompositions parameterized by the value α, the diameter of a circle. Such a space of decompositions (in contrast to a single decomposition) provides a critical benefit that allows persistence analysis. More specifically, when we vary the value of α, some structural features appear and disappear quickly as others persist. Therefore, by analyzing the persistence (i.e., life span) of the features, we can determine better shape decompositions that are more robust to both geometrical and topological noise without parameter tuning. Third, we explored the idea of creating decomposition (called dual decomposition) that can be used for both visually meaningful segmentation and visually convincing simulation. While many shape segmentation methods have been proposed to partitioning mesh into semantic parts, the objective of these methods focuses mostly on the shape analysis and recognition and rarely on interactive applications. We recognized the need to have methods, such as those developed in this project, which provide the benefits from both visual saliency and efficiency from shape segmentation and convex approximation. Finally, we investigated approaches that can handle models with both high topological and geometric complexity. The most challenging task in developing such a decomposition method steamed from that fact that current convex decomposition and shape segmentation methods are computationally expensive and, again, require many user parameters, which are usually unintuitive and make processing a massive number of meshes in applications difficult. Our strategy to handle large complex shapes was to analyze the significance of concave features and avoid resolving insignificant features. An important goal accomplished by this project is the software tools developed for the public domain. These software tools not only enable us to validate our results, but also enable the development of more efficient geometric algorithms in the aforementioned domains and to use feedback to further improve and expand the algorithms and the software. During this project, two new geometric programming courses were developed for advanced undergraduates and graduate students at George Mason University to better prepare students for complex geometric problems.
