问题标签 [octree]

这是我在stackoverflow上的第一个问题，所以我希望我做对了。对于 java 项目，我需要使用八叉树进行光线跟踪。我已经创建了一个简单的八叉树（没有邻居信息或其他东西）并将对象网格的三角形分类到八叉树的 AABB 中。现在我想为每条光线轻松遍历树。（这应该很容易，因为完成这个项目的时间很短）。基本算法如下：

1. 从第一个节点开始
2. 如果这个节点被命中，记住交点在排序列表中的位置
3. 如果此节点有子节点，检查子框是否被击中并将每个交点写入排序列表
4. 从最近的交点的子框开始
5. 如果这个盒子也有孩子，请参阅 4)
6. 如果一个节点没有任何子节点，请检查此框中的每个三角形与射线
7. 如果击中三角形，则获取三角形的颜色（带有阴影和所有内容）并将其绘制在屏幕上

不幸的是，我当前的实现似乎在交集计算（ray vs ABBB）中有一个“错误”。我检查是否击中了 AABB 的任何一侧并记住最近的 ip（距射线原点的最小距离）。

这是我的 BoundingBox 类中此函数的代码：

我想这不是最好的方法。在我的第一个实现中，我只使用了 t 值并比较了它们（以找到我接下来要访问的框）。但问题是一样的。找不到某些交叉点。

我还在这里检查了交集方法： https ://code.google.com/p/3d-workspace/source/browse/trunk/MathLibrary/Bounding/BoundingBox.cpp?r=17 但我看不到如何获取与此代码（甚至任何 t 值）的交点。此外，我测试了此处描述的平板方法：http: //tavianator.com/2011/05/fast-branchless-raybounding-box-intersections/ 但这似乎也错过了一些交叉点，我不知道为什么：

也许我对光线追踪太愚蠢了。

但我的实际问题是：

是否可以使用 t 值来比较哪个框的交点最近？如果是，我怎样才能得到这个 t 值？或者我该怎么做才能使第一个代码被剪断？（到目前为止，我对任何可行的解决方案都很满意，即使这个解决方案很慢）

提前致谢。

我有一个自上而下的过程，它从 3D 对象的高级描述构建一个线性八叉树（例如，叶子排列成一个数组并按莫顿编码排序）。问题是，对于我的预期应用，生成的八叉树必须是 2:1 平衡的，即不能有任何一对相邻块，其中一个块的大小超过另一个块的两倍。

我唯一能找到的是文章“Bottom Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel”（你可以从多个来源找到它，但版权不清楚，不知道链接这样的东西的政策是什么这个网站），它解释了一种算法来做到这一点。问题是所提出的算法在并行消息传递架构中工作，这对我的应用程序来说太过分了。另一个问题是（自下而上）构造和平衡算法似乎捆绑在一起，我不知道如何仅在用我自己的方法构造树之后才能平衡它。

那么什么是 2:1 平衡线性八叉树的（希望简单且）有效的方法？并行算法也很好，但使用共享内存模型，而不是像链接算法那样传递消息。

我正在尝试构建一个表示最初由 CSG（构造实体几何）树描述的体积的八叉树。

我最初的计划是从一个包含整个对象的大立方体开始，然后对八个子立方体中的每一个进行测试，哪些是完全在外部的，哪些是完全在对象内部的，哪些是内部的和外部的。然后这些“中间”立方体将被递归细分。

我的问题可能很愚蠢，但我无法设计一种方法来找到立方体和 CSG 对象的交集，以便能够如上所述对立方体进行分类。

我的 CSG 结构是由诸如立方体、球体和圆柱体（未来可能还有环面）之类的基元构建的，具有并集、交集和减法的布尔运算。

除了 CSG 的显式树结构之外，从它的表示来看，我还有一种距离函数d(x,y,z)，它可以告诉我该点(x,y,z)是在对象外部 (>0) 还是在对象内部 (<0)。

如何找到一个立方体是否与 CSG 结构所描述的对象相交？

我正在开发适用于非常大的场景显示的 3D 引擎。渲染本身的设备（截头剔除，遮挡剔除等），我想知道场景管理的最佳解决方案是什么。

数据是作为一个巨大的 3D 网格列表给出的，它们之间没有任何关系，所以我无法生成门户，我想......

主要目标是能够在 RAM 较低（500MB-1GB）的系统上运行该引擎，并且加载到其中的场景非常大，可以包含数百万个三角形，这会导致非常密集的内存使用。我现在实际上正在使用一个松散的八叉树，在加载时构建，它在中小型场景上运行良好，但是许多场景太大而无法完全适应内存，所以我的问题来了：

您将如何处理场景以动态（并且理想地无缝地）加载和卸载块，以及您将根据什么来确定是否应该加载/卸载块？如果需要，我可以创建自定义文件格式，因为正在使用已知 3D 创作工具上的自定义导出器导出场景。

重要信息：许多场景无法有效遮挡，因为它们的构造。示例：一个非常大的管网，因此没有太多的遮挡，但元素数量非常多。

我只想使用 FCL 库进行碰撞检测。

我的第一个对象是机器人，我想使用球形来指定它，第二个对象是使用八叉树来指定世界上的障碍物。

我尝试按照说明创建此检测代码。

如何从 ROS wiki 中的 API 填写以下信息？

