问题标签 [bounding-volume]

I created a bounding volume hierarchy that is generated every frame. Due to it's use, each node must have two children, no more, no less.

Traversal is the single most expensive computation for my program right now and it prevents large scenes (>2k triangles) from running at acceptable frame rates. I am at a loss as to how it can be performed faster. A simple square with 16 triangles introduces a noticeable frame drop when many rays pass through it at once.

To traverse it I used the concepts provided by the paper at this link, where each thread traverses the following code.

What can be done to make it increase it's speed?

At the moment, this function is used in a much larger kernal. Will isolating it within its own dispatch call help at the cost of using more memory to store its output?

I tried to minimize the memory accesses within the context of the algorithm, however the divergence, which I assume to be the problem, seems an impossible hurdle to overcome.

For each mesh (THREE.Object3D) Three.js provide a very handy properties - boundingSphere and boundingSphere that have intersectsSphere and isIntersectionBox methods.

With all this I thought I can use it for simple collision detection but when I try it appears that collision happens all the time because (I tried boundingSphere) boundingSphere.center is always in (0, 0, 0); So If I want to check collisions between 2 meshes I should for each object - clone boundingSphere object and then get it world coordinates and only then to use intersectsSphere.

something like this:

is this how it suppose to be used or am I missing something and there are more convenient way of doing collisions detection based on boundingBox/boundingSphere?

我很难想出一个好的策略来减少以下问题的内存分配：

我正在建造一棵树。一开始，我只有包含一些数据的根（std::vector索引列表（））。我分成两部分，其中一部分索引到左孩子，另一部分到右孩子。我不知道有多少人会去左/右。有一次，我完成了对根的处理，我不再需要为它存储索引。事实上，我只对那些叶子感兴趣。此外，可以在每次拆分时添加其他数据！所以，如果根有 20 个元素，那么在拆分后左边的可能有 12 个元素，右边的可能有 10 个。

在每个节点中，我保留一个std::vector包含这些索引的。当我添加元素时，我push_back()是导致许多内存分配的元素。

保留索引的好策略是什么？

该问题与 SBVH 数据结构的生成有关。

代码：

我正在尝试使用 MATLAB 测试包围体算法（光线追踪之前）背后的数学。

到目前为止，我已经成功地创建了相对简单的轴对齐包围体，并且我相信我已经成功地创建了包围球。

然后我尝试创建一个与对象对齐的边界体积——但尽管我相信我的主轴是正确的，因为盒子看起来是一个合适的形状——但我无法将它正确地“翻译”到形状上。

本质上我的问题是 - 我在我的算法中做错了什么以及如何将我的边界体积转换为形状。

我一直在使用的两个来源是Maths for 3D Games，以及一个博客，它给出了一些关于进行翻译的指示 - 但似乎效果不佳。

我已将我的源代码放在下面 - 非常感谢！

作为编写 3D 游戏库的一部分，我正在尝试实现截锥体剔除，以避免渲染相机透视截锥体之外的对象。为此，我首先需要为每个网格计算一个边界球，并查看它是否与视锥体的六个侧面中的任何一个发生碰撞。这是我目前（非常）幼稚的实现，为每个模型计算边界球体，如model.py我的代码中所写：

我只是从我的网格中取出成对的点，并使用我找到的最大距离作为我的直径。在每帧 100 个简单的立方体测试模型上调用它非常慢，将我的帧速率从 120 fps 提高到 1 fps！这并不奇怪，因为我假设这个成对代码的时间复杂度是 O(n^2)。

我的问题是，在给定网格中的一组 3D 点的情况下，哪种算法可以快速且相当简单地计算（至少）一个近似边界球？我查看了这个Wikipedia 页面，发现有一种算法叫做“Ritter 的边界球”。但是，这需要我在网格中选择一些随机点 x 并希望它是近似中心，以便我得到一个相当紧凑的边界球。有没有一种快速的方法来选择一个好的起点 x？任何帮助或建议将不胜感激！

更新：

在@Aaron3468 的回答之后，这是我的库中的代码，用于计算边界框和相应的边界球：

我已经编写了自己的 3D 游戏引擎（花了我一年的时间），我想创建一个在我的 CPU（不是 GPU ！！）上运行的 Raytracer

目前，光线追踪过程被简化如下：

1. 为每个输出像素投射一条光线。
2. 如果当前光线击中一个物体，将输出像素颜色设置为“白色”
3. 否则设置为黑色

为了提高光线追踪器的速度，我为每个实体添加了一个球形边界框。如果当前光线与边界框相交，它将对实体的每个三角形运行相交测试。

我在射线三角形相交和射线点距离上使用最快的方法，但仍然每条射线都必须测试每个可能相交的实体的每个三角形。

