Heuristic approach to automatic texture atlas composition
We present a variant of 2D containment problem, to create a texture atlas. The texture atlas is an efficient color representation for a given VRML scene. It contains a composition of several texture images stored in one file. The containment problem is a way to place a set of shapes into another shape without overlapping. In our case we place a set of texture images of arbitrary shape into a rectangle, trying to minimize the rectangular area. We use heuristic search algorithm based on Minkowski operators to solve 2D translational containment problem. This particular approach is called packing problem and is known to be NP-complete. We present its practical implementation and show results measured on several test scenes.