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.

1. [1] M. Inui, “Fast inverse offset computation using polygon rendering hardware,” Computer-Aided Design, Vol.35, pp. 191-201, 2003.
2. [2] M. Inui, N. Umezu, and Y. Kitamura, “Visualizing Sphere-Contacting Areas on Automobile Parts for ECE Inspection,” J. of Computational Design and Engineering, Vol.2, Issue 1, pp. 55-66, 2015.
3. [3] T. Maekawa, “An Overview of Offset Curves and Surfaces,” Computer-Aided Design, Vol.31, pp. 165-173, 1999.
4. [4] J. R. Rossignac and A. A. G. Requicha, “Offsetting Operations in Solid Modelling,” Computer Aided Geometric Design, Vol.3, pp. 129-148, 1986.
5. [5] T. Satoh and H. Chiyokura, “Boolean Operations on Sets Using Surface Data,” Proc. of ACM Symp. on Solid Modeling Foundations and CAD/CAM Applications, pp. 119-127, Austin, Texas, 1991.
6. [6] M. Forsyth, “Shelling and Offsetting Bodies,” Proc. of Third Symp. on Solid Modeling and Applications, pp. 373-381, Salt Lake City, Utah, 1995.
7. [7] D. E. Breen and S. Mauch, “Generating Shaded Offset Surfaces with Distance, Closest Point and Color Volumes,” Proc. of Int. Workshop on Volume Graphics, pp. 307-320, 1999.
8. [8] D. E. Breen, S. Mauch, and R. T. Whitaker, “3D Scan Conversion of CSG Models into Distance Volumes,” Proc. of IEEE Symp. on Volume Visualization, pp. 7-14, 1998.
9. [9] J. Huang, Y. Li, R. Crawfis, S. C. Lu, and S. Y. Liou, “A Complete Distance Field Representation,” Proc. of the Conf. on Visualization, pp. 247-254, 2001.
10. [10] S. Liu and C. C. L. Wang, “Fast Intersection-free Offset Surface Generation from Freeform Models with Triangular Meshes,” IEEE Trans. on Automation Science and Engineering, Vol.8, No.2, pp. 347-360, 2011.
11. [11] C. C. L. Wang and Y. Chen, “Thickening Freeform Surfaces for Solid Fabrication,” Rapid Prototyping J., Vol.19, No.6, pp. 395-406, 2013.
12. [12] W. Li and S. McMains, “A GPU-Based Voxelization Approach to 3D Minkowski Sum Computation,” Proc. of the 14th ACM Symp. on Solid and Physical Modeling, pp. 31-40, 2010.
13. [13] W. Li and S. McMains, “Voxelized Minkowski Sum Computation on the GPU with Robust Culling,” Computer-Aided Design, Vol.43, No.10, pp. 1270-1283, 2011.
14. [14] C. C. L. Wang and D. Manocha, “GPU-Based Offset Surface Computation using Point Samples,” Computer-Aided Design, Vol.45, No.2, pp. 321-330, 2013.
15. [15] C. C. L. Wang, “Computing on Rays: A Parallel Approach for Surface Mesh Modeling from Multi-Material Volumetric Data,” Computers in Industry, Vol.62, No.7, pp. 660-671, 2011.
16. [16] M. O. Benouamer and D. Michelucci, “Bridging the gap between CSG and brep via a triple ray representation,” Proc. of ACM Symp. on Solid Modeling and Applications, pp. 68-79, 1997.
17. [17] B. K. Choi and R. B. Jerard, “Sculptured Surface Machining, Theory and Applications, Kluwer Academic Publishers,” pp. 255-258, 1998.
18. [18] T. Van Hook, “Real-time shaded NC milling display,” Proc. of 13th Annual Conf. on Computer Graphics and Interactive Techniques (SIGGRAPH 1996), Vol.20, No.4, pp. 15-20, 1996.
19. [19] W. E. Lorensen and H. E. Cline, “Marching Cubes: A High Resolution 3D Surface Construction Algorithm,” Proc. of the 14th Annual Conf. on Computer Graphics and Interactive Techniques, pp. 163-169, 1987.
20. [20] T. J. F. Losasso, S. Schaefer, and J. Warren, “Dual Contouring of Hermite Data,” Proc. of ACM SIGGRAPH, pp. 339-346, 2002.
21. [21] T. Moller and E. Haines, “Real-Time Rendering,” A K Peters, 1999.
22. [22] NVIDIA, “CUDA C Programming Guide,” 2018.