주어진 BSP 트리가 최적인지 여부를 어떻게 테스트합니까?

Question

BSP 트리를 만들고 싶은 삼각형의 다각형 수프가 있습니다. 내 현재 프로그램은 단순히 모든 삼각형이 소비 될 때까지 한 번에 하나씩 모델에서 임의의 삼각형을 삽입하여 BSP 트리를 구성하고 트리의 깊이와 폭을 점검하고 달성 한 최고의 점수 (가장 낮은 깊이, 가장 낮은 폭 ).

정의에 따르면, 가장 좋은 깊이는 log2 (n)입니다 (또는 공동 평면 삼각형이 그룹화되는 경우) 여기서 N은 내 모델의 삼각형 수이며 가장 좋은 폭은 N입니다 (의미 분할이 발생하지 않음). 그러나이 정점에 도달하지 못하는 삼각형의 특정 구성이 있습니다.

내 BSP 트리의 품질을 점검하기위한 효율적인 테스트가 있습니까? 구체적으로, 나는 내 프로그램이보다 최적의 구성을 찾아야한다는 것을 알 수있는 방법을 찾으려고 노력하고 있습니다.

Answer 1

최적의 트리의 구성은 NP- 완료 문제입니다. 주어진 트리가 최적인지 여부를 결정하는 것은 본질적으로 동일한 문제입니다.

이것으로부터 BSP FAQ:

문제는 분할 대 트리 밸런싱의 하나입니다. 이들은 상호 배타적 인 요구 사항입니다. 나무를 사용하는 방법에 따라 좋은 나무를 만들기위한 전략을 선택해야합니다.

Answer 2

당신이 좋은 나무에 기회가 될 때까지 무작위로 bsp 나무를 만드는 것은 실제로, 실제로 비효율적 일 것입니다.

분할 비행기로 사용하기 위해 무작위로 TRI를 선택하는 대신, 몇 가지 (아마도 그들 모두 또는 임의의 샘플링)를 시도하고 휴리스틱에 따라 하나를 선택하려고합니다. 휴리스틱은 일반적으로 (a) 그 결과 자식 노드의 균형을 잡는 방법과 (b) 얼마나 많은 트리스를 분할 할 것인지를 기반으로합니다.

트리스의 더 작거나 큰 샘플링을 후보 분할 계획으로 고려하여 성능과 품질을 트레이드 할 수 있습니다.

그러나 결국, 당신은 실제 데이터에 대해 완전히 최적의 트리를 얻기를 희망 할 수 없으므로 '충분히 좋은'것을 해결해야 할 수도 있습니다.

Answer 3

• 분할 비행기로 대부분의 비행기에 의해 분할 될 수있는 비행기를 선택하십시오. 분할 평면을 분할 할 수 없습니다.
• 뒤쪽과 같은 평면에 가까운 비행기를 선택하십시오.
• 너무 많은 분할을 유발하지 않는 비행기를 선택하십시오.
• 다른 많은 표면이있는 코플라나 비행기를 선택하십시오.

이 기준을 샘플링하고 스코어링 시스템을 제시하여 분할 비행기에 가장 적합한 선택 일 가능성이 가장 높은 시스템을 결정해야합니다. 예를 들어, 균형이 멀어 질수록 점수가 커집니다. 20 개의 분할을 유발하면 페널티는 -5 * 20 (예 :)입니다. 가장 좋은 점수를 선택하십시오. 모든 다각형을 샘플링 할 필요는 없으며 꽤 좋은 것을 검색하십시오.