[📜일지] 복셀 옥트리

[익명(ppukku999)]

지난번에 만들던 청크 기반 LOD는 렉 안걸리게 잘 마무리 지어뒀지만, 옥트리 구조를 알게 된 이후로 손이 안감.

옥트리는 쿼드트리와 비슷하지만, 3D공간을 8개로 균일하게 나누는 자료구조임.

주로 이용되는 이유는 효율적으로 공간을 탐색할 수 있기 때문인걸로 앎.

특히 SVO(sparse voxel octree)는 공간을 8분할 하다가, 아무것도 없는 공간이 나오면 nullptr을 두기 때문에,

비어있는 공간(또는 동일한 블록만 있는 공간)에는 메모리가 전혀 들어가지 않을 뿐더러, 

월드를 순회할 때 한번에 많은 공간을 스킵할 수가 있기 때문에 꽤 많이 쓰이는 구조임.

레이 트레이싱에서 연산량을 어마어마하게 줄일 수 있는 구조라고 하는데, 난 여기까지는 모르겠음.

기본적으로 마인크래프트류 게임을 만드는데 옥트리는 전혀 쓰일 이유가 없음. 메모리가 부족한것도 아니고 공간을 순회하는 계산도 없으니깐.

구글에서 마인크래프트 제작 관련 글들 찾아보면 옥트리 관련해서 말이 많은데, 

사실 메모리 절약을 제외하면 아무 이득없이 구조만 복잡해져서 그냥 청크를 3차원 배열로 관리하거나 해쉬맵으로 처리하는게 훨씬 편함.

그런데 만약 LOD를 구현하고 싶다면, 이제 옥트리를 사용할 이유가 생김.

지금껏 lod에서 옥트리를 어떻게 이용하라는건지 모르겠고, 아무리 찾아도 아무도 안알려줘서 넘어갔는데, 갑자기 이해해버렸음.

우선 마인크래프트같은 게임에서 옥트리를 이용하는 방법에는 여러가지가 있음.

청크를 옥트리로 관리하고, 블록 데이터는 3차원 배열로 관리

청크를 옥트리로 관리하고, 청크 내의 블록 데이터 역시 옥트리로 관리

청크 구분 없이 하나의 거대한 옥트리로 관리

옥트리를 이용해서 빠른 속도로 lod를 자동으로 생성할거라면, 블록 데이터 역시 옥트리로 관리하면 됨.

그러지 않고, 수동으로 생성해서 쓸거면 굳이 블록데이터를 옥트리로 관리할 필요는 없음.

청크를 옥트리로 관리하는건, LOD에 너무나도 적합함.

특히, 옥트리 여러개로 월드를 관리하고, 옥트리 하나에 청크 2^n,2^n,2^n개씩 할당해놓는 구조.(나는 32x32x32)

플레이어와의 거리에 따라서 옥트리를 분할시켜서, 가까울수록 공간이 많이 분할되어있고, 멀리 있을수록 공간이 합쳐져있음.

공간을 분할시키는 방법은, 그냥 어떻게 처리할 지 생각만 해뒀는데, 최대 lod레벨을 5로 두면,

lod5 노드를 순회, 이 노드의 lod가 5레벨이여야 하는지, 아니면 그 밑으로 분할되어야 하는지 구함.

레벨5여야 한다면, 자식노드가 있을 때 자식노드 전부 제거.

분할되어야 한다면 자신이 단말노드였다면, 노드 밑에 lod4레벨 8개를 생성시켜줌.

그 다음은 방금 생성한 lod4레벨을 포함한 lod4 노드 전체를 순회, 이 노드가 lod4여야 하는지, 분할되어야 하는지 구함.

반복.

최대 lod부터 내려오기 때문에, lod4 8개가 lod5로 합쳐져야 하는지는 신경쓰지 않아도 됨. 

해당 상황은, lod5에서 lod4의 자식 8개를 전부 제거하면서 처리 됨.

옥트리의 단말노드만 활성화 메쉬로 둔다면 매우 효율적임.

청크마다 하나의 메쉬를 이용하는게 아니라, 

거리에 따라 최대 32x32x32개의 청크를 하나의 메쉬로 만들기 때문에, 로드거리가 길어져도 메쉬가 크게 늘지 않음.

lod레벨이 높을수록 옥트리에서 상위 노드라서 범위가 넓음.

디테일이 2x2x2배 떨어진다면, 메쉬의 크기가 2x2x2배 커짐. 

모든 메쉬의 메모리상 크기가 상당히 균일해지기 때문에, 안정적임.

lod레벨이 0이면, 32x32x32범위를 1x1x1블록마다 계산하고,

lod레벨이 1이면, 64x64x64범위를 2x2x2블록마다 계산함.

옥트리로 청크를 관리할 때, 월드가 무한하면 어떻게 처리해야 하는지에 대해 정보가 별로 없어서 고민해봤음.

내가 할 방식처럼, 많은 청크를 합쳐둔 옥트리를 기존 청크 관리하듯 관리하는 방법이 있고, 아니면 옥트리를 조정시켜주는 방법도 있음.

플레이어가 옥트리의 범위를 벗어나면, 해당 방향으로 루트노드 위에 노드를 하나 둬서 옥트리를 확장시키고, 

플레이어가 적당한 범위에 들어오면, 다시 루트노드를 없애서 축소시키는 방법.

옥트리로 공간을 나눴기 때문에, 모든 공간을 순회하면서 lod수준을 업데이트해도 크게 무리가 가지 않음.

또한 필요한 메모리가 줄어들기 때문에, 거리를 더욱 늘리기가 쉬워짐.

여기서 조금 더 응용한다면, 플레이어 주변만 lod수준을 0으로 맞추는게 아니라, 

특정 건물 또는 npc가 존재하는곳은 강제로 lod수준을 낮춰버려서 멀리에서도 제대로 렌더링 되게 할 수 있음.

참고로 이건 블록형 복셀에만 적용되는게 아님.

내가 고려중인게 있다면 dual contouring 알고리즘.

이 방법은 부드러운 지형을 표현하면서 블록 역시 표현이 가능함. 대신 어렵다고 소문남.

여기 설명 잘해둠.

https://web.archive.org/web/20160305101254/https://upvoid.com/devblog/2013/05/terrain-engine-part-1-dual-contouring/

만들 게임의 설계를 하는 중임.

한학기 휴학하고 공익갈거라 시간 많을 듯. 꾸준히 해야지

꾸준히 오랫동안 하면 아무리 어려워도 어떻게든 할 수 있지 않을까

올해 진짜 열심히 산것 같음. 일년 중 최소 9~10개월동안 쉬지않고 프로그래밍만 한 듯.

다만 뒤로 갈수록 툴을 다루기보단 하루종일 비주얼 스튜디오 안에서만 끙끙거렸던게 살짝 걸림.