0024739: TKOpenGl - port ray-tracing from OpenCL to GLSL for better integration and...
[occt.git] / src / BVH / BVH_Tree.lxx
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// =======================================================================
17// function : Clear
18// purpose :
19// =======================================================================
20template<class T, int N>
21void BVH_Tree<T, N>::Clear()
22{
fc73a202 23 myDepth = 0;
24
3c4e78f2 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// =======================================================================
35template<class T, int N>
36Standard_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// =======================================================================
53template<class T, int N>
54Standard_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// =======================================================================
71template<class T, int N>
72Standard_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// =======================================================================
83template<class T, int N>
84Standard_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
91namespace 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// =======================================================================
135template<class T, int N>
136T 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}