结果，我用大约 10000 个多边形渲染一个对象 (1920x1080) 需要超过 5 分钟，我认为这不是我想要的。

有什么方法可以减少我需要检查的三角形数量吗？

问候，芬恩

因此，我在我的任务中使用了 Matterport 3D 数据集，它使用标准结构描述了定向边界框，其中一项更改如下：

我知道定向边界框通常由质心、局部坐标系轴和沿这些轴的长度定义。

就我而言，考虑到对象仅在世界坐标系中围绕垂直轴（z 轴）旋转，我想找出它围绕 z 轴旋转的角度。但为此，我需要将世界坐标系转换为局部坐标系的旋转矩阵。在标准表示的情况下，旋转矩阵只是 3x3 矩阵，轴作为列向量。但是，在这种情况下，如果您查看归一化轴数组，则会给出 9 个值，但没有约定哪个轴应该是旋转矩阵中的第一列向量或第二列向量。

假设对象位置是垂直的并且仅围绕 z 轴旋转，我可以确定旋转矩阵的最后一列。例如，上述示例中的 [0, 0, 1]。但是如何确定另外两个轴呢？有没有办法在确定时考虑“dominantNormal”信息？

我的公司使用 Qt3D 来显示其 CAD 模型。Wee 尝试使用该函数QCamera::viewEntity(Qt3DCore::QEntity *entity)来计算给定实体的边界球，并让实体适应屏幕。

现在，我们偶然发现了一个在空QEntity节点的情况下无法解决的问题。如果它根本不包含任何顶点/点，我将把它称为空节点。在这种情况下，我预计在计算包围体时应该忽略它。相反，它似乎会被处理，因为它有一个中心为 (0.,0.,0.) 且半径为 0 的边界球。

下面的代码说明了这个问题：

主文件

我有两个半径为 0.5 的蓝色球体，彼此之间的距离为 20。我期待一个中心（20,0,0）和半径（10.5）的边界球。

相反，程序打印：

似乎值 2.14455 真的来自无处可去，而且我添加的边界体积球体有些不可预测。

如果我用结果替换翻译QVector3D(20, 10, 0)，QVector3D(0,10,0)结果会像预期的那样。

如何从我的包围体计算中排除根实体？

我正在开发一个 Opengl 光线追踪器，它能够加载 obj 文件并对其进行光线追踪。我的应用程序使用 assimp 加载 obj 文件，然后使用着色器存储对象将所有三角形面（顶点和索引）发送到片段着色器。基本结构是将结果从片段着色器渲染到四边形。

当我加载更大的 obj-s（超过 100 个三角形）时，计算机需要很长时间才能完成交点，因此我开始创建 BVH-tree 以加快处理速度。我的 BVH 根据 AABB 中包含的三角形面的平均中值，递归地将空间分成两个轴对齐的边界框。

我成功构建了 BVH 树结构（在 CPU 上），现在我想将其转换为一个简单的数组，然后将其发送到片段着色器（到着色器存储缓冲区）。

这是我的 BVH 类的结构。

但首先我想将它转换为一个简单的数组，因为 GLSL 不支持指针。我读过关于可以将二叉树转换为数组的信息（当然，如果树是完整的）。我正在拔头发。我如何遍历整个节点，包括子节点，当然还有如何用空节点完成它（以实现完整二叉树的定义）？我开始编写如下所示的方法，但是当我将nodes变量声明为全局变量时出现分段错误。我不知道为什么。

我想，当我创建树时，我需要以某种方式在左右孩子开始的每个节点上签名。

任何帮助表示赞赏。

我正在为多边形模型创建一个基于 OpenGL 的光线追踪器。为了加速我正在使用 BVH 树的应用程序。因为 GLSL 中没有递归，所以我决定寻找另一种方法来遍历边界框，将其作为着色器存储缓冲区发送到片段着色器。

我想实现这种方式：在着色器中遍历 BVH 树

其实我真的不明白如何在树的构建过程中计算命中和未命中链接。命中和未命中链接帮助程序在遍历过程中导航到下一个节点（边界框），无论它是否相交。

到目前为止，我创建了构造树的方法，并且我还可以将树放入一个简单的数组中。我有深度优先实现将树展平到数组中。

以下是深度优先的树展平方法：

我必须计算以下“链接”：

图片来自：来源。该图显示了不同的链接。因此，例如光线与边界框（命中链接）相交，我们可以移动到数组中的下一个节点。这没关系，因为我有深度优先遍历。当我必须搬到兄弟姐妹甚至父母的兄弟姐妹时，问题就来了。如何实现这些链接/偏移？我知道我应该创建和索引，但是如何通过深度优先树构造来做到这一点。

任何帮助表示赞赏。