标签: octree

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

            | BSP | Quadtree | Octree
------------+----------------+-------
Situation A |  X  |          |
Situation B |     |     X    |
Situation C |     |          |   X

什么是A,B和C？

我正在寻找一种良好的光线八叉树交叉算法,它以迭代的方式为我提供了光线穿过的叶子.我打算在CPU上实现它,因为我还不想潜入CUDA :)

目前,我的Voxel raycaster只在XxYxZ体素的非分层阵列上执行3D DDA(Amanatides/Woo版本).你可以想象,当有很多空的空间时,这是非常昂贵的,如下图所示(更亮的红色=更多的工作:) :):

我已经发现这个任务有两种算法:自下而上,从叶子向上运行,自上而下,这是基本的深度优先搜索.

我已经从2000年发现了Revelles的算法,称为八元遍历的高效参数算法,看起来很有趣,但是很老了.这是一种自上而下的算法.

最流行的自下而上的方法似乎是K. Sung,用于光线跟踪的DDA八叉树遍历算法,Eurographics'91,North Holland-Elsevier,ISBN 0444 89096 3,p.73-85.问题是大多数DDA八叉树遍历算法都期望八叉树具有相同的深度,这是我不想要的 - 空子树应该只是一个空指针或类似的东西.

在最近关于Sparse Voxel Octrees的文献中,我已经设法通读了(最值得注意的是Laine在SVO上的工作,它们似乎都基于某种GPU实现的DDA版本(Amanatides/Woo风格).

现在,这是我的问题:有没有人有任何实现基本的,没有多余的Ray-octree交叉算法的经验？你会推荐什么？

到目前为止,关于设计决策的一些背景......我开发了一种可以存储点的八叉树结构.我选择基于某个基本体素大小来限制"世代"的递归.只有在将点添加到该节点时才会创建子节点.这不是动态图形应用程序 - 这个八叉树及其中的对象是静态的,因此不需要考虑提高性能的预处理.

现在,我想在我的八叉树中添加"形状" - 特别是由三角形组成的表面网格.这些三角形的顶点不对应于存储在八叉树中的点.如何在八叉树中存储这些形状？我看到两个选择......

灰色节点是"空的",因为它们没有形状.在备选方案1中,形状存储在它们相交的每个节点中 - 即,节点1a包含shape1和4c和4d共享shape2.在备选方案2中,形状仅存储在它们相交的最小节点中 - 即,节点1a包含shape1而节点4包含shape2.

我见过的八角树上的大多数帖子都假设为Alt1,但他们从未解释过为什么.Alt2对我来说更有意义,只会为那些驻留在节点边界上的形状创建额外的工作.为什么Alt1更受欢迎？

编辑:为了澄清,我使用的实现语言是C++,所以我更喜欢该语言的示例实现,但问题是与语言无关.对不起,如果标签使用不正确.

编辑2:虽然与形状存储问题没有直接关系,但这个链接对问题背后的八叉树遍历有很好的讨论.我认为这可能有助于任何有兴趣研究这个问题的人.

更新:四年后,Alt2最终变得更容易实现,但速度非常慢,因为在八叉树的每次遍历中都会测试存储在较高八叉树级别的大三角形 - 在我的情况下,这意味着需要进行数百到数千次不必要的测试.我最后修改了我的代码以使用R*-Tree变体,这很容易实现并且速度更快.

我试图弄清楚哪种结构对点,kd树或八叉树的半径搜索更好？在这个问题中已经提到过,但没有答案.在我看来,由于八叉树具有固定的叶子大小,它已经可以计算出我需要访问的分支,而对于kd-tree,你必须迭代地访问分支,直到覆盖半径.

我正在尝试使用GKOctree在 3D 空间中有效检索对象。但是，以下代码似乎没有按预期工作：

import GameplayKit

let tree = GKOctree(boundingBox: GKBox(
  boxMin: vector_float3(x: -10, y: -10, z: -10),
  boxMax: vector_float3(x: 10, y: 10, z: 10)
), minimumCellSize: 0.1)

tree.add(NSObject(), at: vector_float3(x: 0, y: 0, z: 0))
tree.elements(at: vector_float3(x: 0, y: 0, z: 0)).count // 1, fine

tree.elements(in: GKBox(
  boxMin: vector_float3(x: -1, y: -1, z: -1),
  boxMax: vector_float3(x: 1, y: 1, z: 1)
)).count // 0, ??

tree.elements(in: GKBox(
  boxMin: vector_float3(x: 1, y: 1, z: 1),
  boxMax: vector_float3(x: -1, y: …

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

优选地,可以在HLSL中容易地实现.(我正在使用光线投射/体素应用)

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

更新

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

我将编写一个KDTree的模板化实现,现在它只能作为四叉树或八叉树用于BarnesHut实现.

这里的关键点是设计,我想指定树被定义为模板参数的维数,然后简单地声明一些常用方法,它们会自动表现出正确的方式(我认为当时需要一些模板专业化).

我想专门化模板,以便有2 ^ 2(四叉树)或2 ^ 3(八叉树)节点.

有人有一些设计理念吗？我想避免继承,因为它限制我做动态内存分配而不是静态分配.

这里N可以是2或3

template<int N>
class NTree
{
public:
    NTree<N>( const std::vector<Mass *> &);
    ~NTree<N>()
    {
       for (int i=0; i<pow(2,N); i++)
          delete nodes[i];
    }
 private:
    void insert<N>( Mass *m );
    NTree *nodes[pow(2,N)]; // is it possible in a templatized way?
};

另一个问题是四叉树有4个节点但是2维,八叉树有8个节点,但是3维,即节点数是2^dimension.我可以通过模板元编程指定吗？我想保留4号和8号,这样循环展开器可以更快.

谢谢!

我有以下内容.结构是原型,所以它编译得很好.

struct vertexNodeInfo
{
    vector<vertexNodeInfo> node;
};

我正在尝试写一个八叉树的东西.我想要做的是使用递归函数继续向每个节点添加一个节点,直到我到达一个特定的点,此时函数,而不是添加另一个节点,添加一个叶子.如果可能的话,如果没有其他节点或叶子添加,我想不使用内存.

也许模板会在这种情况下有所帮助,但我不确定如何使用它们......

我不认为我已经很好地解释了自己.这是一个图表:

我不知道我所要求的是不可能或者太难以理解或者只是简单的愚蠢,但我无法自己解决这个问题.对不起,我无法解释它.

我正在使用C++ 98/03(VC++ 2008),不能使用C++ 11

任何帮助都将非常感激.

附加信息:

更好的解释:我想要一个数组数组的数组数组.内存使用非常重要(我存储了数百万个元素,因此单个字节会产生巨大差异).每个数组可以包含8个以上的数组,但在我需要使用它之前,我希望每个数组都不使用内存.这是一种八重奏.

更多附加信息:

这是另一张图.它有点大,所以您可能需要右键单击它并选择Open image in new tab使其可读.

我不想要的是"棕色"(红色+绿色)框,其中每个框都为更多节点和叶数据保留内存.这将为我的需求使用太多的内存.

这基本上就是我想要实现的,为简单起见为2D:

我目前正在研究一个高效的计算引擎，用于 CPU 和 GPU 中的粒子模拟。我最近一直在研究八叉树，我成功地为空间中的粒子编写了八叉树的工作版本，并且还有效地处理了它们的碰撞。现在我必须在我的八叉树中插入三角形网格（STL 对象），以便我也可以处理粒子和对象三角形之间的碰撞。我很困惑如何以有效的方式将三角形插入到已经创建的八叉树中？请提出实现这一目标的方法。如果这有帮助，我正在使用 C++。已经谢谢了。

我目前在C中使用自己的八叉树.树将包含几十亿个对象,因此内存效率是关键.为了实现这一点,我目前使用一个带有标志和联合的结构,但我认为它不干净并且它浪费了内部节点的空间,因为我只需要一个8位标志但是为64位保留了内存指数.我的代码目前如下:

typedef struct _OctreeNode
{
    uint64_t location_code;
    union
    {
        uint8_t child_exists;
        uint64_t object_index;
    } data;
    uint8_t type;
} OctreeNode;

我想把它分成两个不同的结构.一个叶节点和一个内节点.如下:

typedef struct _OctreeInnerNode
{
    uint64_t location_code;
    uint8_t child_exists;
    uint8_t type;
} OctreeInnerNode;

typedef struct _OctreeLeafNode
{
    uint64_t location_code;
    uint64_t object_index;
    uint8_t type;
} OctreeLeafNode;

现在问题出现在我的无序地图上,基于位置代码的哈希值.它使用void指针,因此存储两个不同的结构不是问题.我知道有可能将标志作为第一个元素并取消引用指向flag数据类型的指针来派生类型,如下所示:

typedef struct _OctreeLeafNode
{
    uint8_t type;
    uint64_t location_code;
    uint64_t object_index;
} OctreeLeafNode;

void
func(void* node)
{
    uint8_t type = *(uint8_t*)node;
    if (type == LEAF_NODE) {
        OctreeLeafNode* leaf_node = (OctreeLeafNode*)node;
    }
}

我想知道是否有更清洁的方式.或者这不推荐？我怎么能处理结构和void指针的多种可能性？

提前致谢!