问题标签 [octree]

我最近了解了二进制空间分区树及其在 3d 图形和碰撞检测中的应用。我还简要阅读了有关四叉树和八叉树的材料。你什么时候会在 bsp 树上使用四叉树，反之亦然？它们可以互换吗？如果我有足够的信息来填写这样的表格，我会很满意：

什么是 A、B 和 C？

我是 SceneMax 的创始人 - 自 2005 年以来是一种 3D 脚本语言。我想使用一个使用 3ds max 等 3d 包构建的网格对象添加场景渲染，并按八叉树算法分割以优化性能。

你知道我在哪里可以找到一种算法，它采用网格 .X 文件，将其拆分为节点（八叉树）并知道如何渲染它？我想将它添加到我的引擎中。该引擎是开源的（如果您有兴趣，请在谷歌上搜索 SceneMax）。

任何人都可以建议一种快速、有效的方法来存储和访问稀疏八叉树吗？

最好是可以在 HLSL 中轻松实现的东西。（我正在使用光线投射/体素应用程序）

在这种情况下，可以预先计算树，所以我主要关心大小和搜索时间。

更新

对于任何想要这样做的人，更有效的解决方案可能是将节点存储为使用 Z 阶曲线/莫顿树生成的线性八叉树。这样做消除了内部节点的存储，但可能需要使用第二个“数据纹理”交叉引用线性树阵列，其中包含有关单个体素的信息。

Could anyone provide a short & sweet explanation (or suggest a good tutorial) on how to cast a ray against a voxel octree without recursion?

I have a complex model baked into an octree, and I need to find the best/closest leaf that intersects a ray. A standard drill-down iterative tree walk:

1. Grab the root node
2. Check for intersection
3. No? Exit
4. Yes? Find child that intersects the ray that is closest to the ray's origin
5. Loop until I reach a leaf or exit the tree

Always returns a leaf, but in instances where the tree stores, say, terrain, the closest node to the ray's origin doesn't necessarily contain the leaf that's the best match. This isn't suprising - taller objects in farther nodes won't get tested using this approach.

I can do this recursively by finding all of the intersecting leaves in the tree, sorting by distance and picking the closest one to the ray's position. However, this is slow and requires recursion.

I've read a little about using the Bresenham line algorithm to walk the tree, which seems to require that each node contain pointers to adjacent neighbors, but I'm unclear on how to implement this in a useful way.

Any suggestions? I can fake a stack in HLSL using a fixed-length array or a struct with an element for each potential stack entry, but the memory requirements for that can become crippling with a sufficiently large tree.

Help.

我正在尝试将八叉树存储在 OpenGL 中的 3D 纹理中，以便使用 Cg 在 GPU 上使用，来自 GPU Gems 2 的一章，可在此处找到http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter37.html。但是我得到的结果是不正确的。我认为这是因为我如何创建八叉树。

在该章的附录中，它说“如果我们以重复模式（GL_REPEAT）绑定间接池纹理（八叉树纹理）......”。

这只是意味着将过滤器和包装设置为重复，还是我需要做其他事情？到目前为止，这是我的代码

谢谢您的帮助 ：）

可能重复：
快速、模板化、C++ 八叉树实现

任何人都可以在 C 或 C++ 中为 CPU 或 GPU 上的八叉树建议一些经过良好调整的实现吗？

此外，由于八叉树可以用指针表示，也可以不用指针表示，有人可以告诉我这两种技术可能的优点或缺点。

谢谢，

我正在尝试在 CPU 上投射八叉树（我知道 GPU 更好，但我现在无法让它工作，我相信我的八叉树纹理创建不正确）。

我了解需要做什么，到目前为止，我为每个像素投射了一条射线，并检查该射线是否与八叉树中的任何节点相交。如果是这样并且该节点不是叶节点，我检查光线是否与它的子节点相交。我一直这样做，直到一个叶节点被命中。一旦叶节点被击中，我就会得到该节点的颜色。

我的问题是，将其绘制到屏幕上的最佳方式是什么？目前我将颜色存储在一个数组中并使用 glDrawPixels 绘制它们，但这不会产生正确的结果，渲染中的间隙以及投影错误（我使用的是 glRasterPos3fv）。

编辑：到目前为止，这是一些代码，需要清理，抱歉。我省略了八叉树射线投射代码，因为我不确定它是否需要，但如果它有帮助我会发布:)

我对 N-Body 和 SPH 等粒子算法很感兴趣。这些应用程序中的一个重要步骤是，给定一个查询点，找到位于半径为“h”的指定球体内的粒子。

现在我听说八叉树是解决 N 体或 SPH 等问题的良好空间数据结构。

但是在八叉树构造之后，我无法理解“在半径内定位粒子”步骤是如何执行的。有人可以指点我做这一步的一些参考资料、论文或文章吗？

我见过创建八叉树、添加和删除数据的代码，但实际上如何构建八叉树呢？是否有 3d 体素软件可以保存到某种数组中，然后可以转换为八叉树？或者你可以直接保存到八叉树吗？

我开始在 Python 中为 Blender 开发这个粒子引擎：http ://www.youtube.com/watch?v=uoK4QV3jg58&feature=channel_video_title

所有数据都由我的脚本处理，Blender 只是用于视觉效果。我现在的问题是，在上面的视频中，我计算了所有粒子的每个粒子之间的距离，以检测它们是否相互碰撞。

我开始阅读：

• 八叉树
• kd树
• BVH树
• AABB树
• ...还有很多

Kdtree 似乎对于搜索最近的邻居非常有效，但仅适用于静态云。我的粒子总是在移动，因此每次迭代都必须重新生成 kdTree，我认为这消耗了太多的过程。我读过很多游戏都使用 AABB 树。我有点迷茫……我不知道该选择什么。我想要的是：

• 检测大量粒子（250 000 或更多）之间的碰撞
• 不需要是实时的（无论如何有 250 000 个粒子是不可能的）。200 万个粒子每帧 20 分钟对我来说不是问题。
• 我的粒子总是球体
• 检测粒子和多边形对象之间的碰撞
• 减少必要距离计算的算法（避免为其他粒子或多边形计算所有粒子，即使它们很远）
• 我的粒子是动态的，我的多边形对象可以是动态的或静态的。

如果有人能告诉我什么是最好的猜测，我在哪里可以找到 Python 文档和示例。