<p>The purpose of this thesis is to document the development of the graphics part of an extremely pluggable game engine/lab environment for a course in advanced game programming. This thesis is one out of five, and concerns indoor, realtime computer 3D graphics. It covers state-of-the-art techniques such as GLSL - the OpenGL Shading Language - and more well known techniques such as portal based rendering.</p>

This thesis presents an efficient computational voxelization approach that utilizes the graphics pipeline. Our approach is hybrid in that it performs a precise gap-free computational voxelization, employs fixed-function components of the GPU, and utilizes the stages of the graphics pipeline to improve parallelism. This approach makes use of the latest features of OpenGL and fully supports both conservative and thin voxelization. In contrast to other computational voxelization approaches, this approach is implemented entirely in OpenGL, and achieves both triangle and fragment parallelism through its use of both the geometry and fragment shaders. A novel approach utilizing the graphics pipeline to complement geometric triangle intersection computations is presented. By exploiting features of the existing graphics pipeline we are able to rapidly compute accurate scene voxelization in a manner that integrates well with existing OpenGL applications, is robust across many different models, and eschews the need for complex work/load-balancing schemes. / Graduation date: 2013

We present a new method for rendering novel images of flexible 3D objects from a small number of example images in correspondence. The strength of the method is the ability to synthesize images whose viewing position is significantly far away from the viewing cone of the example images ("view extrapolation"), yet without ever modeling the 3D structure of the scene. The method relies on synthesizing a chain of "trilinear tensors" that governs the warping function from the example images to the novel image, together with a multi-dimensional interpolation function that synthesizes the non-rigid motions of the viewed object from the virtual camera position. We show that two closely spaced example images alone are sufficient in practice to synthesize a significant viewing cone, thus demonstrating the ability of representing an object by a relatively small number of model images --- for the purpose of cheap and fast viewers that can run on standard hardware.

Due to the increasing demand of three-dimensional (3D) graphic applications in various consumer electronics, how to develop a low-cost 3D graphic hardware accelerator suitable for the embedded systems has become an important issue. A typical 3D graphic accelerator includes a geometry sub-system and a rendering sub-system. In this thesis a highly-efficient 3D graphic rendering intellectual property (IP) based on the tiled-based approach is proposed. An entire rendering IP consists of several modules. The main contributions of this thesis focus on the development of the setup-engine, rasterization module, and the integration of the whole modules for the rendering IP. In the design of setup engine, the thesis develops a folded arithmetic unit architecture mainly consisting of one iterative divider, three multipliers and several adders, which can finish the overall computation of the setup equations within less than 50 cycles. As for the rasterization module, this thesis develops several scan-conversion algorithms including hierarchical, fast skip, and boundary-edge test methods suitable for the tiled-based rendering process. The ordinary line drawing algorithm for the scan-line boundary search or the direct in-out test approach is not efficient for tile-based approach since the shape of triangle primitives may become irregular after tiling. Our experimental results show that the boundary-edge test can lead to the most compact design since it can transform the normal in-out test circuit for single pixel to detect two end-points of the scan-line simultaneously. In addition, the rasterization module can be divided into the scan-line and the fragment generation parts which can help the optimization and speedup of the individual part to achieve the desired overall fill-rate goal. Our simulation shows the fill-rate improvement based on this approach is around 60%. Finally, this thesis integrates all the sub-modules to the entire rendering IP core. This IP has been realized by 0.18 um technology. The total gate count is 504k. It can run up to 166 Mhz, and deliver the peak fill rate of 333M pixels/sec and 1.3G texels/sec. This IP has been highly verified, and achieves more than 95% code coverage. It has also been integrated with OPENGL ES software module, Linux operation system and geometry module, and successfully prototyped on the ARM versatile platform.

GPU-based raycasting is the state-of-the-art rendering technique for interactive volume visualization. The ray traversal is usually implemented in a fragment shader, utilizing the hardware in a way that was not originally intended. New programming interfaces for stream processing, such as CUDA, support a more general programming model and the use of additional device features, which are not accessible through traditional shader programming. In this paper we propose a slab-based raycasting technique that is modeled specifically to use these features to accelerate volume rendering. This technique is based on experience gained from comparing fragment shader implementations of basic raycasting to implementations directly translated to CUDA kernels. The comparison covers direct volume rendering with a variety of optional features, e.g., gradient and lighting calculations. Our findings are supported by benchmarks of typical volume visualization scenarios. We conclude that new stream processing models can only gain a small performance advantage when directly porting the basic raycasting algorithm. However, they can be advantageous through novel acceleration methods which use the hardware features not available to shader implementations.

