next up previous

2.5 Implementation

Finally, we note that, of all the intersection points that pass the above tests, shading still has not been accounted for. For example, in Figure 4, both surfaces 12 and 2 pass the above tests. Hence, it is necessary to establish all valid intersections per the above 3 tests, and then to select the unique intersection of minimum distance. Again, since we do not use the distance for anything but a comparison of length, it is not necessary to take the square root. Thus, of all the currently ``valid'' intersections, we design the loop to yield the single, valid intersection of minimum

The above four-step sequence is implemented as an exclusive binary search over all surfaces in the enclosure. Each test can be implemented as ``true'' or ``false'' for those surfaces which pass the test (i.e., are viable candidates for intersection).

We note that the above process may be viewed from the vantage point of parallel execution. Viz., given an assemblage of many particles and focusing attention on a particular surface L, how many particles pass the tests at each level? In other words, each criterion acts as a sieve to filter out particles which cannot possibly intersect the present surface and to pass through the sieve those particles which meet the criterion. Later, we shall return to this topic, i.e., strategies for implementing the above algorithm on vector or parallel architectures.