K-d 트리

Ahn9807 (토론 | 기여)님의 2023년 4월 5일 (수) 10:29 판 (새 문서: 분류:그래픽 가속 알고리즘 ==개요== 축과 평행한 면으로 공간을 분할하여 트리구조를 생성한뒤 그를 통해 삼각형과의 교점을 찾는 방식이다. 컴퓨터 과학에서, k-d 트리 (영어: k-d tree, k-차원(dimensional) 트리)는 k차원 공간의 점들을 구조화 하는 공간 분할 자료 구조이다. k-d 트리는 다차원 탐색 키에 관련된 탐색 같은 적용분야에 유용한 자료구조이다(예: 범위 탐...)
(차이) ← 이전 판 | 최신판 (차이) | 다음 판 → (차이)


개요

축과 평행한 면으로 공간을 분할하여 트리구조를 생성한뒤 그를 통해 삼각형과의 교점을 찾는 방식이다. 컴퓨터 과학에서, k-d 트리 (영어: k-d tree, k-차원(dimensional) 트리)는 k차원 공간의 점들을 구조화 하는 공간 분할 자료 구조이다. k-d 트리는 다차원 탐색 키에 관련된 탐색 같은 적용분야에 유용한 자료구조이다(예: 범위 탐색과 최근접 이웃 탐색). k-d 트리는 이진 공간 분할 트리의 특수한 경우이다.

공간 나누기

Kd-trees.png

축과 평행한 면으로 공간을 제귀적으로 나눈다. 만약 삼각형이 나뉘어 질수 없으면 삼각형이 겹칠 수도 있다.

삼각형 찾기

Finding Kd-trees.png
  1. 앞에서 뒤로
  2. 시선의 반대방향에서 시선 방향으로

BVH와 무었이 다른가?

  1. BVH는 정점을 나누지만, Kd-tree는 공간을 나눈다.
  2. BVH는 leaf node 가 반드시 하나의 삼각형만을 가르키지만 kd-tree는 leaf node의 삼각형이 중첩될 수도 있다.
  3. BVH는 반드시 leaf node 까지 찾아야 하지만 kd-tree는 중간에 탐색을 끝낼 수도 있다.