데이터 구조 오버 헤드 및 기타 논리적 / 수학적 요인으로 인해 모든 압축 방법과 같은 모든 분할 방법이 결국 더 이상의 압축이 발생하지 않는 곳에서 팬 아웃되지만 사용하는 공간 분할 방법에 따라 다릅니다. 옥트리에서 예제를 찾을 수 있습니다. 옥트리의 각 노드에 대해 의미있는 순회를 가능하게하려면 포인터를 부모 및 / 또는 자식 (데이터 구조 아키텍처에 대한 방법에 따라)에 유지해야합니다. 모든 트리 구조에는 n 개의 자식이 포함될 수 있습니다. 1 : n의 비율이 낮을수록 공간을보다 효율적으로 사용할 수 있으며 결과적으로 동일한 수의 리프 복셀을 포함하는 더 많은 조상 노드가 있어야하기 때문에 트리 트래버 설에서 오버 헤드가 더 커집니다 (약 510 조) 표면적을 나타내는 이들 중).

귀하의 인스턴스에서 주요 문제는 스토리지 비용과 전체 행성 (또는 그 일부)을 적절한 거리에서 렌더링한다는 점을 고려할 때 옥트리보다 권장하는 데이터 구조가 없습니다. 밉 매핑은 필수입니다. 가장 가까운 2의 더 높은 출력에서 ​​직경 12.8 백만 미터는 2 ^ 24 = 16.8 백만입니다. 순회 할 24 octree 레벨은 엄청난 양의 분기에 해당하며 GPU 및 CPU 모두 매우 비용이 많이 듭니다. 그러나 올바른 일을한다면 한 번에 몇 단계 만 통과하면됩니다. 그러나 필요한 공간의 양을 고려할 때 대안은 거의 없으며 그 사이에 있습니다 (아래 참조).

octrees의 밉 매핑 기능은 여러분이 기술 한 것과 같은 대량의 작업을위한 매우 강력한 도구입니다. 알려진 다른 모든 세분화 방법 (KD 트리 제외)과 달리 octree는 레벨 당 세분화를 최소로 유지합니다. 즉, 밉맵 레벨 간의 시각적 차이와 물리적 차이도 최소로 유지됩니다. 나무 아래로.

반면에 계층 적 그리드 순회가 최소로 유지되는 세계를 생성하려면 속도를 높이기 위해 공간을 절충해야합니다.

이상적인 1 : n 비율에 대해 말하면,이 점에서 kd-tree보다 더 미세한 구조는 없습니다. octree가 각 축에 대해 2로 나뉘어 2 ^ 3 = 8 개별 자식 셀이되는 경우 kd 트리는 세분화 수준 당 정확히 한 번 분할됩니다. 이에 대한 문제는 분할 할 하이퍼 플레인을 선택해야하며이 하이퍼 플레인은 3 개의 축 중 하나를 선택할 수 있다는 것입니다. 공간 측면에서는 최적이지만 동적 포털 유형 구조를 기록해야하므로 3D 탐색 (예 : 물리 또는 렌더링에 옥트리를 사용할 때의 기본 op) 인 3D 탐색을 훨씬 더 어렵게 만듭니다. 인터페이스 개별 kd- 트리 노드 사이의 .

RLE은 압축에 대한 또 다른 접근 방법이지만 RLE 압축은 1 차원이기 때문에 이와 같은 문제 (작업 기반이 구형 인 경우)에는 적용하기가 더 어렵습니다. 작동하는 축을 선택해야합니다. 행성에서는 극축을 선택할 수 있지만, 단일 축을 선택하면 최적이 아닌 각도에서 작동 할 때 렌더링 및 물리학에 대한 횡단 문제가 발생합니다. 물론 스토리지 비용을 3 배로 늘리거나 추가 최적화를 위해 6 축 (-x, + x, -y, + y, -z, + z)으로 RLE를 동시에 실행할 수도 있습니다.

따라서 귀하의 질문에 대답하십시오 (또는 아닙니다!)

어떤 종류의 하드웨어에 직접 대답하지는 않지만 octree 관점에서 보는 것이 시작 된다고 생각 합니다. 가능한 어떤 종류의 하드웨어에 당신이 실제로 무엇의 아이디어를 제공 할 수 있습니다. 이 경로를 따라가는 것이 좋습니다. 정말로 알고 싶다면 간단한 스파 스 옥트리를 구현하는 것이 가장 쉬울 수 있습니다.(참조에 Laine의 논문 참조) 구형 복셀 껍질을 그 안에 넣고 결과 공간 사용량이 어떻게되는지 확인하십시오. 거기에서 단계. 시스템 메모리가 나오기 전에 얼마나 멀리 갈 수 있는지보십시오. 시각화를 원하지 않는 한 렌더러를 작성할 필요가 없습니다. 또한 이것은 CPU에서 가장 잘 수행된다는 것을 명심하십시오 .GPU는 일반적 으로이 규모의 문제를 처리 할 메모리 용량이 없습니다. 이것이 인텔이 대규모 병렬 프로세서로 전환하려는 이유 중 하나입니다. GPGPU의 이점은 이런 종류의 시스템에 더 유리한 시스템 버스 병목 현상없이 훨씬 더 넓은 메모리 공간에 적용될 수 있습니다. 여기 또는 mathematics.stackexchange.com에 다른 것이있을 수 있습니다.

당신의 무한한 시거리 요구의 관점에서, 그러나 문제는 항상 “어떤 거리에서 얼마나 상세하게”에 달려 있습니다. 무한한 디테일을 렌더링하려면 무한한 리소스가 필요합니다. 그것이 바로 씬마다 가변적 인 밉 매핑이 작용하는 곳입니다. 또한 모든 데이터 구조는 공간에 대한 속도의 상충 관계를 구현하거나 그 반대로도 구현한다는 점을 명심하십시오. 같은 양의 엔지니어링 노력으로 더 큰 세상을 원한다면 렌더링이 적거나 느려집니다.

답변