Research On Modeling And Rendering Of Point-based Geometry

There are many expression methods of curved surfaces in computer graphics realm. The models expressed using those methods are usually transformed into those expressed by triangles before rendering in hardware. The geometry of the model surface can effectively be conveyed using triangles. In addition, processing and rendering of triangle-based models have got the support of graphics hardware. But, as the geometric scenes become more and more complex, the quantity of triangles increases fast. Some triangles may contribute to less than one pixel when displayed. In this case, the traditional progressive method of raster becomes less effective because the cost of rendering triangles is high. The processing of plenty of small triangles leads to the bottleneck in bandwidth and excessive floating computation. Moreover, 3D scanning devices have been widely used in generating 3D sampled data recently. This urgently demands new methods that can be used to effectively express, process and render large-scale and highly complex geometric models. The traditional method is to transform point set into triangles before processing and rendering. However, with the rapid development of 3D scanning techniques, the quantity of vertices acquired by scanning devices reaches the magnitude order of billion. The triangulation of such great deal of point samples is a very time-consuming task. Due to the restriction of time and space, the traditional mesh simplification methods and progressive display methods become more and more inefficient as the scale of sampled data becomes larger continuously. Owing to the above reasons, point-based techniques in representing, processing and rendering models have attracted people's attention again. The basic idea of these techniques is that the models would be represented by point samples before processing and rendering. There are no explicit topological connections between point samples. This makes geometry processing easier and avoids many constraint conditions that are imposed for the purpose of guaranteeing the topology correctness in the procedure of mesh processing. Besides, triangulation and rasterization can be omitted during rendering. Since point-based methods have obvious advantages in some aspects compared with triangle-based methods, it is of great significance to study the techniques of point-based modeling and rendering.Recently, Point-Based Modeling and Rendering (PBMR) gradually becomes a hot research topic in computer graphics realm and attracts more and more attention. This thesis investigates some relevant techniques in the aspect of Point-Based Modeling and Rendering and proposes several new methods. The main contributions of this thesis include:(1) This thesis proposes a novel point primitive that we call"Spherical Patch Point". We use"Spherical Patch Point"to approximate the vicinity of a surface point. We can effectively simplify and refine point-based models using this point representation. The representation is prone to the implementation of ray tracing of point-based models. The attributes of a spherical patch point comprise position, normal, sphere radius, sphere center, neighbor radius and material. The methods of evaluating normals are classified into two types depending on the source of point cloud data. If the point cloud data comes from files in PLY or WRL format, we evaluate the vertex normals by means of triangles. If the point cloud data comes from ASC format files that only store point information, we evaluate normals by solving a covariance matrix of k nearest neighbors of a point. For neighbor radius, our scheme is to compute neighbor radius of a certain point according to density of points spatially around it. We choose the maximum distance from a spherical patch point to its neighbors as the spherical patch point's neighbor radius. For convenience, we usually store the square of neighbor radius instead of the neighbor radius itself. To determine sphere radius, we seek help from the normal of spherical patch point and the Euclidean distance from a spherical patch point to its neighbors for the computation. Firstly, we evaluate normal curvatures of point-based surface at a given point along all the tangential directions corresponding to its neighbors using related normals and Euclidean distances. Secondly, we compute the average of these normal curvatures. At last, we choose the reciprocal of the average as sphere radius of the given point. The average of normal curvatures is used to approximate the mean curvature of point-based surface at the given point.(2)This thesis proposes a simplification algorithm for point-based models. There are many simplification methods for traditional triangle-based models. Compared with this, we also need corresponding methods to simplify point-based models to a certain degree. That is, we need to find a point set of low density to replace the original point set with minor errors. For this reason, many researchers use various hierarchical organization schemes to reach lower frequency versions of the original model. However, the problem of removing redundant points has not been given enough attention so far. Our algorithm is to remove the points of high redundancy on point-based models. In our algorithm, whether a point can be removed depends on two factors. One is the redundancy of the point. The other is whether the neighbor disk of the point can be replaced by the disks of the point's neighbors. We use neighborhood flatness to describe the redundancy of a point. Only when the neighborhood flatness of a point is less than a certain threshold can we choose the point as candidate point. To check whether the neighbor disk of a certain candidate point can be replaced by the disks of the candidate's neighbors, we design two subalgorithms. One divides a particular line segment by a circle and the other divides an equilateral triangle by a circle. Since our algorithm use heap structure for the comparison of neighborhood flatness of candidate points, the asymptotic time complexity of our algorithm is O(nlogn), where n is the number of candidate points. Experiment results show that the proposed simplification method can effectively remove the redundant points on point-based models and preserve the geometric shapes of the models well.(3)This thesis proposes a refinement algorithm for point-based models. Since point-based models are sampled models, the sampling density of point-based models can not satisfy arbitrary resolutions. When sampling density of a local area can not satisfy the display resolution, we need to resample the area. Our refinement algorithm guarantees that there could be fewer points where the point-based surface is relatively planar and there could be more points where the point-based surface is violently fluctuated. In our algorithm, we use neighborhood flatness to describe the flatness of the vicinity of a point. Only when the neighborhood flatness of a point exceeds a certain threshold can we choose the point as refinement related point. The refinement is accomplished by inserting the appropriate points between the refinement related points and their neighbor points. Position and normal of the inserted point are acquired using weighted average method. The asymptotic time complexity of our algorithm is O(n), where n is the number of refinement related points. Experiment results show that the proposed refinement algorithm solves the undersampling problem of point-based models well.(4)Considering the fact that previous methods on ray tracing point-based models either are extremely slow or result in unsatisfactory visual quality, this thesis proposes a new algorithm of intersecting a ray with point geometry and thus implements the ray tracing of point-based models. In the intersection algorithm, only when a ray intersects the neighbor disk of a spherical patch point can we decide the ray intersects the point. Determination of the intersection point between the ray and the spherical patch point relies on different types of sphere radiuses. The intersection point between a ray and a spherical patch point is defined using the intersection point between the ray and the corresponding sphere. Among all the intersection points related to the ray, we choose the one closest to the origin of the ray as the final intersection point. To achieve a much smoother model surface, we form the normal of the final intersection point by weighting all the influential normals.For shadow generation, we implement projected shadows on point-based models using shadow testline method. As to texture mapping, we accomplish a technique of 2D colored texture mapping on point-based models. We also test for reflection and refraction using our point-based rendering method and get satisfied results. The proposed rendering method in this thesis is prone to get good visual appearance of silhouette. It can be seen from experiment results that our method performs better than related methods in the way of silhouette representation. To test the performance of our intersection algorithm we compare it in rendering time with related technique. Experiment results show that our intersection algorithm can improve rendering speed while maintaining similiar visual quality.(5)This thesis proposes a new particle swarm optimizer (PSO) based method for detecting features of point-based models. The method solves the problem of fast detection and display of features of large-scale models. It applies modified particle swarm optimizer to feature detecting in 3D space so as to accomplish the search of multiple objective regions. By redefining the particle, fitness function, initial termination condition, gBest, pBest and iterative formula of PSO, the proposed method in this thesis combines local search with global search for the purpose of finding multiple targets fast. It detects feature points by fitness function which is able to estimate local surface variation and marks those points to display the features of model fast. Experiment results show that the proposed method is suitable for fast detection of features of large-scale point-based models.