[알고리즘] Atlas : Shelf, Guillotine, Maxrects

[알고리즘] Atlas : Shelf, Guillotine, Maxrects

 

---

개요

1. 기록에 들어가기 전
2. UV
   • UV 배치, 편집은 아래와 같은 기준들이 존재한다.
   • UV 편집과 Atlas의 공통점과 차이점
3. Atlas algorithm
   • Shelf
   • Guillotine(단두대)
   • Maxrects
4. 정리 : 간략하게 책과 책장으로 예시로 들면 이렇다.
5. Atlas algorithm 관련 링크

---

기록에 들어가기 전

 게임의 UI 등에서 드로우콜을 줄이기 위하여 2D Sprite Atlas를 진행한다.

 Atlas를 어떤 방식으로 진행하느냐에 따라서 정해진 사이즈에 더 많이 넣을 수도, 적게 넣을 수도 있다.

 이 부분에 흥미가 생겨서 Atlas 알고리즘을 찾아보고 정리해 본다.  구현이 목적이 아니기 때문에, 코드도 없고, 프로그래머의 시각과 다른 정리가 될 것 같다.  동시에 이 글은 나도 알고리즘에 대한 이해를 위하여 정리하며 즉흥적으로 정리한 것이기 때문에, 문장이 어색하는 등의 우려가 있다.

 먼저 Atlas에 대해서 생각해 보면 Mesh의 UV를 배치하는 것이 떠올랐다.  우리는 UV를 배치하고, 편집할 때, 프로젝트, 사용 용도, 제작자의 기호 등 수많은 니즈에 의하여 배치가 달라진다.

UV 배치, 편집은 아래와 같은 기준들이 존재한다.

1. 중요도 : 가장 중요한 부분을 가장 크게 UV를 핀다.  예를 들어 캐릭터의 UV를 핀다면, 유저가 가장 가까이서 볼 수 있고, 가장 유심히 보는 '얼굴'을 가장 크게 핀다.  물론, 그렇지 않은 게임들도 존재한다.
2. 기능 : UV를 흘리는 애니메이션 등을 넣어야 한다면, 임의로 UV 사이즈를 변경하는 등의 작업을 진행한다.  그리고 어쩔 수 없이 UV를 상하, 좌우 끝점에 맞추는 경우도 존재한다.
3. 작업의 편의 : Texture 자체는 비효율적일 수 있지만, 빈 공간이 많이 생기더라도, Mesh의 면이 하늘을 바라보는 방향에 맞추어 배치하는 경우도 존재한다.  이 방법은 오래전 포토샵 등으로 만 맵핑을 진행할 때 자주 사용되었다.
4. 자동 : DCC 툴이 발전함에 있어서, 자동으로 언랩 UV를 해주면, 3D 객체(Mesh)를 대상으로 맵핑하기 때문에 UV가 끊어진 심 부분이나, UV가 로테이션 되어도 작업공정의 난이도가 올라가지 않게 되어 사용되고 있다.  단점으로 Texture의 사이즈가 작아 픽셀이 육안으로 잘 보일 정도라면, 심 부분에서 매끄럽지 못할 수 있다.

UV 편집과 Atlas의 공통점과 차이점

 공통점은 UV와 Atlas 모두 면을 구성하는 기본 트라이앵글에 그려진다는 것이다.  UI에 올리는 Sprite라고 해도, 사실 사각형 메쉬에 맵핑 한 것이라고 생각하면 좋을 것 같다.

 가장 큰 차이점은 전체 UV를 항상 균일한 사이즈로 진행하지 않는 경우가 존재한다는 것이다.  그렇다 보니, UV를 배치하며 크기를 키울 때도, 줄일 때도 존재한다.  Atlas를 진행할 때는 모두 정 사이즈로 '배치'만 해야 한다.  지금 컴퓨터가 아무리 발전하였고, AI 역시 발전하였더라도, 개발자의 의도대로 Atlas를 진행하는 Sprite들의 사이즈를 늘리고 줄일 경우, 문제가 생길 수 있으며, 디버깅하는 것도 쉽지 않다.

Atlas algorithm

 이제 그만 UV 작업에서 벗어나 Atlas 알고리즘을 알아보자.  세 가지 알고리즘에 대하여 알아보겠다.  이해는 하였지만, 조리 있게 설명하는 것이 쉽지 않은 듯하여, 순서에 맞춰 설명 후, 정리하는 방식으로 접근해 본다.

1. Shelf
2. Guillotine(단두대)
3. Maxrects

 

어떤 식으로 돌아가는지 알아보자.

1. Shelf algorithm

