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

由于用于生成高分辨率复杂模型的改进技术，由数百万（或更多）小平面组成的几何模型今天很常见。 大尺寸使得在这些模型上执行一些基本的几何操作是不可行的。 例如，计算大卫模型的Minkowski和需要超过14亿次几何联合运算。 为大型模型重新设计现有算法将需要大量的时间和精力，并且可能并不总是可行的。 该项目正在研究近似凸分解（ACD），这是一种大型几何图形的替代表示方法，它使用一组凸对象近似表示原始模型。 通过使用更小的凸近似代替原始模型，ACD允许现有的（低效的）方法和软件有效地执行大型几何形状，而无需设计和实现新的算法。 该项目的一个重要目标是开发简单的算法，不仅允许有效的重建，但也允许实际的implementation.This项目将作出重大贡献的几何计算，如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.