35

I need to pack triangles into a box as tightly as reasonable, as part of a 3D optimization (I'm stuffing alpha-using segments of different textures into a single different texture, for use with depth-sorting, so textures don't switch with every new tri)

Is there an algorithm for doing this? The triangles themselves can be made to be plyable (transformable to be right angles, effectively making this a box-stuffing algorithm instead), but I would like to avoid this if possible, as it would distort the underlying texture art.

15
  • 1
    Intriguing problem. Are reflections and arbitrary rotations of the triangles allowed? Jul 14, 2014 at 11:57
  • 1
    Hmm, there are 32 (not 16) ways of packing 2 triangles A and B together that avoid extending 1 of the 4 edges of A's bounding box: 4 90-degree rotations of B w.r.t. A, and the following 8 "layouts" for each of these: A to the {left, right} of B with their {top, bottom}most points aligned; A {above, below} B with their {left, right}most points aligned. But I don't think it's sufficient to consider only these unfortunately -- it might be possible to get a smaller overall bounding box by placing B in some "intermediate" position... :( Jul 14, 2014 at 20:45
  • 1
    I'm afraid I don't have a "full" answer that I'm planning to give, but OTOH please ignore the close votes -- they accrue on almost every question these days, perhaps because they can only be voted "up". This is IMHO a very interesting question and would be best left open :) Jul 15, 2014 at 9:58
  • 10
    I am pretty sure this problem is NP-Complete. Doing a quick search I found a 5 page paper that describes a heuristic algorithm for packing triangles into a square, but I don't think you will be able to find a perfect polynomial time solution.
    – daxvena
    Nov 21, 2015 at 3:03
  • 1
    Just for clarification, is box in this context 3-dimensional (cuboid) or 2-dimensional (square/rectangle)? I'm used to seeing heuristics for this in 2D to pack triangles or quads into a texture coordinate UV space, but not one that operates in 3 dimensions.
    – user4842163
    Nov 24, 2015 at 16:54

1 Answer 1

1

"tight as reasonable" -> Something working is better than nothing.

These code fragments provide a simple solution to stuff shapes (also triangles) band by band into a rectangle.

public abstract class Shape {
    protected Point offset = new Point();
    public abstract int getHeight();
    public abstract int getWidth();
}

public class Triangle extends Shape {
    // all points are relative to offset (from Shape)
    Point top = new Point(); // top.y is always 0, left.y >= 0 right.y >= 0 
    Point left = new Point(); // left.x < right.x
    Point right = new Point();

    public int getHeight() {
        return left.y >= right.y ? left.y : right.y;
    }

    public int getWidth() {
        int xmin = left.x <= top.x ? left.x : top.x;
        int xmax = right.x >= top.x ? right.x : top.x;
        return xmax - xmin;
    }
}

public class StuffRectangle extends Shape {
    private Point ww = new Point();

    private ArrayList<Shape> maintained = new ArrayList<Shape>();
    private int insx;
    private int insy;
    private int maxy;

    public int getHeight() {
        return ww.y;
    }

    public int getWidth() {
        return ww.x;
    }

    public void clear() {
        insx = 0;
        insy = 0;
        maxy = 0;
        maintained.clear();
    }

    /**
     * Fill the rectangle band by band.
     * 
     * The inserted shapes are removed from the provided shape collection.
     * 
     * @param shapes
     *            the shapes to insert
     * @return the count of inserted shapes.
     */
    public int stuff(Collection<Shape> shapes) {
        int inserted = 0;

        for (;;) {
            int insertedInPass = 0;
            for (Iterator<Shape> i = shapes.iterator(); i.hasNext();) {
                Shape shape = i.next();

                // does the shape fit into current band?
                int sx = shape.getWidth();
                if (insx + sx > getWidth())
                    continue;
                int sy = shape.getHeight();
                if (insy + sy > getHeight())
                    continue;

                // does fit
                ++insertedInPass;

                // remove from shapes
                i.remove();

                // add to maintained and adjust offset
                maintained.add(shape);
                shape.offset.x = insx;
                shape.offset.y = insy;

                insx += sx;
                if (sy > maxy)
                    maxy = sy;

            }
            inserted += insertedInPass;
            if (shapes.isEmpty())
                break;
            // nothing fits current band - try a new band
            if (insertedInPass == 0) {
                // already a new band - does not fit at all
                if (insx == 0)
                    break;

                // start new band
                insx = 0;
                insy += maxy;
                maxy = 0;
                continue;
            }
        }

        return inserted;
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.