Triangle Texture Packing Problem

Question

I'm trying to create a texture atlas where each triangle face is laid separately from each other (i.e. it is not typical mesh parameterization). In order to do this, I would have to pack the triangles into a 2D texture image. Can someone suggest a good algorithm to do this efficiently, both timely and spatially?

Answer 1

Note: this algorithm is my "empirical approach", I did no research paper on the topic, so chances are high that a better algorithm exists. Simply since there's no simple to retrieve algorithm it is easier for me to create my own. I assume the following stuff:

• Triangles can be rotate inside the atlas
• Triangles can't be morphed inside the atlas

You start by taking the triangle with the widest surface and by placing it in the middle of your atlas.

At each iteration you seek the next bigger triangle, and you attach it trying to match as much as possible one of its edges with unconnected edges on the atlas.

void AddTriangleToAtlas( Atlas atlas, Triangle triangle){

    var edges = atlas.Edges;
    Edge atlasEdge = null;
    Edge triangleEdge = null;
    float previousScore = 0;

    foreach(var edge in edges)
    {
        foreach(var triEdge in triangle.Edges)
        { 
             var match_score = edge.Lenght / triEdge .Lenght;
             if(match_score > previousScore && match_score<=1)
             {
                 if( atlas.SimulateAdd( triangle, triEdge , edge))
                 {
                     // Simulation went OK! (the triangle do not intersect other triangles)
                     atlasEdge = edge;
                     triangleEdge = triEdge;
                     previousScore = atch_score;
                 }
             }
        }
    }

    // adds the triangle to the atlas, rotating it to match edges,
    // but preserving size, surface and shape.
    // NOTE THIS UPDATE THE EDGES LIST OF THE ATLAS
    // (one edge is removed, 2 are added)
    atlas.Add( tringle, triEdge, edge);
}

Each triangle you add, open 2 edges, so the computational cost of this algorithm is not very cheap, however you can improve it greatly by some euristics:

• You can keep a list of edges sorted by Lenght, so you can search only the firsto 20/30 edges.
• You can check, whenever the placement simulation fails, if it is failed by a good margin (in example the triangle was intersecting 50% of its surface with pre-existing triangles, in that case you can remove the edge from the list to avoid it is re-used for a simulation).
• edges near texture limits are automatically discarded

Chances for optimization are many. The algorithm in itself is not very complicated, however you need the following stuff before starting to develop it:

• An algorithm to rotate triangles and to place it over another image
• Another algorithm to check intersection between triangles (actually it can be faster, especially for small triangles, to just rotate them and then see if you are going to write to a pixel that is already occupied or not).

By using the above euristics you could basically ends up in an algorithm that is O(n log n + p) where n is number of triangles to be placed and p is number of pixels (total surface).

Without euristics the algorithm is O(n^2 log n+p)