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

该项目是美国-以色列计算机科学合作(USICCS)计划的一部分。通过这一计划，NSF和美国-以色列双国科学基金会(BSF)共同支持美国研究人员和以色列研究人员之间的合作。该研究项目的目标是协同设计高效的算法来计算用于分析三维实体模型的距离结构。这些结构是许多应用领域算法的基本构件，包括形状分析、分割、邻近查询、有限元分析的网格划分、模式识别和运动规划，具有广泛的社会和经济效益，从安全到药物设计。提出的方法建立在协作PI初步结果的基础上，该结果引入了结合低包络方法和大规模并行图形处理单元(GPU)计算的算法方法。将开发新的算法来直接从定义CAD模型的曲面计算距离结构，包括事实上的行业标准非均匀有理B-Spline(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.