Irregular packing for mobile game texture atlases

Abstract

For the efficient realtime rendering on a mobile device and for efficient delivery of a mobile game application, the texture atlases used in a mobile game need to packed as tightly as possible, but at the same time due to various practical limitations, the time required for the packing should be minimized. The packing of a texture atlas means positioning a set irregular 2D shapes in non-overlapping positions on a minimum number of atlases with limited item rotations and mirrorings being allowed. This task is well-known subclass of Cutting and Packing problems, and we investigate the various approaches for irregular packing in the literature and introduce two new placement algorithms based on the existing methods. We evaluate 22 combinations of packing algorithm variations for both the achieved packing density and the required compute time when packing production content derived from a medium-sized mobile game. We are able to show that for low compute time budgets, a placement method we introduced is able to outperform the traditional methods.

Mobiililaitteella tapahtuvaa suorituskykyistä reaaliaikaista grafiikkalaskentaa varten ja tehokasta mobiilisovellusten jakelua varten on tarpeellista pakata mobiilipelin käyttämät pintakarttakokoelmat mahdollisimman tiiviisti, mutta samalla on kuitenkin käytännön rajoituksista johtuen minimoitava pakkaamiseen käytetty aika. Tämä pintakarttakokoelmien pakkaaminen tarkoittaa kaksiulotteisten epäsäännöllisten kappaleiden asemointia niin, etteivät ne leikkaa toisiaan mahdollisimman pienelle määrälle pintakarttakokoelmia samalla sallien kappaleiden rajallisen kääntämisen ja peilaamisen. Tämä ongelma kuuluu tunnettuun leikkaus- ja pakkausongelmien alaluokkaan ja tässä diplomityössä tutkitaan monia kirjallisuudessa tunnettuja menetelmiä epäsäännöllisten kappaleiden pakkaamiseen ja esitellään kaksi uutta asemointimenetelmää, jotka pohjautuvat tunnettuihin menetelmiin. Työssä arvioidaan kokeellisesti 22 eri pakkausmenetelmäyhdistelmän saavuttamaa pakkaustiheyttä ja kuluttamaa laskenta-aikaa pakatessa keskikokoisen mobiilipelin tuotantomateriaalia. Kokeet osoittavat, että matalilla laskenta-aikabudjeteilla esittämämme asemointimenetelmä on parempi kuin perinteiset menetelmät.