GPU 가속을 이용한 정밀한 스윕 볼륨 경계 계산
Precise Sweep Volume Computation Accelerated by GPU
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
요 약본 논문에서는 삼각형 메시의 스윕 볼륨 표면을 정밀하고 안정적으로 계산하는 GPU 알고리즘을 제안한다. 삼각형 메시의 기하 요소들을 스윕하여 근사적으로 삼각형 집합을 생성하고, 이 집합의 엔벨롭을 계산하면 스윕 볼륨의 최외곽 경계 표면을 얻을 수 있다. 엔벨롭을 찾기 위하여 우리는 삼각형 집합의 공간 분할을 계산하고 그 분할의 최외곽 경계를 추출하였다. 알고리즘의 안정성을 확보하기 위하여 우리는 스윕 정점들을 초기에 랜덤 섭동하는 방법과 다중 정밀도 구간 연산 기법을 적용하였다. 전체 알고리즘은 대부분의 계산을 GPU에서 처리하도록 구현되었고, 결과적으로 기존 알고리즘에 비해 수십~수백 배의 성능을 보여준다.
Abstract
We present a robust GPU algorithm constructing a sweep volume boundary for a triangular mesh model. Sweeping geometric entities of a triangular mesh object is first approximated to a set of triangles, the envelope of which becomes the outer boundary of the sweep volume. We find the envelope by computing the arrangement of the triangle set and extracting its outmost boundary. To ensure robustness of the algorithm, we adopt random perturbation of sweep vertices and the interval arithmetic using multi-level precisions. The algorithm is implemented to perform most computation on GPU, and as a result it runs two orders of magnitude faster than other algorithms.
참고문헌 (12)
- Young J. Kim, "Fast Swept Volume Approximation of Complex Polyhedral Models", Proc. of ACM Symposium on Solid Modeling and Applications, pp.11~22 (2003)
- Xinyu Zhang, "Reliable sweep", SIAM, 2009, 373~378
- Campen, M., "Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes", Computer Graphics Forum, 29 (2010)
- Sacks, E., "Controlled linear perturbation", Computer-Aided Design, 43(10), pp.1250~1257 (2011)
- Pottmann, H., "Handbook of Computer Aided Geometric Design", pp.43~73 (2002), Elsevier
- Abrams, S., "Computing swept volmues", Journal of Visualization and Computer Animation, 11 (1997)
- J. R. Rossignac, "Boundary of the volume swept by a free-form solid in screw motion", Computer-Aided Design, 39(9), pp.745~755 (2006)
- 김재정, "스크류 운동을 하는 다면체의 스웹 볼륨 생성", 한국CDE학회 논문집, 7(4) (2002), 한국CDE학회
- Abdel-Malek, K., "Swept volumes : foundations, perspectives and applications", International Journal of Shape Modeling (2004)
- von Dziegielewski, A., "High Precision Conservative Surface Mesh Generation for Swept Volumes", Proc. of IEEE International Conference on Robotics and Automation (2012)
- 경민호, "GPU를 이용한 대량 삼각형 교차 알고리즘", 한국컴퓨터그래픽스학회논문지, 17(3), pp.9~19 (2011), (사)한국컴퓨터그래픽스학회
- Fogel, E, "CGAL Arrangement and Their Applications: A Step-by-Step Guide(Geometry and Computing)" (2012), Springer