CloudCompare中DgmOctree结构的分析

CloudCompare中使用DgmOctree作为八叉树数据结构。具体实现过程如下&＃xff1a;

如上图所示&＃xff0c;使用3个bit位存储当前级别中点在八叉树的位置。3位中的顺序:zyx顺序区分。从小递增到大。

011表示的是在当前level中的位置。

64位编译环境时&＃xff1a;最高允许有21层次的分割&＃xff0c;32位编译环境时&＃xff1a;最高允许有10层次的分割。

&＃xff08;1&＃xff09;CellCode的定义

#ifdef OCTREE_CODES_64_BITS

    using CellCode &＃61; unsigned long long; //max 21 levels (but twice more memory!)

#else

    using CellCode &＃61; unsigned; //max 10 levels

#endif

对于最高21层次的分割&＃xff0c;每层需要3个bit存储其在当前层次的位置&＃xff0c;故21*3&＃61;63bit存储其当前的CellCode

&＃xff08;2&＃xff09;CellCode的编码初始化

这个步骤主要是建立单维上坐标&＃xff08;x或y或z&＃xff09;和CellCode的映射关系

具体映射方法如下&＃xff1a;

将原有的value按位&＃xff0c;扩充至3位。

CellCode是按照低级别在高位&＃xff0c;高级别在低位方式存储。对于64位编译环境&＃xff0c;一个CellCode对应long long结构&＃xff0c;存储了1-N的所有信息。

&＃xff08;3&＃xff09;CellPos分析

CellPos存储的是当前最高级别划分下的对应xyz坐标系中的坐标。由于是最高级别下的坐标&＃xff0c;所以其最大值不会超过2^21(64位编译环境下)

&＃xff08;4&＃xff09;CellPos和CellCode的转换

建立DgmOctree的时候&＃xff0c;dec一直为0。其表示的是处于MAX_OCTREE_LEVEL级别时的CellCode。

当dec不为0时候&＃xff0c;其表示的是当前传入的level下的CellCode。

上述是按照zyx样式bit组合顺序&＃xff0c;将三维的CellCode组合起来。

&＃xff08;5&＃xff09;CloudCompare中Octree的使用

菜单栏Edit > Octree > Compute

勾选Octree显示&＃xff0c;切换显示级别&＃xff0c;可显示当前level下的外廓线

参考

[1] https://www.cloudcompare.org/doc/wiki/index.php?title&＃61;CloudCompare_octree