====== 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 * [[octree#m_pleafpool|m_pLeafPool]]
  * MemPool * [[octree#m_phashpool|m_pHashPool]]
  * OctantHash * [[octree#m_poctanthash|m_pOctantHash]]
  * int [[octree#m_ilevelcount[max_octree_level]|m_iLevelCount[MAX_OCTREE_LEVEL]]]
  * int [[octree#m_imaxlevel|m_iMaxLevel]]
  * int [[octree#m_ioptlevel|m_iOptLevel]]
  * double [[octree#m_dboundbox[6]|m_dBoundbox[6]]]
  * double [[octree#m_dstep[3]|m_dStep[3]]]
  * PosGetter [[octree#m_pfgetpos|m_pfGetPos]]
**//Public interface//**
  * [[octree#octree1|Octree]](ulong size,double * boundary,PosGetter func )
  * void	[[octree#insertdata|insertData]](void * pData)
  * void	[[octree#removedata|removeData]](void * pData)
  * void	[[octree#insertdata|insertData]](double * pos,void * pData)
  * void *	[[octree#searchdata|searchData]](double * pos)
  * void *	[[octree#searchnearestdata|searchNearestData]](double * pos)
  * void	[[octree#searchadjacentdata|searchAdjacentData]](double * pos, double radius, LinkList * pTgts,bool bSort = false)
  * void	[[octree#removedata|removeData]](double * pos,void * pData)
  * void	[[octree#updateoptimicaldepth|updateOptimicalDepth]]()
  * void	[[octree#clear|clear]]()
  * void	[[octree#test|test]]()
**//Private interface//**
  * void	[[octree#insertrootleaf|insertRootLeaf]]()
  * ulong	[[octree#getmortonkey|getMortonKey]](double * pos,int level = MAX_OCTREE_LEVEL)
  * int		[[octree#getdepth|getDepth]](ulong key)
  * void	[[octree#appenddata|appendData]](OctreeLeaf * pLeaf, void * pData)
  * void	[[octree#removedata|removeData]](ulong key,void * pData)
  * void	[[octree#removeleaf|removeLeaf]](ulong key)
  * void	[[octree#splitleaf|splitLeaf]](OctreeLeaf * pLeaf)
  * void	[[octree#searchdata|searchData]](ulong key, LinkList * pTgts)
  * void	[[octree#searchdatainradius|searchDataInradius]](ulong key, double * pos,double radius,LinkList * pTgts)
  * void	[[octree#searchsortdatainradius|searchSortDataInradius]](ulong key, double * pos,double radius,LinkList * pTgts)
  * ulong	[[octree#truncatekey|truncateKey]](ulong key,int level)
  * void	[[octree#getindex|getIndex]](ulong key,int* index)
  * OctreeLeaf * [[octree#createleaf|createLeaf]](ulong key,void * pData)
  * int		[[octree#getchildcount|getChildCount]](ulong key)
  * void	[[octree#getcenterbykey|getCenterByKey]](ulong key,double * pos)

----

{{anchor:m_pleafpool}}
**MemPool * m_pLeafPool**

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

{{anchor:m_phashpool}}
**MemPool * m_pHashPool**

用于分配Hash节点的内存池

{{anchor:m_poctanthash}}
**OctantHash * m_pOctantHash**

叶节点Hash

{{anchor:m_ilevelcount[max_octree_level]}}
**int m_iLevelCount[MAX_OCTREE_LEVEL]**

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

{{anchor:m_imaxlevel}}
**int m_iMaxLevel**

最大深度

{{anchor:m_ioptlevel}}
**int m_iOptLevel**

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

{{anchor:m_dboundbox[6]}}
**double m_dBoundbox[6]**

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

{{anchor:m_dstep[3]}}
**double m_dStep[3]**

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

{{anchor:m_pfgetpos}}
**PosGetter m_pfGetPos**

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

----

{{anchor:octree1}}
**Octree(ulong size,double * boundary,PosGetter func )**
  *function: 构建元素规模为size，边界为boundary的八叉树空间，坐标计算函数为func
  *parameters: 
    - [i]ulong size: 元素规模
    - [i]double * boundary: 空间边界
    - [i]PosGetter func : 坐标计算函数
  *return value: 无

{{anchor:insertdata}}
**void	insertData(void * pData)**
  *function: 插入元素
  *parameters: 
    - [i]void * pData: 元素指针 
  *return value: 无

{{anchor:removedata}}
**void	removeData(void * pData)**
  *function: 删除元素
  *parameters: 
    - [i]void * pData: 元素指针 
  *return value: 无

{{anchor:insertdata}}
**void	insertData(double * pos,void * pData)**
  *function: 插入坐标为pos的元素pData
  *parameters: 
    - [i]double * pos: 元素pData对应的坐标
    - [i]void * pData: 元素指针
  *return value: 无

{{anchor:searchdata}}
**void *	searchData(double * pos)**
  *function: 搜索在位置pos上的元素
  *parameters: 
    - [i]double * pos: 位置坐标
  *return value: 如在最大深度上对应于pos的叶节点存在则返回该叶节点的第一个元素，否则返回0

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

{{anchor:searchadjacentdata}}
**void	searchAdjacentData(double * pos, double radius, LinkList * pTgts,bool bSort = false)**
  *function: 搜索相邻元素
  *parameters: 
    - [i]double * pos: 位置坐标
    - [i] double radius: 搜索半径
    - [i] LinkList * pTgts: 存放相邻元素的链表
    - [i]bool bSort = false: 对否对相邻元素按照距离进行排序，默认否
  *return value: 无

{{anchor:removedata}}
**void	removeData(double * pos,void * pData)**
  *function: 删除在位置pos的元素pData（如存在）
  *parameters: 
    - [i]double * pos: 位置坐标
    - [i]void * pData: 元素指针
  *return value: 无

{{anchor:updateoptimicaldepth}}
**void	updateOptimicalDepth()**
  *function: 计算更新最佳深度（优化深度）
  *parameters: NULL
  *return value: 无

{{anchor:clear}}
**void	clear()**
  *function: 清除所有元素
  *parameters: NULL
  *return value: 无

----

{{anchor:insertrootleaf}}
**void	insertRootLeaf()**
  *function: 插入根节点
  *parameters: NULL
  *return value: 无

{{anchor:getmortonkey}}
**ulong	getMortonKey(double * pos,int level = MAX_OCTREE_LEVEL)**
  *function: 按最大层次level计算位置pos的morton码
  *parameters: 
    - [i]double * pos: 位置坐标
    - [i]int level = MAX_OCTREE_LEVEL: 最大深度，默认为10，不能比10大
  *return value: pos对应的Morton码

{{anchor:getdepth}}
**int		getDepth(ulong key)**
  *function: 获取Morton码的深度值
  *parameters: 
    - [i]ulong key: Morton码
  *return value: 

{{anchor:appenddata}}
**void	appendData(OctreeLeaf * pLeaf, void * pData)**
  *function: 将元素添加到叶节点pLeaf上
  *parameters: 
    - [i]OctreeLeaf * pLeaf: 叶节点
    - [i] void * pData: 待添加的元素，元素的坐标需与pLeaf相容
  *return value: 无

{{anchor:removedata}}
**void	removeData(ulong key,void * pData)**
  *function: 从Morton编码为key的叶节点中删除元素pData
  *parameters: 
    - [i]ulong key: 叶节点的Morton码
    - [i]void * pData: 元素指针
  *return value: 无

{{anchor:removeleaf}}
**void	removeLeaf(ulong key)**
  *function: 删除Morton码为key的叶节点以及属于它的更低层次的所有叶节点
  *parameters: 
    - [i]ulong key: Morton码
  *return value: 无

{{anchor:splitleaf}}
**void	splitLeaf(OctreeLeaf * pLeaf)**
  *function: 将叶节点细分使当前节点的元素深度加1
  *parameters: 
    - [i]OctreeLeaf * pLeaf: 待细分的叶节点
  *return value: 无

{{anchor:searchdata}}
**void	searchData(ulong key, LinkList * pTgts)**
  *function: 从key所属的子空间开始往下搜索所有的元素
  *parameters: 
    - [i]ulong key: Morton码
    - [i] LinkList * pTgts: 搜索得到的元素放入到此链表中
  *return value: 无

{{anchor:searchdatainradius}}
**void	searchDataInradius(ulong key, double * pos,double radius,LinkList * pTgts)**
  *function: 从key开始往下搜索离pos距离radius以内的所有元素
  *parameters: 
    - [i]ulong key: Morton码
    - [i] double * pos: 位置坐标
    - [i]double radius: 搜索半径
    - [i]LinkList * pTgts: 目标元素放入到此链表中
  *return value: 无

{{anchor:searchsortdatainradius}}
**void	searchSortDataInradius(ulong key, double * pos,double radius,LinkList * pTgts)**
  *function: 
  *parameters: 
    - [i]ulong key: 
    - [i] double * pos: 
    - [i]double radius: 
    - [i]LinkList * pTgts: 
  *return value: 

{{anchor:truncatekey}}
**ulong	truncateKey(ulong key,int level)**
  *function: 按深度level截断key形成新的Morton码
  *parameters: 
    - [i]ulong key: Morton码
    - [i]int level: 深度
  *return value: 新的Morton码

{{anchor:getindex}}
**void	getIndex(ulong key,int* index)**
  *function: 将Morton码转化为以m_dStep为步长的索引值
  *parameters: 
    - [i]ulong key: Morton码
    - [i]int* index: 0-base索引值
  *return value: 无

{{anchor:createleaf}}
**OctreeLeaf * createLeaf(ulong key,void * pData)**
  *function: 创建Morton码为key的叶节点，并将元素pData加入到该叶节点中
  *parameters: 
    - [i]ulong key: Morton码
    - [i]void * pData: 元素，元素的坐标需与Morton码相容
  *return value: 叶节点指针

{{anchor:getchildcount}}
**int		getChildCount(ulong key)**
  *function: 获取Morton码为key的子空间所包含的所有元素个数
  *parameters: 
    - [i]ulong key: Morton码
  *return value: 元素个数

{{anchor:getcenterbykey}}
**void	getCenterByKey(ulong key,double * pos)**
  *function: 获取Morton码为key的子空间的中心坐标
  *parameters: 
    - [i]ulong key: Morton码
    - [i]double * pos: Morton码为key的子空间的中心坐标
  *return value: 无