File AABBTree.h

File List > include > structure > AABBTree.h

Go to the documentation of this file

#pragma once

#include <array>
#include <cstddef>
#include <memory>
#include <vector>

#include "mesh/Mesh.h"
#include "../mesh/Vector3D.h"

namespace Argos {

class AABBTree {
public:
    using Vec3 = Vector3D<double>;

    struct Triangle {
        std::array<int, 3> vertexIndices; 
        Vec3 a; 
        Vec3 b; 
        Vec3 c; 
        std::size_t sourceFaceIndex; 
    };

    explicit AABBTree(const Mesh& mesh);

    bool empty() const;

    std::size_t triangleCount() const;

    const std::vector<Triangle>& getTriangles() const;

    double nearestDistanceSquared(const Vec3& point) const;

    double nearestDistance(const Vec3& point) const;

    std::vector<Triangle> nearestTriangles(const Vec3& point) const;

    int getNbIntersections(const Vec3& v1, const Vec3& v2);

private:
    struct AABB {
        Vec3 min;
        Vec3 max;
    };

    struct Node {
        AABB box;
        std::size_t begin;
        std::size_t end;
        std::unique_ptr<Node> left;
        std::unique_ptr<Node> right;

        bool isLeaf() const;
    };

    static constexpr std::size_t LeafTriangleCount = 8;

    std::vector<Triangle> triangles_;
    std::vector<std::size_t> indices_;
    std::unique_ptr<Node> root_;

    void buildTriangles(const Mesh& mesh);
    void reserveTriangleStorage(const std::vector<Face>& faces);
    void appendFaceTriangles(const Face& face,
                             std::size_t faceIndex,
                             const std::vector<Vec3>& vertices);

    std::unique_ptr<Node> buildNode(std::size_t begin, std::size_t end);

    static AABB makeEmptyAABB();
    static AABB makeTriangleAABB(const Triangle& triangle);
    static AABB mergeAABB(const AABB& lhs, const AABB& rhs);
    AABB computeNodeAABB(std::size_t begin, std::size_t end) const;

    static Vec3 triangleCentroid(const Triangle& triangle);
    static int longestAxis(const AABB& box);
    static double axisValue(const Vec3& point, int axis);

    static double clamp01(double value);
    static bool nearlyEqual(double lhs, double rhs);

    static double pointAABBDistanceSquared(const Vec3& point, const AABB& box);
    static double pointSegmentDistanceSquared(const Vec3& point, const Vec3& a, const Vec3& b);
    static double pointTriangleDistanceSquared(const Vec3& point, const Triangle& triangle);

    void nearestTriangles(const Node* node,
                          const Vec3& point,
                          double& bestDistanceSquared,
                          std::vector<std::size_t>& resultIndices) const;

    int getNbIntersections(const Node* node, const Vec3& v1, const Vec3& v2);

    bool RayIntersectsTriangle(const Vector3D<double> &rayOrigin, const Vector3D<double> &rayVector,
                               const Triangle &triangle);
};

} // namespace Argos