대부분 비어 있는 큰 복셀 월드에서 주변 셀 조회와 지형 수정이 자주 일어납니다. 조밀 배열·해시 청크·옥트리를 메모리와 접근·갱신 비용으로 어떻게 비교하나요?

대부분 비어 있는 큰 복셀 월드를 조밀한 3차원 배열로 저장하면 좌표 계산과 이웃 접근은 빠르지만 빈 영역까지 메모리를 차지합니다. 실제로 존재하는 청크만 해시로 찾고 청크 내부를 연속 배열로 두면 희소성은 활용하면서 주변 셀 조회의 캐시 지역성을 얻을 수 있습니다. 옥트리는 균일한 빈 공간이나 같은 재질의 큰 영역을 상위 노드 하나로 묶어 넓은 범위를 건너뛸 수 있지만, 포인터·노드 탐색·분할·갱신 비용이 생깁니다. 따라서 접근 패턴에 맞는 희소 표현(access-pattern-aware sparse representation)을 선택해야 합니다.

세 구조의 비용

조밀 배열은 임의 셀을 O(1)로 계산하고 이웃 순회가 단순하지만 월드 크기와 해상도가 커질수록 빈 공간 비용이 바로 증가합니다. 해시 청크는 청크 좌표를 해시해 존재하는 지역을 찾고 내부는 연속 메모리에서 읽습니다. 충돌·경로처럼 근처 셀을 반복 조회하거나 작은 지역 수정이 잦을 때 유리할 수 있지만, 청크 경계마다 해시 조회가 필요하고 부재 청크·미로딩 청크·명시적 빈 청크를 구분해야 합니다. 옥트리는 넓고 균일한 공간 쿼리나 ray가 빈 영역을 건너뛰는 데 유리하지만, 경계가 복잡하거나 한 셀씩 자주 수정하면 노드 분할과 병합으로 갱신 비용이 커질 수 있습니다. 정적 지형과 동적 변경의 빈도가 다르면 같은 표현으로 묶지 않겠습니다. 정적 청크는 팔레트 압축·비트팩으로 저장하고, 동적 점유는 별도 오버레이에서 관리해 한 셀 수정 때문에 큰 블록 전체를 재인코딩하지 않게 할 수 있습니다. 압축 블록을 수정할 때는 새 버전을 만든 뒤 포인터를 원자적으로 교체하고, 이전 블록을 참조하는 raycast·경로 작업이 끝날 때까지 유지합니다. 청크 버전과 포맷 버전은 저장·스트리밍·파생 데이터의 호환성을 판단하는 메타데이터입니다.

측정과 혼합 구조

빈 공간 비율만 바꾼 벤치마크는 부족합니다. 이웃 6·26방향 순회, 임의 셀 조회, 작은 집중 수정, 넓은 영역 raycast, 경계 복잡도, 청크 로딩·언로딩, 여러 워커의 읽기·쓰기를 실제 분포로 재현하겠습니다. 저장량·메모리 상주량·p99 조회·수정 지연·단편화·스트리밍 지연을 따로 봅니다. 큰 균일 지역은 옥트리나 압축 블록으로, 활발한 지역은 해시 청크의 연속 배열로 두는 혼합 구조가 단일 자료구조보다 나을 수 있습니다. 데이터가 실제로 희소해도 조회가 무작위이고 모든 셀을 자주 읽으면 해시·포인터 비용이 조밀 배열의 이점보다 클 수 있습니다. 반대로 공간이 넓고 쿼리가 큰데 경계가 복잡하면 옥트리 최악 비용이 커집니다. 운영 패턴을 측정한 뒤 구조를 선택하고, 포맷 변경과 이전 버전 읽기까지 포함해 메모리-접근-갱신의 삼각 절충(memory-access-update trade-off)을 평가하겠습니다.

청크 해시에서 부재를 곧바로 빈 공간으로 반환하면 스트리밍과 물리 의미가 섞입니다. 무한한 빈 영역, 저장소에 아직 없는 영역, 로딩 중 청크, 로딩됐지만 빈 청크를 별도 상태로 두고 질의자가 정책을 적용해야 합니다. 해시 충돌과 디스크 캐시 미스를 같은 현상으로 세지 않도록 계측하겠습니다. 옥트리나 압축 블록을 사용해도 활발한 수정 지역에는 쓰기 증폭이 생깁니다. 작은 델타 오버레이를 두면 읽기 계층이 늘어나므로 오버레이 깊이와 병합 임계치를 p99 조회·수정 지연으로 정합니다. 포맷 변환 실패를 빈 청크로 위장하지 않겠습니다. 읽기 스냅샷이 오래 살아 있으면 이전 블록이 쌓입니다. 최대 수명은 취소 요청과 완료 확인, 새 작업 수락 제한을 위한 운영 상한이지 살아 있는 독자를 무시하고 강제 해제할 근거가 아닙니다. 참조가 끝나야 메모리를 회수합니다.