How do you fit the little cubes into a given volume and present it graphically on a web page?

Disclaimer: Ok, I know your question is not 100% answered and also the code it is veeery old (as can be done from old fashioned CVS comments) and I wouldn't write it like that today. It still works in Java 8, although I tested it. But in addition to solving the problem of information informatics, the problem of water flowing through a 3D matrix of cuboids from top to bottom, depending on how much the matrix (symbolizing some kind of Swiss cheese) "leaks", it also uses very simple 3D rendering via Java 3D. Thus, you need to install Java 3D and put the appropriate libraries in your classpath.

The 3D result looks something like this:

package vhs.bwinfo.cheese;

// $Id: Cuboid.java,v 1.1.2.1 2006/01/10 19:48:41 Robin Exp $

import javax.media.j3d.Appearance;
import javax.media.j3d.QuadArray;
import javax.media.j3d.Shape3D;
import javax.vecmath.Point3f;
import javax.vecmath.TexCoord2f;
import javax.vecmath.Vector3f;

public class Cuboid extends Shape3D {
  private static final float POS = +0.5f;
  private static final float NEG = -0.5f;
  private static final Point3f[] POINTS = new Point3f[] {
    new Point3f(NEG, NEG, NEG),
    new Point3f(POS, NEG, NEG),
    new Point3f(POS, NEG, POS),
    new Point3f(NEG, NEG, POS),
    new Point3f(NEG, POS, NEG),
    new Point3f(POS, POS, NEG),
    new Point3f(POS, POS, POS),
    new Point3f(NEG, POS, POS)
  };
  private static final TexCoord2f[] TEX_COORDS = new TexCoord2f[] {
    new TexCoord2f(0, 1),
    new TexCoord2f(1, 1),
    new TexCoord2f(1, 0),
    new TexCoord2f(0, 0)
  };
  private static final int VERTEX_FORMAT =
    QuadArray.COORDINATES |
      QuadArray.NORMALS |
      QuadArray.TEXTURE_COORDINATE_2;

  public Cuboid(float scaleX, float scaleY, float scaleZ) {
    Point3f[] points = new Point3f[8];
    for (int i = 0; i < 8; i++)
      points[i] = new Point3f(
        POINTS[i].x * scaleX,
        POINTS[i].y * scaleY,
        POINTS[i].z * scaleZ
      );

    Point3f[] vertices = {
      points[3], points[2], points[1], points[0],  // bottom
      points[4], points[5], points[6], points[7],  // top
      points[7], points[3], points[0], points[4],  // left
      points[6], points[5], points[1], points[2],  // right
      points[7], points[6], points[2], points[3],  // front
      points[5], points[4], points[0], points[1]    // back
    };

    QuadArray geometry = new QuadArray(24, VERTEX_FORMAT);
    geometry.setCoordinates(0, vertices);
    for (int i = 0; i < 24; i++)
      geometry.setTextureCoordinate(0, i, TEX_COORDS[i % 4]);

    Vector3f normal = new Vector3f();
    Vector3f v1 = new Vector3f();
    Vector3f v2 = new Vector3f();
    Point3f[] pts = new Point3f[4];
    for (int i = 0; i < 4; i++)
      pts[i] = new Point3f();

    for (int face = 0; face < 6; face++) {
      geometry.getCoordinates(face * 4, pts);
      v1.sub(pts[0], pts[2]);
      v2.sub(pts[1], pts[3]);
      normal.cross(v1, v2);
      normal.normalize();
      for (int i = 0; i < 4; i++)
        geometry.setNormal((face * 4 + i), normal);
    }
    setGeometry(geometry);
    setAppearance(new Appearance());
  }

  public Cuboid(float scaleFactor) {
    this(scaleFactor, scaleFactor, scaleFactor);
  }
}

      

        
        
        
      

    

package vhs.bwinfo.cheese;

// $Id: LeakyCheese.java,v 1.2.2.2 2006/01/10 15:37:14 Robin Exp $

import com.sun.j3d.utils.applet.JMainFrame;

import javax.swing.*;
import java.util.Random;

import static java.lang.System.out;

public class LeakyCheese {
  private int width = 20, height = 20, depth = 20;
  private int numClasses = 100, samplesPerClass = 100;
  private double pMin = 0, pMax = 1;
  private double pDiff = pMax - pMin;
  private double classSize = pDiff / numClasses;
  private int[] stats;

