Expand description
高性能的松散叉树
Modules§
- oct_
helper - 八叉相关接口
- quad_
helper - 四叉相关接口
- tilemap
- 瓦片地图，可在瓦片内放多个id的AABB。 要求插入AABB节点时的id， 应该是slotmap的Key。 内部使用SecondaryMap来存储链表，这样内存连续，瓦片地图本身就可以快速拷贝。 通过AABB的中心点计算落在哪个瓦片内，可以查询该瓦片内所有的节点。 AABB的范围相交查询时，需要根据最大节点的大小，扩大相应范围，这样如果边界上有节点，也可以被查到相交。
- tree
- 高性能的松散叉树 采用二进制掩码 表达xyz的大小， child&1 == 0 表示x为小，否则为大。 采用Slab，内部用偏移量来分配八叉空间。这样内存连续，八叉树本身可以快速拷贝。 要求插入AABB节点时的id， 应该是可以用在数组索引上的。 分裂和收缩： ChildNode的Branch(BranchKey), 如果BranchKey对应八叉空间下的节点总数量小于收缩阈值，则可以收缩成ChildNode的Ab(List) ChildNode的Ab(List), 如果List中节点的数量大于分裂阈值，则也可以分裂成Branch(BranchKey) 收缩阈值一般为4，分裂阈值一般为8。 在这个结构下，不会出现反复分裂和收缩。 如果一组节点重叠，并且超过6，则会导致会分裂到节点所能到达的最低的层，应用方应该尽量避免这种情况 更新aabb： 节点只会在3个位置： 1. 如果超出或相交边界，则在tree.outer上 这种情况下，node.parent为null 2. 如果节点大小下不去，则只能在本层活动，则在BranchNode的nodes 这种情况下，node.layer==parent.layer. node.parent_child==N 3. 其余的节点都在ChildNode的Ab(List)中 node.layer<parent.layer. node.parent_child<N 更新节点就是在这3个位置上挪动