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.