c++ - 我什么时候应该找到附加到模型的 BoundingBox 的最小值和最大值

Question

我正在为我的 DirectX 11/12 管道中的任何 3D 模型实现一个 ModelClass。

我的具体问题在于计算我希望用作 ModelClass 成员的 BoundingBox 结构的最小值和最大值。

我有两种计算它们的方法。

方法 1.当从文件中读取每个顶点时，存储当前的 minx、y、z 和 maxx、y、z，并根据当前的最小/最大 x、y、z 检查每个顶点。

方法 2.加载完所有顶点后，按 x、y、z 排序，找到每个点的最低值和最高值。

您会推荐哪种方法，为什么？

Answer 1

方法一

时间复杂度为 O(n)，内存复杂度为 O(1)。

实现起来很简单。

方法二

时间复杂度为 O(nLogn) 内存复杂度可能至少是线性的(如果您复制数组或使用合并排序)或 O(1) 如果您使用像快速排序这样的就地排序算法。

每个维度都必须执行 3 次。

总而言之，方法 1 在我能想到的所有场景中都是最好的。