标签: octree

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

任何人都可以提供一个简短而甜蜜的解释(或建议一个很好的教程),如何在没有递归的情况下对一个体素八叉树投射光线？

我有一个复杂的模型烤成八叉树,我需要找到与光线相交的最佳/最接近的叶子.标准的向下钻取迭代树步骤:

1. 抓住根节点
2. 检查交叉点
3. 没有？出口
4. 是？找到与最接近光线原点的光线相交的子项
5. 循环直到我到达树叶或退出树

始终返回叶子,但在树存储地形的实例中,与光线原点最接近的节点不一定包含最匹配的叶子.这并不令人惊讶 - 使用这种方法不会对更远节点中的较高对象进行测试.

我可以通过查找树中所有相交的叶子,按距离排序并选择最接近光线的位置来递归地执行此操作.但是,这很慢并且需要递归.

我已经阅读了一些关于使用Bresenham线算法来遍历树的一些内容,这似乎要求每个节点都包含指向相邻邻居的指针,但我不清楚如何以有用的方式实现它.

有什么建议？我可以使用固定长度的数组或带有每个潜在堆栈条目的元素的结构来伪造HLSL中的堆栈,但是对于它的内存要求可能会变得非常大.

救命.

问题陈述:使用Octree查找每个粒子的最近GRID ID.

图.1]:

图[2]:

我有一个粒子系统(~6k,可移动),我需要检查哪个网格点(刚性;图中)最接近.有人建议我选择Octree,因为3D Grids的速度很快(可能).

这是递归八叉树的正确算法,以获得最近的网格点网格点吗？

1. 得到一个输入作为点P开始坐标C(第一次[0,0,0])
2. 起始尺寸= [Sx,Sy,Sz]
3. 得到所有8个中点Mi = {M1,..,M8}得到Mi和P的最小距离

4. 假设M得到M的起始位置为Cn设定大小Sn = [Sx/8,Sy/8,Sz/8]

5. 如果M和P的距离小于2*(网格空间G):

   5.1.迭代从Cn到Sn的所有网格点

   5.2.打印最少结果

6. 其他

   6.1.将起始坐标设置为Cn

   6.2.将大小设置为Sn

   6.3.转到1

问题:如果粒子在边界上或几乎在边界上,那么最后一次迭代会吃掉所有速度,因为它会检查所有A x B x C.

请建议您是否有更好的方法来解决此问题.

我有一个自上而下的过程,从3D对象的高级描述构建一个线性八叉树(例如,叶子排列在一个数组中并按莫顿编码排序).问题是,对于我的预期应用,得到的八叉树必须是2:1平衡,即不得有任何一对相邻的块,其中一个是另一个的两倍以上.

我唯一能找到的是文章"自下而上的构造和平行线性八分之一的2:1平衡"(你从多个来源找到它但版权不明确,不确定链接这样的东西的政策是什么这个网站),解释了这样做的算法.问题是所提出的算法在并行消息传递架构中工作,并且对我的应用程序来说太过分了.另一个问题是(自下而上)构造和平衡算法似乎捆绑在一起,我不知道如何在用我自己的方法构造树之后如何仅平衡它.

那么2:1平衡线性八叉树的(希望简单且有效)方法是什么？并行算法也很棒,但是使用共享内存模型,而不是传递链接算法之类的消息.

我开发游戏服务器，并希望在地图上保留实时对象的位置。为此，我使用octree算法。但是现在我的实现占用大量RAM，为了进行测试，我试图填充几张地图，即使没有对象，八叉树也占用了大约1 GB +每张地图大约1 GB的对象（我将所有对象存储在字典中，并单独存储向导列表根据每个八叉树节点的坐标）。

在我的实现下面：

class OctreeNode(object):

    MAX_CHILD_NODES = 8

    def __init__(self, **kwargs):
        self.x0 = kwargs.pop('x0')
        self.x1 = kwargs.pop('x1')
        self.y0 = kwargs.pop('y0')
        self.y1 = kwargs.pop('y1')
        self.z0 = kwargs.pop('z0')
        self.z1 = kwargs.pop('z1')

        self.root_node: OctreeNode = None
        self.parent_node: OctreeNode = None
        self.child_nodes = None

       self.objects = None
       self.guids = None

    def get_root_node(self) -> 'OctreeNode':
        return self.root_node

    def set_root_node(self, node: 'OctreeNode') -> None:
        self.root_node = node

    def get_parent_node(self) -> 'OctreeNode':
        return self.parent_node

    def set_parent_node(self, node: 'OctreeNode') -> None:
        self.parent_node = node

    def get_child_nodes(self) …

