Partitioning of an AABB

Question

I have a problem where I need to divide an AABB into a number of small AABBs. I need to find the minimum and maximum points in each of the smaller AABB.

If we take this cuboid as an example, we can see that is divided into 64 smaller cuboids. I need to calculate the minimum and maximum points of all of these smaller cuboids, where the number of cuboids (64) can be specified by the end user.

I have made a basic attempt with the following code:

// Half the length of each side of the AABB.
float h = side * 0.5f;

// The length of each side of the inner AABBs.
float l = side / NUMBER_OF_PARTITIONS;

// Calculate the minimum point on the parent AABB.
Vector3 minPointAABB(
    origin.getX() - h,
    origin.getY() - h,
    origin.getZ() - h
);

// Calculate all inner AABBs which completely fill the parent AABB.
for (int i = 0; i < NUMBER_OF_PARTITIONS; i++)
{
    // This is not correct! Given a parent AABB of min (-10, 0, 0) and max (0, 10, 10) I need to
    // calculate the following positions as minimum points of InnerAABB (with 8 inner AABBs).
    // (-10, 0, 0), (-5, 0, 0), (-10, 5, 0), (-5, 5, 0), (-10, 0, 5), (-5, 0, 5), 
    // (-10, 5, 5), (-5, 5, 5)

    Vector3 minInnerAABB(
        minPointAABB.getX() + i * l,
        minPointAABB.getY() + i * l,
        minPointAABB.getZ() + i * l
    );

    // We can calculate the maximum point of the AABB from the minimum point 
    // by the summuation of each coordinate in the minimum point with the length of each side.
    Vector3 maxInnerAABB(
        minInnerAABB.getX() + l,
        minInnerAABB.getY() + l,
        minInnerAABB.getZ() + l
    );

    // Add the inner AABB points to a container for later use.
}

Many thanks!

Answer 1

I assume that your problem is that you don't get enough sub-boxes. The number of partitions refers to partitions per dimension, right? So 2 partitions yield 8 sub-boxes, 3 partitions yield 27 sub-boxes and so on.

Then you must have three nested loops, one for each dimension:

for (int k = 0; k < NUMBER_OF_PARTITIONS; k++)
    for (int j = 0; j < NUMBER_OF_PARTITIONS; j++)
        for (int i = 0; i < NUMBER_OF_PARTITIONS; i++)
        {
            Vector3 minInnerAABB(
                minPointAABB.getX() + i * l,
                minPointAABB.getY() + j * l,
                minPointAABB.getZ() + k * l
            );

            Vector3 maxInnerAABB(
                minInnerAABB.getX() + l,
                minInnerAABB.getY() + l,
                minInnerAABB.getZ() + l
            );

            // Add the inner AABB points to a container for later use.
        }
    }
}

Alternatively, you can have one huge loop over the cube of your partitios and sort out the indices by division and remainder operations inside the loop, which is a bit messy for three dimensions.

It might also be a good idea to make the code more general by calculating three independent sub-box lengths for each dimension based on the side lengths of the original box.