20c. PURPOSE
20e. APPROACH
Key Personnel - FY1996 J. Gustafson (PI) (0.8 FTE); B. Harmon (PI) (0.1 FTE); D. Turner (PI) (1.0 FTE)
Contributing Principal Investigators - FY1996 S. Elbert, D. Heller
20f. TECHNICAL PROGRESS
Algorithms For Parallel Computers and Computational Techniques
Dr. Gustafson has evolved an approach to program development in which the application programmer is assigned the burden of stating and proving the performance of the program. The application programmer describes methods that will guarantee needs are met based on guarantees from the hardware description and the operating system/compiler, in response to the end-user performance requirements (answer quality, reliability, total execution time, input data quality). The current approach is to describe tasks using an assembly-like specification of individual operations like addition, testing, etc. However, each "instruction" is accompanied by statements of numerical range, reliability, cost in current dollars, maximum execution time, and what other statements may be executed simultaneously. One may augment a conventional algorithm to fit this paradigm by the addition of information by an application programmer. Once complete, such an instruction-level design should be compilable to a very broad range of platforms (or flagged as impossible by the compiler to a particular computer) for several decades without change.
Note that performance metrics such as precision, execution time, and reliability become promoted to pass/fail decisions for a compiler. This is a fundamental shift in the burden of computer use from the end user to the application programmer. At the same time, the job of the compiler writers becomes easier because intractable problems of scheduling and discovering implied parallelism are removed from their duties.
Dr. Gustafson, Snell, and Shorb have created a program called PHOTON that embodies the discoveries and inventions made in FY1994 regarding complete solutions to Kajiya's Rendering Equation. Dr. Gustafson has provided the theoretical design of the program; Snell has coded and debugged the program, including shared-memory parallelization; Shorb built and parallelized the viewing program, an elaborate undertaking in itself; Bower built a preprocessor that trades memory use for higher speed.
Several principles in PHOTON are novel and unique, and patent protection is being explored. The scene is decomposed into four-dimensional areas (two dimensions for the surface location and two for the solid angle of the direction) and a dynamic histogram of photon events dictates scene refinement. Use of discrete photons solves the load imbalance problem of following "power packets" of light until they attenuate below some level. Use of histogram bins instead of precise ray histories allows the resulting answer to fit in main memory instead of being relegated to mass storage. The preprocessor of the input geometry accelerates the testing of photon-surface intersections by one to three orders of magnitude. Generation of diffuse-surface photon distributions is done by a terse method with two random number generations and only nine floating point operations (no trigonometric functions); the literature shows general ignorance of how critical it is to have correct distributions, perhaps because it has been thought too expensive in terms of operations.
We have tested our method and obtained agreement with analytic methods and progressive radiosity methods; as a side effect of this research, we discovered major errors in published methods for scene rendering. We are pursuing a collaborative effort with George Davidson and Arthurine Breckenridge at Sandia National Laboratories to incorporate the PHOTON approach into MUSE.
Both PHOTON and the viewer are very compute-intensive, and have been parallelized for the Power Onyx with high efficiency. We are not currently memory-bound, but this could change as algorithmic advances let us increase the photons per second rate of the program. We estimate that a realistic rendering for a simple scene with 1000 polygons will require about 1 gigabyte of main memory.
In connection with the work on solutions to Kajiya's Rendering Equation, we have been led to explore precise experimental comparison between simulated images and actual images. Such experimental testing is extremely rare in the graphics literature; we are aware of only one paper (Goral et al., 1984) that showed anyone has attempted it. We have acquired a high-resolution digital camera that will allow pixel-by-pixel comparison between actual and simulated appearance of objects and scenes.
Dr. Gustafson, Snell, and Shorb have also designed a controlled environment called "the Tunnel" for viewing measured and simulated images for comparison with actual views. Construction is nearly complete at the time of this writing. It will provide stereoptic input at the limits of accuracy of the human visual system, accounting for monocular depth perception, contrast range, color accuracy, and fovea-limited resolution. The only restriction will be a small field of view. In this sense, The Tunnel is complementary to the CAVE in which visual fidelity is sacrificed to achieve full-field views.
We have built a small radar cross-section program that produces numerical results in concordance with theoretical solutions. This is a critical first step in transferring the algorithmic methods of PHOTON to the RCS problem. We have determined that the RCS community makes many of the same errors as the graphics community, including the assumption that answer quality is proportional to number of elements in geometry decomposition.
Grand Challenge
This work has produced a total of 14 papers.
20g. FUTURE ACCOMPLISHMENTS
Algorithms For Parallel Computers and Computational Techniques
"Immortal Code"
We will attempt to build compilers that can read programs written in our proposed contractual style, and that can negotiate terms with the application programmer and a hardware description file according to the paradigm. Since the compiler reports an "error" when a performance criterion cannot be met, the application programmer must choose a dimension of the requirements that can be relaxedÉ time, cost, reliability, input quality, or answer quality. Some of the choices can be made automatically or as defaults, but we will need to experiment to determine the best programming environment. This is a very large project, and we harbor no illusions regarding its difficulty. Because it is so difficult, private industry seems to be making no effort that is similar in thrust. Because of this, and because the potential payoff (a permanent reduction in the cost of writing and maintaining computer programs) is so large, it seems especially appropriate for federal laboratory research.
The "immortal code" programming model is a difficult one. However, if successful, it will make possible the formation at last of a lasting repository of computer programs. Past attempts to produce libraries of algorithms have failed because they did not effectively deal with the dynamics of computer languages, changing architectures, and other variables. Any effort to make computer programming into a science rests on the assumption that results can be collected, widely understood, and valid for many years as results are in other scientific fields.
PHOTON
PHOTON is designed to allow correct photon-surface interaction. Effects such as polarization and fluorescence have never been attempted in rendering methods, yet they appear to have profound effects on ordinary interior scene renderings. Experiments with a low-cost spectrophotometer show that significant fluorescence takes place between visible light bands, necessitating off-diagonal terms in the RGB treatment of any graphics. Existing programs universally assume complete independence of light frequencies, producing errors as large as about 30% even when the physical scene contains only ordinary pigments.
We are working on providing translators between the PHOTON input file format and other rendering formats, such as Inventor. This will permit comparison of image quality with other rendering methods, and increase the practical value of the PHOTON software. We will explore methods of increasing the speed of the program, including more massively-parallel distributed memory decompositions suitable for networks of workstations.
We will accumulate evidence that our global illumination model provides superior answers to existing methods, ignoring issues of computation effort. As computer performance continues its inexorable increase, our methods will become more tractable and mainstream, and should have considerable influence on the graphics community. We may discuss hardware accelerators for PHOTON with vendors such as Silicon Graphics; some of the algorithm appears amenable to this approach.
The Tunnel
We will use the Tunnel to test whether current display technology is capable of producing stereoptic images indistinguishable from reality. It appears possible, but paper analysis of the human visual system probably leaves out many subtle features that the brain uses to analyze visual input; only experiment will tell.
One innovation we will explore is the use of software calibration of the camera-display system. By using the digital camera to digitize the output of the displayed images on a monitor, we will have a complete "loop" that will reveal degradation in the image from reality to screen perception. By computing the inverse of the transfer function, one can in theory correct for the color error in the entire display pipeline (since the tristimulus values of the retina are not the same as those of a digitizing camera or an RGB display, errors are still possible even if the transfer function is the identity).
Radar Cross-Section by Hierarchical Methods
We will extend the RCS program to the point where full comparisons can be made between other methods and one based on our ideas. Unlike PHOTON, an RCS method deals with wave properties and electromagnetic interaction, so the line-plane intersection ideas of PHOTON will not be applicable. However, the idea of dynamic hierarchical refinement without Greengard-Rocklin approximations will be applicable, and should give higher accuracy for the same number of operations (and for far less storage).
Work in hierarchical methods will continue in general. We hope to be able to use them to solve radar cross-section problems of unprecedented size and detail, equivalent to current methods scaled by two orders of magnitude. We will explore any area for which the traditional solution technique requires setup and solution of a large, dense matrix to see if hierarchical methods apply.
The two main thrusts of the research in advanced algorithms are ultimate-fidelity video and novel approaches to Radar Cross-Section. At a more fundamental level, we pursue problems for which the measure of answer quality has been vague at best, and for which a rigorous measure points to new methods. One example where this has not yet been done, but could be done, is in N-body methods. While the Greengard or Appel methods are rigorous in analyzing the accuracy of the pairwise force approximations, there has been no success in figuring the accuracy of timestepping. If we can provide a bound on the solution to an N-body simulation in terms of particle location after M timesteps, we suspect a new algorithm will emerge from this analysis. Many of the Grand Challenge areas are badly in need of confidence bounds on the answers produced. We will seek to restore rigor to scientific simulations in general, so that computational approaches will be usable as hard proof and not merely serve as approximate predictors of qualitative behavior.
Grand Challenge
20h. RELATIONSHIPS TO OTHER PROJECTS
Algorithms For Parallel Computers and Computational Techniques
See also Technical Progress (20f.).
Grand Challenge