삼각형 메쉬를위한 KD 트리가 너무 느립니다

StackOverflow https://stackoverflow.com//questions/20019110

  •  21-12-2019
  •  | 
  •  

문제

KD 알고리즘은 두 개의 새 어레이 (왼쪽 및 오른쪽 프리미티브)를 만들기 위해 프리미티브 (삼각형, 구체, ...)를 파티션하여 루트 BSP 노드를 생성하여 시작합니다. 하위 트리.

왼쪽 및 오른쪽 프리미티브는 주어진 프리미티브 배열을 두 개의 어레이로 분할하여 계산됩니다. 분할 평면 위치는 각각의 삼각형의 간격 (주어진 축 (x, y 또는 z로 투사)의 중앙값을 복용하여 계산됩니다.

, 예를 들어 x 좌표가있는 삼각형 : 1, 2, 3은 middelpoint 1= (3-1) / 2 (x 축을 따라) X 좌표가있는 삼각형 : 2, 3, 8은 MiddelPoint 3= (8-2) / 2 (x 축을 따라) X 좌표가있는 삼각형 : 4, 3, 8에는 MiddelPoint 2.5= (8-3) / 2 (x 축을 따라) 이들 3 개의 삼각형을 포함하는 원시적 어레이는 yz- 평면에 평행 한 x= 2.5 (중앙값)를 통해 평면에 의해 분할된다. 결과 왼쪽 프리미티브 어레이는 3 개의 삼각형을 포함하고 있으며, 결과적으로 오른쪽 프리미티브 어레이는 3 개의 삼각형을 포함합니다.

왼쪽 및 오른쪽 프리미티브가있는 두 개의 결과 배열은 KD 노드의 왼쪽 및 오른쪽 하위 트리를 구성하는 데 사용됩니다 (프리미티브는 리프 노드에만 저장됩니다).

왼쪽 하위 트리의 경우 : 

If (the left primitives are empty) then the left subtree points to NULL
else if (the number of left primitives is smaller than the minimal number || the depth == 1) then the left subtree is a leaf node
else the left subtree is another tree.

create the left subtree with the left primitives along the axis (++axis % 3) with --depth as depth and the same minimal number.
.

오른쪽 하위 트리의 무의비.

알고리즘은 작동을 구현했지만 트리가별로 잘 분할되지 않기 때문에 매우 느립니다. 5500 개의 삼각형의 토끼를 광선 추적 할 때, 1 개의 삼각형의 많은 리프 노드가 많이 있으며 마지막 리프 노드에는 여전히 762 개의 삼각형이 들어 있습니다.

더 나은 분할 알고리즘이 있습니까 (내 것이 표면으로 변환 된 단일 점에 대한 KD 트리의 구현 일뿐 만 아니라) 트리의 균형을 유지합니까?

업데이트 : 간격의 배열을 절단점에 따라 두 개의 간격으로 분할 할 수있는 알고리즘 또는 휴리스틱을 검색했습니다. 왼쪽 배열은 절단점의 왼쪽에있는 간격과 절삭 점을 포함하는 간격을 포함합니다. 오른쪽 배열에 대한 불가능합니다. 두 배열 모두 동일한 간격이 있고 중복 간격의 수는 최대한 활용되어야합니다. 이 알고리즘은 복잡성이 아닐 수도 있습니다 (n ^ 2).

도움이 되었습니까?

해결책

중간 점의 계산이 올바르지 않습니다.X 좌표 2,3,8의 삼각형의 경우 중간 점은 2 + (8-2) / 2= 5이어야합니다. X 좌표 1,2,3의 삼각형은 중간 점 1 + (3-1) / 2가 있어야합니다.= 2. 이것은 불균형 한 잎을 설명 할 수 있습니다.

다른 팁

최적의 분할을 찾는 데 표면적 인 휴리스틱스 (SAH)를 사용해야합니다.

하위 트리가있는 광선 교차 확률은 해당 하위 트리의 경계 상자의 표면적에 비례합니다.

그러나 잎 - 하위 트리에 많은 삼각형이 포함되어있는 경우, 우리는 그들을 횡단해야한다는 것을 의미합니다.

그래서 SAH의 주요 아이디어는 다음과 같은 두 가지를 최소화하는 것입니다 : 하위 트리의 표면적 및 그 안에있는 다각형의 수.

여기에 이미지 설명

작은 2D 예제를 살펴보십시오.

여기에 이미지 설명

또한 SAH 사용 - KD-TREE의 건물 중에 종료 조건을 결정하는 데 도움이됩니다.

1) KD- 트리 건설의 각 단계에서 하위 트리가 분리되기 전에 현재 하위 트리의 SAH를 계산해야합니다 

SAH_initial = number_of_polygons * area_of_subtree
.

2) 현재 하위 트리의 가장 최적의 분할의 SAH를 찾아야하는 aftre 

SAH_optimal = min(S_left * N_left + S_right * N_right)
.

3) 비교 해야하는 Aftre : 

define some split_cost
...

if( SAH_optimal + split_cost < SAH_initial ) { 
   it would be optimal to split that subtree
} else {
   you don't have to split current subtree
}
.

여기에 다른 SAH에 대한 기사에 대한 referebces가 포함 된 stackoverflow 에 대한 답변이 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top