VecGeom/management/HybridManager2.h

0001 /*
0002  * HybridManager2.h
0003  *
0004  *  Created on: 27.08.2015 by yang.zhang@cern.ch
0005  *  integrated into main development line by sandro.wenzel@cern.ch 24.11.2015
0006  *
0007  */
0008
0009 #ifndef VECGEOM_HYBRIDMANAGER_H
0010 #define VECGEOM_HYBRIDMANAGER_H
0011
0012 #include "VecGeom/base/Global.h"
0013
0014 #include "VecGeom/volumes/PlacedVolume.h"
0015 #include "VecGeom/base/SOA3D.h"
0016 #include "VecGeom/base/Vector3D.h"
0017 #include "VecGeom/management/GeoManager.h"
0018 #include "VecGeom/base/Transformation3D.h"
0019 #include "VecGeom/volumes/kernel/BoxImplementation.h"
0020 #include "VecGeom/base/AlignmentAllocator.h"
0021 #include "VecGeom/management/ABBoxManager.h"
0022
0023 #include <queue>
0024 #include <map>
0025 #include <vector>
0026
0027 namespace vecgeom {
0028 inline namespace VECGEOM_IMPL_NAMESPACE {
0029
0030 // a singleton class which manages a particular helper structure for voxelized navigation
0031 // the helper structure is a hybrid between a flat list of aligned bounding boxed and a pure boundary volume hierarchy
0032 // (BVH)
0033 // and is hence called "HybridManager": TODO: come up with a more appropriate name
0034 class HybridManager2 {
0035
0036 public:
0037   using Float_v = vecgeom::VectorBackend::Float_v;
0038   typedef float Real_t;
0039   typedef Vector3D<Float_v> ABBox_v;
0040
0041   // scalar or vector vectors
0042   typedef Vector3D<Precision> ABBox_s;
0043   // use old style arrays here as std::vector has some problems
0044   // with Vector3D<kVc::Double_t>
0045   typedef ABBox_s *ABBoxContainer_t;
0046   typedef ABBox_v *ABBoxContainer_v;
0047
0048   // first index is # daughter index, second is step
0049   typedef std::pair<int, double> BoxIdDistancePair_t;
0050   using HitContainer_t = std::vector<BoxIdDistancePair_t>;
0051
0052   // the actual class encapsulating the bounding boxes + tree structure information
0053   // for a shallow bounding volume hierarchy acceleration structure
0054   struct HybridBoxAccelerationStructure {
0055     size_t fNumberOfOriginalBoxes = 0; // the number of objects/original bounding boxes this structure is representing
0056     ABBoxContainer_v fABBoxes_v   = nullptr;
0057     std::vector<int> *fNodeToDaughters = nullptr;
0058   };
0059
0060 private:
0061   // keeps/registers an acceleration structure for logical volumes
0062   std::vector<HybridBoxAccelerationStructure const *> fStructureHolder;
0063
0064 public:
0065   // initialized the helper structure for a given logical volume
0066   void InitStructure(LogicalVolume const *lvol);
0067
0068   // initialized the helper structure for the complete geometry
0069   void InitVoxelStructureForCompleteGeometry()
0070   {
0071     std::vector<LogicalVolume const *> logicalvolumes;
0072     GeoManager::Instance().GetAllLogicalVolumes(logicalvolumes);
0073     for (auto lvol : logicalvolumes) {
0074       InitStructure(lvol);
0075     }
0076   }
0077
0078   static HybridManager2 &Instance()
0079   {
0080     static HybridManager2 manager;
0081     return manager;
0082   }
0083
0084   // removed/deletes the helper structure for a given logical volume
0085   void RemoveStructure(LogicalVolume const *lvol);
0086
0087   template <typename C, typename Compare>
0088   static void sort(C &v, Compare cmp)
0089   {
0090     std::sort(v.begin(), v.end(), cmp);
0091   }
0092
0093   // verbose output of helper structure
0094   VPlacedVolume const *PrintHybrid(LogicalVolume const *) const;
0095
0096   ABBoxContainer_v GetABBoxes_v(HybridBoxAccelerationStructure const &structure, int &size, int &numberOfNodes) const
0097   {
0098     constexpr auto kVS = vecCore::VectorSize<Float_v>();
0099     VECGEOM_ASSERT(structure.fNumberOfOriginalBoxes != 0);
0100     int numberOfFirstLevelNodes =
0101         structure.fNumberOfOriginalBoxes / kVS + (structure.fNumberOfOriginalBoxes % kVS == 0 ? 0 : 1);
0102     numberOfNodes = numberOfFirstLevelNodes + structure.fNumberOfOriginalBoxes;
0103     size = numberOfFirstLevelNodes / kVS + (numberOfFirstLevelNodes % kVS == 0 ? 0 : 1) + numberOfFirstLevelNodes;
0104     VECGEOM_ASSERT(structure.fABBoxes_v != nullptr);
0105     return structure.fABBoxes_v;
0106   }
0107
0108   HybridBoxAccelerationStructure const *GetAccStructure(LogicalVolume const *lvol) const
0109   {
0110     return fStructureHolder[lvol->id()];
0111   }
0112
0113   // public method allowing to build a hybrid acceleration structure
0114   // given a vector of aligned bounding boxes
0115   // can be used by clients (not coupled to LogicalVolumes)
0116   HybridBoxAccelerationStructure *BuildStructure(ABBoxManager<Precision>::ABBoxContainer_t alignedboxes,
0117                                                  size_t numberofboxes) const;
0118
0119 private:
0120   // private methods use
0121
0122   template <typename Container_t>
0123   void EqualizeClusters(Container_t &clusters, SOA3D<Precision> &centers, SOA3D<Precision> const &allvolumecenters,
0124                         size_t const maxNodeSize);
0125
0126   template <typename Container_t>
0127   void InitClustersWithKMeans(ABBoxManager<Precision>::ABBoxContainer_t, int, Container_t &, SOA3D<Precision> &,
0128                               SOA3D<Precision> &, int const numberOfInterations = 50) const;
0129
0130   void RecalculateCentres(SOA3D<Precision> &centers, SOA3D<Precision> const &allvolumecenters,
0131                           std::vector<std::vector<int>> const &clusters);
0132   struct OrderByDistance {
0133     bool operator()(std::pair<int, Precision> const &a, std::pair<int, Precision> const &b)
0134     {
0135       return a.second < b.second;
0136     }
0137   };
0138   typedef std::priority_queue<std::pair<int, Precision>, std::vector<std::pair<int, Precision>>, OrderByDistance>
0139       distanceQueue;
0140   void AssignVolumesToClusters(std::vector<std::vector<int>> &clusters, SOA3D<Precision> const &centers,
0141                                SOA3D<Precision> const &allvolumecenters);
0142
0143   void BuildStructure_v(LogicalVolume const *vol);
0144
0145   static bool IsBiggerCluster(std::vector<int> const &first, std::vector<int> const &second)
0146   {
0147     return first.size() > second.size();
0148   }
0149
0150 }; // end class
0151 } // namespace VECGEOM_IMPL_NAMESPACE
0152 } // namespace vecgeom
0153
0154 #endif