Ray/Triangle Intersection Statistical Analysis

While the emphasis of this algorithm is on reduced data storage, it is interesting to evaluate its computational efficiency. Here the algorithm is compared to Badouel's coordinate intersection method. Both algorithms must either eliminate triangles that are coplanar to the ray or eliminate triangles that are backfacing (or coplanar) to the ray. These algorithms have similar branching structures, which break their function into four discrete parts:

By determining the probability that each branch is taken and counting the operations performed in each section of code, an average computation time can be derived.

Branching studies were performed on three environments containing triangle data. These environments are described and shown at the bottom of this page. The results were averaged to find representative percentages for the execution of each section of the routine. It should be observed that code before the ray/plane test is executed 100% of the time.

Noncoplanar Test Back Face Culling
Model After Det After u After v After det After u After v
Car 100.0% 29.9% 4.9% 45.0% 12.8% 1.9%
Mandala 99.7% 25.9% 5.0% 45.4% 13.0% 2.6%
Fallingwater 100.0% 38.5% 17.0% 47.3% 12.4% 3.2%
Average 99.9% 31.4% 9.0% 45.7% 12.7% 2.6%

Of course, different data sets and ray casting implementations might produce somewhat different percentages. For example, if a ray casting program is not very selective when choosing triangles to test, a lower percentage of rays will pass the u and v tests. The orientation of the rays with respect to the data impacts the percentage of rays eliminated by back face culling. In the case of these statistics, the viewing rays do not have a uniform directional distribution. This causes less than the expected 50% of triangles to pass the culling test.

For the purposes of this evaluation, the operations within each code section are divided into four types: addition/subtraction, multiplication, division and comparisons. While this breakdown cannot account for every cycle of computation, it provides a reasonably complete characterization of the work to be done. It is presumed that if efficiency were of primary concern, collateral loading and storing operations could be minimized.

On most modern hardware the listed operations (except for division) are completed in the same number of cycles. Division can take from four to eight times as long as the other operations. To account for this disparity, divisions are counted here as four computational units, while the other operations are counted as one computational unit.

The following four tables present computational totals for our method and Badouel's method, both with noncoplanar test and back face culling. Each table lists the number of operations of each type in each section of code. These operation counts are then scaled by each code section's execution percentages, and then summed to find an average total operation count.

Our Method - Noncoplanar Test
Section ADD MUL DIV CMP % Total
Before det 11 9 0 2 100.0 22.0
After det 5 4 1 2 99.9 15.0
After u 6 10 0 2 31.4 5.7
After v 2 4 0 0 9.0 0.5
Operations 18.1 16.5 4.0 4.6 43.2
Badouel's Method - Noncoplanar Test
Section ADD MUL DIV CMP % Total
Before det 2 3 0 2 100.0 7.0
After det 13 9 2 3 99.9 33.0
After u 2 1 1 2 31.4 2.8
After v 0 0 0 0 9.0 0.0
Operations 15.6 12.3 9.3 5.6 42.8
Our Method - Backface Culling
Section ADD MUL DIV CMP % Total
Before det 11 9 0 1 100.0 21.0
After det 5 3 0 2 45.9 4.6
After u 6 9 0 2 12.7 2.2
After v 2 6 1 0 2.6 0.3
Operations 14.1 11.7 0.1 2.2 28.1
Badouel's Method - Backface Culling
Section ADD MUL DIV CMP % Total
Before det 2 3 0 1 100.0 6.0
After det 13 9 2 3 45.9 15.2
After u 2 1 1 2 12.7 1.1
After v 0 0 0 0 2.6 0.0
Operations 8.2 7.3 4.2 2.6 22.3

The average total operation values demonstrate that the presented method is computationally equivalent to Badouel's method when back facing triangles are not culled. When such faces are culled, Badouel's method is 20% faster than our method. If the edge vector computations (mentioned in the paper) are performed as a preprocess, the operation counts for our method drop to 37.3 for the noncoplanar method and 22.1 for the back face culling method. The same preprocess would reduce Badouel's method counts by less, to 38.8 for the noncoplanar method and 20.5 for the back face culling method.

The two non-coplanar methods were implemented in an efficient ray tracer. Figure 1 presents ray tracing runtimes from a Hewlett-Packard 9000/735 workstation for each of the three models. In this particular implementation, the performance of the two methods is roughly comparable.

Model Objects Polygons Lights Our method sec. Badouel sec.
Car 497 83,408 1 365 413
Mandala 1,281 91,743 2 242 244
Fallingwater 4,072 182,166 15 3,143 3,184

Contents and runtimes for data sets used in this paper

Car (model courtesy of
Nya Perspektiv Design AB) 		Mandala Falling Water