XT Document

User Tools

Site Tools

Trace: • octree
class:kernel:octree

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

Public interface

Private interface

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: 无
class/kernel/octree.txt · Last modified: 2020/06/20 22:43 (external edit)

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki