102 lines
2.6 KiB
C++
102 lines
2.6 KiB
C++
/* -----------------------------------------------------------------------------
|
|
GSFramework
|
|
Copyright 2001-2013 Emmanuel Julien. All Rights Reserved.
|
|
----------------------------------------------------------------------------- */
|
|
|
|
|
|
#include "bih/bih.h"
|
|
|
|
using namespace GS;
|
|
using namespace GS::BIH;
|
|
|
|
|
|
//------------------------------------------------------------------------------
|
|
void Tree::Raytrace(Trace &trace, const Vector4 &s, const Vector4 &d, float l, void *parm)
|
|
{
|
|
trace.has_i = false;
|
|
trace.i_t = -1;
|
|
trace.node_visited = 0;
|
|
trace.stack_pos = 0;
|
|
|
|
// Intersect BIH bounding volume.
|
|
float tmin, tmax;
|
|
if (!minmax.IntersectRay(s, d, tmin, tmax))
|
|
return;
|
|
|
|
// Reject if intersection is too far away.
|
|
if ((l > 0) && (tmin >= l))
|
|
return;
|
|
|
|
// Initialize trace.
|
|
trace.s = s;
|
|
trace.d = d;
|
|
|
|
tmax = ((l > 0) && (tmax > l)) ? l : tmax;
|
|
|
|
// Iterative trace.
|
|
float i_t[2];
|
|
|
|
for (Node *node = root; node; )
|
|
{
|
|
if (!trace.has_i || ((tmin < trace.i_t) && trace.want_closest)) // Only bother about rays that could lead to a closer hit.
|
|
{
|
|
while (node->axis != 3)
|
|
{
|
|
if (d[node->axis] == 0) // Axis aligned.
|
|
{
|
|
if (node->split[0] > s[node->axis])
|
|
{
|
|
if (s[node->axis] > node->split[1])
|
|
{
|
|
trace.stack[trace.stack_pos].node = &((Node *)node->p)[1];
|
|
trace.stack[trace.stack_pos].tmin = tmin;
|
|
trace.stack[trace.stack_pos++].tmax = tmax;
|
|
}
|
|
node = &((Node *)node->p)[0];
|
|
}
|
|
else if (s[node->axis] > node->split[1])
|
|
node = &((Node *)node->p)[1];
|
|
else break; // Empty space.
|
|
}
|
|
else
|
|
{
|
|
float idn = 1.f / d[node->axis];
|
|
i_t[0] = (node->split[0] - s[node->axis]) * idn;
|
|
i_t[1] = (node->split[1] - s[node->axis]) * idn;
|
|
|
|
int min = d[node->axis] > 0 ? 0 : 1, max = 1 - min;
|
|
|
|
if (i_t[min] > tmin)
|
|
{
|
|
if (tmax > i_t[max])
|
|
{
|
|
trace.stack[trace.stack_pos].node = &((Node *)node->p)[max];
|
|
trace.stack[trace.stack_pos].tmin = (i_t[max] > tmin) ? i_t[max] : tmin;
|
|
trace.stack[trace.stack_pos++].tmax = tmax;
|
|
}
|
|
node = &((Node *)node->p)[min];
|
|
tmax = (i_t[min] < tmax) ? i_t[min] : tmax;
|
|
}
|
|
else if (tmax > i_t[max])
|
|
{
|
|
node = &((Node *)node->p)[max];
|
|
tmin = (i_t[max] > tmin) ? i_t[max] : tmin;
|
|
}
|
|
else break; // Empty space.
|
|
}
|
|
trace.node_visited++;
|
|
}
|
|
if (node->axis == 3)
|
|
TraceLeaf(node, tmin, tmax, trace, parm);
|
|
}
|
|
|
|
if (!trace.stack_pos)
|
|
break;
|
|
|
|
node = trace.stack[--trace.stack_pos].node;
|
|
tmin = trace.stack[trace.stack_pos].tmin;
|
|
tmax = trace.stack[trace.stack_pos].tmax;
|
|
}
|
|
}
|
|
//------------------------------------------------------------------------------
|