BSF:2012362:Parallel GPU Algorithms for Proximity Analysis of Freeforms

该项目是美国-以色列计算机科学合作（USICCS）计划的一部分。通过该计划，NSF和美国-以色列两国科学基金会（BSF）共同支持美国研究人员和以色列研究人员之间的合作。本研究项目的目标是协同设计有效的算法来计算距离结构，用于分析3D实体模型。这些结构是许多应用领域算法的基本构建模块，包括形状分析、分割、邻近查询、有限元分析网格化、模式识别和运动规划，具有从安全到药物设计的广泛社会和经济效益。所提出的方法建立在合作PI的初步结果的基础上，该结果引入了一种结合了低包络方法和大规模并行图形处理单元（GPU）计算的算法方法。将开发新的算法，直接从定义CAD模型的曲面计算距离结构，包括非均匀有理B样条（NURBS）曲面的事实上的行业标准。这个问题以前被认为是棘手的，因为所产生的高阶表面，如果解析解决。所提出的基于GPU的方法将通过直接分析曲面来解决速度和鲁棒性问题，而不是使用输入的分段线性近似。该研究将包括最坏情况下的误差理论分析和测量的近似误差在实践中，以最佳地解决速度与精度的权衡。

This project is funded as part of the United States-Israel Collaboration in Computer Science (USICCS) program. Through this program, NSF and the United States - Israel Binational Science Foundation (BSF) jointly support collaborations among US-based researchers and Israel-based researchers. The objective of this research project is to collaboratively design efficient algorithms to compute distance structures for analyzing 3D solid models. These structures are essential building blocks for algorithms in numerous application areas, including shape analysis, segmentation, proximity queries, meshing for finite element analysis, pattern recognition, and motion planning, with wide-ranging societal and economic benefits ranging from security to drug design. The proposed approach builds on the collaborating PIs preliminary results that introduced an algorithmic approach that combines lower-envelope methods and massively parallel Graphics Processing Unit (GPU) computations. New algorithms will be developed to compute distance structures directly from the curved surfaces defining CAD models, including the defacto industry standard of Non-Uniform Rational B-Spline (NURBS) surfaces. This problem was previously considered intractable because of the resulting high order surfaces if solved analytically. The proposed GPU-based approach will address issues of speed and robustness by analyzing the curved surfaces directly, instead of using piecewise-linear approximations of the input. The research will encompass both theoretical error analysis of worst-case error and measurement of the approximation error in practice so as to optimally address the speed versus accuracy tradeoff.