官方參考地址：CloudCompare octree - CloudCompareWiki

CC的octree算法主要體現在DgmOctree.h和DgmOctree.cpp中，他采用了一種分級的結構，最大支持21級，如下，

static const int MAX_OCTREE_LEVEL = 21;

然后，會事先計算得到一個分級表，

預先計算好的數據表

CC這么做的原因是，把事先能計算好的數據先存儲起來，用空間換時間的辦法，來加速運算速度。

(1) PRE_COMPUTED_BIT_SHIFT_VALUES

//! Pre-computed bit shift values (one for each level) struct BitShiftValues {//! Default initializationBitShiftValues(){//we compute all possible valuesfor (unsigned char level = 0; level <= DgmOctree::MAX_OCTREE_LEVEL; ++level){values[level] = (3 * (DgmOctree::MAX_OCTREE_LEVEL - level));}}//! Valuesunsigned char values[DgmOctree::MAX_OCTREE_LEVEL+1]; }; static BitShiftValues PRE_COMPUTED_BIT_SHIFT_VALUES;unsigned char DgmOctree::GET_BIT_SHIFT(unsigned char level) {//return (3 * (DgmOctree::MAX_OCTREE_LEVEL - level));return PRE_COMPUTED_BIT_SHIFT_VALUES.values[level]; }

所以這個value實際相當于這樣一個表，

[0] 63 [1] 60 [2] 57 [3] 54 [4] 51 [5] 48 [6] 45 [7] 42 [8] 39 [9] 36 [10] 33 [11] 30 [12] 27 [13] 24 [14] 21 [15] 18 [16] 15 [17] 12 [18] 9 [19] 6 [20] 3 [21] 0

(2) PRE_COMPUTED_POS_CODES

static const int MAX_OCTREE_LENGTH = (1 << MAX_OCTREE_LEVEL);//! Pre-computed cell codes for all potential cell positions (along a unique dimension) struct MonoDimensionalCellCodes {//! Total number of positions/values/** There are 1024 possible values at level 10, and 2M. at level 21.\warning Never pass a 'constant initializer' by reference**/static const int VALUE_COUNT = DgmOctree::MAX_OCTREE_LENGTH;//! Default initializationMonoDimensionalCellCodes(){//we compute all possible values for cell codes//(along a unique dimension, the other ones are just shifted)for (int value = 0; value < VALUE_COUNT; ++value){int mask = VALUE_COUNT;DgmOctree::CellCode code = 0;for (unsigned char k = 0; k < DgmOctree::MAX_OCTREE_LEVEL; k++){mask >>= 1;code <<= 3;if (value & mask){code |= 1;}}values[value] = code;}//we compute all possible masks as well! (all dimensions)//DgmOctree::CellCode baseMask = (1 << (3 * DgmOctree::MAX_OCTREE_LEVEL));//for (int level = DgmOctree::MAX_OCTREE_LEVEL; level >= 0; --level)//{// masks[level] = baseMask - 1;// baseMask >>= 3;//}}//! Mono-dimensional cell codesDgmOctree::CellCode values[VALUE_COUNT];//! Mono-dimensional cell masks//DgmOctree::CellCode masks[DgmOctree::MAX_OCTREE_LEVEL + 1]; }; static MonoDimensionalCellCodes PRE_COMPUTED_POS_CODES;

這里，MAX_OCTREE_LENGTH == (1<<21) == 2097152 == 0x200000 ，是一個位置的極限值，這個表實際上相當于，

[0] 0 [1] 1 [2] 8 [3] 9 [4] 64 [5] 65 [6] 72 [7] 73 [8] 512 [9] 513 [10] 520 [11] 521 [12] 576 [13] 577 [14] 584 [15] 585 [16] 4096 [17] 4097 [18] 4104 [19] 4105 [20] 4160 [21] 4161 [22] 4168 [23] 4169 [24] 4608 [25] 4609 [26] 4616 [27] 4617 [28] 4672 [29] 4673 [30] 4680 [31] 4681 ......

計算基礎之cellCode

