cube-game-plus-plus/common/utils/KDTree.h

#ifndef KDTREE_H
#define KDTREE_H

#include <vector>

#include "common/utils/Array.h"
#include "common/math/Vector.h"
#include "client/rendering/Lines.h"

struct KDTree final {

    class Triangle {
        Array<Vector3, 3> v;
        Vector3 mid;
    public:
        Triangle(const Vector3& a, const Vector3& b, const Vector3& c);
        const Array<Vector3, 3>& data() const;
        const Vector3& operator[](int index) const;
        const Vector3& getMid() const;
    };

private:

    struct Node {
        std::vector<Triangle> data;
        int splitDim;
        float splitValue;
        Node* lessEqual;
        Node* greater;
        Node();
    };

    Node root;

public:
    KDTree();
    ~KDTree();
    KDTree(const KDTree& other) = delete;
    KDTree(KDTree&& other) = delete;
    KDTree& operator=(const KDTree& other) = delete;
    KDTree& operator=(KDTree&& other) = delete;

    void build(std::vector<KDTree::Triangle>& data);
    void fillLines(Lines& lines, const std::vector<KDTree::Triangle>& data);
private:
    void clean(Node* n);
    float median(std::vector<KDTree::Triangle>& data, int dim) const;
    void build(Node* n, std::vector<KDTree::Triangle>& data);
    void fillLines(Lines& lines, Node* n, const Vector3& min, const Vector3& max);
};

#endif