123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869 |
- #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() = default;
- 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* childs[2];
- int color;
- Node();
- };
- Node root;
-
- float minDistance;
- Vector3 intersection;
- KDTree::Triangle intersectionTriangle;
- Vector3 original;
- Vector3 min;
- Vector3 max;
- public:
- KDTree() = default;
- ~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;
- bool findIntersection(const Vector3& pos, const Vector3& direction);
- Vector3 getIntersection() const;
- KDTree::Triangle getIntersectedTriangle() const;
-
- private:
- void clean(Node* n);
- void cleanVisited(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, const Node* n, const Vector3& min, const Vector3& max) const;
- bool findIntersection(Node* n, const Vector3& pos, const Vector3& direction, float tMax);
-
- float orient(const Vector3& a, const Vector3& b, const Vector3& c, const Vector3& d) const;
- float testIntersection(const Vector3& pos, const Vector3& direction, const KDTree::Triangle& t) const;
- };
- #endif
|