GPU를 이용한 대량 삼각형 교차 알고리즘 = Robust GPU-based intersection algorithm for a large triangle set

다국어 초록 (Multilingual Abstract)

Computing triangle-triangle intersections has been a fundamental task required for many 3D geometric problems. We propose a novel robust GPU algorithm to efficiently compute intersections in a large triangle set. The algorithm has three stages:k-d tree construction, triangle pair generation, and exact intersection computation. All three stages are executed on GPU except, for unsafe triangle pairs. Unsafe triangle pairs are robustly handled by CLP(controlled linear perturbation) on a CPU thread. They are identified by floating-point filtering while exact intersection is computed on GPU. Many triangles crossing a split plane are duplicated in k-d tree construction, which form a lot of redundant triangle pairs later. To eliminate them efficiently, we use a split index which can determine redundancy of a pair by a simple bitwise operation. We applied the proposed algorithm to computing 3D Minkowski sum boundaries to verify its efficiency and robustness.

국문 초록 (Abstract)

삼각형간의 교차 계산은 많은 3차원 기하 문제들을 해결하는데 있어서 기본적으로 요구되는 연산 과정이다. 본 논문에서는 대량의 삼각형 집합 안에서의 교차 계산을 효율적이며 강인하게 처리할 수 있는 GPU 알고리즘을 제안한다. 이알고리즘은 k-d 트리의 구성, 삼각형쌍 생성, 정확한 교차 계산을 모두 GPU에서 처리한다. 여기서 사용되는 k-d 트리에서는 분할 과정 중에 삼각형들의 복사가 많이 발생한다. 이렇게 복사된 삼각형들로 인하여 중복된 삼각형쌍들이 많이생성되는데,이러한중복삼각형쌍들을효율적으로제거하기위하여분할인덱스를도입하였다.분할인덱스는간단한논리곱연산만으로중복여부를효과적으로판단할수있다.수치적강인성을높이기위하여는부동소숫점필터링을통해불안전한삼각형쌍들을분리하고, CLP(controlled linear perturbation)를이용하여CPU쓰레드에서처리하도록하였다.
제안한 알고리즘은 기존의 민코스키합 알고리즘의 합삼각형 교차계산에 적용하여 효율성과강인성을입증하였다

참고문헌 (Reference)

1 C. Lauterbach, "gproximity: Hierarchical gpu-based operations for collision and distance queries" 2010

2 H. Samet, "The Design and Analysis of Spatial Data Structures" Addision-Wesley 1989

3 신하용, "Self-intersection removal in triangular mesh offsetting" Computer Aided Design Solutions 1 (1): 477-484, 2004

4 V. Milenkovic, "Robust minkowski sums of polyhedra via controlled linear perturbation" 23-30, 2010

5 X. Zhang, "Reliable sweeps" ACM 373-378, 2009

6 K. Zhou, "Real-time kd-tree construction on graphics hardware" 27 (27): 126:1-126:11, 2008

7 M. Campen, "Polygonal boundary evaluation of minkowski sums and swept volums" 29 (29): 1613-1622, 2010

8 M. Harris, "Parallel prefix sum (scan) with cuda" Addison Wesley 851-876, 2007

9 I.Wald, "On building fast kd-trees for ray tracing, and on doing that in o(n log n)" 61-69, 2006

10 S. Gottschalk, "Obbtree: A hierarchical structure for rapid interference detection" ACM 171-180, 1996

11 Y. J. Kim, "Fast swept volume approximation of complex polyhedral models" Pergamon Press Ltd. 36 (36): 1013-1027, 200409

12 C. Lauterbach, "Fast bvh construction on gpus" 28 (28): 1-10, 2009

13 M. Campen, "Exact and robust (self) intersections for polygonal meshes" 29 (29): 397-406, 2010

14 P. Volino, "Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity" 13 (13): 155-166, 1994

15 S. Abrams, "Computing swept volumes" 11 (11): 82-, 2000

16 A. Requicha, "Boolean operations in solid modeling: Boundary evaluation and merging algorithms" 30-44, 1985

17 O. Tropp, "A fast triangle to triangle intersection test for collision detection" 17 : 527-535, 2006