K-D Tree

Creator

Creator

Seonglae Cho

Created

Created

2021 Jul 24 16:24

Editor

Editor

Seonglae Cho

Edited

Edited

2024 Jul 27 16:22

Refs

Refs

KD tree

AABB 를 이용해서 계층적으로 이진트리로 공간을 분할하는 구조

모든 노드가 k차원 점인 이진 트리

모든 리프 노드는 암시적으로 공간을 반평면의 두 부분으로 나누는 분할 초평면을 만드는 것으로 생각할 수 있다

k차원 공간의 점들을 구조화 하는 공간 분할 자료 구조

교차검사는 매우 빠르지만 즉 렌더링 성능은 가장 좋지만, 트리 생성시간이나 수정시간이 매우 오래 걸려서 동적인 물체에 대해서는

BVH 가 더 사용된다

레이트레이싱의 KD트리와 BVH

DXR(MicrosoftX Raytracing)의 활용이 점점 늘어나고 관심도 늘어가고 있다. DXR 자료는 점점 많아 지고 있는데, 그중에 BVH(Bounding Volume Hierarchy)라는 단어가 흔하게 등장한다. 레이트레이싱 세계에서는 이미 오래전부터 사용되던 구조인데...

https://blog.hybrid3d.dev/2019-03-22-raytracing-kdtree-bvh

Backlinks

Recommendations

/////////