암시적 k-d 트리

그리드 중위수 분할 기능을 사용한 2D 암묵적 최대 kd-ree의 구성 및 저장.직사각형 그리드의 각 셀에는 낮음(밝은 파란색)에서 높음(밝은 빨간색)까지의 스칼라 값이 하나씩 할당되어 있다.그리드의 메모리 풋프린트는 하단에 표시된다.암묵적 max kd-tree의 사전 정의된 메모리 풋프린트는 그것보다 적은 하나의 스칼라 값을 필요로 한다.노드의 최대값 저장은 상선에 표시된다.

암묵적 k-d 트리는 직선 격자 위에 암묵적으로 정의된 k-d 트리다.그것의 분할 평면의 위치와 방향은 명시적으로 주어지는 것이 아니라 나무의 노드에 속하는 초정직선에 정의된 어떤 재귀적 분할 기능에 의해 암시적으로 주어진다.각 내부 노드의 분할면은 기본 그리드의 그리드 평면에 위치하여 노드의 그리드를 두 개의 하위 그리드로 분할한다.

명명 및 참조

"min/max k-d tree"와 "implicit k-d tree"라는 용어가 혼재되기도 한다.이는 "implificate k-d tree"라는 용어를 사용한 첫 번째 간행물이 실제로 명시적인 최소/최대 k-d 트리를 사용했지만, "implific k-d tree"라고 언급하여 주어진 ISO 표면에서 암묵적으로 추적하는 데 사용될 수 있음을 나타냈기 때문이다.그럼에도 불구하고, 본 간행물은 또한 두 개의 힘을 가진 부차적인 경도를 가진 정수 초직선 위에만 건설될 수 있다는 제한을 가진 암묵적인 k-d 나무의 하위 집합인 슬림한 k-d 나무도 사용했다.여기서 정의한 암묵적 k-d 트리가 최근 컴퓨터 그래픽에 응용된 형태로 도입되었다.^[2][3]암묵적 k-d 트리 노드에 속성을 할당할 수 있으므로, 노드에 최소/최대 값을 할당하는 암묵적 k-d 트리를 "적절한 최소/최대 k-d 트리"라고 할 수 있다.

건설

암묵적 k-d 트리는 일반적으로 명시적으로 구성되지 않는다.노드에 접근할 때 트리를 정의하는 분할 기능을 사용하여 분할 평면 방향과 위치를 평가한다.서로 다른 분할 기능으로 동일한 기본 그리드에 대해 서로 다른 트리가 발생할 수 있다.

분할 기능

분할 기능은 특수 목적에 맞게 조정할 수 있다.특수 분할 기능 등급의 두 가지 사양 아래.

• 비감속 분할 기능은 퇴보된 노드(해당 정수 하이퍼 직각의 볼륨이 0인 노드)를 생성할 수 없다.이들의 암묵적 k-d 트리는 완전한 바이너리 트리로서, n 리프 노드 n - 1 내부 노드를 가지고 있다.그들의 암묵적 k-d 나무는 퇴화되지 않은 암묵적 k-d 나무다.
• 완전 분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할-분할해당 암묵적 k-d 트리는 완전한 암묵적 k-d 트리다.

전체 분할 함수는 그리드 중위수 분할 함수를 예로 들 수 있다.암묵적 k-d 트리의 각 노드에 속하는 k차원 정수 초정형 hyprec[2][k]를 사용하여 상당히 균형 잡힌 암묵적 k-d 트리를 만든다.고직사각형은 직선 그리드의 어떤 그리드 셀이 해당 노드에 속하는지 정의한다.이 고직각의 부피가 1과 같으면 해당 노드는 단일 그리드 셀이며 따라서 더 이상 세분화되지 않고 리프 노드로 표시된다.그렇지 않으면 방향 o로 초직각의 가장 긴 범위를 선택한다.해당 분할면 p는 그 방향을 따라 고직각의 격자 중위수에 가장 가까운 격자 평면에 위치한다.

분할 평면 방향 o:

o = 최소{argmax(i = 1 ...k: (hyprec[1][i] - hyprec[0]])}

분할 평면 위치 p:

p = 라운드다운(hyprec[0][o] + hyprec[1][o]] / 2)

암시적 k-d 트리 노드에 특성 할당

암묵적인 k-d 트리의 장점은 분할 평면의 방향과 위치를 명시적으로 저장할 필요가 없다는 것이다.

그러나 일부 애플리케이션은 분할 평면의 방향 외에 추가로 내부 트리 노드에 속성을 배치해야 한다.이러한 속성은 단일 비트 또는 단일 스칼라 값일 수 있으며, 노드에 속하는 하위 그리드가 관심 있는지 여부를 정의한다.완전한 암시적 k-d 트리의 경우, 올바른 크기의 속성 배열을 미리 할당하고 트리의 각 내부 노드를 할당된 배열의 고유한 요소에 할당할 수 있다.