我为闭合曲面创建了一个边界八叉树。所有包含表面的八叉树立方体都被划分到相同的级别。因此所有叶节点的大小相同。我需要帮助找出每个终端立方体的邻居。我尝试参考不同的论文，但无法弄清楚如何在 Matlab 中实际实现它。现在，我将所有终端立方体视为体素立方体（不使用八叉树数据结构），并使用强力找出 26 个可能的邻居中的哪些位于构成表面的立方体列表中。需要很长时间才能获得输出。我是编程新手，所以如果有人能提出更有效地找到叶节点邻居的方法以及如何通过在 matlab 中编码来实现该方法，我将非常感激。谢谢！！

我在网上搜索了一个关于Octree Container如何工作的解释.我找不到任何有效的解释.(至少,这对我有意义......)有谁知道如何实现八叉树容器？一个有8个孩子(左右).如果是这样,你介意分享/解释逻辑......或者我可以去哪里学习如何实现它.

第一次在这里发布，但我已经阅读了几年的网站。我正在尝试在C＃中实现一个简单的通用类型Octree（使用一些XNA包含项）。我已经进行了深入的研究，并且理解了这个概念，但似乎无法使其实用。到处搜索会产生其他语言的一些实现，但是它们似乎都是针对特定应用定制的。而且我还真的无法从这些事情中获得多大意义。

下面是到目前为止的Octree类，Vector3，BoundingBox和ContainmentType来自XNA。我输入最大和最小点，以及边界内的点列表。但是，实际上没有任何点添加到树中。任何帮助将非常感激！

public class Octree<T> : ISerializable
{   
    Vector3 max;
    Vector3 min;
    OctreeNode head;

    public Octree(Vector3 min, Vector3 max, List<Vector3> values)
    {
        this.max = max;
        this.min = min;
        head = new OctreeNode( min, max,  values);           
    }

    public Octree() { }

    public Octree(SerializationInfo info, StreamingContext context)
    {
    }

    public void GetObjectData(SerializationInfo info, StreamingContext context)
    {            
    }

    internal class OctreeNode
    {            
        Vector3 max;
        Vector3 min;
        Vector3 center;
        public Vector3 position;
        public T data;

        public BoundingBox nodeBox;
        public List<OctreeNode> subNodes;
        public OctreeNode( Vector3 …

我很难掌握如何迭代八叉树或四叉树。这可能是因为我没有经历过不同的迭代神话。但是让 \xe2\x80\x99s 假设我生成了一个包含 float x,y,z 的四叉树；双字颜色。现在，让\xe2\x80\x99s也说这个节点一次只能产生4个子节点（并且这些子节点都可以产生4个子节点，等等），直到：达到7个级别（这样子节点可以\xe2 \x80\x99 不再创建子节点，但其兄弟/姐妹可以），创建的所有 4 个子节点具有相同的双字颜色（同样，如果发生这种情况，其兄弟/姐妹仍然可以生成），或者创建的节点总数等于 87380。当发生上述情况时，将其放入容器中。这个过程还在继续。

现在，这个保存节点的容器（例如）有 7 层深，子级的子级的子级的所有子级都有不同的 x、y、z 和颜色。我遇到的问题是如何迭代这个容器，如何遍历所有的孩子，姐妹？由于根导致 4 个子节点，而这 4 个子节点又有 4 个子节点，依此类推：4^1+4^2....+4^7。如何找到我想要的节点，而不编写复杂的 if 语句，并迭代整个节点（从根开始）？容器（生成节点的容器）是否需要额外的代码来简化这一过程？

抱歉，如果问题很笼统。

我有一个八叉树,它存储一个基于体素的液体.当我模拟流体时,我需要访问当前节点周围的树叶,我该如何实现这样的搜索？

您可以假设节点存储指向其父节点的指针.(可能还需要其他数据？)