35aaaeb75a7fd0390847390469cdfc051bf991e1
[occt.git] / src / BVH / BVH_Tree.lxx
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 // =======================================================================
17 // function : Clear
18 // purpose  :
19 // =======================================================================
20 template<class T, int N>
21 void BVH_Tree<T, N>::Clear()
22 {
23   BVHTools::ArrayOp<T, N>::Clear (myMinPointBuffer);
24   BVHTools::ArrayOp<T, N>::Clear (myMaxPointBuffer);
25
26   BVHTools::ArrayOp<Standard_Integer, 4>::Clear (myNodeInfoBuffer);
27 }
28
29 // =======================================================================
30 // function : AddLeafNode
31 // purpose  :
32 // =======================================================================
33 template<class T, int N>
34 Standard_Integer BVH_Tree<T, N>::AddLeafNode (const BVH_VecNt&       theMinPoint,
35                                               const BVH_VecNt&       theMaxPoint,
36                                               const Standard_Integer theBegElem,
37                                               const Standard_Integer theEndElem)
38 {
39   BVHTools::ArrayOp<T, N>::Append (myMinPointBuffer, theMinPoint);
40   BVHTools::ArrayOp<T, N>::Append (myMaxPointBuffer, theMaxPoint);
41
42   BVHTools::ArrayOp<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (1, theBegElem, theEndElem, 0));
43
44   return static_cast<Standard_Integer> (BVHTools::ArrayOp<Standard_Integer, 4>::Size (myNodeInfoBuffer) - 1);
45 }
46
47 // =======================================================================
48 // function : AddInnerNode
49 // purpose  :
50 // =======================================================================
51 template<class T, int N>
52 Standard_Integer BVH_Tree<T, N>::AddInnerNode (const BVH_VecNt&       theMinPoint,
53                                                const BVH_VecNt&       theMaxPoint,
54                                                const Standard_Integer theLftChild,
55                                                const Standard_Integer theRghChild)
56 {
57   BVHTools::ArrayOp<T, N>::Append (myMinPointBuffer, theMinPoint);
58   BVHTools::ArrayOp<T, N>::Append (myMaxPointBuffer, theMaxPoint);
59
60   BVHTools::ArrayOp<Standard_Integer, 4>::Append (myNodeInfoBuffer, BVH_Vec4i (0, theLftChild, theRghChild, 0));
61
62   return static_cast<Standard_Integer> (BVHTools::ArrayOp<Standard_Integer, 4>::Size (myNodeInfoBuffer)  - 1);
63 }
64
65 // =======================================================================
66 // function : AddLeafNode
67 // purpose  :
68 // =======================================================================
69 template<class T, int N>
70 Standard_Integer BVH_Tree<T, N>::AddLeafNode (const BVH_Box<T, N>&   theAABB,
71                                               const Standard_Integer theBegElem,
72                                               const Standard_Integer theEndElem)
73 {
74   return AddLeafNode (theAABB.CornerMin(), theAABB.CornerMax(), theBegElem, theEndElem);
75 }
76
77 // =======================================================================
78 // function : AddInnerNode
79 // purpose  :
80 // =======================================================================
81 template<class T, int N>
82 Standard_Integer BVH_Tree<T, N>::AddInnerNode (const BVH_Box<T, N>&   theAABB,
83                                                const Standard_Integer theLftChild,
84                                                const Standard_Integer theRghChild)
85 {
86   return AddInnerNode (theAABB.CornerMin(), theAABB.CornerMax(), theLftChild, theRghChild);
87 }
88
89 namespace BVHTools
90 {
91   template<class T, int N>
92   void EstimateSAH (const BVH_Tree<T, N>*  theTree,
93                     const Standard_Integer theNode,
94                     T                      theProbability,
95                     T&                     theSAH)
96   {
97     BVH_Box<T, N> aBox (theTree->MinPoint (theNode),
98                         theTree->MaxPoint (theNode));
99
100     if (theTree->IsOuter (theNode))
101     {
102       theSAH += theProbability * (theTree->EndPrimitive (theNode) - theTree->BegPrimitive (theNode) + 1);
103     }
104     else
105     {
106       theSAH += theProbability * static_cast<T> (2.0);
107
108       BVH_Box<T, N> aLftBox (theTree->MinPoint (theTree->LeftChild (theNode)),
109                              theTree->MaxPoint (theTree->LeftChild (theNode)));
110
111       if (theProbability > 0.0)
112       {
113         EstimateSAH (theTree, theTree->LeftChild (theNode),
114                      theProbability * aLftBox.Area() / aBox.Area(), theSAH);
115       }
116
117       BVH_Box<T, N> aRghBox (theTree->MinPoint (theTree->RightChild (theNode)),
118                              theTree->MaxPoint (theTree->RightChild (theNode)));
119
120       if (theProbability > 0.0)
121       {
122         EstimateSAH (theTree, theTree->RightChild (theNode),
123                      theProbability * aRghBox.Area() / aBox.Area(), theSAH);
124       }
125     }
126   }
127 }
128
129 // =======================================================================
130 // function : EstimateSAH
131 // purpose  :
132 // =======================================================================
133 template<class T, int N>
134 T BVH_Tree<T, N>::EstimateSAH() const
135 {
136   T aSAH = static_cast<T> (0.0);
137   BVHTools::EstimateSAH (this, 0, static_cast<T> (1.0), aSAH);
138   return aSAH;
139 }