在設計算法之前，我們需要了解一下OcTree層級的概念。

比如我的所有點都在一個64x64x64的立方體內，那第0層級的邊長就是64，也就是最大的cube框的邊長，那么一個立方體包含8個cube框，下一級第1層級框的邊長大小就是64/2，依此類推，再下一級就是64/4，64/8......

另外，給一個相關講解的參考地址，

參考：數據立方體_點云空間數據組織——八叉樹-白紅宇的個人博客

作者對八叉樹進行了講解，我摘錄了其中的一點。如下，

八叉樹將空間分割成八塊，根據2進制， 3位2進制即可表示8個數字，3位中的順序:zyx ，順序區分，從小遞增到大，如： 011，即z為0，x為1，y為 1的塊位置。所以 64位操作系統最多可分割為64/3 = 21級， 32位操作系統最多可分割為32/3 = 10級。

建立單維索引( CellCode)

將原有的1位2進制轉為3位，如：001轉為000 000 001，010 轉為 000 001 000，以此類推。另外兩個維度的code分別左移1位和2位即可。

軟件初始化時就計算完了所有CellCode。

具體可參考前面講到的結構體
static MonoDimensionalCellCodes PRE_COMPUTED_POS_CODES;

好了，前面的這個要怎么理解和使用呢？

比如，我計算得到cellPos=(2,2,2)，那
PRE_COMPUTED_POS_CODES.values[2] == 8 == 000 001 000
假設對應的層級也是21，那么，GenerateTruncatedCellCode中，返回的數據結果就是

return (PRE_COMPUTED_POS_CODES.values[cellPos.x << shift] | (PRE_COMPUTED_POS_CODES.values[cellPos.y << shift] << 1) | (PRE_COMPUTED_POS_CODES.values[cellPos.z << shift] << 2) ) >> GET_BIT_SHIFT(level);

具體可以參考DgmOctree::GenerateTruncatedCellCode函數。
也就是
000 001 000 | 000 001 000 << 1 | 000 001 000 << 2 == 000 111 000

再比如，我計算得到cellPos=(3,3,3)，那
PRE_COMPUTED_POS_CODES.values[3] == 9 == 000 001 001
那么，在21級，相應的cellcode就是
000 001 001 | 000 001 001 << 1 | 000 001 001 << 2 == 000 111 111

又比如，我計算得到cellPos=(4,4,4)，那
PRE_COMPUTED_POS_CODES.values[3] == 64 == 001 000 000
那么，在21級，相應的cellcode就是
001 000 000 | 001 000 000 << 1 | 001 000 000 << 2 == 111 000 000

看出規律了嗎？

作者的意思，就是要設計一個像c++中std::map這樣的一個結構，能夠迅速通過這個cellCode，找到任意層級的cellPos。

例如，前面在第21層級的cellPos=(4,4,4)，到了第20層級，就要右移3位，因為

GET_BIT_SHIFT(20) == 3

不難判斷，這個cellCode對應的cellPos正是(2,2,2)。

好了，有了這些相關基礎知識之后， 我們開始講解點云的八叉樹算法的架構與原理。

ccPointCloud : ccGenericPointCloud

class QCC_DB_LIB_API ccPointCloud : public CCCoreLib::PointCloudTpl<ccGenericPointCloud, QString> { }

這里，ccGenericPointCloud的父類是GenericIndexedCloudPersist

