src/BVH/BVH_LinearBuilder.hxx

   1 // Created on: 2014-09-11
   2 // Created by: Danila ULYANOV
   3 // Copyright (c) 2013-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #ifndef _BVH_LinearBuilder_Header
  17 #define _BVH_LinearBuilder_Header
  18
  19 #include <BVH_Builder.hxx>
  20
  21 typedef std::pair<Standard_Integer, Standard_Integer> BVH_EncodedLink;
  22
  23 //! Performs fast BVH construction using LBVH building approach.
  24 //! Algorithm uses spatial Morton codes to reduce the BVH construction
  25 //! problem to a sorting problem (radix sort -- O(N) complexity). This
  26 //! Linear Bounding Volume Hierarchy (LBVH) builder produces BVH trees
  27 //! of lower quality compared to SAH-based BVH builders but it is over
  28 //! an order of magnitude faster (up to 3M triangles per second).
  29 //!
  30 //! For more details see:
  31 //! C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, and D. Manocha.
  32 //! Fast BVH construction on GPUs. Eurographics, 2009.
  33 template<class T, int N>
  34 class BVH_LinearBuilder : public BVH_Builder<T, N>
  35 {
  36 public:
  37
  38   typedef typename BVH::VectorType<T, N>::Type BVH_VecNt;
  39
  40 public:
  41
  42   //! Creates binned LBVH builder.
  43   BVH_LinearBuilder (const Standard_Integer theLeafNodeSize = 5,
  44                      const Standard_Integer theMaxTreeDepth = 32);
  45
  46   //! Releases resources of LBVH builder.
  47   virtual ~BVH_LinearBuilder();
  48
  49   //! Builds BVH.
  50   void Build (BVH_Set<T, N>*       theSet,
  51               BVH_Tree<T, N>*      theBVH,
  52               const BVH_Box<T, N>& theBox);
  53
  54 protected:
  55
  56   //! Emits hierarchy from sorted Morton codes.
  57   Standard_Integer EmitHierachy (BVH_Tree<T, N>*                        theBVH,
  58                                  const Standard_Integer                 theBit,
  59                                  const Standard_Integer                 theShift,
  60                                  std::vector<BVH_EncodedLink>::iterator theStart,
  61                                  std::vector<BVH_EncodedLink>::iterator theFinal);
  62
  63 };
  64
  65 #include <BVH_LinearBuilder.lxx>
  66
  67 #endif // _BVH_LinearBuilder_Header