비유클리드 공간 분할을 위한 구면좌표계 기반 Octree의 특징과 한계 분석 = Analysis of Features and Limitations of Spherical Octree for Dividing Non-Euclidean Space Partitioning

다국어 초록 (Multilingual Abstract)

To efficiently retrieve and store geometry information in three dimensional space, those partitioning grids including the octree and kd-tree defined in the Cartesian coordinates are often used. Unlike this, partitioning grids defined in non-Euclidean space are relatively not fully studied. In this paper, I present and discuss the features, applications, and limitations of a non-Euclidean space partitioning method, S-Octree, which is defined in the spherical coordinates to gain some insights for better methods. First, I show discontinuity issues that happen at near certain points. Then, I present how those numerical errors typically occur with angle-based geometry information processing algorithms affect S-Octree by experiments. Those errors can be accumulated by repeated conversions but I represent some cases where the accumulated errors converge to upper bounds. Also, I discuss the rotational invariance for those features required in better new non-Euclidean space partitioning methods.

국문 초록 (Abstract)

3차원 공간에서 기하 정보의 효율적인 저장과 탐색을 위해 주로 직교좌표계에서 octree 또는 kd-tree 등과 같은 공간 분할 방식이 사용된다. 이에 비해, 비유클리드 공간 분할 방식은 내재된 잠재력과 가능성에도 불구하고 상대적으로 연구가 활발하지 않다. 본 논문에서는 비유클리드 공간 분할 방식인 구면좌표계 기반 octree(S-Octree)의 특성과 적용 분야, 한계를 살펴봄으로써 비유클리드 공간 분할 방식의 가능성과 발전 방향을 모색하고자 한다. S-Octree의 한계로 먼저 특정 영역에서 발생하는 불연속 문제를 논의하고 그 다음 각도 기반 기하 정보 처리 방식에서 흔히 발생하는 수치 오류가 S-Octree에서는 어떠한 양상으로 발생하는지 실험을 통해 살펴본다. 이러한 수치 오류는 연산이 연속적으로 수행됨에 따라 누적되는데 누적된 오류가 상한으로 수렴하는 사례들을 제시한다. 또한 보다 나은 새로운 비유클리드 공간 분할 기법에서 요구되는 회전 비의존성을 논의한다.

참고문헌 (Reference)

1 김종현 ; 박태정 ; 김창헌, "구면 좌표계의 특성을 이용한 듀얼 컨투어링 기법 개선" (사)한국컴퓨터그래픽스학회 17 (17): 27-36, 2011

2 A. Jacobson, "libigl : A simple C++ geometry processing library"

3 F. C. Crow, "The aliasing problem in computer-generated shaded images" 20 (20): 799-805, 1977

4 박태정 ; 이성호 ; 김창헌, "S-Octree: An Extension to Spherical Coordinates" 한국멀티미디어학회 13 (13): 1748-1759, 2010

5 N. Sharp, "Navigating intrinsic triangulations" 38 (38): 1-16, 2019

6 W. E. Lorensen, "History of the Marching Cubes Algorithm" 40 (40): 8-15, 2020

7 B. Gärtner, "Fast and Robust Smallest Enclosing Balls" 325-338, 1999

8 박태정 ; 강신진 ; 김창헌, "Face Mesh Compression Based on S-Octree for Game Characters" (사)한국컴퓨터게임학회 25 (25): 67-78, 2012

9 T. Park, "Face Mesh Compression Based on Half-Spherical Coordinates for Home Entertainment Systems" 701-702, 2011

10 T. Ju, "Dual contouring of hermite data" 339-346, 2002

11 C. E. Shannon, "A Mathematical Theory of Communication" Institute of Electrical and Electronics Engineers (IEEE) 27 (27): 379-423, 1948