c++ - una - pozo de potencial finito pdf

¿Embalar triángulos arbitrarios en una caja finita?

Question

Necesito empaquetar triángulos en una caja lo más apretadamente posible, como parte de una optimización 3D (estoy rellenando segmentos con alfa de diferentes texturas en una única textura diferente, para usar con la clasificación en profundidad, para que las texturas no cambien con cada nuevo tri)

¿Hay un algoritmo para hacer esto? Los triángulos en sí pueden hacerse flexibles (transformables para formar ángulos rectos, lo que lo convierte efectivamente en un algoritmo de relleno de cajas), pero me gustaría evitar esto si es posible, ya que podría distorsionar el arte de la textura subyacente.

Answer 1

"ajustado como razonable" -> Algo que funciona es mejor que nada.

Estos fragmentos de código proporcionan una solución simple para rellenar formas (también triángulos) banda por banda en un rectángulo.

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;
    }
}