Point-Sampled Geometry Modeling And Rendering

With the increasing use of 3D geometry in various computer graphics application fieldslike digital museum, digital medical, industrial design, entertainment and so on, more re-quirements on precision and detail of models are presented. The development of modern3Ddigital photography and 3D scanning systems also facilitate the ready acquisition of largerscale and more complex real-world objects, these facts result in a dramatic increase in thevolumes of 3D geometry.To process such complex and large scale's 3D geometry models, the traditionalpolygonal-meshes based geometric representation has been restricted due to the difficulty oftopology reconstruction. Consequently, more and more researchers shift attention to shaperepresentation with point primitives for its distinct advantages on convenient 3D point dataacquirement, simple data structure and no need of maintaining globally consistent topolog-ical information. Then the point-sampled geometry has become an emerging new field ofstudy in computer graphics.As a new type of surface representation, digital geometry processing of point-sampledgeometry is still in infancy and there are no mature theory and application system till now.With increasing complexity of point-sampled geometry and growing demand for advancedmodeling functionality, significant effort is being devoted to the design of efficient, reliable,and scalable algorithms for digital geometry processing.This thesis, which is supported in part by the National Natural Science Foundation ofChina under grants 60573146, mainly focuses on the disign of algorithms for shape modelingand rendering of surfaces represented by point clouds. Through an in-depth study of digitalgeometry processing and geometric surface representation, from viewpoint of discrete pointprimitive, we study 3D geometry by using local surface analysis, digital filtering, clusteringanalysis and encoding theory etc. Based on the studies above, a robust and nearly completeshape modeling and rendering framework for point-sample geometry is presented. The majorcontributions of the dissertation include four parts. 1. A non-iterative, feature preserving point clouds smoothing algorithm is proposedbased on fuzzy vector median filtering.The proposed method smoothes point normal firstly. To do this, we extend the fuzzyordering concept to vector-based data and introduce the fuzzy vector median filter,so as to acquire correct normal of point clouds. As preparation for fairing position,the method combines normal, curvature and position information to construct adaptivelocal neighborhood which suits distributions of local geometric features. This makespoints moving along the correct normal and avoids excursion. Trilateral filter, whichis based on robust statistics and local first-order prediction, analyzes information ofspace and feature simultaneously and processes feature and noise anisotropically, sothe features can be preserved well but noise is faired effectively. Due to the robustnessof local first-order prediction, the proposed method is non-iterative.2. A progressive point-sampled surface algorithm is proposed based on moving leastsquare projection.The basic building block for the construction of progressive point-sampled surfacesis a projection operator. Based on the properties of the projection operator we derivean algorithm to construct a base point set which are more contributive to the refer-ence surface. Starting from this base point set, a refinement rule using the projectionoperator constructs a progressive point-sampled surface from any given manifold sur-face. Based on the high relativity between adjacent surfaces, an effectively progressivecompression algorithm is presented.3. Metamorphosis of point model is studied based on principal components analysis andclustering analysis, and a novel morphing algorithm for large-scale point-sampled sur-face is proposed.The fundamental problem of point-sampled geometry morphing is how to set the cor-responding relationships between points of the two objects which are usually of differ-ent size. The local coordinate systems of two models are first normalized by principalcomponent analysis. Then we transform, rotate and scale the two models so as tolocate them in a common coordinate system. Two processed models, which possesssame natures in the identical direction, combine to a new point set. The new point setis then split recursively into clusters. The corresponding relationships between samplepoints of the two objects are established by performing a local mapping in each cluster.4. A high quality and real-time rendering algorithm for large scale point-sampled geom- etry is presented.The point-sampled geometry will be constructed to a bounding-sphere hierarchy so asto compress the data structure using the relativity of neighbor levels. Then, throughtraversing this hierarchy structure in depth-first order, efficient visibility culling anddepth test can eliminate a large number of sampling points which are irrespective ofrendering. After selecting the appropriate levels, the algorithm assembles the corre-sponding points into a linear structure which would be processed by GPU with pow-erful parallel processing capacity. Finally, to obtain high quality rendering, ellipseweighted average filter is used to antialias the point set surface.This thesis deeply studies four associated phases of geometric modeling and render-ing point-sampled geometry. Every phase is self-contained, but associated each other. Fourphases are progressive and co-constructed an organic whole. We have implemented these al-gorithms with C++ language and evaluated them by using several large scales, high-precisionand more detailed point models. The experimental results have demonstrated the effective-ness and practicability of the proposed algorithms.