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.

由于改进的高分辨率复杂模型的技术，如今由数百万（或更多）组成的几何模型很常见。 大尺寸使得对这些模型进行一些基本的几何操作是不可行的。 例如，需要超过14亿的几何联盟操作来计算大卫模型的Minkowski总和。 重新设计大型模型的现有算法将需要大量的时间和精力，并且可能并非总是可能的。 该项目正在研究近似凸的分解（ACD），这是大量几何形状的替代表示形式，使用一组凸对象代表原始模型。 通过使用较小的凸近似代替原始模型，ACD允许现有（效率低下的）方法和软件在不设计和实施新算法的情况下对大型几何形状进行有效性能。 该项目的一个重要目标是开发简单的算法，这些算法不仅允许有效地重建，而且还允许实施实施。本项目将为几何计算中的基本问题做出重大贡献，例如Minkowski Sum，连续运动碰撞检测，一般穿透性渗透性估计和扫描量。 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提供给公共领域。