⋯1번째 줄 근처
+추가: ## 개요
+추가: 팔진트리(八進 tree, octree)는 각 내부 노드가 정확히 여덟 개의 자식 노드를 갖는 트리 자료구조다. 삼차원 공간을 재귀적으로 여덟 개의 팔분면(octant)으로 분할하는 데 주로 쓰이며, 이차원 공간을 네 개의 사분면으로 분할하는 사분트리(quadtree)의 삼차원 대응물이다. 이름은 그리스어 어근 'oct(여덟)'과 'tree'를 합성한 것이다[1][2][3].
+추가:
+추가: ## 작동 방식과 유형
+추가:
+추가: ### 공간 분할 원리
+추가:
+추가: 각 노드가 자신이 나타내는 공간을 여덟 팔분면으로 분할한다. 분할 기준에 따라 두 주요 유형으로 나뉜다[3].
+추가:
+추가: #### 점 영역(Point Region, PR) 팔진트리
+추가:
+추가: 노드가 명시적 3차원 점을 저장하며, 이 점이 해당 노드 분할의 '중심'이 된다. 이 점은 여덟 자식 각각의 한 모서리를 정의한다. 점 사분트리(point quadtree)와 유사하다. 루트 노드가 무한 공간을 나타낼 수 있다[3].
+추가:
+추가: #### 행렬 기반(Matrix-based, MX) 팔진트리
+추가:
+추가: 분할 점이 노드가 나타내는 공간의 중심으로 암시적으로 정해진다. 영역 사분트리(region quadtree)와 유사하다. 루트 노드는 유한한 유계 공간을 나타내야 하며, 그래야 암시적 중심이 잘 정의된다[3].
+추가:
+추가: ### k-d 트리와의 차이
+추가:
+추가: k-d 트리는 한 차원씩 분할하지만 팔진트리는 한 점을 중심으로 분할한다. k-d 트리는 항상 이진 트리이나 팔진트리는 8진 트리다. 옴니트리(Omnitree)는 각 해상도 수준에서 차원의 부분집합을 분할하도록 허용해 k-d 트리와 팔진트리를 일반화한다[3].
+추가:
+추가: ### 구현 알고리즘 (점 분해)
+추가:
+추가: 재귀적 분해 알고리즘 개요(MATLAB 구문 기준):
+추가:
+추가: 1. 주어진 모든 점을 둘러싸는 단일 빈(bin)으로 시작한다.
+추가: 2. 빈을 8개 팔진트리 영역으로 재귀적으로 분할한다.
+추가: 3. 종료 조건 충족 시 재귀 중단. 대표적 종료 조건:
+추가: - 빈에 포함된 점이 주어진 임계값 미만일 때
+추가: - 빈 크기나 부피가 모서리 길이 기준 최소값에 도달할 때
+추가: - 재귀 깊이가 최대 분할 횟수에 도달할 때[3]
+추가:
+추가: ### 색 양자화 상세 과정
+추가:
+추가: 24비트 RGB 이미지의 전체 색상 목록을 점 입력으로 받아 팔진트리 점 분해 구현에 적용한다. 최상위 레벨 분기 인덱스는 빨강·초록·파랑 최상위 비트를 이용해 4r + 2g + b 공식으로 결정한다. 하위 레벨로 갈수록 다음 비트 중요도를 사용한다. 덜 중요한 비트는 트리 크기 축소를 위해 무시하기도 한다[3].
+추가:
+추가: 리프 노드는 트리에 표현되지 않은 색 데이터를 누적하며 초기에는 단일 비트를 포함한다. 원하는 팔레트 색상 수보다 훨씬 많은 색이 입력되면, 최하위 레벨 노드를 찾아 비트 데이터를 리프 노드로 평균화해 올려 트리 일부를 가지치기하며 크기를 지속적으로 줄인다. 샘플링 완료 후 리프 노드까지 모든 경로를 탐색하며 경로상 비트를 기록하면 대략 원하는 개수의 색상을 얻는다[3].
+추가:
+추가: ## 사례
+추가:
+추가: ### 게임 엔진 및 3D 그래픽스 활용
+추가:
+추가: - **Cube 2: Sauerbraten**: 지오메트리가 거의 전적으로 팔진트리 기반인 3D 게임 엔진[3]
+추가: - **id Tech 6**: 복셀을 팔진트리에 저장해 활용하는 3D 게임 엔진[3]
+추가: - **Irrlicht Engine**: 팔진트리 씬 노드 지원[3]
+추가: - **OGRE**: 팔진트리 씬 매니저 구현 포함[3]
+추가:
+추가: ### 그 밖의 응용 분야
+추가:
+추가: - 3D 컴퓨터 그래픽스에서 디테일 수준(Level of Detail) 렌더링
+추가: - 공간 인덱싱(spatial indexing)
+추가: - 최근접 이웃 탐색(nearest neighbor search)
+추가: - 3차원 효율적 충돌 감지(collision detection)
+추가: - 뷰 프러스텀 컬링(view frustum culling)
+추가: - 고속 다극자 방법(Fast multipole method)
+추가: - 비구조 격자(unstructured grid)
+추가: - 유한 요소 해석(finite element analysis)
+추가: - 희소 복셀 팔진트리(sparse voxel octree)
+추가: - 상태 추정(state estimation)
+추가: - 집합 추정(set estimation)[3]
+추가:
+추가: ## 관련 기술 비교
+추가:
+추가: ### 이진 공간 분할(BSP, Binary Space Partitioning)
+추가:
+추가: 같이 보기 항목에 이진 공간 분할법이 명시되어 있다[2]. BSP는 공간을 이진으로 분할하는 반면 팔진트리는 8진 분할을 수행한다.
+추가:
+추가: ### 경계 구간 계층(Bounding Interval Hierarchy)
+추가:
+추가: 같이 보기 항목에 포함되어 있다[3].
+추가:
+추가: ### 선형 팔진트리(Linear octree)
+추가:
+추가: 같이 보기 항목에 포함되어 있다[3].
+추가:
+추가: ### 복셀(Voxel)
+추가:
+추가: 같이 보기 항목에 포함되어 있으며[2][3], id Tech 6 등에서 복셀 데이터를 팔진트리에 저장해 관리한다[3].
+추가:
+추가: ### 사분트리(Quadtree)
+추가:
+추가: 팔진트리의 이차원 대응물이자 기반 구조다[1][2][3].
+추가:
+추가: 이 문서는 GGWiki AI가 공개 자료(아래 출처)를 조사해 새로 쓴 초안입니다. 틀린 내용은 편집하거나 이의 제기로 알려 주세요.
