It depends on many things - for instance here
are the boxes again.
You showed the boxes ABCD combining together the algorithm needed to identify 4 boxes to be merged would be horrendously complicated given the constraints.
A simpler algorithm would be to combine pairs of boxes so to get to your result would take 3 steps
A+C > AC
B+D > BD
AC + BD > ABCD
or
A+B > AB
C+D > CD
AB+CD > ABCD
One consequence of this is that you probably have little or no control over the order so you might get
A+B > AB
D+E > DE
no more to merge
So if we are to combine pairs-of-boxes we must consider
- how many boxes are there?
- are they moving?
- are new boxes being created as the animation runs?
- is the speed of calculation important (perhaps one off calculation)?
- are the boxes in a fixed volume of space i.e. are their x,y,z coordinates constrained?
The more boxes then the more merge tests are needed and if they are moving then the algorithm needs to be fast. For instance if there are just 10 boxes then each box has to be considered for merger with every other box (9) so there are 90 merge tests to perform.
So for
n boxes number of merge tests is
n(n-1) tests so 1000 boxes would need 999,000 tests
If
n is large and the answers to 4 and 5 are yes then you might consider some form of cell space partitioning e.g. an octree but that is a challenge to program in itself.
The shall-we-merge algorithm is interesting because not only must the boxes must be close enough, their orientation and dimensions must be similar. One approach I thought of was to create a temporary box that just encloses the two boxes being considered. If they are candidates for merging then the sum of their volumes will only be a little smaller than the volume of the enclosing box.
Here is a sketch with Box that demonstrates what I mean. Modify the mergeIndex at line 14 to change the accuracy. The closer to 1.0 the less likely they are to merge.
- Box boxA, boxB, mb;
- public void setup() {
- Box boxA = new Box(100, 200, 300, 40, 60, 80);
- Box boxB = new Box(144, 198, 302, 42, 58, 82);
- Box mb = Box.mergeBox(boxA, boxB);
- if (mb == null)
- println("No merge");
- else
- println(mb);
- }
- public static class Box {
- public static final float mergeIndex = 0.9;
- // The position of the box centre in 3D space
- private float x, y, z;
- // half the size of the box in the 3 axises and volume calculated in constructor
- private final float dx2, dy2, dz2;
- private final float volume;
- public static Box mergeBox(Box b0, Box b1) {
- // Calculate position and size of enclosing box
- float minX = PApplet.min(b0.x - b0.dx2, b1.x - b1.dx2);
- float maxX = PApplet.max(b0.x + b0.dx2, b1.x + b1.dx2);
- float minY = PApplet.min(b0.y - b0.dy2, b1.y - b1.dy2);
- float maxY = PApplet.max(b0.y + b0.dy2, b1.y + b1.dy2);
- float minZ = PApplet.min(b0.z - b0.dz2, b1.z - b1.dz2);
- float maxZ = PApplet.max(b0.z + b0.dz2, b1.z + b1.dz2);
- float x = (b0.x + b1.x)/2;
- float y = (b0.y + b1.y)/2;
- float z = (b0.z + b1.z)/2;
- Box mb = new Box(x, y, z, maxX-minX, maxY-minY, maxZ-minZ);
- // Calculate merge index
- float index = (b0.volume + b1.volume)/mb.volume;
- if (index > mergeIndex)
- return mb;
- else
- return null;
- }
- public Box(float x, float y, float z, float dx, float dy, float dz) {
- super();
- this.x = x;
- this.y = y;
- this.z = z;
- this.dx2 = dx/2;
- this.dy2 = dy/2;
- this.dz2 = dz/2;
- volume = dx * dy * dz;
- }
- public String toString() {
- String s = "[Pos= "+x+","+y+","+z+"] ";
- s += "[Size= "+(2*dx2)+","+(2*dy2)+","+(2*dz2)+"] ";
- return s;
- }
- }