• 한 번에 하나씩 직사각형 모양의 물체를 선반에 배치하는 문제를 해결하는 알고리즘으로 '순서대로' 배치한다.
• Shelf algorithm은 크게 두 가지 유형으로 나뉜다.
  • First fit : 첫 번째 맞춤형 알고리즘은 선반에 놓을 공간이 있는 첫 번째 선반을 찾아 물체를 배치한다.
  • Next fit : 다음 맞춤형 알고리즘은 마지막으로 물체를 배치한 선반에 놓을 공간이 있는지 확인하고, 공간이 없으면 다음 선반을 찾아 물체를 배치한다.
• Shelf algorithm의 성능은 물체의 크기와 선반의 크기에 따라 달라진다.
• 물체의 크기가 다양하면 Fisrt fit, 비슷하면 Next fit이 더 효율적이다.
• Shelf algorithm을 열거하면 이렇다.
  1. Next fit : 특별한 기준 없이 순서대로 배치하여 비효율적이다.  한 줄의 선반에 적재되는 직사각형의 최대 크기에 맞춰 한 층이 형성되고, 한 층이 가득 차면 다음 층으로 넘어가 적재한다.
  2. Smaller height first : 높이가 작은 순서대로 정렬한다.  한 층(한 줄)에 비슷한 높이의 직사각형이 적재되기 때문에 층고에 있어서 Next fit보다 효율적이다.
  3. Lager height first : Smaller와 반대로 높이가 큰 순서대로 정렬한다.  마지막 층에서 공간이 많이 남게 된다.
  4. 참고한 페이지에서 3번을 수정하여 마지막 층의 높이를 늘려 직사각형을 쌓게 되는데, Sprite Atlas에서는 사용이 불가능하다.
  5. rotate 추가 : 기본적으로 3에 의하여 정렬 후, 나머지를 잘라서, roate 하는데, 이 역시 Sprite Atlas에 맞지 사용이 불가능하다.

  2. Guillotine algorithm

• Shelf algorithm은 좌우 한 줄, 한 층씩 나눈다면, Guillotine은 처음 적재되는 직사각형 다음으로 오는 두 번째 직사각형을 아래에 배치하며 최대 사이즈로 상하, 좌우의 열십자 형태로 층을 나누는 식으로 선반의 상하 높이 외에도, 좌우까지 채울 수 있게 만든다.
• 적재되는 첫 직사각형에 비해 두 번째 직사각형의 사이즈가 클 경우, 첫 직사각형의 옆자리에 두 번째 직사각형의 사이즈만큼 빈 공간이 생긴다.  이것은 각 선반의 공간(상하, 좌우 나눈...)

  3. Maxrects algorithm

• Guillotine algorithm에서 적재할 모든 직사각형을 확인하여 배치할 공간에 모두 들어가는지 확인한다.
• 적재할 직사각형을 일정한 규칙(이것은 개발자가 정하는 듯)에 의하여 직사각형 하나를 선택한다.
• 배치할 공간에 선택된 직사각형을 배치한다.
• 배치된 직사각형의 상하좌우 모두 층을 나눠 새로운 직사각형을 빈 공간에 배치하고, 남아 있는 층을 캐싱 한다.
• 캐싱 된 영역에 새로운 직사각형을 또 배치한다.  그리고 이것을 계속해서 반복한다...
• 결국 Guillotine과 비슷하지만, Maxrects는 층을 나눈 공간을 넘어갈 수 있어, 빈 공간이 최대한 없어진다.

알고리즘의 구조를 보면 Shelf > Guillotine > Maxrects 순으로 알고리즘으로 넘어갈 때마다, 공간을 나누는 효율을 증가시킨다.

정리 : 간략하게 책과 책장으로 예시로 들면 이렇다.

1. Shelf : 책장에 책을 배치하는데, 같은 열에서 가장 키가 큰 책의 사이즈에 맞춰 층을 정한다.
2. Guillotine : Shelf 책장에서 열에서 가장 큰 책의 길이가 아닌, 독립적으로 층을 만들어 작은 책에서 생기는 빈 공간을 최소화한다.
3. Maxrects : Guillotine의 문제점은 Shelf에서 다르게 선반(층)이 나뉘게 되면 다음으로 배치되는 책은 앞의 선반(층)의 연장선에서 벗어날 수 없는데, 이 알고리즘의 책장은 책을 배치했다가, 빼서 다른 책을 끼워 볼 수 있어 맞춘 형 선반(층)을 만들어 낼 수 있고, 그로 인하여 빈 공간이 없다.
   
   

Atlas algorithm 관련 링크

https://tibyte.kr/239
https://eatplayhate.me/2013/09/17/adventures-in-engine-construction-rectangle-packing/
https://www.youtube.com/watch?v=UgGdCF0einI