21#include <G3D/Vector3.h>
33#define MAX_STACK_SIZE 64
39 static_assert(
sizeof(float) ==
sizeof(
uint32),
"Size of uint32 and float must be equal for this to work");
41 memcpy(&ret, &f,
sizeof(
float));
47 static_assert(
sizeof(float) ==
sizeof(
uint32),
"Size of uint32 and float must be equal for this to work");
49 memcpy(&ret, &i,
sizeof(
uint32));
72 bounds = G3D::AABox::empty();
74 tree.push_back(3u << 30u);
75 tree.insert(tree.end(), 2, 0);
78 BIH() { init_empty(); }
79 template <
class BoundsFunc,
class PrimArray>
80 void build(PrimArray
const& primitives, BoundsFunc& getBounds,
uint32 leafSize = 3,
bool printStats =
false)
82 if (primitives.size() == 0)
93 getBounds(primitives[0], bounds);
97 getBounds(primitives[i], dat.
primBound[i]);
100 std::vector<uint32> tempTree;
102 buildHierarchy(tempTree, dat, stats);
116 template<
typename RayCallback>
117 void intersectRay(
const G3D::Ray &r, RayCallback& intersectCallback,
float &maxDist,
bool stopAtFirst =
false)
const
119 float intervalMin = -1.f;
120 float intervalMax = -1.f;
121 G3D::Vector3
const& org = r.origin();
122 G3D::Vector3
const& dir = r.direction();
123 G3D::Vector3
const& invDir = r.invDirection();
124 for (
int i=0; i<3; ++i)
126 if (G3D::fuzzyNe(dir[i], 0.0f))
128 float t1 = (bounds.low()[i] - org[i]) * invDir[i];
129 float t2 = (bounds.high()[i] - org[i]) * invDir[i];
132 if (t1 > intervalMin)
134 if (t2 < intervalMax || intervalMax < 0.f)
138 if (intervalMax <= 0 || intervalMin >= maxDist)
143 if (intervalMin > intervalMax)
145 intervalMin = std::max(intervalMin, 0.f);
146 intervalMax = std::min(intervalMax, maxDist);
154 for (
int i=0; i<3; ++i)
157 offsetBack[i] = offsetFront[i] ^ 1;
158 offsetFront3[i] = offsetFront[i] * 3;
159 offsetBack3[i] = offsetBack[i] * 3;
174 uint32 axis = (tn & (3 << 30)) >> 30;
175 bool BVH2 = (tn & (1 << 29)) != 0;
176 int offset = tn & ~(7 << 29);
182 float tf = (
intBitsToFloat(tree[node + offsetFront[axis]]) - org[axis]) * invDir[axis];
183 float tb = (
intBitsToFloat(tree[node + offsetBack[axis]]) - org[axis]) * invDir[axis];
185 if (tf < intervalMin && tb > intervalMax)
187 int back = offset + offsetBack3[axis];
190 if (tf < intervalMin) {
191 intervalMin = (tb >= intervalMin) ? tb : intervalMin;
194 node = offset + offsetFront3[axis];
196 if (tb > intervalMax) {
197 intervalMax = (tf <= intervalMax) ? tf : intervalMax;
202 stack[stackPos].
node = back;
203 stack[stackPos].
tnear = (tb >= intervalMin) ? tb : intervalMin;
204 stack[stackPos].
tfar = intervalMax;
207 intervalMax = (tf <= intervalMax) ? tf : intervalMax;
213 int n = tree[node + 1];
215 bool hit = intersectCallback(r, objects[offset], maxDist, stopAtFirst);
216 if (stopAtFirst && hit)
return;
227 float tf = (
intBitsToFloat(tree[node + offsetFront[axis]]) - org[axis]) * invDir[axis];
228 float tb = (
intBitsToFloat(tree[node + offsetBack[axis]]) - org[axis]) * invDir[axis];
230 intervalMin = (tf >= intervalMin) ? tf : intervalMin;
231 intervalMax = (tb <= intervalMax) ? tb : intervalMax;
232 if (intervalMin > intervalMax)
244 intervalMin = stack[stackPos].
tnear;
245 if (maxDist < intervalMin)
247 node = stack[stackPos].
node;
248 intervalMax = stack[stackPos].
tfar;
254 template<
typename IsectCallback>
255 void intersectPoint(
const G3D::Vector3 &p, IsectCallback& intersectCallback)
const
257 if (!bounds.contains(p))
268 uint32 axis = (tn & (3 << 30)) >> 30;
269 bool BVH2 = (tn & (1 << 29)) != 0;
270 int offset = tn & ~(7 << 29);
279 if (tl < p[axis] && tr > p[axis])
281 int right = offset + 3;
294 stack[stackPos].
node = right;
301 int n = tree[node + 1];
303 intersectCallback(p, objects[offset]);
317 if (tl > p[axis] || tr < p[axis])
328 node = stack[stackPos].
node;
332 bool writeToFile(FILE* wf)
const;
333 bool readFromFile(FILE* rf);
370 numNodes(0), numLeaves(0), sumObjects(0), minObjects(0x0FFFFFFF),
371 maxObjects(0xFFFFFFFF), sumDepth(0), minDepth(0x0FFFFFFF),
372 maxDepth(0xFFFFFFFF), numBVH2(0)
374 for (
int i=0; i<6; ++i) numLeavesN[i] = 0;
379 void updateLeaf(
int depth,
int n);
383 void buildHierarchy(std::vector<uint32> &tempTree, buildData &dat, BuildStats &stats);
388 tempTree[nodeIndex + 0] = (3 << 30) | left;
389 tempTree[nodeIndex + 1] = right - left + 1;
392 void subdivide(
int left,
int right, std::vector<uint32> &tempTree, buildData &dat,
AABound &gridBox,
AABound &nodeBox,
int nodeIndex,
int depth, BuildStats &stats);
static float intBitsToFloat(uint32 i)
static uint32 floatToRawIntBits(float f)
void build(PrimArray const &primitives, BoundsFunc &getBounds, uint32 leafSize=3, bool printStats=false)
void createNode(std::vector< uint32 > &tempTree, int nodeIndex, uint32 left, uint32 right) const
std::vector< uint32 > objects
std::vector< uint32 > tree
void intersectPoint(const G3D::Vector3 &p, IsectCallback &intersectCallback) const
void intersectRay(const G3D::Ray &r, RayCallback &intersectCallback, float &maxDist, bool stopAtFirst=false) const