  enum CubeState {CHEESE, AIR, WATER}

  final private CubeState[][][] cheese;

  private static final Random RND = new Random();

  public LeakyCheese(
    int width, int height, int depth,
    int numClasses, int samplesPerClass,
    double pMin, double pMax
  ) {
    this.width = width;
    this.height = height;
    this.depth = depth;
    this.numClasses = numClasses;
    this.samplesPerClass = samplesPerClass;
    this.pMin = pMin;
    this.pMax = pMax;
    pDiff = pMax - pMin;
    classSize = pDiff / numClasses;
    cheese = new CubeState[width][height][depth];
  }

  public LeakyCheese(
    int width, int height, int depth,
    int numClasses, int samplesPerClass
  ) {
    this(width, height, depth, numClasses, samplesPerClass, 0, 1);
  }

  public LeakyCheese() {
    cheese = new CubeState[width][height][depth];
  }

  private boolean pourWater(int x, int y, int z) {
    if (x < 0 || x >= width || y < 0 || y >= height || z < 0 || z >= depth)
      return false;
    if (cheese[x][y][z] != CubeState.AIR)
      return false;
    cheese[x][y][z] = CubeState.WATER;
    boolean retVal = (y == 0);
    retVal = pourWater(x + 1, y, z) || retVal;
    retVal = pourWater(x - 1, y, z) || retVal;
    retVal = pourWater(x, y + 1, z) || retVal;
    retVal = pourWater(x, y - 1, z) || retVal;
    retVal = pourWater(x, y, z + 1) || retVal;
    retVal = pourWater(x, y, z - 1) || retVal;
    return retVal;
  }

  private boolean isLeaky(double p) {
    for (int x = 0; x < width; x++)
      for (int y = 0; y < height; y++)
        for (int z = 0; z < depth; z++)
          cheese[x][y][z] = (RND.nextDouble() < p)
            ? CubeState.CHEESE
            : CubeState.AIR;
    boolean retVal = false;
    for (int x = 0; x < width; x++)
      for (int z = 0; z < depth; z++)
        retVal = pourWater(x, height - 1, z) || retVal;
    return retVal;
  }

  private void generateStats() {
    if (stats != null)
      return;
    stats = new int[numClasses];
    for (int i = 0; i < numClasses; i++) {
      for (int j = 0; j < samplesPerClass; j++) {
        double p = pMin + classSize * (RND.nextDouble() + i);
        if (isLeaky(p))
          stats[i]++;
      }
    }
  }

  public void printStats() {
    generateStats();
    out.println(
      "p (cheese)        |  p (leaky)\n" +
        "------------------+-----------"
    );
    for (int i = 0; i < numClasses; i++) {
      out.println(
        String.format(
          "%1.5f..%1.5f  |  %1.5f",
          pMin + classSize * i,
          pMin + classSize * (i + 1),
          (double) stats[i] / samplesPerClass
        )
      );
    }
  }

  public static void main(String[] args) {
    //new LeakyCheese().printStats();
    //new LeakyCheese(40, 40, 40, 50, 100, 0.66, .71).printStats();

    LeakyCheese cheeseBlock = new LeakyCheese(5, 20, 5, 20, 100);
    //LeakyCheese cheeseBlock = new LeakyCheese(20, 20, 20, 20, 100);
    while (!cheeseBlock.isLeaky(0.65))
      ;
    out.println("*** required solution found - now rendering... ***");
    JMainFrame f = new JMainFrame(new LeakyCheeseGUI(cheeseBlock.cheese), 512, 512);
    f.setLocationRelativeTo(null);
    f.setExtendedState(JFrame.MAXIMIZED_BOTH);
  }
}

      

        
        
        
      

    

package vhs.bwinfo.cheese;

// $Id: LeakyCheeseGUI.java,v 1.1.2.1 2006/01/10 15:25:18 Robin Exp $

import com.sun.j3d.utils.applet.MainFrame;
import com.sun.j3d.utils.universe.SimpleUniverse;
import vhs.bwinfo.cheese.LeakyCheese.CubeState;

