KDTree.h 1.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
  1. #ifndef KDTREE_H
  2. #define KDTREE_H
  3. #include <vector>
  4. #include "common/utils/Array.h"
  5. #include "common/math/Vector.h"
  6. #include "client/rendering/Lines.h"
  7. struct KDTree final {
  8. class Triangle {
  9. Array<Vector3, 3> v;
  10. Vector3 mid;
  11. public:
  12. Triangle() = default;
  13. Triangle(const Vector3& a, const Vector3& b, const Vector3& c);
  14. const Array<Vector3, 3>& data() const;
  15. const Vector3& operator[](int index) const;
  16. const Vector3& getMid() const;
  17. };
  18. private:
  19. struct Node {
  20. std::vector<Triangle> data;
  21. int splitDim;
  22. float splitValue;
  23. Node* childs[2];
  24. int color;
  25. Node();
  26. };
  27. Node root;
  28. float minDistance;
  29. Vector3 intersection;
  30. KDTree::Triangle intersectionTriangle;
  31. Vector3 original;
  32. Vector3 min;
  33. Vector3 max;
  34. public:
  35. KDTree() = default;
  36. ~KDTree();
  37. KDTree(const KDTree& other) = delete;
  38. KDTree(KDTree&& other) = delete;
  39. KDTree& operator=(const KDTree& other) = delete;
  40. KDTree& operator=(KDTree&& other) = delete;
  41. void build(std::vector<KDTree::Triangle>& data);
  42. void fillLines(Lines& lines) const;
  43. bool findIntersection(const Vector3& pos, const Vector3& direction);
  44. Vector3 getIntersection() const;
  45. KDTree::Triangle getIntersectedTriangle() const;
  46. private:
  47. void clean(Node* n);
  48. void cleanVisited(Node* n);
  49. float median(std::vector<KDTree::Triangle>& data, int dim) const;
  50. void build(Node* n, std::vector<KDTree::Triangle>& data);
  51. void fillLines(Lines& lines, const Node* n, const Vector3& min, const Vector3& max) const;
  52. bool findIntersection(Node* n, const Vector3& pos, const Vector3& direction, float tMax);
  53. float orient(const Vector3& a, const Vector3& b, const Vector3& c, const Vector3& d) const;
  54. float testIntersection(const Vector3& pos, const Vector3& direction, const KDTree::Triangle& t) const;
  55. };
  56. #endif