AABB的划分

Question

我遇到了一个问题，我需要将AABB划分为多个小型AABB。我需要在每个较小的AABB中找到最小和最大的点。

​

​

如果我们以这个长方体为例，我们可以看到它被分成64个较小的长方体。我需要计算所有这些小长方体的最小和最大点，其中长方体的数量(64)可以指定的最终用户。

我对以下代码进行了基本尝试：

// 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.
}

非常感谢！

Answer 1

我想你的问题是你没有足够的子盒子。分区的数量指的是每个维度的分区，对吗？因此，两个分区产生8个子框，3个分区生成27个子框，以此类推。

然后必须有三个嵌套循环，每个维度一个：

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

或者，您可以在分区立方体上有一个巨大的循环，并通过循环中的除法和余数操作来排序索引，这对于三维来说有点混乱。

通过根据原始框的边长计算每个维度的三个独立的子框长度，使代码更加通用也可能是一个好主意。