我目前只为3D三角形实现边界体积层次。遗憾的是,BVH的所有解释都不符合您对对象进行分类以进行拆分的部分。首先,我想以一棵平衡的树为目标,并使用中值切割。这将需要我在当前节点的分割轴上的空间标准之后对三角形或其边界框(AABB)进行排序。我真的不确定BB或三角形的最大或最小延伸是否足以进行适当的分离,因为有些三角形可能更大。我也不确定比较边界框还是三角形更好。
问题的第二部分是,对每一步进行排序似乎都很昂贵。计算机图形学中的其他算法使用预先排序的列表,然后根据拆分标准对这些列表进行拆分。我看不出如何有效地比较三角形并确保它们属于一个列表。这是否意味着我必须每一步都对列表进行排序?
正如您所发现的,您有多个选项。最容易想到的是使用边界框的质心。您也可以按最小坐标进行排序,并分别按最大坐标进行排序。
您可以按每个轴进行排序作为预处理。然后,每次迭代都是一个分区,包括选择在哪个轴上分割以及在哪里分割,并将起点/终点存储在该轴的排序列表中。
参见Ingo Wald的论文:http://www.sci.utah.edu/~wald/Publications/2007/FastBuild/download/FastBuild.pdf
更快、质量更低的方法是线性化的BVH-将每个质心映射到空间填充曲线上的坐标,例如Morton代码,然后根据它们的Morton代码对所有三角形进行排序,然后将跨度拆分为框。
SAH(表面积启发式)是评估在用于光线跟踪的BVH中分割一组三角形的位置的最常见方法。你可以在PBRT书的第4章找到一个很好的解释(http://www.pbrt.org)。这里免费提供:http://pbrt.org/pbrt-2ed-chap4.pdf
如果你对光线追踪有一点兴趣,我建议你买一本完整的书。