dymokomi/luce-render
Source of release 0.1.2
// Closest-hit traversal of luce-render's binary BVH (src/render/bvh.lucb), the
// software path: a short stack, nearer child first, Möller–Trumbore triangles.
// The including kernel declares the buffers `nodes`, `positions` and `indices`.
struct Hit {
float t; // distance along the (unnormalized) direction; t_max when missed
uint triangle; // slot in the reordered index list; 0xffffffff when missed
vec2 uv; // barycentrics of the second and third vertices
};
vec3 point_at(uint index) {
return vec3(positions[index * 3u], positions[index * 3u + 1u], positions[index * 3u + 2u]);
}
// The entry distance of the ray into the box (0 when it starts inside), or -1
// when it misses the box or reaches it only past t_max.
float box_entry(vec3 lo, vec3 hi, vec3 origin, vec3 inverse, float t_max) {
vec3 a = (lo - origin) * inverse;
vec3 b = (hi - origin) * inverse;
vec3 near = min(a, b);
vec3 far = max(a, b);
float enter = max(max(near.x, near.y), max(near.z, 0.0));
float leave = min(min(far.x, far.y), min(far.z, t_max));
return enter <= leave ? enter : -1.0;
}
bool triangle_hit(uint triangle, vec3 origin, vec3 direction, inout Hit hit) {
vec3 p0 = point_at(indices[triangle * 3u]);
vec3 e1 = point_at(indices[triangle * 3u + 1u]) - p0;
vec3 e2 = point_at(indices[triangle * 3u + 2u]) - p0;
vec3 p = cross(direction, e2);
float determinant = dot(e1, p);
if (abs(determinant) < 1e-20) return false;
float inverse = 1.0 / determinant;
vec3 s = origin - p0;
float u = dot(s, p) * inverse;
if (u < 0.0 || u > 1.0) return false;
vec3 q = cross(s, e1);
float v = dot(direction, q) * inverse;
if (v < 0.0 || u + v > 1.0) return false;
float t = dot(e2, q) * inverse;
if (t <= 0.0 || t >= hit.t) return false;
hit.t = t;
hit.triangle = triangle;
hit.uv = vec2(u, v);
return true;
}
#define BVH_STACK 32
Hit trace_closest(vec3 origin, vec3 direction, float t_max) {
Hit hit = Hit(t_max, 0xffffffffu, vec2(0.0));
// Axis-parallel rays: a tiny component instead of zero keeps the slab test
// finite (Metal compiles with fast math, where infinities are not reliable).
vec3 safe = mix(direction, sign(direction) * 1e-20 + vec3(equal(direction, vec3(0.0))) * 1e-20, lessThan(abs(direction), vec3(1e-20)));
vec3 inverse = 1.0 / safe;
uint stack[BVH_STACK];
uint depth = 0u;
uint node = 0u;
// An empty tree's root is inside out (low above high); the slab test
// would read it as a box and walk its missing children forever.
if (nodes[0].lo.x > nodes[0].hi.x || box_entry(nodes[0].lo, nodes[0].hi, origin, inverse, hit.t) < 0.0) return hit;
while (true) {
Node current = nodes[node];
if (current.count > 0u) {
for (uint i = 0u; i < current.count; i++)
triangle_hit(current.first + i, origin, direction, hit);
} else {
uint left = current.first;
uint right = left + 1u;
float a = box_entry(nodes[left].lo, nodes[left].hi, origin, inverse, hit.t);
float b = box_entry(nodes[right].lo, nodes[right].hi, origin, inverse, hit.t);
bool take_left = a >= 0.0;
bool take_right = b >= 0.0;
if (take_left && take_right) {
// Visit the nearer first; the farther waits on the stack.
uint near_child = a <= b ? left : right;
uint far_child = a <= b ? right : left;
if (depth < BVH_STACK) stack[depth++] = far_child;
node = near_child;
continue;
}
if (take_left) { node = left; continue; }
if (take_right) { node = right; continue; }
}
if (depth == 0u) break;
node = stack[--depth];
}
return hit;
}
// Whether anything blocks the ray before t_max: the first hit ends the search.
bool trace_any(vec3 origin, vec3 direction, float t_max) {
Hit hit = Hit(t_max, 0xffffffffu, vec2(0.0));
vec3 safe = mix(direction, sign(direction) * 1e-20 + vec3(equal(direction, vec3(0.0))) * 1e-20, lessThan(abs(direction), vec3(1e-20)));
vec3 inverse = 1.0 / safe;
uint stack[BVH_STACK];
uint depth = 0u;
uint node = 0u;
if (nodes[0].lo.x > nodes[0].hi.x || box_entry(nodes[0].lo, nodes[0].hi, origin, inverse, t_max) < 0.0) return false;
while (true) {
Node current = nodes[node];
if (current.count > 0u) {
for (uint i = 0u; i < current.count; i++)
if (triangle_hit(current.first + i, origin, direction, hit)) return true;
} else {
uint left = current.first;
bool take_left = box_entry(nodes[left].lo, nodes[left].hi, origin, inverse, t_max) >= 0.0;
bool take_right = box_entry(nodes[left + 1u].lo, nodes[left + 1u].hi, origin, inverse, t_max) >= 0.0;
if (take_left && take_right) {
if (depth < BVH_STACK) stack[depth++] = left + 1u;
node = left;
continue;
}
if (take_left) { node = left; continue; }
if (take_right) { node = left + 1u; continue; }
}
if (depth == 0u) break;
node = stack[--depth];
}
return false;
}