[📜일지] 알고리즘 갈아엎음, 최적화

[익명(ppukku999)]

2일동안 하루종일 함.

최적화 하겠다고 코드 뒤집어 엎었는데 엄청난 차이는 없었지만, 결과적으론 만족함.

원래 복셀이란게, 자세히 표현하기를 원한다면, 그리드를 더 정밀하게 만들어야 함.

정말 운이 좋게도, 내가 선택한 알고리즘은 옥트리 구조로 짜여있기만 하면, 아무리 불규칙적이라도 메쉬를 만들어낼 수가 있음.

그래서 내가 작은 도형을 설치하면, 해당 위치의 노드를 적당히 분할시켜주고 있음.

메쉬를 만드는 과정이 뭐냐면,

1. 청크 노드 밑의 모든 데이터 노드에 데이터를 계산해서 채워넣는다.

2. 지형의 표면이 지나는 모서리 주변의 4개의 노드를 이어서 쿼드를 만들어준다.

인데, 1번에서 데이터를 채워넣는게 까다로웠음.

어떤 데이터가 필요하냐면, 각 칸마다 8개의 꼭짓점에서 지형의 안인지 밖인지를 구한 후,12개의 모서리를 체크해서,

만약 모서리의 한쪽이 지형 내부이고 반대쪽이 외부이면, 지형이 해당 모서리를 지나는 정확한 지점과, 그 위치에서의 노말값이 필요함.

청크노드 밑에 데이터노드가 기본으로 32x32x32해서 32768개 존재하는데, 여기서 32768 x 8번 값을 체크하고싶지 않았음.

사실 모서리는 그리드 위의 칸끼리 공유되기 때문에, 각 칸마다 3개의 모서리를 체크해주면 청크 내의 대부분의 모서리를 확인할 수가 있음.

그래서 32768개의 노드를 순회하면서 12개의 모서리를 체크해서 데이터를 채워넣어주는게 아니라, 32x32x32 그리드 위에있는 모서리만 순회하면서 데이터를 채워넣어주고 있음.

그런데 여기서 모서리들을 단순히 순회하면서 계산하면 각 꼭짓점의 값을 여러번 계산하게 됨.

그래서 최종적으로는, 32x32x32그리드 위의 모든 꼭짓점에서의 값을 미리 구한 후, 그리드 위의 모서리 중 지형이 지나는 모서리를 찾아서,

해당 모서리를 둘러싼 4개의 옥트리 노드를 생성하고 그 노드들 안에 모서리 정보를 채워넣어주는 방식으로 처리했음.

그런데 이제 작은 도형을 설치하면 옥트리 노드(그리드 한칸)가 최대 2번, 4x4x4크기로 분할되는 기능을 넣어야 하는데, 이러면 32x32x32의 균등한 그리드가 아니게 됨.

이전에는 또다른 옥트리를 생성해서 문제를 처리했음.

이런식으로 8개의 노드가 각각 2번 분할되어야 한다고 설정되어있으면, 이 8개를 합쳐서 하나로 보고 3번 분할시키는 방식으로 파편처럼 나뉜 노드들을 묶어줬음.

묶인 노드 내에서는 아까 위에서 데이터를 채워넣는 함수를 그대로 이용하면 되서 편했음.

구현방법은

또다른 옥트리를 생성해서 옥트리에 추가로 나뉠 노드들을 넣어주면, 옥트리 위에서 노드의 자식 8개가 같은 횟수로 나뉘면 합쳐지는 방식으로 정리해줌.

내가 왜 이 방식으로 처리했는지 모르겠음. 이 방식으로는 무조건 정육면체, 그것도 옥트리 구조에 속하는 위치와 크기의 정육면체로만 합쳐주기 때문에,

심하면 청크노드를 천개 이상의 범위로 나눔. 그래서 계속 고쳐야지 생각하다가 오늘 드디어 이 알고리즘을 뜯어 고쳤음.

마인크래프트 모작을 해본사람은 알수도 있는데 Greedy meshing이란게 있음.

메쉬를 위해 면을 만들때, 처음에 x방향으로 계속 체크해서 x방향에 면이 있다면 해당 면을 합치고, 다음은 y방향으로 체크해서 합쳐나감.

최대한 많은 면을 뭉쳐서 하나의 메쉬로 만드는 알고리즘임.

같은 원리로, 이번엔 x,y,z방향 으로 최대한 조건을 만족하는 그리드 셀들을 합쳐줘서 청크노드를 여러개의 직육면체 범위로 나눠줬음.

근데 이러니깐 이전의 함수들을 전부 뜯어고쳐야하는 문제가 생김.

