CVKdTree.h

Go to the documentation of this file.

// ----------------------------------------------------------------------------
// -                        CloudViewer: www.cloudViewer.org                  -
// ----------------------------------------------------------------------------
// Copyright (c) 2018-2024 www.cloudViewer.org
// SPDX-License-Identifier: MIT
// ----------------------------------------------------------------------------
 
#pragma once
 
// Local
#include "PointProjectionTools.h"
 
namespace cloudViewer {
 
class GenericIndexedCloud;
class GenericProgressCallback;
 
class CV_CORE_LIB_API KDTree {
public:
    KDTree();
 
    virtual ~KDTree();
 
 
    bool buildFromCloud(GenericIndexedCloud *cloud,
                        GenericProgressCallback *progressCb = nullptr);
 
 
    GenericIndexedCloud *getAssociatedCloud() const {
        return m_associatedCloud;
    }
 
 
    bool findNearestNeighbour(const PointCoordinateType *queryPoint,
                              unsigned &nearestPointIndex,
                              ScalarType maxDist);
 
 
    bool findNearestNeighbourWithMaxDist(const PointCoordinateType *queryPoint,
                                         ScalarType maxDist);
 
 
    unsigned radiusSearch(const PointCoordinateType *queryPoint,
                          ScalarType distance,
                          ScalarType tolerance,
                          std::vector<unsigned> &pointndexes);
 
 
    bool findPointBelowDistance(const PointCoordinateType *queryPoint,
                                ScalarType maxDist);
 
 
    unsigned findPointsLyingToDistance(const PointCoordinateType *queryPoint,
                                       ScalarType distance,
                                       ScalarType tolerance,
                                       std::vector<unsigned> &points);
 
protected:
    struct KdCell {
        KdCell()
            : cuttingDim(0),
              cuttingCoordinate(0),
              leSon(nullptr),
              gSon(nullptr),
              father(nullptr),
              startingPointIndex(0),
              nbPoints(0),
              boundsMask(0) {}
 
        // Warning: put the non aligned members (< 4 bytes) at the end to avoid
        // too much alignment padding!
 
 
        CCVector3 inbbmax;  // 12 bytes
 
        CCVector3 inbbmin;  // 12 bytes
 
        CCVector3 outbbmin;  // 12 bytes
 
        CCVector3 outbbmax;  // 12 bytes
 
        unsigned cuttingDim;  // 4 bytes
        PointCoordinateType cuttingCoordinate;  // 4 bytes
        struct KdCell *leSon;  // 8 bytes
        struct KdCell *gSon;  // 8 bytes
        struct KdCell *father;  // 8 bytes
        unsigned startingPointIndex;  // 4 bytes
        unsigned nbPoints;  // 4 bytes
 
 
        unsigned char boundsMask;  // 1 byte (+ 3 for alignment)
 
        // Total
        // //92 bytes
    };
 
    /*** Protected attributes ***/
 
    KdCell *m_root;
    std::vector<unsigned> m_indexes;
    GenericIndexedCloud *m_associatedCloud;
    unsigned m_cellCount;
 
    /*** Protected methods ***/
 
 
    KdCell *buildSubTree(unsigned first,
                         unsigned last,
                         KdCell *father,
                         unsigned &nbBuildCell,
                         GenericProgressCallback *progressCb = nullptr);
 
    void deleteSubTree(KdCell *cell);
 
    void updateInsideBoundingBox(KdCell *cell);
 
    void updateOutsideBoundingBox(KdCell *cell);
 
 
    ScalarType pointToCellSquareDistance(const PointCoordinateType *queryPoint,
                                         KdCell *cell);
 
 
    ScalarType insidePointToCellDistance(const PointCoordinateType *queryPoint,
                                         KdCell *cell);
 
 
    void pointToCellDistances(const PointCoordinateType *queryPoint,
                              KdCell *cell,
                              ScalarType &min,
                              ScalarType &max);
 
 
    int checkNearerPointInSubTree(const PointCoordinateType *queryPoint,
                                  ScalarType &maxSqrDist,
                                  KdCell *cell);
 
 
    bool checkDistantPointInSubTree(const PointCoordinateType *queryPoint,
                                    ScalarType &maxSqrDist,
                                    KdCell *cell);
 
 
    void distanceScanTree(const PointCoordinateType *queryPoint,
                          ScalarType distance,
                          ScalarType tolerance,
                          KdCell *cell,
                          std::vector<unsigned> &localArray);
};
 
}  // namespace cloudViewer