The objective of doctrine validation is to compute the percentage coverage of the doctrine by a radar volume, and ideally to produce a 2D picture showing this percentage of coverage. The heart of doctrine validation consists of computing the volume of the intersection of the radar and doctrine shapes. We explored at a high-level several simple algorithmic variants for this volume computation using the Proteus system. In particular we explored two techniques for volume computation: ray casting and recursive spatial decomposition using octrees. In both cases technically the result we were after was the projection of the volume onto a 2D surface to produce a 2D picture. We successfully designed and prototyped in Proteus algorithms for both a sequential and data-parallel version of volume computation using adaptive octree decomposition.
The key idea underlying volume computation using octrees is to recursively subdivide the space into 8 orthogonal cubes (octants) and keep only cubes interior to an object, thus deriving an "oct-tree" whose leaves comprise the volume. The technique is "adaptive" in the sense that at each level "empty" leaves -- those exterior to the object -- are thrown away. Our sequential algorithm for octree decomposition performed a depth-first derivation, and was unique in that it used a 4-valued logic for deciding if a cube was interior to object. More precisely, since the object was represented as a CSG ("constructive solid geometry") expression built from union, intersection, and complement operators and primitive shapes, we evaluated whether a cube was interior to a CSG expression by comparing whether the cube as contained in each primitive in the expression and then combining the resulting values -- which were one of "contained", "disjoint", "overlapping", or "unknown" -- by structurally reducing the CSG expression using and, or, and not logic operators conservatively extended for these 4 quaternary values. Subdivision then proceeds on overlapping or unknown comparison results, and the entire process recurses until a desired level of accuracy is reached. To derive a picture from the derived volume, the octree cubes found to be contained in the object had their heights added to , or "dropped" onto, a 2D pixmap. Thus the algorithm was informally termed a "chop-and-drop" approach.
The above algorithm was successfully prototyped in Proteus. However it became rapidly apparent that volume computation is a particularly computationally demanding subtask. Thus we pursued the development and implementation of a data-parallel variant of the algorithm, with the strategy of first expressing the nested data-parallel algorithm in Proteus and validating it using the Proteus interpreter, and then realizing a parallel implementation using the Proteus transformation machinery to translate the nested data-parallel core to the C+DPL vector library. The resultant vector code would be invoked from the Proteus interpreter using the "prog" MIF construct, and would execute in parallel on a MasPar MP-2 or other parallel platform.
The data-parallel algorithm for octree decomposition that we successfully developed and validated using the Proteus interpreter was unique in several respects. First, it was a functional program that used single assignment (a "let" construct). Second, to increase the expressed parallelism the CSG expression was represented in a fixed-depth normal form as a disjunction of conjunctions of positive or complemented primitives. The algorithm then proceeded in log(sqrt(#pixels)) steps of recursive spatial subdivision, at each step processing all the octants in parallel. At each step, each octant was compared with all CSG primitives in parallel, and the result was reduced using the normal form expression to yield a containment decision for each octant. As before, subdivision proceeded on a result of overlapping or unknown. A further algorithmic refinement was to use in containment tests spheres which bounded the octants. The entire amount of code for the data-parallel algorithm expressed in Proteus was ~ 280 lines. Currently we are exercising the transformation machinery and shortly expect to have a functioning parallel implementation.