Comparison of Two Parallel Offsetting Algorithms Free from Conflicts Between Threads
Comparison of Two Parallel Offsetting Algorithms Free from Conflicts Between Threads
复制标题
DOI：
10.20965/ijat.2021.p0784
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
M. Inui;Daiki Ishii;Nobuyuki Umezu
中科院分区：
文献类型：
--
作者：
M. Inui;Daiki Ishii;Nobuyuki Umezu
通过偏移半径扩展多面体对象的偏移计算是制造应用中经常使用的基本几何过程。该过程与三重 dexel 表示实体模型相结合，因其鲁棒性以及与使用图形处理单元 (GPU) 的并行处理的兼容性而变得流行。在并行几何处理中，必须避免线程之间的冲突。因此，我们提出了一种新颖的并行偏移算法，避免了线程之间的冲突。三重 dexel 模型是 x、y 和 z 轴对齐的 dexel 模型的组合。每个 dexel 模型都是基于坐标平面上给出的正交网格来定义的。我们预先将网格细分为多个固定大小的子网格。对于每个子网格，分配一个 GPU 线程块。由于在此方法中每个 GPU 线程始终处理与其他线程不同的 dexel 元素，因此不会发生冲突。我们的研究小组之前提出了一种多面体实体模型的并行偏移计算算法，该算法也使用了 Triple-dexel 表示模型和 GPU。在之前的算法中，模型的表面多边形被预先分为几组。通过选择多边形的偏移处理互不影响的多边形组，实现多多边形组的并行偏移计算。这个选择过程非常耗时。进行计算实验来分析当前算法和我们之前的算法之间的性能差异。在我们的实验中，与之前的偏移算法相比，当前的算法实现了 1.4 倍到 3.2 倍的加速。
Offset computation for expanding a polyhedral object by an offset radius is a fundamental geometric process frequently used in manufacturing applications. This process combined with the triple-dexel representation solid model has become popular because of its robustness and compatibility with parallel processing using a graphics processing unit (GPU). In parallel geometric processing, conflicts between threads must be avoided. Thus, we propose a novel parallel offsetting algorithm free from conflicts between threads. The triple-dexel model is a combination of x-, y-, and z-axis-aligned dexel models. Each dexel model is defined based on an orthogonal grid given on a coordinate plane. We subdivide the grid into several sub-grids of a fixed size in advance. For each sub-grid, a block of GPU threads is assigned. As each GPU thread always processes different dexel elements from the other threads in this method, no conflict occurs. Our research group has previously presented a parallel offset computation algorithm for a polyhedral solid model that also uses a triple-dexel representation model and a GPU. In the previous algorithm, the surface polygons of the model are classified into several groups in advance. The parallel offset computation of multiple polygon groups is realized by selecting groups of polygon in which the offset processing of the polygons does not affect one another. This selection process is time-consuming. Computational experiments were performed to analyze the performance difference between the current algorithm and our previous algorithm. In our experiments, the current algorithm achieved speedups of 1.4 times to 3.2 times compared to our previous offsetting algorithm.