GPU를 이용한 대량 삼각형 교차 알고리즘
Robust GPU-based intersection algorithm for a large triangle set
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
삼각형간의 교차 계산은 많은 3차원 기하 문제들을 해결하는데 있어서 기본적으로 요구되는 연산 과정이다. 본 논문에서는 대량의 삼각형 집합 안에서의 교차 계산을 효율적이며 강인하게 처리할 수 있는 GPU 알고리즘을 제안한다. 이알고리즘은 k-d 트리의 구성, 삼각형쌍 생성, 정확한 교차 계산을 모두 GPU에서 처리한다. 여기서 사용되는 k-d 트리에서는 분할 과정 중에 삼각형들의 복사가 많이 발생한다. 이렇게 복사된 삼각형들로 인하여 중복된 삼각형쌍들이 많이생성되는데,이러한중복삼각형쌍들을효율적으로제거하기위하여분할인덱스를도입하였다.분할인덱스는간단한논리곱연산만으로중복여부를효과적으로판단할수있다.수치적강인성을높이기위하여는부동소숫점필터링을통해불안전한삼각형쌍들을분리하고, CLP(controlled linear perturbation)를이용하여CPU쓰레드에서처리하도록하였다. 제안한 알고리즘은 기존의 민코스키합 알고리즘의 합삼각형 교차계산에 적용하여 효율성과강인성을입증하였다
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.
참고문헌 (17)
- S. Gottschalk, "Obbtree: A hierarchical structure for rapid interference detection", in Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, pp.171~180 (1996), ACM
- C. Lauterbach, "Fast bvh construction on gpus", Eurographics, 28(2), pp.1~10 (2009)
- C. Lauterbach, "gproximity: Hierarchical gpu-based operations for collision and distance queries", Computer Graphics Forum (2010)
- H. Samet, "The Design and Analysis of Spatial Data Structures" (1989), Addision-Wesley
- I.Wald, "On building fast kd-trees for ray tracing, and on doing that in o(n log n)", in Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing, pp.61~69 (2006)
- K. Zhou, "Real-time kd-tree construction on graphics hardware", ACM Transactions on Graphics, 27(5), pp.126:1~126:11 (2008)
- 신하용, "Self-intersection removal in triangular mesh offsetting", COMPUTER-AIDED DESIGN AND APPLICATIONS, 1(1-4), pp.477~484 (2004), Computer Aided Design Solutions
- P. Volino, "Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity", Computer Graphics Forum, 13(3), pp.155~166 (1994)
- M. Campen, "Exact and robust (self) intersections for polygonal meshes", Computer Graphics Forum, 29(2), pp.397~406 (2010)
- M. Campen, "Polygonal boundary evaluation of minkowski sums and swept volums", Computer Graphics Forum, 29(5), pp.1613~1622 (2010)
- V. Milenkovic, "Robust minkowski sums of polyhedra via controlled linear perturbation", in Proceedings of Symposium on Solid and Physical Modeling, pp.23~30 (2010)
- M. Harris, "Parallel prefix sum (scan) with cuda", pp.851~876 (2007), Addison Wesley
- O. Tropp, "A fast triangle to triangle intersection test for collision detection", Computer Animation and Virtual Worlds, 17, pp.527~535 (2006)
- S. Abrams, "Computing swept volumes", Journal of Visualization and Computer Animation, 11(69), pp.82~ (2000)
- A. Requicha, "Boolean operations in solid modeling: Boundary evaluation and merging algorithms", in Proceedings of the IEEE, pp.30~44 (1985)
- X. Zhang, "Reliable sweeps", in 2009 SIAM, 2009, 373~378[DOI]
- Y. J. Kim, "Fast swept volume approximation of complex polyhedral models", CAD Computer Aided Design, 36(11), pp.1013~1027, Pergamon Press Ltd.