0026364: Foundation Classes, TKMath - Optimize BVH binned algorithm
[occt.git] / src / BVH / BVH_BinnedBuilder.hxx
1 // Created on: 2013-12-20
2 // Created by: Denis BOGOLEPOV
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_BinnedBuilder_Header
17 #define _BVH_BinnedBuilder_Header
18
19 #include <BVH_QueueBuilder.hxx>
20
21 #include <algorithm>
22
23 //! Stores parameters of single bin (slice of AABB).
24 template<class T, int N>
25 struct BVH_Bin
26 {
27   //! Creates new node bin.
28   BVH_Bin() : Count (0) {}
29
30   Standard_Integer Count; //!< Number of primitives in the bin
31   BVH_Box<T, N>    Box;   //!< AABB of primitives in the bin
32 };
33
34 //! Performs construction of BVH tree using binned SAH algorithm. Number
35 //! of bins controls BVH quality in cost of construction time (greater -
36 //! better). For optimal results, use 32 - 48 bins. However, reasonable
37 //! performance is provided even for 4 - 8 bins (it is only 10-20% lower
38 //! in comparison with optimal settings). Note that multiple threads can
39 //! be used only with thread safe BVH primitive sets.
40 template<class T, int N, int Bins = 32>
41 class BVH_BinnedBuilder : public BVH_QueueBuilder<T, N>
42 {
43 public:
44
45   //! Type of the array of bins of BVH tree node.
46   typedef BVH_Bin<T, N> BVH_BinVector[Bins];
47
48   //! Describes split plane candidate.
49   struct BVH_SplitPlane
50   {
51     BVH_Bin<T, N> LftVoxel;
52     BVH_Bin<T, N> RghVoxel;
53   };
54
55   //! Type of the array of split plane candidates.
56   typedef BVH_SplitPlane BVH_SplitPlanes[Bins + 1];
57
58 public:
59
60   //! Creates binned SAH BVH builder.
61   BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize = 5,
62                      const Standard_Integer theMaxTreeDepth = 32,
63                      const Standard_Boolean theDoMainSplits = 0,
64                      const Standard_Integer theNumOfThreads = 1);
65
66   //! Releases resources of binned SAH BVH builder.
67   virtual ~BVH_BinnedBuilder();
68
69 protected:
70
71   //! Performs splitting of the given BVH node.
72   typename BVH_QueueBuilder<T, N>::BVH_ChildNodes BuildNode (BVH_Set<T, N>*         theSet,
73                                                              BVH_Tree<T, N>*        theBVH,
74                                                              const Standard_Integer theNode);
75
76   //! Arranges node primitives into bins.
77   virtual void GetSubVolumes (BVH_Set<T, N>*         theSet,
78                               BVH_Tree<T, N>*        theBVH,
79                               const Standard_Integer theNode,
80                               BVH_BinVector&         theBins,
81                               const Standard_Integer theAxis);
82
83 private:
84
85   Standard_Boolean myUseMainAxis; //!< Defines whether to search for the best split or use the widest axis
86
87 };
88
89 #include <BVH_BinnedBuilder.lxx>
90
91 #endif // _BVH_BinnedBuilder_Header