UC Berkeley

This thesis describes new parallel GPU algorithms that accelerate fundamental CAD operations such as spline evaluations, surface-surface intersections, minimum distance computations, moment computations, etc., thereby improving the interactivity of a CAD system.

CAD systems (such as SolidWorks, AutoCAD, ProE, etc.) create graphical user interfaces for solid modeling, which build on fundamental CAD operations that are performed by a modeling kernel. However, since many of these fundamental operations are compute-intensive, the CAD systems make the designer wait until a particular operation is completed before providing visual feedback and allowing new operations to be performed, reducing interactivity. The broad objective of this research is to develop new parallel algorithms for CAD that run on Graphics Processing Units to provide order-of-magnitude better performance than current CPU implementations.

A critical operation that all CAD systems have to perform is the evaluation of Non-Uniform Rational B-Splines (NURBS) surfaces. We developed a unified parallel algorithm to evaluate and render a NURBS surface directly using the GPU. The GPU algorithm can render over 100 NURBS surfaces at 30 frames per second, significantly enhancing interactivity.

Fundamental modeling operations (such as surface intersections, separation distance computations, etc.) are typically performed repeatedly in a CAD system during modeling. We have developed GPU-accelerated algorithms that perform surface-surface intersections more than 50 times faster than the commercial solid modeling kernel ACIS. We have also developed GPU algorithms to perform minimum distance computations, which have applications in multi-axis machining, path planning, and clearance analysis. These algorithms are not only more than two orders of magnitude faster than the CPU implementations, they often have much tighter error bounds.

We have also developed algorithms for computing accurate geometric moments of solid models that are represented using multiple trimmed-NURBS surfaces. We have developed a framework that makes use of NURBS surface data to evaluate surface integrals of trimmed NURBS surfaces in real time. With our framework, we can compute volume and moments of solid models with error estimates. The framework also supports local geometry changes, which is useful for providing interactive feedback to the designer while the solid model is being designed.

Finally, the ultimate objective of this research is to provide a generalized framework to overcome some of the GPU programming challenges in CAD. Using this framework, a programmer could easily develop complex CAD algorithms that utilize the GPU to improve the performance of CAD systems.