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.
