BSP 트리를 구성하고자하는 삼각형의 다각형 스프가 있습니다. 현재 프로그램은 모든 삼각형이 소비 될 때까지 한 번에 하나씩 모델에서 임의의 삼각형을 삽입하여 BSP 트리를 구성한 다음 트리의 깊이와 너비를 확인하고 달성 한 최상의 점수를 기억합니다 (가장 낮은 깊이, 가장 낮은 너비).주어진 BSP 트리가 최적인지 어떻게 테스트 할 수 있습니까?
정의에 따르면, 가장 좋은 깊이는 log2 (n) (또는 동일 평면 삼각형을 그룹화 할 경우 더 작음)입니다. 여기서 n은 모델의 삼각형 수이며, 가장 좋은 너비는 n입니다 (분할 없음을 의미). 발생했습니다.). 그러나이 절정에 결코 도달하지 못할 삼각형의 특정 구성이 있습니다.
내 BSP 트리의 품질을 확인하는 효율적인 테스트가 있습니까? 특히, 내 프로그램이 더 최적의 구조를 찾는 것을 중단해야한다는 것을 알 수있는 방법을 찾으려고 노력하고 있습니다.
최적의 트리 구조는 NP 완전 문제입니다. 주어진 트리가 최적인지 결정하는 것은 본질적으로 같은 문제입니다. 이 BSP faq에서
:
문제는 트리 밸런싱 대 분할 중 하나입니다. 이들은 서로 독점 요구 사항입니다. 나무를 사용하는 방법에 따라 좋은 나무를 짓기위한 전략을 선택해야합니다.
BSP 트리를 무작위로 구축하면 좋은 것을 얻을 때까지 정말 비효율적입니다.
분할 평면으로 사용하기 위해 임의로 트라이를 선택하는 대신 여러 가지 (아마도 모두 또는 아마도 무작위 샘플링)를 시도하고 일부 경험적 방법에 따라 하나를 선택하려고합니다. 휴리스틱은 일반적으로 (a) 결과 노드 노드가 얼마나 균형을 이룰 것인가, (b) 몇 개의 트리 노드가 분할 될지에 기반합니다.
트라이앵글을 후보 분할면으로 더 작게 또는 더 크게 샘플링하여 성능과 품질을 절충 할 수 있습니다.
그러나 결국에는 실제 데이터에 대해 완전히 최적의 트리를 얻을 수 없으므로 '충분 함'으로 해결해야 할 수도 있습니다.
실제로, 단일 랜덤 BSP 트리라도 점 집합의 경우 점근 적으로 최적의 복잡성을 갖습니다. –
다른 표면의 많은 평면 인면을 선택하려고 쪼개는 비행기. 예를 들어, 더 멀리 떨어져있을수록 점수가 더 많이 상실됩니다. 20 개의 스플릿이 발생하면 페널티는 -5 * 20입니다 (예 :). 점수가 가장 좋은 것을 고르십시오. 당신은 모든 폴리곤을 샘플링 할 필요가 없습니다. 꽤 좋은 것을 찾으십시오.
최적의 BSP 트리를 작성하는 것은 NP 완료입니다. 그러나 "충분히 좋은"파티션 평면에 대한 부분 검색 및 경험적 방법을 사용하여 아주 좋은 것을 만들 수 있습니다. – doug65536
일반적으로 솔루션이 최적이고 최적 솔루션을 찾는 것이 동일한 복잡성 클래스에 속할 필요는 없습니다. BSP 트리가 최적인지 확인하는 것이 NP 완성인지 알 수 있습니까? – axel22