Real time rendering of parametric surfaces on the GPU

Resumen

Although the first electronic circuit specifically designed to accelerate rendering was developed in the early 1980s, the term GPU (Graphics Processing Unit) was popularized by the Nvidia Geforce 256 in 1999. From this first single-chip processor, which processes a minimum of ten million polygons per second, to current GPUs, which offer a competitive solution to massive parallel computation, there has been continuous research and uninterrupted growth. In recent years, the demand for computer graphics has expanded across many scientific and engineering areas. Hence, the interactive rendering of complex and realistic models has become a hot topic in computer graphics, supported by unstoppable development in the pipeline of the GPU. Current GPU pipelines are triangle oriented and have been designed to process and render a large amount of triangles. Nevertheless, as the CPU-GPU bus is a habitual bottleneck, a triangle-oriented pipeline has proved to be a limited solution. As complex models can be more precisely described by equations than by a triangle mesh, parametric surfaces have gained ground as a new paradigm as they introduce relevant characteristics into the representation along with the rendering of complex models in real time. The compact representation provided by these surfaces reduces memory consumption and, moreover, its representation provides smoother, more continuous models than a set of triangles. Parametric surfaces can also select the level of detail on the y and they are invariant under an afine transformation, thus they can be easily scalable. In addition to their mathematical characteristics, parametric surfaces provide interesting properties in computer graphics as animation and collision detection become simpler and faster than a set of polygons, owing to the fact that a much smaller number of points need to be processed. Nonetheless, parametric surfaces are usually tessellated as set of triangles in the CPU and finally these triangles are sent down the GPU pipeline to be rendered. This dissertation goes a step further and proposes the evaluation and tessellation of parametric surfaces on the GPU. This dissertation includes a deep analysis of the rendering of parametric surfaces on the GPU focused on the mathematical characteristics of parametric surfaces with the aim of providing an efficient strategy for rendering complex models in real time. Two different parametric surfaces have been analyzed: Bezier and NURBS surfaces. Bezier surfaces have been considered as an input primitive owing to their simple and regular representation. However, as the NURBS descriptions are more suitable for complex models, the direct rendering of NURBS models has also been analyzed in this thesis. In conclusion, this thesis elaborates on different strategies for the real time rendering of complex models represented as parametric surfaces. In this thesis a set of schemes for the tessellation of Bezier surfaces on the GPU are designed: a non-adaptive approach, a fully adaptive proposal and a semiadaptive approach with an intermediate degree of exibility. The non-adaptive proposal is based on the on-the- y generation of the parametric grid according to the level of resolution of each object and the camera position that determines the refinement degree of the surface. This proposal considers each Bezier surface as the input primitive to the pipeline, thus Bezier surfaces are tessellated and evaluated on the GPU and the computational power of current GPUs is exploited with a computational complex shader and an optimized memory access is designed. Although a single version of the proposal is possible, generating two different variants allows many specific details to be tweaked for optimal performance, depending on the speci fic GPU architecture. Therefore, a Vertex Shader Tessellation (VST) variant is designed for GPU which could only operate on existing data, such as pipelines based on DirectX9 Meanwhile a Geometry Shader Tessellation (GST) variant is designed for GPUs which allows the generation and destruction of geometric primitives, such as those based on DirectX10 or DirectX11. With respect to the fully adaptive, Dyanamic and Adaptive Bezier Tessellation (DABT), and semi-adaptive proposals, the aim is to reduce the number of triangles in the final mesh while maintaining the quality of the resulting image. Surface tessellation must be sufficiently fine to capture geometric and appearance details. Nevertheless, overtessellating results in an increasing surface evaluation and rasterization workload. Both schemes are based on a 3-stage pipeline: first, a fixed tessellation pattern is computed to guide the adaptive procedure for the patch; next, the new vertices obtained from the first step are conditionally inserted by applying a set of heuristics consisting of tests local to the patch; finally, a specific scheme is employed to represent the inserted vertices and the reconstruction methodology based on the preprocessing of this information. The quality of the final triangle mesh is determined by both the inserted vertices and the reconstruction method employed to generate the resulting mesh. These proposals allow all triangles generated by them to be processed independently without introducing T-junctions or mesh cracks. Unlike the DABT proposal, which permits multiple levels of resolution inside a patch, the semi adaptive proposal is characterized by a lower degree of divergence, reducing the adaptive degree of exibility. This latter scheme is a tradeoff between a non-adaptive tessellation scheme and a fully adaptive proposal. The objective is to reduce the irregularity of the algorithm and the associated divergence of the DABT in order to optimize the graphics hardware utilization. The final chapter in this dissertation goes a step further, and a new pipeline called Rendering Pipeline for NURBS Surfaces (RPNS) is presented. RPNS is a novel solution for the direct rendering of NURBS surfaces on the GPU with no previous tessellation procedure or preprocessing. A deep analysis of current GPU pipeline evinces that the current stages for primitive generation, such as geometry shader or tessellator, are not suitable for the direct rendering of NURBS surfaces on the GPU. Hence, a NURBS-oriented pipeline (RPNS) has been designed according to the geometric characteristics of NURBS surfaces. The aim is to efficiently render each surface so that the final image has no cracks or holes, neither inside each surface nor between neighbor surfaces, making it possible to exploit the parallelism of the GPU to perform common operations, such as sketching on surfaces, interactive trimming or surface intersection. RPNS is based on a new primitive called KSQuad, which allows the direct rendering of NURBS surfaces. The design of RPNS relies on two mainstays to achieve sound performance and high-qualilty results: adaptive discretization of KSQuad and evaluation of NURBS surfaces with no approximation. To test our proposals, and even though this thesis focuses principally on algorithmic improvements to the rendering pipeline rather than an optimized implementation, these proposals have been implemented to measure their performance on current GPUs, achieving real-time rendering rates.