DC: Small: Collaborative Research: Shape Representation of Large Geometries via Convex Approximation
Grant
Overview
Affiliation
Other
View All
Overview
abstract
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.
