Ray-Casting (by Bill Yakowenko, UNC)

There are three major steps to the algorithm:

	1. Prepare for parallel processing:
	   Normalize the CSG (Constructive Solid Geometry) representations
	   of doctrine and radar to the smaller of CNF or DNF (Conjunctive
	   or Disjunctive Normal Form).
	   Sort all CSG nodes by primitive type, grouping each type together
	   into a sequence for parallel processing.
	
        2. Compute depth maps of doctrines and radar:
	   For each primitive type
              For all CSG nodes of that type, in parallel:
	         For all pixels, in parallel:
                    Compute the intersection of the ray through that pixel
	            and the CSG node.
	         end
	      end
	   end
	
	3. For all pixels, in parallel:
	      Compute the intersection of the doctrine and radar depths.

Because the CSG object tree was normalized, all of the intersections can be done in a small number of passes, one for each kind of CSG primitive. Currently, there are eight supported primitives: polygon, plane, wedge, circle, rect, negation, union, and intersection. In each pass, all CSG nodes of some type are evaluated at all pixels. On a machine with enough parallelism, all pixels could be evaluated at once, and the total time would be based on the number of distinct primitives, which is a constant.

The intersection of a ray and CSG primitive object take advantage of the knowledge that, in this algorithm, rays are vertical. That is, they pass through the center of the Earth, and are perpendicular to the surface at the point where they cross it. Because of this, intersections of rays with leaf CSG nodes are simple: if the ray is within the boundary of the object, its elevation bounds are just those given for that object; if not within the bounds of the object, the intersection is null. Intersections with logical constructors are just the intersections of the segments resulting from the lower-level (and therefore previously computed) nodes. Although the same algorithm could work with parallel rays (ie: not all passing through the Earth's center), the computation of intersection between rays and leaf objects would likely be more difficult to program.

The algorithm went through two major versions. Initially, adaptive subdivision of the map using objects' bounding boxes was seen as a way to reduce the amount of work done. This was developed and refined in several ways to increase its speed or efficiency. Later, it was decided that this approach made extreme parallelization difficult.

In response to that, it was decided to simply evaluate every pixel in parallel, and every object of each CSG type in parallel. This is possible only by normalizing the CSG tree, so there is a specific sequence of primitive types can be evaluated in order, and never need results of a type before it is ready. Although this wastes some amount of work, in practice the clipping region would not be much greater than were the bounding boxes used in adaptive subdivision, so the waste is small. Furthermore, this allows for a great deal more parallelism, and therefore speed.

The advantages and disadvantages of this algorithm both stem from the fact that it analytically computes depths at each pixel. It gains speed and flexibility by taking advantage of the fact that object boundaries are oriented with the projected rays defining each pixel. Therefore, it needs only a small amount of computation per pixel per object, and produces very accurate intersection depths. The disadvantages are that the analytic solution to other primitives might prove difficult. For instance, spheres should be easy to handle, because each pixel could determine its upper and lower limits based only on distance from the sphere's center. But a cylinder whose axis is skewed, neither vertical nor horizontal, might be a little more challenging, and an arbitrarily rotated complex shape could prove difficult.

Conclusions

Metrics

Discussion : 20
Reading : 4
Design : 5
Coding : 70
Testing/Debugging : 30
Total : 129

Buzzwords

CSG tree normalized to smaller of CNF or DNF
Leaves stripped & sorted into sequences by type
Parallel evaluation of one sequence for each primitive type
Analytic solution takes advantage of Earth-centered projection
Only one "contained or not" test needed per pixel per CSG leaf

Log Data

7/11/94 (wjy) first heard of the project
7/15/94 (wjy) meeting w/Lars & Zhi-yong, algorithm outline decided   
        (wjy) coding begun  
7/18/94 (wjy) initial coding done; testing/debugging begun
7/20/94 (wjy) first operational program   
        (wjy) added print_map function   
7/21/94 (wjy) added ppm_map function    
        (wjy) adjusted to track radar-only regions separately
8/03/94 (wjy) adding doctrine-per-region tracking during subdivision   
8/18/94 (wjy) first integrated with validate.pro   
        (wjy) CSG normalization (flattening) routine   
        (wjy) skip adaptive subdivision, flatten CSG tree  
        (wjy) put leaves in table, sequentializing evaluation of shapes   
        (wjy) index_leaves() procedure,    
        (wjy) handling of primitives and constructors made identical
9/06/94 (wjy) flattened-CSG code operational
9/07/94 (wjy) removed bounding boxes from CSG object definitions   
9/10/94 (wjy) new primitive objects added; old ones commented out
9/12/94 (wjy) added ascii2csg() functions
9/14/94 (wjy) added a level of nesting to output, pixels, and srays
        (wjy) modified print_map() and ppm_map() to accept this 
9/23/94 (wjy) adjusted to use correct units for distances, angles, etc.
        (wjy) memory-saving modifications:
        (wjy)   allowed to normalized to smaller of CNF/DNF
        (wjy)   some date redundancy eliminated
        (wjy)   deallocation of dead data space