Octree

Inherited from NULL

Inherited by NULL

Friend class NULL

Description

Octree将空间按照八叉树的结构进行递归的细分，使用Morton码对位置坐标进行编码，从而可以快速的定位和对邻域空间的遍历与搜索(被Octree管理的数据元素必须提供计算坐标的回调函数)。Octree拥有一个唯一的根节点（深度为0），在空间里该节点可以均分为8个子空间（深度为1），即X、Y、Z均分成两部分，每个方向可以用0和1分别标识两个部分，因而可以用000到111的二进制数分别对子空间编码，这个编码即对应的Morton码，而每个子空间又可以均分为8个子空间，每个子空间在上一级的Morton码基础上再增加三位二进制数形成对应的Morton码，这样递归下去（深度逐级增加）可以按最大深度对每个子空间进行编码。Octree只对添加进来的数据创建相应的子空间（即叶节点），所以Octree比较节省内存。

Members

• MemPool * m_pLeafPool
• MemPool * m_pHashPool
• OctantHash * m_pOctantHash
• int m_iLevelCount[MAX_OCTREE_LEVEL]
• int m_iMaxLevel
• int m_iOptLevel
• double m_dBoundbox[6]
• double m_dStep[3]
• PosGetter m_pfGetPos

Public interface

• Octree(ulong size,double * boundary,PosGetter func )
• void insertData(void * pData)
• void removeData(void * pData)
• void insertData(double * pos,void * pData)
• void * searchData(double * pos)
• void * searchNearestData(double * pos)
• void searchAdjacentData(double * pos, double radius, LinkList * pTgts,bool bSort = false)
• void removeData(double * pos,void * pData)
• void updateOptimicalDepth()
• void clear()
• void test()

Private interface

• void insertRootLeaf()
• ulong getMortonKey(double * pos,int level = MAX_OCTREE_LEVEL)
• int getDepth(ulong key)
• void appendData(OctreeLeaf * pLeaf, void * pData)
• void removeData(ulong key,void * pData)
• void removeLeaf(ulong key)
• void splitLeaf(OctreeLeaf * pLeaf)
• void searchData(ulong key, LinkList * pTgts)
• void searchDataInradius(ulong key, double * pos,double radius,LinkList * pTgts)
• void searchSortDataInradius(ulong key, double * pos,double radius,LinkList * pTgts)
• ulong truncateKey(ulong key,int level)
• void getIndex(ulong key,int* index)
• OctreeLeaf * createLeaf(ulong key,void * pData)
• int getChildCount(ulong key)
• void getCenterByKey(ulong key,double * pos)

---

MemPool * m_pLeafPool

用于分配叶节点内存的内存池

MemPool * m_pHashPool

用于分配Hash节点的内存池

OctantHash * m_pOctantHash

叶节点Hash

int m_iLevelCount[MAX_OCTREE_LEVEL]

统计每个深度的数据个数的数组

int m_iMaxLevel

最大深度

int m_iOptLevel

优化深度，一般在这个深度的元素个数最多

double m_dBoundbox[6]

Octree所占据的立方体空间的两个角点

double m_dStep[3]

子空间按最大深度在三个方向的步长

PosGetter m_pfGetPos

用于计算元素坐标的回调函数

---

Octree(ulong size,double * boundary,PosGetter func )

• function: 构建元素规模为size，边界为boundary的八叉树空间，坐标计算函数为func
• parameters:
  1. [i]ulong size: 元素规模
  2. [i]double * boundary: 空间边界
  3. [i]PosGetter func : 坐标计算函数
• return value: 无

void insertData(void * pData)

• function: 插入元素
• parameters:
  1. [i]void * pData: 元素指针
• return value: 无

void removeData(void * pData)

• function: 删除元素
• parameters:
  1. [i]void * pData: 元素指针
• return value: 无

void insertData(double * pos,void * pData)

• function: 插入坐标为pos的元素pData
• parameters:
  1. [i]double * pos: 元素pData对应的坐标
  2. [i]void * pData: 元素指针
• return value: 无

void * searchData(double * pos)

• function: 搜索在位置pos上的元素
• parameters:
  1. [i]double * pos: 位置坐标
• return value: 如在最大深度上对应于pos的叶节点存在则返回该叶节点的第一个元素，否则返回0

void * searchNearestData(double * pos)

• function: 搜索离位置pos最近的元素
• parameters:
  1. [i]double * pos: 位置坐标
• return value: 在优化深度，如pos的领域（-1，1）的空间里存在元素，返回其中最近的元素，否则返回0

