| Popis: |
We present a novel GPU algorithm to compute outer cell boundaries of 3D arrangement subdivided by a given set of triangles. An outer cell boundary is defined as a 2-manifold surface consisting of subdivided polygons facing outward. Many geometric problems, such as Minkowski sum, sweep volume, lower/upper envelop, Bool operations, can be reduced to finding outer cell boundaries with specific properties. Computing outer cell boundaries, however, is a very time-consuming job and also is susceptible to numerical errors. To address these problems, we develop an algorithm based on GPU with a robust scheme combining interval arithmetic and multi-level precisions. The proposed algorithm is tested on Minkowski sum of several polygonal models, and shows 5-20 times speedup over an existing algorithm running on CPU. |
