최소/최대 kd-트리

min/max kd-tree

최소/최대 kd-tree는 최소 및 최대 두 개의 스칼라 값을 노드에 할당하는 k-d 트리입니다.내부 노드의 최소/최대값은 하위 노드의 최소/최대값과 동일하다.

건설

최소/최대 kd-tree는 재귀적으로 구성할 수 있다.루트 노드부터 분할 평면 방향 및 위치를 평가한다.그런 다음 어린이의 분할 평면과 최소/최대 값을 재귀적으로 평가한다.현재 노드의 최소/최대 값은 단순히 하위 노드의 최소/최대값이다.

특성.

최소/최대 kd 트리는 kd-tree의 속성 외에도 내부 노드의 최소/최대 값이 각각 하나의 자식 중 하나의 최소/최대 값과 일치하는 특수 속성을 가지고 있다.이를 통해 내부 노드에 2비트를 저장하고 하위 노드에 최소/최대 값을 할당함으로써 리프 노드의 최소/최대 값 저장을 폐기할 수 있다. 각 내부 노드의 최소/최대 값은 루트 노드의 최소/최대 값이 별도로 저장되는 곳에 미리 알려지게 된다.각 내부 노드에는 두 개의 최소/최대 값 외에 두 개의 비트가 주어지며, 이러한 최소/최대 값이 할당되는 하위 값(0: 왼쪽 하위 1: 오른쪽 하위)을 정의한다.하위 항목에 할당되지 않은 최소/최대 값은 이미 알려진 현재 노드의 최소/최대 값이다.두 비트는 최소/최대값의 최소 중요 비트에 저장될 수 있으며, 따라서 이 비트는 아래/위로 분류하여 근사치해야 한다.

전체 이진 kd-tree의 리프 노드가 트리 노드의 절반이기 때문에 결과적으로 메모리 감소가 작은 것은 아니다.

적용들

최소/최대 kd-tree는 광 주조 이소서페이스/MIP(최대 강도 투영)에 사용된다.Isosurface Ray Casting은 현재 노드의 최소값/최대값 사이에 선택한 iso값이 있는 노드만 통과한다.이 요구 사항을 충족하지 않는 노드는 지정된 iso 값에 대한 등거리면(빈 공간 건너뛰기)을 포함하지 않으므로 생략한다.MIP의 경우, 노드의 최대치가 광선을 따라 현재 최대 강도보다 작으면 노드가 통과되지 않는다.레이 캐스팅의 유리한 시각화 복잡성으로 인해 일반 PC의 대화형 프레이머에서 매우 큰 스칼라 필드의 레이 캐스트(그리고 심지어 이소서페이스의 변경)가 가능하다.특히 암묵적 최대 kd-tree는 직선 그리드에 정의된 스칼라 필드를 시각화하기 위한 최적의 선택이다( 참조).이와 유사하게, 최소/최대 kd-ree를 사용하여 지형 선과 같은 질의를 효율적으로 평가할 수 있다.[4]

참고 항목

참조

  1. ^ 마티아스 그로, 카스텐 로제프스키, 마틴 버트람, 한스 하겐 "고속 암묵적 KD-트리스: 가속 이소서페이스 레이 추적 및 대형 스칼라 필드의 최대 강도 투영" CGIM07: 컴퓨터 그래픽 및 이미징의 진행(2007) 67-74
  2. ^ Ingo Wald, Heiko Friedrich, Gerd Marmitt, Philip Slusionlek 및 Hans-Peter Saidel "Instant Isosurface Ray Tracking with Implicid KD-Trees" IEEEEE Transactions on Visualization and Computer Graphigraphics(2005)
  3. ^ Matthias Groß (PhD, 2009) 쌍방향 레이 주물을 위한 과학적 응용을 위한 연구
  4. ^ 버나드 듀벤헤지 2009년 "아프리카에서 열린 제6차 컴퓨터 그래픽, 가상현실, 시각화 및 상호작용에 관한 국제회의의 진행"에서 "효율적인 지형의 가시선 계산을 위해 Implicit Min/Max KD-Tree 사용"