Realistic computer generated images are computed by combining geometric effects, reflectance models for several captured and phenomenological materials, and real-world lighting according to mathematical models of physical light transport. Several important lighting phenomena should be considered when targeting realistic image simulation. A combination of soft and hard shadows, which arise from the interaction of surface and light geometries, provide necessary shape perception cues for a viewer. A wide variety of realistic materials, from physically-captured reflectance datasets to empirically designed mathematical models, modulate the virtual surface appearances in a manner that can further dissuade a viewer from considering the possibility of computational image synthesis over that of reality. Lastly, in many important cases, light reflects off many different surfaces before entering the eye. These secondary effects can be critical in grounding the viewer in a virtual world, since the human visual system is adapted to the physical world, where such effects are constantly in play. Simulating each of these effects is challenging due to their individual underlying complexity. The net complexity is compounded when several effects are combined. This thesis will investigate real-time approaches for simulating these effects under stringent performance and memory constraints, and with varying degrees of interactivity. In order to make these computations tractable given these added constraints, I will use data and signal analysis techniques to identify predictable patterns in the different spatial and angular signals used during image synthesis. The results of this analysis will be exploited with several analytic and data-driven mathematical models that are both efficient, and yield accurate approximations with predictable and controllable error.

There currently exist several techniques for selecting and combining images from a digital image library into a single image so that the result meets certain prespecified visual criteria. Image mosaic methods, first explored by Connors and Trivedi[18], arrange library images according to some tiling arrangement, often a regular grid, so that the combination of images, when viewed as a whole, resembles some input target image. Other techniques, such as Autocollage of Rother et al.[78], seek only to combine images in an interesting and visually pleasing manner, according to certain composition principles, without attempting to approximate any target image. Each of these techniques provide a myriad of creative options for artists who wish to combine several levels of meaning into a single image or who wish to exploit the meaning and symbolism contained in each of a large set of images through an efficient and easy process. We first examine the most notable and successful of these methods, and summarize the advantages and limitations of each. We then formulate a set of goals for an image collage system that combines the advantages of these methods while addressing and mitigating the drawbacks. Particularly, we propose a system for creating photocollages that approximate a target image as an aggregation of smaller images, chosen from a large library, so that interesting visual correspondences between images are exploited. In this way, we allow users to create collages in which multiple layers of meaning are encoded, with meaningful visual links between each layer. In service of this goal, we ensure that the images used are as large as possible and are combined in such a way that boundaries between images are not immediately apparent, as in Autocollage. This has required us to apply a multiscale approach to searching and comparing images from a large database, which achieves both speed and accuracy. We also propose a new framework for color post-processing, and propose novel techniques for decomposing images according to object and texture information.

Dendritic or branching structures are commonly seen in natural phenomena such as lightning, cracking and vegetal growth. They are also often used for artistic or decorative purposes, ranging from ornamentation to decorative ceramics. Existing procedural methods for modeling these structures remain very limited in terms of control and flexibility. As a result, these objects tend to be modeled individually, which is a painstaking and costly process.<p>We present a new procedural method for modeling dendritic structures based on a path planning approach. Our method includes the implementation of a partial non-scalar distance metric that gives us effective and flexible control handles over the evolving dendritic structure. These control handles are demonstrated by guiding the growth of dendritic structures using input images, allowing us to create a form of stylistic dendritic halftoning and to embed hidden images in dendritic trees to create pareidolia effects. These applications demonstrate the vast diversity of structures that can easily be modeled by our process a flexibility that existing methods definitely lack. We also demonstrate the application of the partial non-scalar distance metric to the context of texture synthesis from example, and show how it holds promise for many other contexts.

Realistic computer generated images are computed by combining geometric effects, reflectance models for several captured and phenomenological materials, and real-world lighting according to mathematical models of physical light transport. Several important lighting phenomena should be considered when targeting realistic image simulation. A combination of soft and hard shadows, which arise from the interaction of surface and light geometries, provide necessary shape perception cues for a viewer. A wide variety of realistic materials, from physically-captured reflectance datasets to empirically designed mathematical models, modulate the virtual surface appearances in a manner that can further dissuade a viewer from considering the possibility of computational image synthesis over that of reality. Lastly, in many important cases, light reflects off many different surfaces before entering the eye. These secondary effects can be critical in grounding the viewer in a virtual world, since the human visual system is adapted to the physical world, where such effects are constantly in play. Simulating each of these effects is challenging due to their individual underlying complexity. The net complexity is compounded when several effects are combined. This thesis will investigate real-time approaches for simulating these effects under stringent performance and memory constraints, and with varying degrees of interactivity. In order to make these computations tractable given these added constraints, I will use data and signal analysis techniques to identify predictable patterns in the different spatial and angular signals used during image synthesis. The results of this analysis will be exploited with several analytic and data-driven mathematical models that are both efficient, and yield accurate approximations with predictable and controllable error.

Global illumination techniques are used to improve the realism of 3D scenes. Calculating accurate global illumination requires a method for solving the rendering equation. However, the integral form of this equation cannot be evaluated. This thesis presents research in non real-time illumination techniques which are evaluated with a finite number of light rays. This includes a new technique which improves realism of the scene over traditional techniques. All computer rendering requires distortion free texture mapping to appear plausible to the eye. Inverse texture mapping, however, can be numerically unstable and computationally expensive. Alternative techniques for texture mapping and texture coordinate generation were developed to simplify rendering. Real-time rendering is improved by pre-calculating non real-time reflections. The results of this research demonstrate that a polynomial approximation of reflected light can be more accurate than a constant approximation. The solution improves realism and makes use of new features in graphics hardware. / May 2007