전의 함수들은, 옥트리 노드와 데이터노드크기를 받아서, 옥트리 노드를 데이터노드크기의 그리드로 나눈다음, 그 위에서 데이터를 채워넣어주는 구조였음.

이러면 정육면체의 범위만 처리할 수 있어서, 직육면체의 범위는 처리가 안됨.

각 함수가 청크노드를 받고, 직육면체 범위 시작 인덱스, 종료 인덱스, 잘게 나뉘는 횟수를 받도록 해서 내부적으로 직육면체 범위에 접근이 가능하도록 만들어줬음.

그리고 그 위에서 나뉘는 횟수만큼 범위를 나눠준 후 모서리들을 순회해서 직육면체 범위 내의 노드들에 한해 데이터를 채워넣어줌.

옥트리 구조로 나눌때 800개의 범위로 나뉘던게 100개정도로 줄어들었는데, 실행시간에는 별반 차이가 없더라.

나뉜 범위의 수가 적을수록, 처리량이 줄어드는건 사실임. 극단적인 경우로 32x32x32그리드 위의 모서리를 순회하냐, 또는 32768개의 셀에서 12개의 모서리를 체크하냐를 생각해보면 됨.

그런데, 나뉜 개수가 8배 줄었다고 시간이 8배로 줄어드는게 아니라, 줄어든 처리량의 비율대로 늘어남.

지금 체크한대로는 아마 잘해봐야 10%단축된것 같음. 근데 이건 나뉘는게 그렇게까지 많지 않은 경우이고, 아마 청크내에 분할되어야 하는 노드들이 많아질수록 단축량이 늘어날 듯.

이 외에도 자잘한 최적화들 진짜 많이 했음.

알고리즘을 수정하면서 코드도 깔끔해졌는데, 이건 확실히 만족함.

또 하나 문제가 있었음

과거에 이럴때마다 엄청 고생했던 기억에 패닉와서 오늘안에 어떻게든 고쳐야지 하고 디버깅했음.

삼각형을 이루는 꼭짓점 사이의 거리를 체크했을때, 거리가 노드 사이즈보다 큰 경우가 하나도 없었는데, 정작 메쉬를 만들면 저런 삼각형들이 만들어지더라.

알고보니 기본 세팅에서는 하나의 메쉬 위에 버텍스 65535개까지만 허용되는데 과하게 분할하다보니 넘어가는거였음. Mesh.indexFormat을 바꿔주고 해결함.

무작정 2번 분할하는건 너무 과한거 같아서, 1번 분할시켰더니 2만개정도 나옴.

좀 신경써서 분할 횟수를 적당히 자동으로 정하도록 만들어야겠음.

또 메모리 문제가 있는데, 이건 다음에 확인하려고.

내 추측으로는 청크별로 버텍스 개수 차이가 많이 나고, 풀링으로 돌려쓰다보니 버텍스 등을 담아두는 리스트의 용량이 상향평준화가 되는것 같음.

수정정보가 있는 청크는 전용 풀을 이용하거나, 아니면

리스트가 아니라 엄청나게 큰 길이의 배열을 할당해서 그 안에서 청크별로 직접 범위를 할당해줘도 될 것 같음.

청크 이동시 lod변화가 일어나는 청크 개수가 400개인데, 진짜 많은 상황임. 보통 80개정도 나오는데, Lod로 나뉘다보니 가끔 저렇게 많이 업데이트가 일어남.

Lod계산과 Mesh생성은 코루틴에서 계속 yield return null을 해줘서 딜레이를 주기 때문에 시간이 늘어난거고,

Updating이 무거운 작업임.

현재 스레드에 그냥 무작위로 작업을 할당해줘서 스레드 일부가 도는 동안 나머지는 놀고있는데, 그거 해결하면 조금은 빨라질 듯.

내 목표는, 일반적인 플레이상황에서, 그러니깐 정말 일부로 블록을 잘게 흐뜨려놓지 않는 경우에, 2000ms를 넘기지 않는게 목표임. 분할이 되면 될수록 소요시간이 진짜 많이 늘어남.

2회 분할시 데이터량이 64배로 늘어나는게 너무 큼.

청크 크기가 32m고 이동속도가 빨라봤자 8m/s로 둘 예정이니 2000ms정도면 여유로울 듯. Lod가 적용되서 시야거리가 넓다보니 조금 지연되도 별로 티 안나더라.

저번에 산 에셋 적용하기 전에 머테리얼에 적용되어있는 색깔만 훔쳐왔는데 진짜 이쁜듯.

[익명(125.248)]

글 하나하나 배울게 많네 ㄳㄳ

[익명(1.234)]

이해도 안간다