Research On Direct Visibility Testing And Shadow Rendering For Point-based Models

As a novel representation technology of 3D geometric shapes, point-based model has attracted more and more interests of researchers in computer graphics society in recent years. Also, some basic problems such as visibility computation, viewer-point dependent reconstruction and shadow generation of point-based models are becoming more urgent to be solved. These fundamental problems have broad application and profound significance. They are playing important roles not only in real computer graphics but also in construction of virtual environment of education and designation of educational software. The research on direct visibility testing and shadow rendering for point-based models has both theoretical and practical significance.In this thesis, the author focuses on how to overcome the shortcomings of current computer graphics hardware that they can only provide depth information for the primitives such as polygon. The author presents an algorithm for calculating direct visibility of point-based models and then expands the applicability of this algorithm on a large scale by constructing sub-convex hull. Consequently, the efficiency of visibility testing for point-based models is raised remarkably. To enrich realism of the image, some shadow rendering techniques are adopted in order to generate shadows of point-based models on specific surfaces planar or no planar. The research work is conducted mainly in the following aspects:Firstly, preliminary visibility testing algorithm for point-based models is presented. Some of invisible points are removed according to the normal and viewer-point to simplify original point sets. Then, visibility of simplified point sets is directly calculated using technology based on convex hull construction. After preliminary simplification, the number of points in point sets is reduced and then the efficiency of post-processing procedure can be improved.Secondly, the direct visibility testing algorithm is proposed and improved after first simplification for point-based models especially for point-based models with large data. To improve the algorithmic efficiency for the point sets with huge number of points, sub-convex hull construction technology is presented. After rotation transformation of simplified point sets, direct visibility testing is conducted based on sub-convex hull construction technology. The time complexity of our direct visibility testing algorithm is remarkably reduced via sub-convex hull construction. At the same time, the applicability of this algorithm can be expanded.Finally, shadows of point-based models are generated to enhance realism of the image. After direct visibility computation for the point-based models, projection shadows technolygy and shadow volume technolygy are utilized to render shadows for point-based models on specific receivers even on no planar surfaces. We try to avoid the complexity of traditional shadow drawing algorithm such as ray tracing algorithm and render shadows of point-based models without graphics hardware support. Ultimately our algorithm can create high efficiency and satisfying rendering effect.