StaticAABBTree.hpp

Go to the documentation of this file.

// This file is part of GranOO, a workbench for DEM simulation.
//
// Author(s)    : - Damien Andre       IRCER/UNILIM, Limoges France
//                  <damien.andre@unilim.fr>
//                - Jean-luc Charles   Arts et Metiers ParisTech, CNRS, I2M, Bordeaux France
//                  <jean-luc.charles@ensam.eu>
//                - Jeremie Girardot   Arts et Metiers ParisTech, CNRS, I2M, Bordeaux France
//                  <jeremie.girardot@ensam.eu>
//                - Cedric Hubert      LAMIH/UPHF, Valenciennes France
//                  <cedric.hubert@uphf.fr>
//                - Ivan Iordanoff     Arts et Metiers ParisTech, CNRS, I2M, Bordeaux France
//                  <ivan.iordanoff@ensam.eu>
//
// Copyright (C) 2008-2019 D. Andre, JL. Charles, J. Girardot, C. Hubert, I. Iordanoff
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
#ifndef StaticAABBTree_hpp
#define StaticAABBTree_hpp
 
#include <vector>     // std::vector
#include <functional> // std::function
 
// AABB structure (used by both Static and Dynamic AABB trees)
// -----------------------------------------------------------
struct AABB
{
 
  double minPoint[3];
  double midPoint[3];
  double maxPoint[3];
  unsigned int primitive = -1;
  unsigned int aabbNode = -1;
  unsigned int nextFree = -1;
  double volume;
  double surface;
  bool isActive = false;
};
 
// AABBNode structure (used by both Static and Dynamic AABB trees)
// ---------------------------------------------------------------
struct AABBNode
{
 
  double location[3];
  unsigned int aabb = -1;
  int height = 0;
  unsigned int depth = 0;
  unsigned int parentNode = -1;
  unsigned int leftNode = -1;
  unsigned int rightNode = -1;
  unsigned int nextFree = -1;
  bool isActive = false;
  bool isCrossed = false;
};
 
// simple Ray structure, to perform ray casting
// --------------------------------------------
struct Ray
{
 
  double origin[3];    // origin point of the ray
  double direction[3]; // direction of the ray
};
 
// now the big piece, the StaticAABBTree class
// -------------------------------------
class StaticAABBTree {
 
public:
  StaticAABBTree();
 
  StaticAABBTree(const std::vector<AABB> &leavesAABBs);
 
  ~StaticAABBTree();
 
public:
  static AABB new_lonely_aabb(double minPoint[3], double maxPoint[3], unsigned int primtiveIndex = -1);
 
public:
  void build(const std::vector<AABB> &leavesAABBs);
 
  const unsigned int node_number() const {
    return _node_count;
  };
 
  const AABBNode node_at_index(unsigned int nodeIndex) const {
    return _nodes[nodeIndex];
  };
 
  const unsigned int aabb_number() const {
    return _aabbsCount;
  };
 
  const AABB aabb_at_index(unsigned int aabbIndex) const {
    return _aabbs[aabbIndex];
  };
 
  const bool is_node_leaf(unsigned int nodeIndex) const {
    return _nodes[nodeIndex].leftNode == NotInList && _nodes[nodeIndex].leftNode == NotInList;
  };
 
  void xraycast_aabb_tree(Ray aRay, unsigned int aNode = 0) const;
 
  void raycast_aabb_tree(Ray aRay, unsigned int aNode = 0) const;
 
  void closest_point(const double *aPoint, double &distance, unsigned int aNode = 0) const;
 
  void furthest_vertex_along_axis(const double *aPoint, const double *anAxis, double &distance, unsigned int aNode = 0) const;
 
  void set_closest_point_callback(std::function<void(unsigned int, const double *, double &)> callback) const {
    closestPointCallback_ = callback;
  };
 
  void set_raycast_aabb_tree_callback(std::function<bool(unsigned int, Ray)> callback) const {
    raycastAABBTreeCallback_ = callback;
  };
 
  void set_furthest_vertex_callback  (std::function<void(unsigned int, const double *, const double *, double &)> callback) const {
    furthestVertexCallback_ = callback;
  };
 
private:
  unsigned int build(std::vector<unsigned int> aabbsIndices, unsigned int depth = 0);
 
  void clear();
 
  unsigned int new_aabb_node();
 
  unsigned int new_aabb_node(AABB anAABB);
 
  unsigned int new_aabb(double minPoint[3], double maxPoint[3], unsigned int primitiveIndex = -1);
 
  unsigned int new_aabb(AABB anAABB);
 
  unsigned int new_aabb_from_aabb(const std::vector<unsigned int> &aabbs);
 
  bool is_point_inside_aabb(const double *aPoint, unsigned int anAABB) const;
 
  double squared_distance_to_aabb_centre(const double *aPoint, unsigned int anAABB) const;
 
  double squared_distance_to_aabb(const double *aPoint, unsigned int anAABB) const;
 
  double inner_squared_distance_to_aabb(const double *aPoint, unsigned int anAABB) const;
 
  void furthest_vertex_on_aabb_along_axis(const double *anAxis, unsigned int anAABB, double (&furthestPoint)[3]) const;
 
  bool is_aabb_hit_by_xray(unsigned int anAABB, Ray aRay) const;
 
  bool is_aabb_hit_by_ray(unsigned int anAABB, Ray aRay) const;
 
  bool AABBFacetIsHitByRay(unsigned int anAABB, double facetNormal[3], Ray aRay) const;
 
private:
  static const unsigned int NotInList = (unsigned int)(-1);
 
private:
  unsigned int _aabbsCount;
 
  unsigned int _node_count;
 
  std::vector<AABB> _aabbs;
 
  std::vector<AABBNode> _nodes;
 
  mutable std::function<void(unsigned int primitiveIndex, const double *aPoint, double &distance)> closestPointCallback_;
 
  mutable std::function<bool(unsigned int primitiveIndex, Ray aRay)> raycastAABBTreeCallback_;
 
  mutable std::function<void(unsigned int primitiveIndex, const double *aPoint, const double *anAxis, double &distance)> furthestVertexCallback_;
};
 
#endif /* StaticAABBTree_hpp */