스파 스 octree를위한 효율적인 저장소?

Question

누구나 빠른 을 제안 할 수 있고, 스파 스 octree를 저장하고 액세스하는 효율적인 방법을 제안 할 수 있습니까?

바람직하게는 HLSL에서 쉽게 구현 될 수있는 것.(RayCasting / Voxel App)

이 경우 트리는 미리 계산 될 수 있으므로 주로 크기와 검색 시간에 관심이 있습니다.

업데이트

누구나이 작업을 수행하려는 누구에게나 효율적인 솔루션은 z-order 곡선 / 모튼 트리로 생성 된 선형 Octree로 노드를 저장할 수 있습니다.이렇게하면 내부 노드의 저장을 제거하지만 개별 Voxel에 대한 정보가 들어있는 두 번째 "데이터 텍스처"로 선형 트리 배열을 교차 참조해야 할 수도 있습니다.

Answer 1

HLSL에서는별로 경험이 없으므로이 문제가 귀하의 필요를 충족시킬 수 없습니다. 여기에 내 생각이 있습니다. 여기에 뭔가가 당신의 필요에 대한 제정신이 아니라면 알려주세요. 나는 토론하고 싶습니다. 아마도 나 자신을 배울 수 있습니다.

1. OCTREE의 모든 노드는 벡터 3로 존재할 수 있습니다. 여기서 (x, y, z) 구성 요소는 노드의 중심점을 나타냅니다. W 구성 요소는 플래그 필드로 사용할 수 있습니다. ㅏ. W-Flags 필드는 현재 노드를 따르는 octant 자식 노드를 나타낼 수 있습니다. 이것은 8 비트의 값이 필요합니다.
2. octree에 저장된 각 엔티티는 r, g, b가 경계 상자 치수 일 수 있고 WALL을 위해 W를 사용할 수있는 경계 상자로 저장할 수 있습니다.
3. 객체 목록이 뒤 따르는 특수 벡터를 정의합니다. 예를 들어 (w + z)가 몇 가지 마법 값 인 경우. 일부 func (x, y)는 다음과 같은 객체의 수가 될 수 있습니다. 또는 어떤 일이 무엇이든간에. ㅏ. 각 노드는 잠재적 으로이 특수 벡터가 뒤 따르면 노드에 저장된 객체가 있음을 나타냅니다. 다음 X 벡터는 모두 객체 식별자 또는 그런 것입니다. 비. 또는 메모리 내 오브젝트 목록을 지정하는 하나의 노드가 하나 가질 수 있습니다. 다시, 여기에 필요한 것을 확실하지 않거나 객체에 액세스하는 방법에 대한 제약 조건을 확실하지 않습니다.

그래서, 먼저 octree를 짓고 객체로 물건을 넣으십시오. 그런 다음 벡터를 메모리 버퍼로 출력하여 OCTREE를 걷습니다.

512x512 텍스처가 8 개의 물체가 들어있는 각각 812x512 텍스처를 완전히 포장 한 Octree 5 레벨 (32,768 노드)을 보유 할 수 있다고 생각합니다. 또는 각각 64 개의 객체가있는 완전히 포장 된 4 레벨 octree.

Answer 2

GPU에 초점을 맞춘 스파 스 octrees에 대한 훌륭한 기사가 있습니다 : 효율적인 스파 스 VoxelOCTREES - 분석, 확장 및 구현