import javax.media.j3d.*;
import javax.vecmath.Point3d;
import javax.vecmath.Vector3f;
import java.applet.Applet;
import java.awt.*;
import java.util.Random;

public class LeakyCheeseGUI extends Applet {
  static final long serialVersionUID = -8194627556699837928L;

  public BranchGroup createSceneGraph(CubeState[][][] cheese) {
    // Create the root of the branch graph
    BranchGroup bgRoot = new BranchGroup();

    // Composite of two rotations around different axes. The resulting
    // TransformGroup is the parent of all our cheese cubes, because their
    // orientation is identical. They only differ in their translation
    // values and colours.
    Transform3D tRotate = new Transform3D();
    Transform3D tRotateTemp = new Transform3D();
    tRotate.rotX(Math.PI / 8.0d);
    tRotateTemp.rotY(Math.PI / -4.0d);
    tRotate.mul(tRotateTemp);
    TransformGroup tgRotate = new TransformGroup(tRotate);
    bgRoot.addChild(tgRotate);

    // Bounding sphere for rendering
    BoundingSphere bounds =
      new BoundingSphere(new Point3d(0.0, 0.0, 0.0), 100.0);

    // Set background colour
    // Note: Using Canvas3D.setBackground does not work, because it is an
    // AWT method. Java 3D, though, gets its background colour from its
    // background node (black, if not present).
    Background background = new Background(0.5f, 0.5f, 0.5f);
    background.setApplicationBounds(bounds);
    bgRoot.addChild(background);

    TransparencyAttributes transpAttr;

    // Little cheese cubes
    Appearance cheeseAppearance = new Appearance();
    transpAttr =
      new TransparencyAttributes(TransparencyAttributes.NICEST, 0.98f);
    cheeseAppearance.setTransparencyAttributes(transpAttr);
    cheeseAppearance.setColoringAttributes(
      new ColoringAttributes(1, 1, 0, ColoringAttributes.NICEST));
    PolygonAttributes pa = new PolygonAttributes();
    //pa.setPolygonMode(PolygonAttributes.POLYGON_LINE);
    pa.setCullFace(PolygonAttributes.CULL_NONE);
    cheeseAppearance.setPolygonAttributes(pa);

    // Little water cubes
    Appearance waterAppearance = new Appearance();
    transpAttr =
      new TransparencyAttributes(TransparencyAttributes.NICEST, 0.85f);
    waterAppearance.setTransparencyAttributes(transpAttr);
    waterAppearance.setColoringAttributes(
      new ColoringAttributes(0, 0, 1, ColoringAttributes.NICEST));
    pa = new PolygonAttributes();
    pa.setCullFace(PolygonAttributes.CULL_NONE);
    waterAppearance.setPolygonAttributes(pa);

    // Little air cubes
    Appearance airAppearance = new Appearance();
    transpAttr =
      new TransparencyAttributes(TransparencyAttributes.NICEST, 0.95f);
    airAppearance.setTransparencyAttributes(transpAttr);
    airAppearance.setColoringAttributes(
      new ColoringAttributes(1, 1, 1, ColoringAttributes.NICEST));
    pa = new PolygonAttributes();
    //pa.setPolygonMode(PolygonAttributes.POLYGON_LINE);
    pa.setCullFace(PolygonAttributes.CULL_NONE);
    airAppearance.setPolygonAttributes(pa);

    // Water-coloured (i.e. blue) wire frame around cheese block, if leaky
    Appearance waterWireFrameAppearance = new Appearance();
    waterWireFrameAppearance.setColoringAttributes(
      new ColoringAttributes(0, 0, 1, ColoringAttributes.NICEST));
    pa = new PolygonAttributes();
    pa.setPolygonMode(PolygonAttributes.POLYGON_LINE);
    pa.setCullFace(PolygonAttributes.CULL_NONE);
    waterWireFrameAppearance.setPolygonAttributes(pa);

    // Cheese-coloured (i.e. yellow) wire frame around cheese block, if not leaky
    Appearance cheeseWireFrameAppearance = new Appearance();
    cheeseWireFrameAppearance.setColoringAttributes(
      new ColoringAttributes(1, 1, 0, ColoringAttributes.NICEST));
    pa = new PolygonAttributes();
    pa.setPolygonMode(PolygonAttributes.POLYGON_LINE);
    pa.setCullFace(PolygonAttributes.CULL_NONE);
    cheeseWireFrameAppearance.setPolygonAttributes(pa);

    // Absolute offsets for the cheese block to fit into the viewing canvas
    final float xOffs = -0.8f;
    final float yOffs = -0.55f;
    final float zOffs = 0;

    // Create all those little cubes ;-)
    final int xSize = cheese.length;
    final int ySize = cheese[0].length;
    final int zSize = cheese[0][0].length;
    final int maxSize = Math.max(xSize, Math.max(ySize, zSize));
    final float xCenterOffs = 0.5f * (maxSize - xSize) / maxSize;
    final float yCenterOffs = 0.5f * (maxSize - ySize) / maxSize;
    final float zCenterOffs = -0.5f * (maxSize - zSize) / maxSize;
    boolean isLeaky = false;
    for (int x = 0; x < xSize; x++)
      for (int y = 0; y < ySize; y++)
        for (int z = 0; z < zSize; z++) {
          Transform3D tTranslate = new Transform3D();
          tTranslate.setTranslation(
            new Vector3f(
              xOffs + xCenterOffs + 1.0f * x / maxSize,
              yOffs + yCenterOffs + 1.0f * y / maxSize,
              zOffs + zCenterOffs - 1.0f * z / maxSize
            )
          );
          TransformGroup tgTranslate = new TransformGroup(tTranslate);
          tgRotate.addChild(tgTranslate);
          Cuboid cube = new Cuboid(1.0f / maxSize);
          switch (cheese[x][y][z]) {
            case CHEESE:
              cube.setAppearance(cheeseAppearance);
              break;
            case WATER:
              cube.setAppearance(waterAppearance);
              if (y == 0)
                isLeaky = true;
              break;
            case AIR:
              cube.setAppearance(airAppearance);
          }
          tgTranslate.addChild(cube);
        }

    // If cheese block is leaky, visualise it by drawing a water-coloured
    // (i.e. blue) wire frame around it. Otherwise use a cheese-coloured
    // (i.e. yellow) one.
    Transform3D tTranslate = new Transform3D();
    tTranslate.setTranslation(
      new Vector3f(
        xOffs + xCenterOffs + 0.5f * (xSize - 1) / maxSize,
        yOffs + yCenterOffs + 0.5f * (ySize - 1) / maxSize,
        zOffs + zCenterOffs - 0.5f * (zSize - 1) / maxSize
      )
    );
    TransformGroup tgTranslate = new TransformGroup(tTranslate);
    tgRotate.addChild(tgTranslate);
    Cuboid cuboid = new Cuboid(
      1.0f * xSize / maxSize,
      1.0f * ySize / maxSize,
      1.0f * zSize / maxSize
    );
    cuboid.setAppearance(isLeaky ? waterWireFrameAppearance : cheeseWireFrameAppearance);
    tgTranslate.addChild(cuboid);

    // Let Java 3D perform optimizations on this scene graph.
    bgRoot.compile();

    return bgRoot;
  }

  public LeakyCheeseGUI(CubeState[][][] cheese) {
    // Create a simple scene and attach it to the virtual universe
    GraphicsConfiguration graphCfg = SimpleUniverse.getPreferredConfiguration();
    Canvas3D canvas = new Canvas3D(graphCfg);
    setLayout(new BorderLayout());
    add(canvas, "Center");
    SimpleUniverse universe = new SimpleUniverse(canvas);

    // This will move the ViewPlatform back a bit so the objects
    // in the scene can be viewed.
    universe.getViewingPlatform().setNominalViewingTransform();
    universe.addBranchGraph(createSceneGraph(cheese));
  }

  public static void main(String[] args) {
    final Random RND = new Random(System.currentTimeMillis());
    CubeState[][][] testCheese = new CubeState[5][8][11];
    for (int x = 0; x < 5; x++)
      for (int y = 0; y < 8; y++)
        for (int z = 0; z < 11; z++)
          testCheese[x][y][z] = (RND.nextFloat() < 0.7f)
            ? CubeState.CHEESE
            : (RND.nextBoolean() ? CubeState.WATER : CubeState.AIR);
    // Applet can also run as a stand-alone application
    new MainFrame(new LeakyCheeseGUI(testCheese), 512, 512);
  }
}