在这个 API 中，他们使用三角形，据我所知，三角形仅用于 3d 网格。我不想使用网格，我想要八叉树和球体作为对象。

1. 那么我该如何修改呢？
2. 之后，我应该使用哪个函数来返回碰撞发生的真或假？
3. 如果我的数据更新了怎么办？我的意思是机器人正在移动，我想不断更新机器人和八叉树的位置？我该怎么做？
4. BVH模型的含义是什么？

我查找了示例并发现了以下内容：

输出为“res1”

“1”是什么意思？这是否意味着它是一个碰撞？这里物理碰撞的含义是什么？对象的位置在哪里，为什么不遵循 ROS wiki 的 API？

很抱歉这个问题很长，但我是第一次使用 FCL，我对此一无所知。

我有两个对象。第一个对象是我的机器人，我想将它表示为一个球体，第二个对象是具有未知形状的障碍物。我想用八叉树来表示障碍物的形状。

如何使用 fcl 的 api 使用 ROS wiki 中的 api 使用 fcl 库检查这两个对象之间的冲突（真或假）？假设机器人正在移动。

此外，使用激光扫描数据检测障碍物？？如何将它填充到八叉树对象中？

如果我创建了一个像

我怎样才能确定这个球体的中心是机器人的中心？

编辑：

我写了以下代码，但我不知道如何填充八叉树

那么，有什么建议吗？？？

我正在尝试制作自己的八叉树版本，如果您尝试添加不同大小的点，则会遇到问题，因为降低深度级别只会覆盖所有内容，因此会删除较大块上的任何信息。

我认为解决此问题的最佳方法是向后检查最后一点，并将列表重建到新点的深度。但是，我实际上无法弄清楚如何构建列表，尽管事实上很容易想到我所追求的输出。

这是使用示例开始和结束列表构建列表所需的数据，我需要它的格式为["Nodes",(coordinate),"Nodes",(coordinate)...]每个坐标覆盖structure列表中的每个项目，直到它到达末尾。

这是一个极端的例子（从深度 4 到 0），会产生 4096 个不同的值，尽管 99% 的情况下它不会有这么大，所以性能应该不太重要。

在示例开始值和结束值的情况下，我不需要每个长度的值，它们只需要最大长度，就像这样 -

我有过尝试，但在它实际上不是递归之后我意识到，无论如何，它就是 -

我真正需要的是运行时的每个列表，所以如果它可以到达一个可以从循环内打印所有组合的阶段，那就太好了，因为存储所有这些组合不会浪费内存:)

我正在使用 LWJGL 在 Java 中创建一个体素引擎，只是为了练习，但我卡在了块管理系统上。更具体地说，我正在尝试将块（块 ID 的整数 3D 数组）转换为八叉树以实现最佳渲染。

到目前为止，我的系统可以正常工作，但是效率非常低。

这是一个 16*16*16 块的屏幕截图，其中 y=8 以下的所有位置都设置为 1（红色块）

https://raw.githubusercontent.com/ninthworld/Octree/master/screenshot0.png

我在 OctNode 生成器代码中添加了一个调试器，以找出访问块数组需要多少次，它返回8392704。

它访问块数组超过 800 万次只是为了生成 8 个子节点。

当我将块数组设置为只有 y=4 以下的块时，程序黑屏将近 30 秒，调试器返回1623199744 次数组访问。

超过 16 亿次数组调用仅用于生成 68 个子节点。

我显然需要减少数组调用的数量，这是肯定的，但我不确定我将如何去做。如果您想查看完整的源代码，这里是项目的 github 页面。

以下是我的代码的重要部分：

主.java

OctNode.java

不幸的是，这是我能解释的最好的。如果你能指出一种更简单、更快捷的方法来做同样的事情，那就太棒了。

我使用主要用 C++ 编写的 iOS 和 Android 的 3D 地图渲染器。我使用八叉树从文件中加载和存储数据。

到目前为止一切都很好，渲染几平方公里的中小型地图都很酷，而且一切都很流畅。但现在我想增加地图的大小，比如整个国家或大陆的大小。

有很多 Octree 实现和教程——但到目前为止，我还没有找到一个教程来解释如何有效地处理大型数据集的延迟加载和树构造。

最好有一个免费的八叉树库，它已经做到了。你知道吗？否则，通常必须做什么才能将延迟加载到八叉树中？

我正在使用 Three.js 在不同的位置和旋转中显示许多自定义几何图形。它们是静态的，很少更改，但用户可以添加、删除或更改每个单独对象的形状。

使用下面的代码片段效果很好：

以上工作正常，尽管不出所料，它与大量对象作斗争。参考： https ://gamedev.stackexchange.com/questions/81570/merging-geometry-mesh-without-losing-benefits

我已经合并了对象，并且在提高速度方面取得了巨大成功，它在 10,000 多个对象上运行良好。我现在正在尝试再次设置选择，但在这里我被卡住了。

上面的链接表明，将网格保持在数组或八叉树中将启用选择，同时保持合并对象的速度优势。我已经实现了一个八叉树，所以这应该很容易再次使用，但是选择对象现在与合并的场景对象不在同一位置。选择对象位于原点，八叉树似乎失去了其对象的位置，可能还有旋转。麻烦代码的快照如下：

自定义几何图形需要手动旋转和定位。欢迎任何想法！谢谢