DynamicAABBTree.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 DynamicAABBTree_hpp
#define DynamicAABBTree_hpp
 
#include <vector>     // std::vector
#include <map>        // std::map
 
#include "GranOO3/Algo/StaticAABBTree.hpp" // AABB trees traits
 
class DynamicAABBTree {
 
public:
  DynamicAABBTree();
 
  ~DynamicAABBTree();
 
public:
  static AABB new_lonely_aabb(double minPoint[3], double maxPoint[3], double fatness, unsigned int primtiveIndex = -1);
 
  static AABB merged_lonely_aabb(AABB aabb1, AABB aabb2, unsigned int primtiveIndex = -1);
 
public:
  void insert_node(AABB anAABB);
 
  void set_fatness(double fatness) {
    _fatness = fatness;
  };
 
  bool update_primitive(unsigned int primitiveIndex, AABB tightAABB);
 
  void remove_primitive(unsigned int primitiveIndex);
 
  void clear();
 
  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;
  };
 
  const int NodeBalance(unsigned int nodeIndex) const {
    return _nodes[_nodes[nodeIndex].leftNode].height-_nodes[_nodes[nodeIndex].rightNode].height;
  };
 
  const bool Primitiveexists(unsigned int primitiveIndex) const;
 
  void PrimitivesList(std::vector<unsigned int> &primitivesList) const;
 
  void collidersPairs(std::vector<std::pair<unsigned int, unsigned int> > &collidersPairs) const;
 
  void collidersList(unsigned int primitiveIndex, std::vector<unsigned int> &collidersList) const;
 
  /* ******************************************** */
  /* DEBUGGING METHODS                            */
  /* ******************************************** */
  void printAABBNodes();
  void saveAABBs();
  void saveAABBs(std::vector<unsigned int> primitivesList);
 
private:
  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);
 
  void remove_node(unsigned int leafNode);
 
  void delete_node(unsigned int aNodeIndex);
 
  void delete_aabb(unsigned int anAABBIndex);
 
  unsigned int balance_node(unsigned int rootNodeIndex);
 
  unsigned int rotate_left(unsigned int rootNodeIndex);
 
  unsigned int rotate_right(unsigned int rootNodeIndex);
 
  void update_node_aabb(unsigned int aNode);
 
  void update_node_height(unsigned int aNode);
 
  const bool aabb_do_overlap(unsigned int aabb1, unsigned int aabb2) const;
 
  const bool is_aabb_contain_aabb(unsigned int anAABBIndex, AABB anAABB) const;
 
private:
  static const unsigned int NotInList = (unsigned int)(-1);
 
private:
  double _fatness;
 
  unsigned int _aabbsCount;
 
  unsigned int _node_count;
 
  unsigned int _rootNodeIndex;
 
  unsigned int _firstFreeNodeIndex;
 
  unsigned int _firstFreeAABBIndex;
 
  std::vector<unsigned int> _primitivesToNode;
 
  std::vector<AABB> _aabbs;
 
  std::vector<AABBNode> _nodes;
};
 
 
#endif /* DynamicAABBTree_hpp */