CCCoreLib 31 May 2022
CloudCompare Core algorithms
|
The octree structure used throughout the library. More...
#include <DgmOctree.h>
Classes | |
struct | BoxNeighbourhood |
Input/output parameters structure for getPointsInBoxNeighbourhood. More... | |
struct | CellDescriptor |
Structure used during nearest neighbour search. More... | |
struct | CylindricalNeighbourhood |
Input/output parameters structure for getPointsInCylindricalNeighbourhood. More... | |
struct | IndexAndCode |
Association between an index and the code of an octree cell. More... | |
struct | NearestNeighboursSearchStruct |
Container of in/out parameters for nearest neighbour(s) search. More... | |
struct | octreeCell |
Octree cell descriptor. More... | |
struct | octreeTopDownScanStruct |
Internal structure used to perform a top-down scan of the octree. More... | |
struct | PointDescriptor |
Structure used during nearest neighbour search. More... | |
struct | ProgressiveCylindricalNeighbourhood |
Input/output parameters structure for getPointsInCylindricalNeighbourhoodProgressive. More... | |
Public Types | |
enum | RayCastProcess { RC_NEAREST_POINT , RC_CLOSE_POINTS } |
Ray casting processes. | |
using | CellCode = unsigned |
Type of the code of an octree cell. More... | |
using | cellCodesContainer = std::vector< CellCode > |
Octree cell codes container. | |
using | cellIndexesContainer = std::vector< unsigned int > |
Octree cell indexes container. | |
using | NeighboursSet = std::vector< PointDescriptor > |
A set of neighbours. | |
using | NeighbourCellsSet = std::vector< CellDescriptor > |
A set of neighbour cells descriptors. | |
using | cellsContainer = std::vector< IndexAndCode > |
Container of 'IndexAndCode' structures. | |
using | octreeCellFunc = bool(*)(const octreeCell &, void **, NormalizedProgress *) |
Generic form of a function that can be applied automatically to all cells of the octree. More... | |
Public Member Functions | |
DgmOctree (GenericIndexedCloudPersist *cloud) | |
DgmOctree constructor. More... | |
~DgmOctree () override=default | |
DgmOctree destructor. | |
virtual void | clear () |
Clears the octree. | |
int | build (GenericProgressCallback *progressCb=nullptr) |
Builds the structure. More... | |
int | build (const CCVector3 &octreeMin, const CCVector3 &octreeMax, const CCVector3 *pointsMinFilter=nullptr, const CCVector3 *pointsMaxFilter=nullptr, GenericProgressCallback *progressCb=nullptr) |
Builds the structure with constraints. More... | |
unsigned | getNumberOfProjectedPoints () const |
Returns the number of points projected into the octree. More... | |
const CCVector3 & | getOctreeMins () const |
Returns the lower boundaries of the octree. More... | |
const CCVector3 & | getOctreeMaxs () const |
Returns the higher boundaries of the octree. More... | |
void | getBoundingBox (CCVector3 &bbMin, CCVector3 &bbMax) const |
Returns the octree bounding box. More... | |
const int * | getMinFillIndexes (unsigned char level) const |
Returns the lowest cell positions in the octree along all dimensions and for a given level of subdivision. More... | |
const int * | getMaxFillIndexes (unsigned char level) const |
Returns the highest cell positions in the octree along all dimensions and for a given level of subdivision. More... | |
const PointCoordinateType & | getCellSize (unsigned char level) const |
Returns the octree cells length for a given level of subdivision. More... | |
void | getCellDistanceFromBorders (const Tuple3i &cellPos, unsigned char level, int *cellDists) const |
Returns distance form a cell to the filled octree borders in all directions. More... | |
void | getCellDistanceFromBorders (const Tuple3i &cellPos, unsigned char level, int neighbourhoodLength, int *cellDists) const |
Returns distance from cell center to cell neighbourhood INSIDE filled octree. More... | |
bool | getPointsInCellByCellIndex (ReferenceCloud *cloud, unsigned cellIndex, unsigned char level, bool clearOutputCloud=true) const |
Returns the points lying in a specific cell. More... | |
bool | getPointsInCell (CellCode cellCode, unsigned char level, ReferenceCloud *subset, bool isCodeTruncated=false, bool clearOutputCloud=true) const |
Returns the points lying in a specific cell. More... | |
ReferenceCloud * | getPointsInCellsWithSortedCellCodes (cellCodesContainer &cellCodes, unsigned char level, ReferenceCloud *subset, bool areCodesTruncated=false) const |
Returns the points lying in multiple cells. More... | |
unsigned | findPointNeighbourhood (const CCVector3 *_queryPoint, ReferenceCloud *Yk, unsigned maxNumberOfNeighbors, unsigned char level, double &maxSquareDist, double maxSearchDist=0, int *finalNeighbourhoodSize=nullptr) const |
Finds the nearest neighbours around a query point. More... | |
double | findTheNearestNeighborStartingFromCell (NearestNeighboursSearchStruct &nNSS) const |
Advanced form of the nearest neighbour search algorithm (unique neighbour) More... | |
unsigned | findNearestNeighborsStartingFromCell (NearestNeighboursSearchStruct &nNSS, bool getOnlyPointsWithValidScalar=false) const |
Advanced form of the nearest neighbours search algorithm (multiple neighbours) More... | |
int | findNeighborsInASphereStartingFromCell (NearestNeighboursSearchStruct &nNSS, double radius, bool sortValues=true) const |
Advanced form of the nearest neighbours search algorithm (in a sphere) More... | |
int | getPointsInSphericalNeighbourhood (const CCVector3 &sphereCenter, PointCoordinateType radius, NeighboursSet &neighbours, unsigned char level) const |
Returns the points falling inside a sphere. More... | |
std::size_t | getPointsInCylindricalNeighbourhood (CylindricalNeighbourhood ¶ms) const |
Returns the points falling inside a cylinder. More... | |
std::size_t | getPointsInCylindricalNeighbourhoodProgressive (ProgressiveCylindricalNeighbourhood ¶ms) const |
Same as getPointsInCylindricalNeighbourhood with progressive approach. More... | |
std::size_t | getPointsInBoxNeighbourhood (BoxNeighbourhood ¶ms) const |
Returns the points falling inside a box. More... | |
void | getTheCellPosWhichIncludesThePoint (const CCVector3 *thePoint, Tuple3i &cellPos) const |
Returns the position FOR THE DEEPEST LEVEL OF SUBDIVISION of the cell that includes a given point. More... | |
void | getTheCellPosWhichIncludesThePoint (const CCVector3 *thePoint, Tuple3i &cellPos, unsigned char level) const |
Returns the position for a given level of subdivision of the cell that includes a given point. More... | |
void | getTheCellPosWhichIncludesThePoint (const CCVector3 *thePoint, Tuple3i &cellPos, unsigned char level, bool &inBounds) const |
Returns the position for a given level of subdivision of the cell that includes a given point. More... | |
void | getCellPos (CellCode code, unsigned char level, Tuple3i &cellPos, bool isCodeTruncated) const |
Returns the cell position for a given level of subdivision of a cell designated by its code. More... | |
void | computeCellCenter (CellCode code, unsigned char level, CCVector3 ¢er, bool isCodeTruncated=false) const |
Returns the cell center for a given level of subdivision of a cell designated by its code. More... | |
void | computeCellCenter (const Tuple3i &cellPos, unsigned char level, CCVector3 ¢er) const |
Returns the cell center for a given level of subdivision of a cell designated by its position. More... | |
void | computeCellCenter (const Tuple3s &cellPos, unsigned char level, CCVector3 ¢er) const |
Short version of computeCellCenter. | |
void | computeCellLimits (CellCode code, unsigned char level, CCVector3 &cellMin, CCVector3 &cellMax, bool isCodeTruncated=false) const |
Returns the spatial limits of a given cell. More... | |
unsigned | getCellIndex (CellCode truncatedCellCode, unsigned char bitShift) const |
Returns the index of a given cell represented by its code. More... | |
unsigned char | findBestLevelForAGivenNeighbourhoodSizeExtraction (PointCoordinateType radius) const |
Determines the best level of subdivision of the octree at which to apply the nearest neighbours search algorithm (inside a sphere) depending on the sphere radius. More... | |
unsigned char | findBestLevelForComparisonWithOctree (const DgmOctree *theOtherOctree) const |
Determines the best level of subdivision of the octree at which to apply a cloud-2-cloud distance computation algorithm. More... | |
unsigned char | findBestLevelForAGivenPopulationPerCell (unsigned indicativeNumberOfPointsPerCell) const |
Determines the best subdivision level of the octree that gives the average population per cell closest to the input value. More... | |
unsigned char | findBestLevelForAGivenCellNumber (unsigned indicativeNumberOfCells) const |
Determines the best subdivision level of the octree to match a given number of cells. More... | |
const CellCode & | getCellCode (unsigned index) const |
Returns the ith cell code. | |
bool | getCellCodes (unsigned char level, cellCodesContainer &vec, bool truncatedCodes=false) const |
Returns the list of codes corresponding to the octree cells for a given level of subdivision. More... | |
bool | getCellIndexes (unsigned char level, cellIndexesContainer &vec) const |
Returns the list of indexes corresponding to the octree cells for a given level of subdivision. More... | |
bool | getCellCodesAndIndexes (unsigned char level, cellsContainer &vec, bool truncatedCodes=false) const |
Returns the list of indexes and codes corresponding to the octree cells for a given level of subdivision. More... | |
void | diff (const cellCodesContainer &codesA, const cellCodesContainer &codesB, cellCodesContainer &diffA, cellCodesContainer &diffB) const |
Returns the cells that differ between two octrees (for a same implicit level of subdivision) More... | |
bool | diff (unsigned char octreeLevel, const cellsContainer &codesA, const cellsContainer &codesB, int &diffA, int &diffB, int &cellsA, int &cellsB) const |
Returns the differences (in terms of number of cells) between two octrees for a given level of subdivision. More... | |
const unsigned & | getCellNumber (unsigned char level) const |
Returns the number of cells for a given level of subdivision. | |
double | computeMeanOctreeDensity (unsigned char level) const |
Computes mean octree density (point/cell) at a given level of subdivision. More... | |
int | extractCCs (const cellCodesContainer &cellCodes, unsigned char level, bool sixConnexity, GenericProgressCallback *progressCb=nullptr) const |
Computes the connected components (considering the octree cells only) for a given level of subdivision (partial) More... | |
int | extractCCs (unsigned char level, bool sixConnexity, GenericProgressCallback *progressCb=nullptr) const |
Computes the connected components (considering the octree cells only) for a given level of subdivision (complete) More... | |
unsigned | executeFunctionForAllCellsStartingAtLevel (unsigned char startingLevel, octreeCellFunc func, void **additionalParameters, unsigned minNumberOfPointsPerCell, unsigned maxNumberOfPointsPerCell, bool multiThread=true, GenericProgressCallback *progressCb=nullptr, const char *functionTitle=nullptr, int maxThreadCount=0) |
Method to apply automatically a specific function to each cell of the octree. More... | |
unsigned | executeFunctionForAllCellsAtLevel (unsigned char level, octreeCellFunc func, void **additionalParameters, bool multiThread=false, GenericProgressCallback *progressCb=nullptr, const char *functionTitle=nullptr, int maxThreadCount=0) |
Method to apply automatically a specific function to each cell of the octree. More... | |
bool | rayCast (const CCVector3 &rayAxis, const CCVector3 &rayOrigin, double maxRadiusOrFov, bool isFOV, RayCastProcess process, std::vector< PointDescriptor > &output) const |
Ray casting algorithm. | |
GenericIndexedCloudPersist * | associatedCloud () const |
Returns the associated cloud. | |
const cellsContainer & | pointsAndTheirCellCodes () const |
Returns the octree 'structure'. | |
Public Member Functions inherited from CCCoreLib::GenericOctree | |
virtual | ~GenericOctree ()=default |
Default destructor. | |
Static Public Member Functions | |
static unsigned char | GET_BIT_SHIFT (unsigned char level) |
Returns the binary shift for a given level of subdivision. More... | |
static int | OCTREE_LENGTH (int level) |
Returns the octree length (in term of cells) for a given level of subdivision. More... | |
static CellCode | GenerateTruncatedCellCode (const Tuple3i &cellPos, unsigned char level) |
Generates the truncated cell code of a cell given its position at a given level of subdivision. More... | |
static CellCode | GenerateTruncatedCellCode (const Tuple3s &pos, unsigned char level) |
Short version of GenerateTruncatedCellCode. | |
static PointCoordinateType | ComputeMinDistanceToCellBorder (const CCVector3 &queryPoint, PointCoordinateType cs, const CCVector3 &cellCenter) |
Computes the minimal distance between a point and the borders (faces) of the cell (cube) in which it is included. More... | |
static bool | MultiThreadSupport () |
Returns whether multi-threading (parallel) computation is supported or not. | |
Static Public Attributes | |
static const int | MAX_OCTREE_LEVEL = 10 |
Max octree subdivision level. More... | |
static const int | MAX_OCTREE_LENGTH = (1 << MAX_OCTREE_LEVEL) |
Max octree length at last level of subdivision (number of cells) More... | |
static const CellCode | INVALID_CELL_CODE = (~static_cast<CellCode>(0)) |
Invalid cell code. More... | |
Protected Member Functions | |
int | genericBuild (GenericProgressCallback *progressCb=nullptr) |
Generic method to build the octree structure. More... | |
void | updateCellSizeTable () |
Updates the tables containing the octree cells length for each level of subdivision. | |
void | updateCellCountTable () |
Updates the tables containing the number of octree cells for each level of subdivision. | |
void | computeCellsStatistics (unsigned char level) |
Computes statistics about cells for a given level of subdivision. More... | |
void | getNeighborCellsAround (const Tuple3i &cellPos, cellIndexesContainer &neighborCellsIndexes, int neighbourhoodLength, unsigned char level) const |
Returns the indexes of the neighbourhing (existing) cells of a given cell. More... | |
void | getPointsInNeighbourCellsAround (NearestNeighboursSearchStruct &nNSS, int neighbourhoodLength, bool getOnlyPointsWithValidScalar=false) const |
Gets point in the neighbourhing cells of a specific cell. More... | |
unsigned | getCellIndex (CellCode truncatedCellCode, unsigned char bitShift, unsigned begin, unsigned end) const |
Returns the index of a given cell represented by its code. More... | |
Protected Attributes | |
cellsContainer | m_thePointsAndTheirCellCodes |
The coded octree structure. More... | |
GenericIndexedCloudPersist * | m_theAssociatedCloud |
Associated cloud. | |
unsigned | m_numberOfProjectedPoints |
Number of points projected in the octree. | |
unsigned | m_nearestPow2 |
Nearest power of 2 smaller than the number of points (used for binary search) | |
CCVector3 | m_dimMin |
Min coordinates of the octree bounding-box. | |
CCVector3 | m_dimMax |
Max coordinates of the octree bounding-box. | |
CCVector3 | m_pointsMin |
Min coordinates of the bounding-box of the set of points projected in the octree. | |
CCVector3 | m_pointsMax |
Max coordinates of the bounding-box of the set of points projected in the octree. | |
PointCoordinateType | m_cellSize [MAX_OCTREE_LEVEL+2] |
Cell dimensions for all subdivision levels. | |
int | m_fillIndexes [(MAX_OCTREE_LEVEL+1) *6] |
Min and max occupied cells indexes, for all dimensions and every subdivision level. | |
unsigned | m_cellCount [MAX_OCTREE_LEVEL+1] |
Number of cells per level of subdivision. | |
unsigned | m_maxCellPopulation [MAX_OCTREE_LEVEL+1] |
Max cell population per level of subdivision. | |
double | m_averageCellPopulation [MAX_OCTREE_LEVEL+1] |
Average cell population per level of subdivision. | |
double | m_stdDevCellPopulation [MAX_OCTREE_LEVEL+1] |
Std. dev. of cell population per level of subdivision. | |
The octree structure used throughout the library.
Implements the GenericOctree interface. Corresponds to the octree structure developed during Daniel Girardeau-Montaut's PhD (see PhD manuscript, Chapter 4).
using CCCoreLib::DgmOctree::CellCode = unsigned |
Type of the code of an octree cell.
using CCCoreLib::DgmOctree::octreeCellFunc = bool (*)(const octreeCell &, void **, NormalizedProgress *) |
Generic form of a function that can be applied automatically to all cells of the octree.
See DgmOctree::executeFunctionForAllCellsAtLevel and DgmOctree::executeFunctionForAllCellsStartingAtLevel. The parameters of such a function are:
|
explicit |
int DgmOctree::build | ( | const CCVector3 & | octreeMin, |
const CCVector3 & | octreeMax, | ||
const CCVector3 * | pointsMinFilter = nullptr , |
||
const CCVector3 * | pointsMaxFilter = nullptr , |
||
GenericProgressCallback * | progressCb = nullptr |
||
) |
Builds the structure with constraints.
Octree spatial limits must be specified. Also, if specified, points falling outside the "pointsFilter" limits won't be projected into the octree structure. Otherwise, all points will be taken into account. Octree 3D limits in space should be cubical.
octreeMin | the lower limits for the octree cells along X, Y and Z |
octreeMax | the upper limits for the octree cells along X, Y and Z |
pointsMinFilter | the lower limits for the projected points along X, Y and Z (if specified) |
pointsMaxFilter | the upper limits for the projected points along X, Y and Z (if specified) |
progressCb | the client application can get some notification of the process progress through this callback mechanism (see GenericProgressCallback) |
int DgmOctree::build | ( | GenericProgressCallback * | progressCb = nullptr | ) |
Builds the structure.
Octree 3D limits are determined automatically.
progressCb | the client application can get some notification of the process progress through this callback mechanism (see GenericProgressCallback) |
|
inline |
Returns the cell center for a given level of subdivision of a cell designated by its code.
code | the cell code |
level | the level of subdivision |
center | the computed center |
isCodeTruncated | indicates if the given code is truncated or not |
|
inline |
Returns the cell center for a given level of subdivision of a cell designated by its position.
cellPos | the cell position |
level | the level of subdivision |
center | the computed center |
void DgmOctree::computeCellLimits | ( | CellCode | code, |
unsigned char | level, | ||
CCVector3 & | cellMin, | ||
CCVector3 & | cellMax, | ||
bool | isCodeTruncated = false |
||
) | const |
Returns the spatial limits of a given cell.
code | the cell code |
level | the level of subdivision |
cellMin | the minimum coordinates along each dimension |
cellMax | the maximum coordinates along each dimension |
isCodeTruncated | indicates if the given code is truncated or not |
|
protected |
Computes statistics about cells for a given level of subdivision.
This method requires some computation, therefore it shouldn't be called too often.
level | the level of subdivision |
double DgmOctree::computeMeanOctreeDensity | ( | unsigned char | level | ) | const |
Computes mean octree density (point/cell) at a given level of subdivision.
level | the level of subdivision |
|
inlinestatic |
Computes the minimal distance between a point and the borders (faces) of the cell (cube) in which it is included.
queryPoint | the point |
cs | the cell size (as cells are cubical, it's the same along every dimension) |
cellCenter | the cell center |
void DgmOctree::diff | ( | const cellCodesContainer & | codesA, |
const cellCodesContainer & | codesB, | ||
cellCodesContainer & | diffA, | ||
cellCodesContainer & | diffB | ||
) | const |
Returns the cells that differ between two octrees (for a same implicit level of subdivision)
Warning: the two octrees should have been computed with the same bounding-box.
codesA | the cell codes of the first octree for the implicit level |
codesB | the cell codes of the second octree for the implicit level |
diffA | the cells of the first octree that are not in the second octree |
diffB | the cells of the second octree that are not in the first octree |
bool DgmOctree::diff | ( | unsigned char | octreeLevel, |
const cellsContainer & | codesA, | ||
const cellsContainer & | codesB, | ||
int & | diffA, | ||
int & | diffB, | ||
int & | cellsA, | ||
int & | cellsB | ||
) | const |
Returns the differences (in terms of number of cells) between two octrees for a given level of subdivision.
Warning: the two octrees should have been computed with the same bounding-box.
octreeLevel | the octree level |
codesA | the cell codes (and point index) of the first octree |
codesB | the cell codes (and point index) of the second octree |
diffA | the number of cells of the first octree that are not in the second octree |
diffB | the number of cells of the second octree that are not in the first octree |
cellsA | the number of cells of the first octree for the given number of subdivision |
cellsB | the number of cells of the second octree for the given number of subdivision |
unsigned DgmOctree::executeFunctionForAllCellsAtLevel | ( | unsigned char | level, |
octreeCellFunc | func, | ||
void ** | additionalParameters, | ||
bool | multiThread = false , |
||
GenericProgressCallback * | progressCb = nullptr , |
||
const char * | functionTitle = nullptr , |
||
int | maxThreadCount = 0 |
||
) |
Method to apply automatically a specific function to each cell of the octree.
The function to apply should be of the form DgmOctree::octreeCellFunc. In this case the octree cells are scanned one by one at the same level of subdivision.
Parallel processing is based on tbb::parallel_for or QtConcurrent.
level | the level of subdivision |
func | the function to apply |
additionalParameters | the function parameters |
multiThread | whether to use parallel processing or not |
progressCb | the client application can get some notification of the process progress through this callback mechanism (see GenericProgressCallback) |
functionTitle | function title |
maxThreadCount | the maximum number of threads to use (0 = all). Ignored if 'multiThread' is false or with tbb. |
unsigned DgmOctree::executeFunctionForAllCellsStartingAtLevel | ( | unsigned char | startingLevel, |
octreeCellFunc | func, | ||
void ** | additionalParameters, | ||
unsigned | minNumberOfPointsPerCell, | ||
unsigned | maxNumberOfPointsPerCell, | ||
bool | multiThread = true , |
||
GenericProgressCallback * | progressCb = nullptr , |
||
const char * | functionTitle = nullptr , |
||
int | maxThreadCount = 0 |
||
) |
Method to apply automatically a specific function to each cell of the octree.
The function to apply should be of the form DgmOctree::octreeCellFunc. In this case the octree cells are scanned one by one at the same level of subdivision, but the scan can also be sometimes done (inside the cell) at deeper levels, in order to limit the number of points in a cell. Thanks to this, the function is applied on a limited number of points, avoiding great loss of performances. The only limitation is when the level of subdivision is deepest level. In this case no more splitting is possible.
Parallel processing is based on tbb::parallel_for or QtCocncurrent.
startingLevel | the initial level of subdivision |
func | the function to apply |
additionalParameters | the function parameters |
minNumberOfPointsPerCell | minimal number of points inside a cell (indicative) |
maxNumberOfPointsPerCell | maximum number of points inside a cell (indicative) |
multiThread | whether to use parallel processing or not |
progressCb | the client application can get some notification of the process progress through this callback mechanism (see GenericProgressCallback) |
maxThreadCount | the maximum number of threads to use (0 = all). Ignored if 'multiThread' is false or with tbb. |
functionTitle | function title |
int DgmOctree::extractCCs | ( | const cellCodesContainer & | cellCodes, |
unsigned char | level, | ||
bool | sixConnexity, | ||
GenericProgressCallback * | progressCb = nullptr |
||
) | const |
Computes the connected components (considering the octree cells only) for a given level of subdivision (partial)
The octree is seen as a regular 3D grid, and each cell of this grid is either set to 0 (if no points lies in it) or to 1 (if some points lie in it, e.g. if it is indeed a cell of this octree). This version of the algorithm can be applied by considering only a specified list of octree cells (ignoring the others).
cellCodes | the cell codes to consider for the CC computation |
level | the level of subdivision at which to perform the algorithm |
sixConnexity | indicates if the CC's 3D connexity should be 6 (26 otherwise) |
progressCb | the client application can get some notification of the process progress through this callback mechanism (see GenericProgressCallback) |
int DgmOctree::extractCCs | ( | unsigned char | level, |
bool | sixConnexity, | ||
GenericProgressCallback * | progressCb = nullptr |
||
) | const |
Computes the connected components (considering the octree cells only) for a given level of subdivision (complete)
The octree is seen as a regular 3D grid, and each cell of this grid is either set to 0 (if no points lies in it) or to 1 (if some points lie in it, e.g. if it is indeed a cell of this octree). This version of the algorithm is directly applied on the whole octree.
level | the level of subdivision at which to perform the algorithm |
sixConnexity | indicates if the CC's 3D connexity should be 6 (26 otherwise) |
progressCb | the client application can get some notification of the process progress through this callback mechanism (see GenericProgressCallback) |
unsigned char DgmOctree::findBestLevelForAGivenCellNumber | ( | unsigned | indicativeNumberOfCells | ) | const |
Determines the best subdivision level of the octree to match a given number of cells.
indicativeNumberOfCells | 'desired' number of cells |
unsigned char DgmOctree::findBestLevelForAGivenNeighbourhoodSizeExtraction | ( | PointCoordinateType | radius | ) | const |
Determines the best level of subdivision of the octree at which to apply the nearest neighbours search algorithm (inside a sphere) depending on the sphere radius.
radius | the sphere radius |
unsigned char DgmOctree::findBestLevelForAGivenPopulationPerCell | ( | unsigned | indicativeNumberOfPointsPerCell | ) | const |
Determines the best subdivision level of the octree that gives the average population per cell closest to the input value.
indicativeNumberOfPointsPerCell | 'desired' average number of points per cell |
unsigned char DgmOctree::findBestLevelForComparisonWithOctree | ( | const DgmOctree * | theOtherOctree | ) | const |
Determines the best level of subdivision of the octree at which to apply a cloud-2-cloud distance computation algorithm.
The octree instance on which is "applied" this method should be the compared cloud's one. "theOtherOctree" should be the reference cloud's octree.
theOtherOctree | the octree of the other cloud |
unsigned DgmOctree::findNearestNeighborsStartingFromCell | ( | NearestNeighboursSearchStruct & | nNSS, |
bool | getOnlyPointsWithValidScalar = false |
||
) | const |
Advanced form of the nearest neighbours search algorithm (multiple neighbours)
This version is optimized for a multiple nearest neighbours search that is applied around several query points included in the same octree cell. See DgmOctree::NearestNeighboursSearchStruct for more details.
nNSS | NN search parameters |
getOnlyPointsWithValidScalar | whether to ignore points having an invalid associated scalar value |
int DgmOctree::findNeighborsInASphereStartingFromCell | ( | NearestNeighboursSearchStruct & | nNSS, |
double | radius, | ||
bool | sortValues = true |
||
) | const |
Advanced form of the nearest neighbours search algorithm (in a sphere)
This version is optimized for a spatially bounded search instead of a search bounded by a number of neighbours.
nNSS | a pack of parameters |
radius | the sphere radius |
sortValues | specifies if the neighbours needs to be sorted by their distance to the query point or not |
unsigned DgmOctree::findPointNeighbourhood | ( | const CCVector3 * | _queryPoint, |
ReferenceCloud * | Yk, | ||
unsigned | maxNumberOfNeighbors, | ||
unsigned char | level, | ||
double & | maxSquareDist, | ||
double | maxSearchDist = 0 , |
||
int * | finalNeighbourhoodSize = nullptr |
||
) | const |
Finds the nearest neighbours around a query point.
This is the simplest form of the nearest neighbour search algorithm. It should only be used for unique/few requests as it is not optimized for repetitive search around points lying in the same octree cell (see DgmOctree::findNearestNeighborsStartingFromCell for example). Moreover, distances between each neighbour and the query aren't stored in this version of the algorithm.
_queryPoint | the query point | |
Yk | the nearest neighbours | |
maxNumberOfNeighbors | the maximal number of points to find | |
level | the subdivision level of the octree at which to perform the search | |
maxSquareDist | the square distance between the farthest "nearest neighbour" and the query point | |
maxSearchDist | the maximum search distance (ignored if <= 0) | |
[out] | finalNeighbourhoodSize | the final neighborhood (half)size (optional) |
double DgmOctree::findTheNearestNeighborStartingFromCell | ( | NearestNeighboursSearchStruct & | nNSS | ) | const |
Advanced form of the nearest neighbour search algorithm (unique neighbour)
This version is optimized for a unique nearest-neighbour search. See DgmOctree::NearestNeighboursSearchStruct for more details.
nNSS | NN search parameters |
|
static |
Generates the truncated cell code of a cell given its position at a given level of subdivision.
For a given level of subdivision (lets call it N), the cell position can be expressed as 3 integer coordinates between 0 and 2^N-1 (the number of cells along each dimension). This method computes the corresponding cell code, truncated at the level N (meaning that it is only valid for the Nth level, not for other levels).
cellPos | the cell position |
level | the level of subdivision |
|
protected |
Generic method to build the octree structure.
METHODS
progressCb | the client application can get some notification of the process progress through this callback mechanism (see GenericProgressCallback) |
|
static |
Returns the binary shift for a given level of subdivision.
This binary shift is used to truncate a full cell code in order to deduce the cell code for a given level of subdivision.
level | the level of subdivision |
Returns the octree bounding box.
Method to request the octree bounding box limits
bbMin | lower bounding-box limits (Xmin,Ymin,Zmin) |
bbMax | higher bounding-box limits (Xmax,Ymax,Zmax) |
bool DgmOctree::getCellCodes | ( | unsigned char | level, |
cellCodesContainer & | vec, | ||
bool | truncatedCodes = false |
||
) | const |
Returns the list of codes corresponding to the octree cells for a given level of subdivision.
Only the non empty cells are represented in the octree structure.
level | the level of subdivision |
vec | the list of codes |
truncatedCodes | indicates if the resulting codes should be truncated or not |
bool DgmOctree::getCellCodesAndIndexes | ( | unsigned char | level, |
cellsContainer & | vec, | ||
bool | truncatedCodes = false |
||
) | const |
Returns the list of indexes and codes corresponding to the octree cells for a given level of subdivision.
Only the non empty cells are represented in the octree structure. Cell indexes are expressed relatively to the DgmOctree structure. They correspond to the indexes of the first points of each cell.
level | the level of subdivision |
vec | the list of codes & indexes |
truncatedCodes | indicates if the resulting codes should be truncated or not |
void DgmOctree::getCellDistanceFromBorders | ( | const Tuple3i & | cellPos, |
unsigned char | level, | ||
int * | cellDists | ||
) | const |
Returns distance form a cell to the filled octree borders in all directions.
WARNING: distance values may be negative! (if cell is outside
cellPos | cell position |
level | level at which octree grid is considered |
cellDists | output |
void DgmOctree::getCellDistanceFromBorders | ( | const Tuple3i & | cellPos, |
unsigned char | level, | ||
int | neighbourhoodLength, | ||
int * | cellDists | ||
) | const |
Returns distance from cell center to cell neighbourhood INSIDE filled octree.
WARNING: if cell neighbourhood is totally outside filled octree, the method returns false and cellDists is invalid.
cellPos | center cell position |
level | level at which octree grid is considered |
neighbourhoodLength | cell neighbourhood "radius" |
cellDists | output |
unsigned DgmOctree::getCellIndex | ( | CellCode | truncatedCellCode, |
unsigned char | bitShift | ||
) | const |
Returns the index of a given cell represented by its code.
The index is found thanks to a binary search. The index of an existing cell is between 0 and the number of points projected in the octree minus 1. If the cell code cannot be found in the octree structure, then the method returns an index equal to the number of projected points (m_numberOfProjectedPoints).
truncatedCellCode | truncated cell code (i.e. original cell code shifted of 'bitShift' bits) |
bitShift | binary shift corresponding to the level of subdivision (see GET_BIT_SHIFT) |
|
protected |
Returns the index of a given cell represented by its code.
Same algorithm as the other "getCellIndex" method, but in an optimized form. The binary search can be performed on a sub-part of the DgmOctree structure.
truncatedCellCode | truncated cell code (i.e. original cell code shifted of 'bitShift' bits) |
bitShift | binary shift corresponding to the level of subdivision (see GET_BIT_SHIFT) |
begin | first index of the sub-list in which to perform the binary search |
end | last index of the sub-list in which to perform the binary search |
bool DgmOctree::getCellIndexes | ( | unsigned char | level, |
cellIndexesContainer & | vec | ||
) | const |
Returns the list of indexes corresponding to the octree cells for a given level of subdivision.
Only the non empty cells are represented in the octree structure. Cell indexes are expressed relatively to the DgmOctree structure. They correspond to the indexes of the first points of each cell.
level | the level of subdivision |
vec | the list of indexes |
void DgmOctree::getCellPos | ( | CellCode | code, |
unsigned char | level, | ||
Tuple3i & | cellPos, | ||
bool | isCodeTruncated | ||
) | const |
Returns the cell position for a given level of subdivision of a cell designated by its code.
code | the cell code |
level | the level of subdivision |
cellPos | the computed position |
isCodeTruncated | indicates if the given code is truncated or not |
|
inline |
Returns the octree cells length for a given level of subdivision.
As the octree is cubical, cells are cubical.
level | the level of subdivision (up to MAX_OCTREE_LEVEL+1 for convenience) |
|
inline |
Returns the highest cell positions in the octree along all dimensions and for a given level of subdivision.
For example, at a level n, the octree length is 2^n cells along each dimension. The highest cell position along each dimension will be expressed between 0 and 2^n-1.
level | the level of subdivision |
|
inline |
Returns the lowest cell positions in the octree along all dimensions and for a given level of subdivision.
For example, at a level n, the octree length is 2^n cells along each dimension. The lowest cell position along each dimension will be expressed between 0 and 2^n-1.
level | the level of subdivision |
|
protected |
Returns the indexes of the neighbourhing (existing) cells of a given cell.
This function is used by the nearest neighbours search algorithms.
cellPos | the query cell |
neighborCellsIndexes | the found neighbourhing cells |
neighbourhoodLength | the distance (in terms of cells) at which to look for neighbour cells |
level | the level of subdivision |
|
inline |
Returns the number of points projected into the octree.
|
inline |
Returns the higher boundaries of the octree.
|
inline |
Returns the lower boundaries of the octree.
std::size_t DgmOctree::getPointsInBoxNeighbourhood | ( | BoxNeighbourhood & | params | ) | const |
Returns the points falling inside a box.
bool DgmOctree::getPointsInCell | ( | CellCode | cellCode, |
unsigned char | level, | ||
ReferenceCloud * | subset, | ||
bool | isCodeTruncated = false , |
||
bool | clearOutputCloud = true |
||
) | const |
Returns the points lying in a specific cell.
cellCode | the unique cell code | |
level | the level of subdivision | |
[out] | subset | set of points lying in the cell (references, no duplication) |
isCodeTruncated | specifies if the code is given in a truncated form or not | |
clearOutputCloud | whether to clear or not the output cloud (subest) if no points lie in the specified cell |
bool DgmOctree::getPointsInCellByCellIndex | ( | ReferenceCloud * | cloud, |
unsigned | cellIndex, | ||
unsigned char | level, | ||
bool | clearOutputCloud = true |
||
) | const |
Returns the points lying in a specific cell.
Each cell at a given level of subdivision can be recognized by the index in the DgmOctree structure of the first point that lies inside it. By construction, we are assured that every point lying in the same cell for a given level of subdivision are next to each others in the octree structure (which is the vector "m_thePointsAndTheirCellCodes" in practical). This is the quickest way to access the points inside a given cell (but its kind of hard to know directly what is the index of a given cell ;)
cloud | ReferenceCloud to store the points lying inside the cell |
cellIndex | the cell index |
level | the level of subdivision |
clearOutputCloud | whether to clear the input cloud prior to inserting the points or not |
ReferenceCloud * DgmOctree::getPointsInCellsWithSortedCellCodes | ( | cellCodesContainer & | cellCodes, |
unsigned char | level, | ||
ReferenceCloud * | subset, | ||
bool | areCodesTruncated = false |
||
) | const |
Returns the points lying in multiple cells.
Cells are recognized here by their unique "code". They should be sorted along by codes, with an ascendant order. See DgmOctree::getPointsInCellByCellIndex for more information.
cellCodes | the cells codes | |
level | the level of subdivision | |
[out] | subset | set of points lying in the cell (references, no duplication) |
areCodesTruncated | specifies if the codes are given in a truncated form or not |
std::size_t DgmOctree::getPointsInCylindricalNeighbourhood | ( | CylindricalNeighbourhood & | params | ) | const |
Returns the points falling inside a cylinder.
Use findBestLevelForAGivenNeighbourhoodSizeExtraction to get the right value for 'level' (only once as it only depends on the radius value ;).
params | input/output parameters structure |
std::size_t DgmOctree::getPointsInCylindricalNeighbourhoodProgressive | ( | ProgressiveCylindricalNeighbourhood & | params | ) | const |
Same as getPointsInCylindricalNeighbourhood with progressive approach.
Can be called multiple times (the 'currentHalfLength' parameter will increase each time until 'maxHalfLength' is reached).
|
protected |
Gets point in the neighbourhing cells of a specific cell.
nNSS | NN search parameters (from which are used: cellPos, pointsInNeighbourCells and level) |
neighbourhoodLength | the new distance (in terms of cells) at which to look for neighbour cells |
getOnlyPointsWithValidScalar | whether to ignore points having an invalid associated scalar value |
int DgmOctree::getPointsInSphericalNeighbourhood | ( | const CCVector3 & | sphereCenter, |
PointCoordinateType | radius, | ||
NeighboursSet & | neighbours, | ||
unsigned char | level | ||
) | const |
Returns the points falling inside a sphere.
Use findBestLevelForAGivenNeighbourhoodSizeExtraction to get the right value for 'level' (only once as it only depends on the radius value ;).
sphereCenter | center | |
radius | radius | |
[out] | neighbours | points falling inside the sphere |
level | subdivision level at which to apply the extraction process |
|
inline |
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-1 as the point can lie outside the octree bounding-box.
thePoint | the query point |
cellPos | the computed position |
|
inline |
Returns the position for a given level of subdivision of the cell that includes a given point.
The cell coordinates can be negative or greater than 2^N-1 (where N is the level of subdivision) as the point can lie outside the octree bounding-box.
thePoint | the query point |
cellPos | the computed position |
level | the level of subdivision |
|
inline |
Returns the position for a given level of subdivision of the cell that includes a given point.
The cell coordinates can be negative or greater than 2^N-1 (where N is the level of subdivision) as the point can lie outside the octree bounding-box. In this version, method indicates if the query point is inside ("inbounds") or outside the octree bounding-box.
thePoint | the query point |
cellPos | the computed position |
level | the level of subdivision |
inBounds | indicates if the query point is inside or outside the octree bounding-box |
|
static |
Returns the octree length (in term of cells) for a given level of subdivision.
level | the level of subdivision |
Invalid cell code.
|
protected |
The coded octree structure.
ATTRIBUTES
|
static |
Max octree length at last level of subdivision (number of cells)
|
static |
Max octree subdivision level.
STRUCTURES
Number of bits used to code the cells position: 3*MAX_OCTREE_LEVEL