c++ - 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

我认为您的问题是您没有获得足够的子框。分区数是指每个维度的分区，对吧？所以 2 个分区产生 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.
        }
    }
}

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

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