CloudCompare源码分析_八叉树（Octree）算法基础CC中的八叉树结构

官方参考地址：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 initialization
    BitShiftValues()
    {
        //we compute all possible values
        for (unsigned char level = 0; level = 1;
                code = 3;
        //}
    }

    //! Mono-dimensional cell codes
    DgmOctree::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 == (1x y >= m_pointsMin[1]) && (P->y z >= m_pointsMin[2]) && (P->z theIndex = i; it->theCode = GenerateTruncatedCellCode(cellPos, MAX_OCTREE_LEVEL); ...... ++it; ++m_numberOfProjectedPoints; } ...... //we sort the 'cells' by ascending code order ParallelSort(m_thePointsAndTheirCellCodes.begin(), m_thePointsAndTheirCellCodes.end(), IndexAndCode::codeComp); //update the pre-computed 'number of cells per level of subdivision' array updateCellCountTable(); ...... }

下面我们来看这个函数是如何计算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 level
    m_cellSize[0] = m_dimMax.x - m_dimMin.x;

    unsigned long long d = 1;
    for (int k = 1; k y - m_dimMin.y) / cs);
    cellPos.z = static_cast(/*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