void searchAdjacentData(double * pos, double radius, LinkList * pTgts,bool bSort = false)

• function: 搜索相邻元素
• parameters:
  1. [i]double * pos: 位置坐标
  2. [i] double radius: 搜索半径
  3. [i] LinkList * pTgts: 存放相邻元素的链表
  4. [i]bool bSort = false: 对否对相邻元素按照距离进行排序，默认否
• return value: 无

void removeData(double * pos,void * pData)

• function: 删除在位置pos的元素pData（如存在）
• parameters:
  1. [i]double * pos: 位置坐标
  2. [i]void * pData: 元素指针
• return value: 无

void updateOptimicalDepth()

• function: 计算更新最佳深度（优化深度）
• parameters: NULL
• return value: 无

void clear()

• function: 清除所有元素
• parameters: NULL
• return value: 无

---

void insertRootLeaf()

• function: 插入根节点
• parameters: NULL
• return value: 无

ulong getMortonKey(double * pos,int level = MAX_OCTREE_LEVEL)

• function: 按最大层次level计算位置pos的morton码
• parameters:
  1. [i]double * pos: 位置坐标
  2. [i]int level = MAX_OCTREE_LEVEL: 最大深度，默认为10，不能比10大
• return value: pos对应的Morton码

int getDepth(ulong key)

• function: 获取Morton码的深度值
• parameters:
  1. [i]ulong key: Morton码
• return value:

void appendData(OctreeLeaf * pLeaf, void * pData)

• function: 将元素添加到叶节点pLeaf上
• parameters:
  1. [i]OctreeLeaf * pLeaf: 叶节点
  2. [i] void * pData: 待添加的元素，元素的坐标需与pLeaf相容
• return value: 无

void removeData(ulong key,void * pData)

• function: 从Morton编码为key的叶节点中删除元素pData
• parameters:
  1. [i]ulong key: 叶节点的Morton码
  2. [i]void * pData: 元素指针
• return value: 无

void removeLeaf(ulong key)

• function: 删除Morton码为key的叶节点以及属于它的更低层次的所有叶节点
• parameters:
  1. [i]ulong key: Morton码
• return value: 无

void splitLeaf(OctreeLeaf * pLeaf)

• function: 将叶节点细分使当前节点的元素深度加1
• parameters:
  1. [i]OctreeLeaf * pLeaf: 待细分的叶节点
• return value: 无

void searchData(ulong key, LinkList * pTgts)

• function: 从key所属的子空间开始往下搜索所有的元素
• parameters:
  1. [i]ulong key: Morton码
  2. [i] LinkList * pTgts: 搜索得到的元素放入到此链表中
• return value: 无

void searchDataInradius(ulong key, double * pos,double radius,LinkList * pTgts)

• function: 从key开始往下搜索离pos距离radius以内的所有元素
• parameters:
  1. [i]ulong key: Morton码
  2. [i] double * pos: 位置坐标
  3. [i]double radius: 搜索半径
  4. [i]LinkList * pTgts: 目标元素放入到此链表中
• return value: 无

void searchSortDataInradius(ulong key, double * pos,double radius,LinkList * pTgts)

• function:
• parameters:
  1. [i]ulong key:
  2. [i] double * pos:
  3. [i]double radius:
  4. [i]LinkList * pTgts:
• return value:

ulong truncateKey(ulong key,int level)

• function: 按深度level截断key形成新的Morton码
• parameters:
  1. [i]ulong key: Morton码
  2. [i]int level: 深度
• return value: 新的Morton码

void getIndex(ulong key,int* index)

• function: 将Morton码转化为以m_dStep为步长的索引值
• parameters:
  1. [i]ulong key: Morton码
  2. [i]int* index: 0-base索引值
• return value: 无

OctreeLeaf * createLeaf(ulong key,void * pData)

• function: 创建Morton码为key的叶节点，并将元素pData加入到该叶节点中
• parameters:
  1. [i]ulong key: Morton码
  2. [i]void * pData: 元素，元素的坐标需与Morton码相容
• return value: 叶节点指针

int getChildCount(ulong key)

• function: 获取Morton码为key的子空间所包含的所有元素个数
• parameters:
  1. [i]ulong key: Morton码
• return value: 元素个数

void getCenterByKey(ulong key,double * pos)

• function: 获取Morton码为key的子空间的中心坐标
• parameters:
  1. [i]ulong key: Morton码
  2. [i]double * pos: Morton码为key的子空间的中心坐标
• return value: 无