절두체 컬링을위한 느슨한 옥트리 트리 - 약간의 조언이 필요합니다.

동적 객체에 대한 절두체 컬링을 내 엔진에 구현하고 있으며, "느슨한 옥트리"와 같이 읽을 수 있습니다. 불행히도 대부분의 출처는 아주 모호하며 실제로 얼마나 좋은지, O (1) 삽입 및 삭제를했지만 그 뒤에 어떤 논리도 설명하지 않은 사람들의 게시물이 많이 있습니다.절두체 컬링을위한 느슨한 옥트리 트리 - 약간의 조언이 필요합니다.

나는 octact가 더 커야하고 느슨한 요소는 2까지 올라갈 수 있다는 주된 원칙을 알고 있습니다. 이것은 객체가 크기에 따라 단일 노드에 삽입 될 수 있음을 의미합니다. 문제는 기사의 많은 부분이 2의 "k- 요소"(아마도 더 딱 맞도록)를 사용하지 않기 때문에 빠른 삽입/삭제를 잃을 수 있다는 것입니다. 대신 인접 구조를 유지하므로 주어진 깊이에서 모든 노드를 탐색하고 각 노드로 객체의 중심을 테스트 할 수 있습니다.

거친 컬링 테스트 만 필요하며 O (1) 삽입 시간을 갖고 싶습니다. 오브젝트를 삽입해야하는 깊이 (레벨)를 계산하는 공식을 계산했습니다. 그러나 개체의 크기와 위치에서 정확한 노드를 계산하는 공식을 논의하는 기사를 찾을 수 없습니다.

나는 알고리즘을 완전히 오해하고 가능한 것이없는 것을 찾고 있습니까? 누구든지 좋은 논문이나 기사를 가르쳐 줄 수 있다면 (내가 http://tulrich.com/geekstuff/을 읽었습니다) 그러면 좋을 것입니다.

PS 그것은 내가 어떤 도움

출처

2011-03-14 Downie

gamedev 포럼에서 답변을 얻었습니다. 내가 찾고 있던 방정식은 실제로 매우 간단했습니다.

int NodeIndex = depth * (bb.centre.x/sceneBB.width);

출처

2011-03-18 15:17:42 Downie

고마워. , 당신의 프로젝트와 함께 행운을 빕니다 – Bytemain

여기 또 다른 좋은 표정이 있습니다. (나는별로 이해하지 못하지만, 그것이 당신을 도울 수 있다고 생각했습니다.) : http://fgiesen.wordpress.com/2010/10/17/view-frustum - 컬링 – Bytemain

당신은 옥트리의 다차원 검색을 의미하지 않았다위한

감사 1D 배열에 저장된 선형 옥트리를 사용하고 있음을 언급 할 가치가있을 수 있습니다? 공간 채우기 곡선은 어떻습니까?

출처

2011-03-14 12:11:45 Bytemain

필자는 공간 채우기 곡선이 절두체 컬링에 공통적이라고 생각하지 않습니다 (정확히 왜 그런지는 모르지만 이유가 있다고 가정합니다). 실제로 주요 쟁점은 오브젝트의 중심점과 트리의 노드 사이의 관계를 찾는 것입니다 (깊이를 계산 한 후). 예를 들어, 완전한 트리로 표현되는 크기가 100x100x100 인 월드는 깊이 레벨 1 (크기 0은 루트 레벨 임)에서 크기가 60 인 객체를 갖습니다. 그 수준에서 모든 노드를 반복하지 않고 삽입 할 수있는 수준의 노드를 만드는 방법에 대해 들어 봤습니다 (복잡한 형제 관계를 유지해야합니다). – Downie

예, 나에게 투표하는 것을 잊어 버렸고, filling-curve는 colision을 탐지하는 데 사용되며 sfc-tree에 삽입하는 것은 재귀 적 알고리즘을 사용하지 않으면 매우 간단합니다. – Bytemain

내가 15 살이되기 전에는 분명히 투표 할 수 없습니다 (평판은 무엇입니까?, XP? lol). 나는 커브를 더 자세히 살펴볼 것이다. 나는 이미 가지고있는 코드를 사용하기를 바랐다. ( – Downie

절두체 컬링을위한 느슨한 옥트리 트리 - 약간의 조언이 필요합니다.

답변

관련 문제