TrueKdTree.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 "DistanceComputationTools.h"
#include "ReferenceCloud.h"
 
// system
#include <cstdint>
 
namespace cloudViewer {
 
class GenericIndexedCloudPersist;
class GenericProgressCallback;
 
class CV_CORE_LIB_API TrueKdTree {
public:
    // Warning: never pass a 'constant initializer' by reference
    static const uint8_t X_DIM = 0;
    static const uint8_t Y_DIM = 1;
    static const uint8_t Z_DIM = 2;
    static const uint8_t NODE_TYPE = 0;
    static const uint8_t LEAF_TYPE = 1;
 
    class BaseNode {
    public:
        explicit BaseNode(uint8_t nodeType) : parent(nullptr), type(nodeType) {}
        virtual ~BaseNode() = default;
 
        bool isNode() const { return type == NODE_TYPE; }
        bool isLeaf() const { return type == LEAF_TYPE; }
 
    public:
        // Warning: put the non aligned members (< 4 bytes) at the end to avoid
        // too much alignment padding!
        BaseNode* parent;  // 8 bytes
 
    protected:
        const uint8_t type;  // 1 byte (+ 3 for alignment)
 
        // Total //12 bytes
    };
 
    class Node : public BaseNode {
    public:
        // Warning: put the non aligned members (< 4 bytes) at the end to avoid
        // too much alignment padding!
        PointCoordinateType splitValue;  // 4 bytes
        BaseNode* leftChild;             // 8 bytes
        BaseNode* rightChild;            // 8 bytes
        uint8_t splitDim;                // 1 byte (+ 3 bytes for alignment)
 
        // Total
        // //24 bytes (+ 12 for father)
 
        Node()
            : BaseNode(NODE_TYPE),
              splitValue(0),
              leftChild(nullptr),
              rightChild(nullptr),
              splitDim(X_DIM) {}
 
        ~Node() override {
            delete leftChild;
            delete rightChild;
        }
    };
 
    class Leaf : public BaseNode {
    public:
        // Warning: put the non aligned members (< 4 bytes) at the end to avoid
        // too much alignment padding!
        ReferenceCloud* points;          // 8 bytes
        PointCoordinateType planeEq[4];  // 16 bytes
        ScalarType error;                // 4 bytes
        int userData;                    // 4 bytes
 
        // Total
        // //32 bytes (+ 12 for father)
 
 
        Leaf(ReferenceCloud* set,
             const PointCoordinateType planeEquation[],
             ScalarType _error)
            : BaseNode(LEAF_TYPE), points(set), error(_error), userData(0) {
            memcpy(planeEq, planeEquation, sizeof(PointCoordinateType) * 4);
        }
 
        ~Leaf() override { delete points; }
    };
 
    using LeafVector = std::vector<Leaf*>;
 
    explicit TrueKdTree(GenericIndexedCloudPersist* cloud);
 
    ~TrueKdTree();
 
    inline GenericIndexedCloudPersist* associatedCloud() const {
        return m_associatedCloud;
    }
 
 
    bool build(double maxError,
               DistanceComputationTools::ERROR_MEASURES errorMeasure =
                       DistanceComputationTools::RMS,
               unsigned minPointCountPerCell = 3,
               unsigned maxPointCountPerCell = 0,
               GenericProgressCallback* progressCb = nullptr);
 
    void clear();
 
    inline double getMaxError() const { return m_maxError; }
 
    inline DistanceComputationTools::ERROR_MEASURES getMaxErrorType() const {
        return m_errorMeasure;
    }
 
    bool getLeaves(LeafVector& leaves) const;
 
protected:
    BaseNode* split(ReferenceCloud* subset);
 
    BaseNode* m_root;
 
    GenericIndexedCloudPersist* m_associatedCloud;
 
    double m_maxError;
 
    DistanceComputationTools::ERROR_MEASURES m_errorMeasure;
 
 
    unsigned m_minPointCountPerCell;
 
 
    unsigned m_maxPointCountPerCell;
};
 
}  // namespace cloudViewer