Research On Surface Reconstruction Of Point Set And Real-Time Rendering Method

With the advent of faster processors and cheaper storage, the amount of collected data has grown dramatically in digital musum, computer-aided design, virtual operation, games and so on. Even if the development of GPU, the rendering speed has been improved dramatically, these large data sets with hundreds of millions to billions of points, are often many times larger than the memories of commodity computers, and overwhelm the algorithms and data formats used to manage and analyze them. Therefore, such large amounts of data necessitate efficient algorithms, both in terms of time and memory, to process the collected samples in a reasonable amount of time and render 3D models in realtime.This thesis presents several novel techniques for efficient modeling and realtime rendering method for 3D models, including streaming surface reconstruction algorithm for large point sets and realtime rendering techniques for coarse meshes.The main contributions of the thesis are as follows:1. We present a memory and time efficient surface reconstruction algorithm for large point sets that may not fit within the main memory. Unlike prior works that require input points to be pre-sorted, our algorithm exploits the spatial coherence already in existence in the input points to address the challenge of limited memory. To this end, it treats the input points as forming layers of surface patches, and then performs reconstruction by working on multiple layers of surface patches concurrently. Additionally, the memory usage of the algorithm can be understood through a few simple quantities in relation to the spatial coherence of the input points. Tests on the algorithm with large point sets verify that it produces good outputs too. This demonstrates the capability of our algorithm to handle a variety of point sets with reasonable spatial coherence that is not necessarily pre-sorted.2. Coarse piecewise linear approximation of surfaces causes undesirable polygonal appearance of silhouettes. We present an efficient method for smoothing the silhouettes of coarse triangle meshes using efficient 3D curve reconstruction and simple local re-meshing. It does not assume the availability of a fine mesh and generates only moderate amount of additional data at run time. Furthermore, polygonal feature edges are also smoothed in a unified framework. Our method is based on a novel interpolation scheme over silhouette triangles and this ensures that smooth silhouettes are faithfully reconstructed and always change continuously with respect to continuous movement of the view point or objects. We speed up computation with GPU assistance to achieve real-time rendering of coarse meshes with the smoothed silhouettes. Experiments show that this method outperforms previous methods for silhouette smoothing.3. We present a new scheme for rendering both artistic smoothing silhouette outlines and a high-quality interior toon-shading for 3D coarse polygonal meshes in real-time. Rather than use silhouette edges of the model directly as the basis for drawing strokes, we use efficient 3D curve reconstruction over silhouette triangles to generate clean, smooth, coherent and stylistic silhouette lines, with little or no clutter. In order to achieve a more pleasing quality of the interior shading of the refined coarse mesh, we use pixel-shading for cartoon shading and use 2D toon texture to create a wide range of effects. We use GPU to speed up the computation and render efficiently at interactive rates.All those techniques can be widely used to large indoor and outdoor scenes.Other techniques for realtime rendering, such as texture and coherent suggestivecontour for coarse polygonal meshes, are the future work.