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