1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#include "bvh.h"
5#include "bvh_statistics.h"
6
7namespace embree
8{
9 template<int N>
10 BVHN<N>::BVHN (const PrimitiveType& primTy, Scene* scene)
11 : AccelData((N==4) ? AccelData::TY_BVH4 : (N==8) ? AccelData::TY_BVH8 : AccelData::TY_UNKNOWN),
12 primTy(&primTy), device(scene->device), scene(scene),
13 root(emptyNode), alloc(scene->device,scene->isStaticAccel()), numPrimitives(0), numVertices(0)
14 {
15 }
16
17 template<int N>
18 BVHN<N>::~BVHN ()
19 {
20 for (size_t i=0; i<objects.size(); i++)
21 delete objects[i];
22 }
23
24 template<int N>
25 void BVHN<N>::clear()
26 {
27 set(BVHN::emptyNode,empty,0);
28 alloc.clear();
29 }
30
31 template<int N>
32 void BVHN<N>::set (NodeRef root, const LBBox3fa& bounds, size_t numPrimitives)
33 {
34 this->root = root;
35 this->bounds = bounds;
36 this->numPrimitives = numPrimitives;
37 }
38
39 template<int N>
40 void BVHN<N>::clearBarrier(NodeRef& node)
41 {
42 if (node.isBarrier())
43 node.clearBarrier();
44 else if (!node.isLeaf()) {
45 BaseNode* n = node.baseNode(); // FIXME: flags should be stored in BVH
46 for (size_t c=0; c<N; c++)
47 clearBarrier(n->child(c));
48 }
49 }
50
51 template<int N>
52 void BVHN<N>::layoutLargeNodes(size_t num)
53 {
54#if defined(__64BIT__) // do not use tree rotations on 32 bit platforms, barrier bit in NodeRef will cause issues
55 struct NodeArea
56 {
57 __forceinline NodeArea() {}
58
59 __forceinline NodeArea(NodeRef& node, const BBox3fa& bounds)
60 : node(&node), A(node.isLeaf() ? float(neg_inf) : area(bounds)) {}
61
62 __forceinline bool operator< (const NodeArea& other) const {
63 return this->A < other.A;
64 }
65
66 NodeRef* node;
67 float A;
68 };
69 std::vector<NodeArea> lst;
70 lst.reserve(num);
71 lst.push_back(NodeArea(root,empty));
72
73 while (lst.size() < num)
74 {
75 std::pop_heap(lst.begin(), lst.end());
76 NodeArea n = lst.back(); lst.pop_back();
77 if (!n.node->isAABBNode()) break;
78 AABBNode* node = n.node->getAABBNode();
79 for (size_t i=0; i<N; i++) {
80 if (node->child(i) == BVHN::emptyNode) continue;
81 lst.push_back(NodeArea(node->child(i),node->bounds(i)));
82 std::push_heap(lst.begin(), lst.end());
83 }
84 }
85
86 for (size_t i=0; i<lst.size(); i++)
87 lst[i].node->setBarrier();
88
89 root = layoutLargeNodesRecursion(root,alloc.getCachedAllocator());
90#endif
91 }
92
93 template<int N>
94 typename BVHN<N>::NodeRef BVHN<N>::layoutLargeNodesRecursion(NodeRef& node, const FastAllocator::CachedAllocator& allocator)
95 {
96 if (node.isBarrier()) {
97 node.clearBarrier();
98 return node;
99 }
100 else if (node.isAABBNode())
101 {
102 AABBNode* oldnode = node.getAABBNode();
103 AABBNode* newnode = (BVHN::AABBNode*) allocator.malloc0(sizeof(BVHN::AABBNode),byteNodeAlignment);
104 *newnode = *oldnode;
105 for (size_t c=0; c<N; c++)
106 newnode->child(c) = layoutLargeNodesRecursion(oldnode->child(c),allocator);
107 return encodeNode(newnode);
108 }
109 else return node;
110 }
111
112 template<int N>
113 double BVHN<N>::preBuild(const std::string& builderName)
114 {
115 if (builderName == "")
116 return inf;
117
118 if (device->verbosity(2))
119 {
120 Lock<MutexSys> lock(g_printMutex);
121 std::cout << "building BVH" << N << (builderName.find("MBlur") != std::string::npos ? "MB" : "") << "<" << primTy->name() << "> using " << builderName << " ..." << std::endl << std::flush;
122 }
123
124 double t0 = 0.0;
125 if (device->benchmark || device->verbosity(2)) t0 = getSeconds();
126 return t0;
127 }
128
129 template<int N>
130 void BVHN<N>::postBuild(double t0)
131 {
132 if (t0 == double(inf))
133 return;
134
135 double dt = 0.0;
136 if (device->benchmark || device->verbosity(2))
137 dt = getSeconds()-t0;
138
139 std::unique_ptr<BVHNStatistics<N>> stat;
140
141 /* print statistics */
142 if (device->verbosity(2))
143 {
144 if (!stat) stat.reset(new BVHNStatistics<N>(this));
145 const size_t usedBytes = alloc.getUsedBytes();
146 Lock<MutexSys> lock(g_printMutex);
147 std::cout << "finished BVH" << N << "<" << primTy->name() << "> : " << 1000.0f*dt << "ms, " << 1E-6*double(numPrimitives)/dt << " Mprim/s, " << 1E-9*double(usedBytes)/dt << " GB/s" << std::endl;
148
149 if (device->verbosity(2))
150 std::cout << stat->str();
151
152 if (device->verbosity(2))
153 {
154 FastAllocator::AllStatistics stat(&alloc);
155 for (size_t i=0; i<objects.size(); i++)
156 if (objects[i])
157 stat = stat + FastAllocator::AllStatistics(&objects[i]->alloc);
158
159 stat.print(numPrimitives);
160 }
161
162 if (device->verbosity(3))
163 {
164 alloc.print_blocks();
165 for (size_t i=0; i<objects.size(); i++)
166 if (objects[i])
167 objects[i]->alloc.print_blocks();
168 }
169
170 std::cout << std::flush;
171 }
172
173 /* benchmark mode */
174 if (device->benchmark)
175 {
176 if (!stat) stat.reset(new BVHNStatistics<N>(this));
177 Lock<MutexSys> lock(g_printMutex);
178 std::cout << "BENCHMARK_BUILD " << dt << " " << double(numPrimitives)/dt << " " << stat->sah() << " " << stat->bytesUsed() << " BVH" << N << "<" << primTy->name() << ">" << std::endl << std::flush;
179 }
180 }
181
182#if defined(__AVX__)
183 template class BVHN<8>;
184#endif
185
186#if !defined(__AVX__) || !defined(EMBREE_TARGET_SSE2) && !defined(EMBREE_TARGET_SSE42) || defined(__aarch64__)
187 template class BVHN<4>;
188#endif
189}
190
191