Optimised Scanning of a Visibility Graph Data Structure for Efficient Ray-Tracing

An eff{i}cient way to implement a ray tracing is to use the visibility relations between geometric primitives, as in Hoppe's work. Authors present a novel approach subdivided in two steps. First, a graph is computed to encode the visibility relations. This preprocess is easier and less restrictive than the Hoppe's one. Moreover, the computation precision can be tuned to satisfy a required accuracy, or the scene complexity. Secondly, an optimised graph scanning is used to reduce the computation time of the deterministic ray tracing, using the source-image theory. An interesting property is that the graph scanning does not have any impact on the calculation accuracy. As a consequence, the precision wanted by the user is preserved. This leads to an efficient tools able to compute efficiently and precisely the impulse responses, as needed for channel characterisation for instance.