0026364: Foundation Classes, TKMath - Optimize BVH binned algorithm
[occt.git] / src / BVH / BVH_BinnedBuilder.hxx
CommitLineData
3c4e78f2 1// Created on: 2013-12-20
2// Created by: Denis BOGOLEPOV
d5f74e42 3// Copyright (c) 2013-2014 OPEN CASCADE SAS
3c4e78f2 4//
5// This file is part of Open CASCADE Technology software library.
6//
d5f74e42 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
3c4e78f2 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
0ef61b50 19#include <BVH_QueueBuilder.hxx>
3c4e78f2 20
a096a7a5 21#include <algorithm>
22
65578e1c 23//! Stores parameters of single bin (slice of AABB).
3c4e78f2 24template<class T, int N>
25struct BVH_Bin
26{
27 //! Creates new node bin.
28 BVH_Bin() : Count (0) {}
29
30 Standard_Integer Count; //!< Number of primitives in the bin
228de226 31 BVH_Box<T, N> Box; //!< AABB of primitives in the bin
3c4e78f2 32};
33
65578e1c 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.
3c4e78f2 40template<class T, int N, int Bins = 32>
0ef61b50 41class BVH_BinnedBuilder : public BVH_QueueBuilder<T, N>
3c4e78f2 42{
43public:
44
a1c05aa5 45 //! Type of the array of bins of BVH tree node.
3c4e78f2 46 typedef BVH_Bin<T, N> BVH_BinVector[Bins];
47
a1c05aa5 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
3c4e78f2 58public:
59
60 //! Creates binned SAH BVH builder.
61 BVH_BinnedBuilder (const Standard_Integer theLeafNodeSize = 5,
f751596e 62 const Standard_Integer theMaxTreeDepth = 32,
65578e1c 63 const Standard_Boolean theDoMainSplits = 0,
64 const Standard_Integer theNumOfThreads = 1);
3c4e78f2 65
66 //! Releases resources of binned SAH BVH builder.
67 virtual ~BVH_BinnedBuilder();
68
69protected:
70
65578e1c 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);
3c4e78f2 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
f751596e 83private:
84
85 Standard_Boolean myUseMainAxis; //!< Defines whether to search for the best split or use the widest axis
86
3c4e78f2 87};
88
89#include <BVH_BinnedBuilder.lxx>
90
91#endif // _BVH_BinnedBuilder_Header