그리드의 그리드 셀의 양은 그리드에 속하는 정수 하이퍼 직각의 부피와 동일하다.완전한 암묵적 k-d 트리는 그리드 셀보다 한 개의 내부 노드를 가지고 있기 때문에, 얼마나 많은 속성을 저장해야 하는가를 미리 알고 있다."내측 노드에 대한 정수 하이퍼 직각 볼륨" 관계는 할당된 배열의 고유한 요소를 각 분할 평면에 할당하는 재귀 공식과 함께 완전한 분할 기능을 정의한다.해당 알고리즘은 아래의 C-pseudo 코드로 주어진다.

// 전체 암시적 k-d 트리의 내부 노드에 속성 할당  // 정수 도움말 하이퍼 직각 하이프레크 생성(이 볼륨(하이프레크)은 잎의 양과 동일) 인트로 하이프렉[2][k] = { { 0, ..., 0 }, { length_1, ..., length_k } }; // 전체 암시적 k-d 트리에 대한 속성 배열을 한 번 할당 동뜨다 *a = 새로운 동뜨다[부피(하이프렉) - 1];  동뜨다 암묵적 KdTreeAttributes(인트로 하이프렉[2][k], 동뜨다 *a) {   만일 (vol(하이프렉) > 1) // 현재 노드가 내부 노드임   {     // 기초적인 전체 분할 기능을 사용하여 분할 평면의 방향 o 및 위치 p를 평가한다.     인트로 o, p;     completeSplittingFunction(하이프렉, &o, &p);     // 어린이의 정수 하이퍼레방글 hyprec_l 및 hyprec_r을 평가     인트로 hyprec_l[2][k], hyprec_r[2][k];     hyprec_l       = 하이프렉;     hyprec_l[1][o] = p;     hyprec_r       = 하이프렉;     hyprec_r[0][o] = p;     // 아동의 기억 위치 a_l 및 a_r 평가     동뜨다* a_l = a + 1;     동뜨다* a_r = a + vol(hyprec_l);     // 아이들의 속성 c_l과 c_r을 재귀적으로 평가한다.     동뜨다 c_l = 암묵적 KdTreeAttributes(hyprec_l, a_l);     동뜨다 c_r = 암묵적 KdTreeAttributes(hyprec_r, a_r);     // 자녀의 속성을 현재 특성 c에 병합     동뜨다 c = 합병하다(c_l, c_r);     // 현재 속성을 저장하고 반환     a[0] = c;     돌아오다 c;   }   // 현재 노드는 리프 노드.해당 그리드 셀에 속하는 속성 반환   돌아오다 기여하다(하이프렉); } 

이 알고리즘이 모든 직선 그리드에 적용된다는 것은 언급할 가치가 있다.해당 정수 초직각은 반드시 2의 힘인 부차적 거리를 가질 필요는 없다.

적용들

암묵적 max-k-d 트리는 광 주물 isosurfaces/MIP(최대 강도 투영)에 사용된다.각 내부 노드에 할당된 속성은 노드에 속하는 서브그리드(subgrid)에 주어진 최대 스칼라 값이다.노드의 스칼라 값이 광선을 따라 검색된 ISO 값/현재 최대 강도보다 작을 경우 노드는 통과되지 않는다.암묵적 최대 kd-ree의 낮은 저장 요건과 레이 주물의 유리한 시각화 복잡성으로 인해 일반 PC의 대화형 프레이머에서 매우 큰 스칼라 필드의 레이캐스트(그리고 심지어 이소서페이스도 변경)가 가능하다.이와 유사하게, 최소/최대 kd-ree를 사용하여 지형 선과 같은 질의를 효율적으로 평가할 수 있다.^[4]

복잡성

격자 셀이 n개인 k차원 그리드에 걸쳐 있는 암시적 k-d 트리가 주어진다.

• 트리의 노드에 속성을 할당하는 데 $O{\displaystyle \mathrm{}(k}$ n${\displaystyle }$) ${\displaystyle \mathrmat {O}(kn)}$시간이 소요된다.
• 노드에 속성을 저장하려면 $O{\displaystyle \mathrm{}(n}$) ${\displaystyle \mathrmat {O}(n)}$개의$$ 메모리가 필요하다.
• 해당 암묵적 max k-d 트리를 사용하는 Ray casting iso-surfaces/MIP 기본 스칼라 필드는 $대략{\displaystyle \mathrm{}}$ O${\displaystyle (\log }$ ${\displaystyle }$ ${\displaystyle (n}$)${\displaystyle \mathrm {O}(\log(n)})}$시간이$$ 소요된다.

참고 항목

• k-d 트리
• 최소/최대 k-d 트리

참조