DC: Small: Collaborative Research: Shape Representation of Large Geometries via Convex Approximation

由于生成高分辨率复杂模型的技术改进，由数百万（或更多）个面组成的几何模型在今天很常见。由于尺寸太大，使得对这些模型进行一些基本的几何运算变得不可行。例如，计算David模型的Minkowski和需要超过14亿次几何联合运算。为大型模型重新设计现有的算法将需要大量的时间和精力，并且可能并不总是可能的。该项目正在研究近似凸分解（ACD），这是一种大型几何图形的替代表示，它使用一组凸对象近似地表示原始模型。通过使用更小的凸近似代替原始模型，ACD允许现有的（低效的）方法和软件有效地执行大型几何形状，而无需设计和实现新的算法。该项目的一个重要目标是开发简单的算法，不仅允许有效的重建，而且允许实际实施。本项目将对几何计算的基础问题做出重大贡献，如Minkowski和、连续运动碰撞检测、一般穿透深度估计和扫描体积。除了这些基本的几何运算之外，该项目还将在机器人技术（例如，环境/地图表示、运动规划和抓取规划）、模式识别（例如，结构显著特征识别、基于视觉的部件分解和蛋白质结构中的基元识别）和计算机图形学（例如，数据压缩、基于物理的仿真和骨架化）等几个领域提供处理几何问题的新方法。本项目开发的软件将提供给公共领域。

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.