Project SkyFire Core
SkyFire 5.4.8 server core API documentation
Loading...
Searching...
No Matches
BoundingIntervalHierarchy.h
Go to the documentation of this file.
1/*
2* This file is part of Project SkyFire https://www.projectskyfire.org.
3* See LICENSE.md file for Copyright information
4*/
5
6#ifndef _BIH_H
7#define _BIH_H
8
9#include "G3D/Vector3.h"
10#include "G3D/Ray.h"
11#include "G3D/AABox.h"
12
13#include "Define.h"
14
15#include <stdexcept>
16#include <vector>
17#include <algorithm>
18#include <limits>
19#include <cmath>
20
21#define MAX_STACK_SIZE 64
22
23static inline uint32 floatToRawIntBits(float f)
24{
25 union
26 {
27 uint32 ival;
28 float fval;
29 } temp;
30 temp.fval=f;
31 return temp.ival;
32}
33
34static inline float intBitsToFloat(uint32 i)
35{
36 union
37 {
38 uint32 ival;
39 float fval;
40 } temp;
41 temp.ival=i;
42 return temp.fval;
43}
44
45struct AABound
46{
47 G3D::Vector3 lo, hi;
48};
49
56
57class BIH
58{
59 private:
60 void init_empty()
61 {
62 tree.clear();
63 objects.clear();
64 // create space for the first node
65 tree.push_back(3u << 30u); // dummy leaf
66 tree.insert(tree.end(), 2, 0);
67 }
68 public:
69 BIH() { init_empty(); }
70 template< class BoundsFunc, class PrimArray >
71 void build(const PrimArray &primitives, BoundsFunc &getBounds, uint32 leafSize = 3, bool printStats=false)
72 {
73 if (primitives.size() == 0)
74 {
75 init_empty();
76 return;
77 }
78
79 buildData dat;
80 dat.maxPrims = leafSize;
81 dat.numPrims = primitives.size();
82 dat.indices = new uint32[dat.numPrims];
83 dat.primBound = new G3D::AABox[dat.numPrims];
84 getBounds(primitives[0], bounds);
85 for (uint32 i=0; i<dat.numPrims; ++i)
86 {
87 dat.indices[i] = i;
88 getBounds(primitives[i], dat.primBound[i]);
89 bounds.merge(dat.primBound[i]);
90 }
91 std::vector<uint32> tempTree;
92 BuildStats stats;
93 buildHierarchy(tempTree, dat, stats);
94 if (printStats)
95 stats.printStats();
96
97 objects.resize(dat.numPrims);
98 for (uint32 i=0; i<dat.numPrims; ++i)
99 objects[i] = dat.indices[i];
100 //nObjects = dat.numPrims;
101 tree = tempTree;
102 delete[] dat.primBound;
103 delete[] dat.indices;
104 }
105 uint32 primCount() const { return objects.size(); }
106
107 template<typename RayCallback>
108 void intersectRay(const G3D::Ray &r, RayCallback& intersectCallback, float &maxDist, bool stopAtFirst=false) const
109 {
110 float intervalMin = -1.f;
111 float intervalMax = -1.f;
112 G3D::Vector3 org = r.origin();
113 G3D::Vector3 dir = r.direction();
114 G3D::Vector3 invDir;
115 for (int i=0; i<3; ++i)
116 {
117 invDir[i] = 1.f / dir[i];
118 if (G3D::fuzzyNe(dir[i], 0.0f))
119 {
120 float t1 = (bounds.low()[i] - org[i]) * invDir[i];
121 float t2 = (bounds.high()[i] - org[i]) * invDir[i];
122 if (t1 > t2)
123 std::swap(t1, t2);
124 if (t1 > intervalMin)
125 intervalMin = t1;
126 if (t2 < intervalMax || intervalMax < 0.f)
127 intervalMax = t2;
128 // intervalMax can only become smaller for other axis,
129 // and intervalMin only larger respectively, so stop early
130 if (intervalMax <= 0 || intervalMin >= maxDist)
131 return;
132 }
133 }
134
135 if (intervalMin > intervalMax)
136 return;
137 intervalMin = std::max(intervalMin, 0.f);
138 intervalMax = std::min(intervalMax, maxDist);
139
140 uint32 offsetFront[3];
141 uint32 offsetBack[3];
142 uint32 offsetFront3[3];
143 uint32 offsetBack3[3];
144 // compute custom offsets from direction sign bit
145
146 for (int i=0; i<3; ++i)
147 {
148 offsetFront[i] = floatToRawIntBits(dir[i]) >> 31;
149 offsetBack[i] = offsetFront[i] ^ 1;
150 offsetFront3[i] = offsetFront[i] * 3;
151 offsetBack3[i] = offsetBack[i] * 3;
152
153 // avoid always adding 1 during the inner loop
154 ++offsetFront[i];
155 ++offsetBack[i];
156 }
157
158 StackNode stack[MAX_STACK_SIZE];
159 int stackPos = 0;
160 int node = 0;
161
162 while (true) {
163 while (true)
164 {
165 uint32 tn = tree[node];
166 uint32 axis = (tn & (3 << 30)) >> 30;
167 bool BVH2 = tn & (1 << 29);
168 int offset = tn & ~(7 << 29);
169 if (!BVH2)
170 {
171 if (axis < 3)
172 {
173 // "normal" interior node
174 float tf = (intBitsToFloat(tree[node + offsetFront[axis]]) - org[axis]) * invDir[axis];
175 float tb = (intBitsToFloat(tree[node + offsetBack[axis]]) - org[axis]) * invDir[axis];
176 // ray passes between clip zones
177 if (tf < intervalMin && tb > intervalMax)
178 break;
179 int back = offset + offsetBack3[axis];
180 node = back;
181 // ray passes through far node only
182 if (tf < intervalMin) {
183 intervalMin = (tb >= intervalMin) ? tb : intervalMin;
184 continue;
185 }
186 node = offset + offsetFront3[axis]; // front
187 // ray passes through near node only
188 if (tb > intervalMax) {
189 intervalMax = (tf <= intervalMax) ? tf : intervalMax;
190 continue;
191 }
192 // ray passes through both nodes
193 // push back node
194 stack[stackPos].node = back;
195 stack[stackPos].tnear = (tb >= intervalMin) ? tb : intervalMin;
196 stack[stackPos].tfar = intervalMax;
197 stackPos++;
198 // update ray interval for front node
199 intervalMax = (tf <= intervalMax) ? tf : intervalMax;
200 continue;
201 }
202 else
203 {
204 // leaf - test some objects
205 int n = tree[node + 1];
206 while (n > 0) {
207 bool hit = intersectCallback(r, objects[offset], maxDist, stopAtFirst);
208 if (stopAtFirst && hit) return;
209 --n;
210 ++offset;
211 }
212 break;
213 }
214 }
215 else
216 {
217 if (axis>2)
218 return; // should not happen
219 float tf = (intBitsToFloat(tree[node + offsetFront[axis]]) - org[axis]) * invDir[axis];
220 float tb = (intBitsToFloat(tree[node + offsetBack[axis]]) - org[axis]) * invDir[axis];
221 node = offset;
222 intervalMin = (tf >= intervalMin) ? tf : intervalMin;
223 intervalMax = (tb <= intervalMax) ? tb : intervalMax;
224 if (intervalMin > intervalMax)
225 break;
226 continue;
227 }
228 } // traversal loop
229 do
230 {
231 // stack is empty?
232 if (stackPos == 0)
233 return;
234 // move back up the stack
235 stackPos--;
236 intervalMin = stack[stackPos].tnear;
237 if (maxDist < intervalMin)
238 continue;
239 node = stack[stackPos].node;
240 intervalMax = stack[stackPos].tfar;
241 break;
242 } while (true);
243 }
244 }
245
246 template<typename IsectCallback>
247 void intersectPoint(const G3D::Vector3 &p, IsectCallback& intersectCallback) const
248 {
249 if (!bounds.contains(p))
250 return;
251
252 StackNode stack[MAX_STACK_SIZE];
253 int stackPos = 0;
254 int node = 0;
255
256 while (true) {
257 while (true)
258 {
259 uint32 tn = tree[node];
260 uint32 axis = (tn & (3 << 30)) >> 30;
261 bool BVH2 = tn & (1 << 29);
262 int offset = tn & ~(7 << 29);
263 if (!BVH2)
264 {
265 if (axis < 3)
266 {
267 // "normal" interior node
268 float tl = intBitsToFloat(tree[node + 1]);
269 float tr = intBitsToFloat(tree[node + 2]);
270 // point is between clip zones
271 if (tl < p[axis] && tr > p[axis])
272 break;
273 int right = offset + 3;
274 node = right;
275 // point is in right node only
276 if (tl < p[axis]) {
277 continue;
278 }
279 node = offset; // left
280 // point is in left node only
281 if (tr > p[axis]) {
282 continue;
283 }
284 // point is in both nodes
285 // push back right node
286 stack[stackPos].node = right;
287 stackPos++;
288 continue;
289 }
290 else
291 {
292 // leaf - test some objects
293 int n = tree[node + 1];
294 while (n > 0) {
295 intersectCallback(p, objects[offset]); // !!!
296 --n;
297 ++offset;
298 }
299 break;
300 }
301 }
302 else // BVH2 node (empty space cut off left and right)
303 {
304 if (axis>2)
305 return; // should not happen
306 float tl = intBitsToFloat(tree[node + 1]);
307 float tr = intBitsToFloat(tree[node + 2]);
308 node = offset;
309 if (tl > p[axis] || tr < p[axis])
310 break;
311 continue;
312 }
313 } // traversal loop
314
315 // stack is empty?
316 if (stackPos == 0)
317 return;
318 // move back up the stack
319 stackPos--;
320 node = stack[stackPos].node;
321 }
322 }
323
324 bool writeToFile(FILE* wf) const;
325 bool readFromFile(FILE* rf);
326
327 protected:
328 std::vector<uint32> tree;
329 std::vector<uint32> objects;
330 G3D::AABox bounds;
331
332 struct buildData
333 {
334 uint32 *indices;
335 G3D::AABox *primBound;
336 uint32 numPrims;
337 int maxPrims;
338 };
339 struct StackNode
340 {
341 uint32 node;
342 float tnear;
343 float tfar;
344 };
345
346 class BuildStats
347 {
348 private:
349 int numNodes;
350 int numLeaves;
351 int sumObjects;
352 int minObjects;
353 int maxObjects;
354 int sumDepth;
355 int minDepth;
356 int maxDepth;
357 int numLeavesN[6] = { };
358 int numBVH2;
359
360 public:
361 BuildStats():
362 numNodes(0), numLeaves(0), sumObjects(0), minObjects(0x0FFFFFFF),
363 maxObjects(0xFFFFFFFF), sumDepth(0), minDepth(0x0FFFFFFF),
364 maxDepth(0xFFFFFFFF), numBVH2(0)
365 {
366 for (int i=0; i<6; ++i) numLeavesN[i] = 0;
367 }
368
369 void updateInner() { numNodes++; }
370 void updateBVH2() { numBVH2++; }
371 void updateLeaf(int depth, int n);
372 void printStats();
373 };
374
375 void buildHierarchy(std::vector<uint32> &tempTree, buildData &dat, BuildStats &stats);
376
377 void createNode(std::vector<uint32> &tempTree, int nodeIndex, uint32 left, uint32 right) const
378 {
379 // write leaf node
380 tempTree[nodeIndex + 0] = (3 << 30) | left;
381 tempTree[nodeIndex + 1] = right - left + 1;
382 }
383
384 void subdivide(int left, int right, std::vector<uint32> &tempTree, buildData &dat, AABound &gridBox, AABound &nodeBox, int nodeIndex, int depth, BuildStats &stats);
385};
386
387#endif // _BIH_H
intBitsToFloat
static float intBitsToFloat(uint32 i)
Definition BoundingIntervalHierarchy.h:34
MAX_STACK_SIZE
#define MAX_STACK_SIZE
Definition BoundingIntervalHierarchy.h:21
floatToRawIntBits
static uint32 floatToRawIntBits(float f)
Definition BoundingIntervalHierarchy.h:23
uint32
std::uint32_t uint32
Definition Define.h:77
BIH::BuildStats::updateLeaf
void updateLeaf(int depth, int n)
Definition BoundingIntervalHierarchy.cpp:265
BIH::writeToFile
bool writeToFile(FILE *wf) const
Definition BoundingIntervalHierarchy.cpp:234
BIH::build
void build(const PrimArray &primitives, BoundsFunc &getBounds, uint32 leafSize=3, bool printStats=false)
Definition BoundingIntervalHierarchy.h:71
BIH::createNode
void createNode(std::vector< uint32 > &tempTree, int nodeIndex, uint32 left, uint32 right) const
Definition BoundingIntervalHierarchy.h:377
BIH::objects
std::vector< uint32 > objects
Definition BoundingIntervalHierarchy.h:329
BIH::buildHierarchy
void buildHierarchy(std::vector< uint32 > &tempTree, buildData &dat, BuildStats &stats)
Definition BoundingIntervalHierarchy.cpp:14
BIH::tree
std::vector< uint32 > tree
Definition BoundingIntervalHierarchy.h:328
BIH::primCount
uint32 primCount() const
Definition BoundingIntervalHierarchy.h:105
BIH::readFromFile
bool readFromFile(FILE *rf)
Definition BoundingIntervalHierarchy.cpp:248
BIH::bounds
G3D::AABox bounds
Definition BoundingIntervalHierarchy.h:330
BIH::intersectPoint
void intersectPoint(const G3D::Vector3 &p, IsectCallback &intersectCallback) const
Definition BoundingIntervalHierarchy.h:247
BIH::intersectRay
void intersectRay(const G3D::Ray &r, RayCallback &intersectCallback, float &maxDist, bool stopAtFirst=false) const
Definition BoundingIntervalHierarchy.h:108
BIH::subdivide
void subdivide(int left, int right, std::vector< uint32 > &tempTree, buildData &dat, AABound &gridBox, AABound &nodeBox, int nodeIndex, int depth, BuildStats &stats)
Definition BoundingIntervalHierarchy.cpp:28