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

DC：小型：协作研究：通过凸近似表示大型几何形状

• 批准号: 0916053
• 负责人: Nancy Amato
• 金额: $ 20万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916053&HistoricalAwards=false
• 关键词: DC; Small; Collaborative; Research; Shape

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.

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