Ray Object Traversal
Content of this page: This page describes how to use the built-in functions for ray / object traversal.
Note that the current version of Visionaray is an early preview. At this stage, the framework, including the API, are likely to undergo frequent changes.
In order to test a single ray or a packet of rays for intersection with a single geometric primitive, the intersect() function is used, which is a customization point and as such can be overloaded for custom user primitives.
In most real world applications, the user will however need to test rays for intersection with a set of geometric primitives rather than a single one. When intersecting rays with a set of geometric primitives, several types of ray / object traversal queries may be of interest:
- Closest-Hit: determines the intersection with the geometric primitive that is closest to the ray origin in the ray direction. Closest-Hit testing in general requires testing the ray against all geometric primitives in the set with complexity O(n), where n is the number of geometric primitives. The complexity of this operation can be reduced to O(log(n)) with special acceleration data structures. The latter holds true for all traversal types outlined in this section.
- Any-Hit: determines any intersection of the ray with the set of geometric primitives. Any-Hit testing in general also has O(n) complexity, where n is the number of geometric primitives, but implies a termination criterion to stop traversal when the first primitive was hit.
- Multi-Hit: determines the first N closest hits with the set of geometric primitives. This operation in general has complexity O(nN), with n being the number of geometric primitives, because each time the algorithm finds a valid intersection, the hit_record associated with the intersection is inserted into a sorted list of length N.
An additional query type, which is however not implemented by the Visionaray API, is All-Hit, where all intersections of geometric primitives with the ray or the packet of rays are recorded. All-Hit can be implemented by using Multi-Hit traversal and a conservative estimate for N. For an overview of ray / object traversal concepts see e.g. Ams15.
Ray / object traversal in Visionaray is implemented in terms of three template functions: closest_hit(), any_hit(), and multi_hit(). The following code listings show exemplarily how the three template functions may be used. The traversal functions are passed random-access iterators to the first element and one element past the last element in a list of geometric primitives, which may e.g. be set up as follows.
//---------------------------------------------------------
// Build up a list of triangles.
typedef basic_triangle<3, float> triangle_t;
// aligned_vector is basically an std::vector,
// but with an allocator caring for the content
// being allocated at aligned addresses, which is
// important when using SSE or AVX.
// The traversal templates are in general compatible
// with any iterator type that provides random iterator
// semantics.
aligned_vector<triangle_t> primitives;
// ... fill the vector with triangles here.
// Some ray to test with.
basic_ray<float> ray;
ray.ori = ...;
ray.dir = ...;The Closest-Hit query can be performed with any randomly iterable container. Inside the closest_hit() function, intersect() will be called several times. The closest_hit() function's return type is the same as the return type of the respective intersect() function. intersect(), when being called with a ray or ray packet as first parameter, and with a basic_triangle as second parameter, will return a general-primitive hit_record, and so will closest_hit().
//---------------------------------------------------------
// Perform Closest-Hit intersection.
auto hit_rec = closest_hit(
ray,
primitives.begin(),
primitives.end()
);
// intersect(ray, triangle) returns a
// hit_record<primitive>, and so does
// closest_hit() in this case.
// Let's do smth. useful with it.
std::cout << hit_rec.hit << '\n';
std::cout << hit_rec.t << '\n';
std::cout << hit_rec.prim_id << '\n';
std::cout << hit_rec.geom_id << '\n';
std::cout << hit_rec.u << '\n';
std::cout << hit_rec.v << '\n';The Any-Hit query will behave likewise, but there is however no guarantee that the intersection that is returned is the closest one.
//---------------------------------------------------------
// Perform Any-Hit intersection.
auto hit_rec = any_hit(
ray,
primitives.begin(),
primitives.end()
);
// any_hit() also returns the
// hit_record returned by the
// respective intersect() function.
std::cout << hit_rec.hit << '\n';
std::cout << hit_rec.t << '\n';
std::cout << hit_rec.prim_id << '\n';
std::cout << hit_rec.geom_id << '\n';
std::cout << hit_rec.u << '\n';
std::cout << hit_rec.v << '\n';The implementation of the Multi-Hit ray / object traversal query is special in that the template function does not return a single hit record, but a statically allocated array of hit records. The multi_hit() template determines the size of the static array by inspecting a template parameter (defaulting to 16) so that there is no need to dynamically reallocate memory to accommodate the hit records.
NOTE: In the literature (see e.g. Ams15) the Multi-Hit traversal query was proposed to be optimized by means of callback functions and early exit, and was proposed to be implemented by using the custom intersector feature that is provided by several ray tracing APIs and also by Visionaray. In order to be most general, the Visionaray implementation however implements the Multi-Hit ray / object traversal query in the most basic fashion by maintaining a list of sorted hit records, which can be accessed after traversal finished.
//---------------------------------------------------------
// Get the four closest intersections.
auto hit_recs = multi_hit<4>(
ray,
primitives.begin(),
primitives.end()
);
// Iterate over the array of hit records.
// Can also use hit_recs.begin() / hit_recs.end()
// or operator[] array access.
for (auto hit_rec : hit_recs)
{
std::cout << hit_rec.hit << '\n';
std::cout << hit_rec.t << '\n';
std::cout << hit_rec.prim_id << '\n';
std::cout << hit_rec.geom_id << '\n';
std::cout << hit_rec.u << '\n';
std::cout << hit_rec.v << '\n';
}
//---------------------------------------------------------
// The following function calls are equivalent:
// 1.)
// Default to N=16 closest intersections.
auto hit_recs = multi_hit(
ray,
primitives.begin(),
primitives.end()
);
// 2.)
// Explicitly call multi_hit() with N=16.
auto hit_recs = multi_hit<16>(
ray,
primitives.begin(),
primitives.end()
);Ray / object traversal can be customized in several ways. The most natural way for the user to customize traversal is by providing her own geometric primitive type with a custom intersect() overload and optionally a custom hit_record. The traversal functions internally use the following control flow (exemplarily outlined for the closest_hit() function) to determine intersections and update the traversal result.
HitRecord closest_hit(Ray ray, Primitive first, Primitive last)
{
HitRecord result = /* Far_Away */;
for (it = first; it != last; ++it)
{
HitRecord hr = intersect(ray, it);
Mask closer = is_closer(hr, result);
update_if(result, hr, closer);
}
return result;
}By providing overloads for the udate_if() and is_closer() customization points, the user can influence the way that the traversal functions determine if one geometric primitive is closer to the ray's origin than another one, and if the hit record that is returned requires update.
Ray / object traversal can also be customized by means of using custom intersectors. In that case, the user will write a functor implementing the interface of intersect() in its operator() to implement custom behavior. This can be used to ignore certain ray / primitive intersections based e.g. on a texture lookup. For a detailed description of custom intersectors, see the documentation for that feature. The custom intersector instance is passed to the traversal function templates as a fourth function parameter.
//---------------------------------------------------------
// Simple custom intersector intercepting
// intersect(ray, triangle).
struct custom_intersector
: basic_intersector<custom_intersector>
{
template <typename Ray>
auto operator(Ray r, triangle_t tri)
-> decltype(intersect(r, tri)) // return just what
// intersect() would return.
{
// Some custom logic here that
// intercepts intersect().
}
};
//---------------------------------------------------------
// With a custom intersector, instead of
// calling intersect() directly, closest_hit()
// will first call intersector.operator(), which
// may (or may not) route through to intersect().
custom_intersector intersector;
// Call traversal template with intersector.
auto hit_rec = closest_hit(
ray,
primitives.begin(),
primitives.end(),
intersector
);When accelerating ray / object traversal e.g. by using bounding volume hierarchies, the traversal query type (Closest-Hit, Any-Hit, Multi-Hit) is automatically communicated to the intersect() function for the data structure, so that Any-Hit traversal benefits from early exit potential and Multi-Hit traversal returns an array of hit records. For this to come into effect, the user has to call the traversal method with the acceleration data structure itself as primitive type:
//---------------------------------------------------------
// Setup BVH primitives.
typedef ... = bvh_t;
aligned_vector<triangle_t> triangles;
aligned_vector<bvh_t> bvhs(NumBvhs);
for (auto b : bvhs)
{
b = build<bvh_t>(
triangles.data(),
triangles.size()
);
}
//---------------------------------------------------------
// Now traverse the bvhs.
auto hit_rec = any_hit(
ray,
bvhs.begin(),
bvhs.end()
);For more general information on why and how to use bounding volume hierarchies and acceleration data structures in general, see the section on Acceleration data structures and traversal.