3D 게임에서 충돌 탐지를 효과적으로 하기 위해 구성하는 공간 분할 트리는 분할 평면을 결정하는데 트리 밸런스와 분할 평면과 겹치는 폴리곤의 개수 등을 고려해야 한다. 본 논문에서는 3D 게임 공간 분할 트리에서 트리 빌드 조건에 대한 가중치를 제어하는 휴리스틱 알고리즘을 제안하였다. 가중치의 변화에 따라서 트리 빌드 시간, 분할 평면과 겹치는 폴리곤을 쪼갤 때 시각적 불일치를 유발할 수 있는 T-junction 의 제거 시간, 트리 밸런스에 따른 렌더링 속도(frame per second) 등을 3D 게임 시뮬레이션을 통하여 분석하였다.

Spatial partitioning trees are needed for processing collision detections efficiently. In order to select split planes for spatial partitioning trees, the tree balance and the number of polygons overlapped with the split plane should be considered. In this paper, the heuristic algorithm controlling weight values of tree build criteria is proposed for spatial partitioning trees of 3D games. As the weight values are changed, tree build time, T-junction elimination time which can cause visual artifacts in splitting polygons overlapped with the split plane, rendering speed (frame per second: FPS) according to tree balance are analysed under 3D game simulations.

• 김영식 | Kim, Youngsik