class QCC_DB_LIB_API ccGenericPointCloud : public ccShiftedObject, public CCCoreLib::GenericIndexedCloudPersist {friend class ccMesh;

這是一個純虛類，GenericIndexedCloudPersist，其所有的上級父類也都是純虛類，或者說是接口，包括GenericIndexedCloud，GenericIndexedCloud， 以及GenericCloud，

class CC_CORE_LIB_API GenericIndexedCloudPersist : virtual public GenericIndexedCloud {...... }class CC_CORE_LIB_API GenericIndexedCloud : virtual public GenericCloud {...... }class CC_CORE_LIB_API GenericCloud{...... }

計算過程（程序結構）

當在CloudCompare中按下Edit-->Octree-->Compute之后，就會啟動ocTree的計算，

void MainWindow::doActionComputeOctree() {if ( !ccEntityAction::computeOctree(m_selectedEntities, this) )return;refreshAll();updateUI(); }

computeOctree會對所有選中的實際進行計算，在該函數中，先是得到entity的點云clouds，然后逐個對其進行計算，octree = cloud->computeOctree(..)，或者直接生成octree = ccOctree::Shared(new ccOctree(cloud))，

bool computeOctree(const ccHObject::Container &selectedEntities, QWidget* parent) {for (ccHObject* ent : selectedEntities){......ccGenericPointCloud* cloud = ccHObjectCaster::ToGenericPointCloud(ent, &lockedVertices);......clouds.insert(cloud);......}.......for (const auto cloud : clouds){......switch (coDlg.getMode()){case ccComputeOctreeDlg::DEFAULT:octree = cloud->computeOctree(&pDlg);break;case ccComputeOctreeDlg::MIN_CELL_SIZE:case ccComputeOctreeDlg::CUSTOM_BBOX:{......octree = ccOctree::Shared(new ccOctree(cloud));......}break;}}...... }

接下，調用ccGenericPointCloud::computeOctree，

ccOctree::Shared ccGenericPointCloud::computeOctree(CCCoreLib::GenericProgressCallback* progressCb, bool autoAddChild/*=true*/) {deleteOctree();ccOctree::Shared octree = ccOctree::Shared(new ccOctree(this));if (octree->build(progressCb) > 0){setOctree(octree, autoAddChild);}else{octree.clear();}return octree; }

在這里面，會先new出一個ccOcTree，并把this也就是ccGenericPointCloud傳入進去給m_theAssociatedCloud，然后通過build進行octree的計算，

int DgmOctree::build(GenericProgressCallback* progressCb) {if (!m_theAssociatedCloud){assert(false);return -1;}if (!m_thePointsAndTheirCellCodes.empty()){clear();}m_theAssociatedCloud->getBoundingBox(m_pointsMin, m_pointsMax);m_dimMin = m_pointsMin;m_dimMax = m_pointsMax;//we make this bounding-box cubical (+0.1% growth to avoid round-off issues when projecting points in the octree)CCMiscTools::MakeMinAndMaxCubical(m_dimMin, m_dimMax, 0.001);return genericBuild(progressCb); }

這里要注意，ccOctree的父類正是DgmOctree，

class QCC_DB_LIB_API ccOctree : public QObject, public CCCoreLib::DgmOctree

計算OcTree

結構體IndexAndCode中，給出的是點的index和所在的cube的code，大體上是這樣定義的，

struct IndexAndCode{//! indexunsigned theIndex;//! cell codeCellCode theCode;......}using cellsContainer = std::vector<IndexAndCode>;//! The coded octree structurecellsContainer m_thePointsAndTheirCellCodes;

接下來我們看一下DgmOctree::genericBuild函數的主體，

int DgmOctree::genericBuild(GenericProgressCallback* progressCb) {......try{m_thePointsAndTheirCellCodes.resize(pointCount); }......updateCellSizeTable();//for all pointscellsContainer::iterator it = m_thePointsAndTheirCellCodes.begin();for (unsigned i = 0; i < pointCount; i++){const CCVector3* P = m_theAssociatedCloud->getPoint(i);//does the point falls in the 'accepted points' box?//(potentially different from the octree box - see DgmOctree::build)if ( (P->x >= m_pointsMin[0]) && (P->x <= m_pointsMax[0])&& (P->y >= m_pointsMin[1]) && (P->y <= m_pointsMax[1])&& (P->z >= m_pointsMin[2]) && (P->z <= m_pointsMax[2]) ){//compute the position of the cell that includes this pointTuple3i cellPos;getTheCellPosWhichIncludesThePoint(P, cellPos);......it->theIndex = i;it->theCode = GenerateTruncatedCellCode(cellPos, MAX_OCTREE_LEVEL);......++it;++m_numberOfProjectedPoints;}......//we sort the 'cells' by ascending code orderParallelSort(m_thePointsAndTheirCellCodes.begin(), m_thePointsAndTheirCellCodes.end(), IndexAndCode::codeComp);//update the pre-computed 'number of cells per level of subdivision' arrayupdateCellCountTable();...... }

下面我們來看這個函數是如何計算octree的，

(1) 函數中先是通過m_thePointsAndTheirCellCodes.resize分配內存，

m_thePointsAndTheirCellCodes.resize(pointCount);

（2）然后，通過updateCellSizeTable不斷分割尺寸，得到每一級cube框的大小，例如，假設最大的框的邊長為64，那么一個立方體包含8個cube框，下一級框的邊長大小就是64/2，依此類推，再下一級就是64/4，64/8......

void DgmOctree::updateCellSizeTable() {//update the cell dimension for each subdivision levelm_cellSize[0] = m_dimMax.x - m_dimMin.x;unsigned long long d = 1;for (int k = 1; k <= MAX_OCTREE_LEVEL; k++){d <<= 1;m_cellSize[k] = m_cellSize[0] / d;} }

然后，函數開始逐個點逐個點地計算。

(3) 通過getTheCellPosWhichIncludesThePoint計算點的cellPos。這里的cellPos是指最小的cube的序號，和前面的講解一樣，假設0級cell大小是64，那么第20級的cell大小就是cs = 64/2^20 = 0.00006103515625，那么在某個維度上其序號就是(x-xmin)/cs，如下，

//! Type of the coordinates of a (N-D) point using PointCoordinateType = float;//! Returns the position FOR THE DEEPEST LEVEL OF SUBDIVISION of the cell that includes a given point/** The cell coordinates can be negative or greater than 2^MAX_OCTREE_LEVEL-1as the point can lie outside the octree bounding-box.\param thePoint the query point\param cellPos the computed position**/ inline void getTheCellPosWhichIncludesThePoint(const CCVector3* thePoint, Tuple3i& cellPos) const {const PointCoordinateType& cs = getCellSize(MAX_OCTREE_LEVEL);//DGM: if we admit that cs >= 0, then the 'floor' operator is useless (int cast = truncation)cellPos.x = static_cast<int>(/*floor*/(thePoint->x - m_dimMin.x) / cs);cellPos.y = static_cast<int>(/*floor*/(thePoint->y - m_dimMin.y) / cs);cellPos.z = static_cast<int>(/*floor*/(thePoint->z - m_dimMin.z) / cs); }

(4) 獲取點的cellCode，

這個，是我們在基礎部分講過的函數DgmOctree::GenerateTruncatedCellCode，

DgmOctree::CellCode DgmOctree::GenerateTruncatedCellCode(const Tuple3i& cellPos, unsigned char level) {assert(cellPos.x >= 0 && cellPos.x < MonoDimensionalCellCodes::VALUE_COUNT&&cellPos.y >= 0 && cellPos.y < MonoDimensionalCellCodes::VALUE_COUNT&&cellPos.z >= 0 && cellPos.z < MonoDimensionalCellCodes::VALUE_COUNT);const unsigned char shift = MAX_OCTREE_LEVEL - level;return(PRE_COMPUTED_POS_CODES.values[cellPos.x << shift]|(PRE_COMPUTED_POS_CODES.values[cellPos.y << shift] << 1)|(PRE_COMPUTED_POS_CODES.values[cellPos.z << shift] << 2)) >> GET_BIT_SHIFT(level); }

(5)按cellCode大小排序

ParallelSort(m_thePointsAndTheirCellCodes.begin(), m_thePointsAndTheirCellCodes.end(), IndexAndCode::codeComp);

值得說明的是，在函數中，對變量m_fillIndexes也進行了計算，因為源碼比較簡單，一目了然，這里就不展開講了。

本文結束。

總結

以上是生活随笔為你收集整理的CloudCompare源码分析_八叉树（Octree）算法基础CC中的八叉树结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。