The objective of this research is to strengthen the theoretical foundations of computer graphics by carefully formulating its mathematical underpinnings, applying formal methods of computer science, and exploring fundamental connections with other disciplines. The work plan is organized into four categories: 1) mathematical underpinnings, 2) numerical methods, 3) computational complexity, and 4) formal methods. Within each category several specific projects are described. Work done under this grant will depart from previous work in both the tools applied and in the areas investigated. Among the novel tools to be applied are mathematical methods from functional analysis (e.g. measure theory), information-based complexity (e.g. radius of information), and formal methods of computer science (e.g. refinement calculus); these tools will be applied to fundamental problems of computer graphics, such as deriving and clarifying radiometric principles, placing a priori limits on the accuracy of image-based rendering, and differentiating images of non-Lambertian scenes. These projects are firmly rooted in previous work performed by the author.
Among the novel areas to be investigated are proving the correctness of rendering algorithms, "inverting" rendering algorithms in response to user queries, and formalizing the use of default assumptions, ambiguity, and contradiction in human-computer interaction. The fundamental educational objectives of this work are to infuse computer graphics with appropriate mathematical structure, to train future graphics researchers in the art of constructing rigorous proofs and formally verifiable algorithms, and to integrate the tools and fundamental concepts of computer graphics into the core computer science curriculum. These goals cannot be attained through the introduction of a single course, but will instead require exposing students to the necessary concepts at many levels. Toward this end, elements of computer graphics will be introduced into an existing sophomore-level course on the theory of computation, and an advanced graduate-level course will be devised that explores the interplay of computer graphics, human-computer interaction, and artificial intelligence, while emphasizing the role of mathematical abstraction and formal verification.