Space Discrete Point Set Of 3d Modeling And Simplified Algorithm Research

Taken the spatial unorganized points as the research object, a set of three dimensional shape reconstruction algorithms are studied in this paper. From a view of the mathmatics, related definitions are made towards the modelling problems. Then, the illegal constructions are pointed out based on the geometric features of the spatial object's shape. The specific research content includes:1. The features of a given spatial unorganized points set are studied from several different aspects such as the coordinate distribution, scale space, Pearson product-moment correlation coefficient, the deviation of the points and point of view of the statistics. By doing this, the features of points can be quantitated so as to help cluster analysising, three dimensional modelling, model simplification, etc. In fact, the spatial shape is usually complex in sense; it cannot be built through a general algorithm. It's easy to find that splitted the points to a series of child points set, bulit models separately and then fusion them together is an effective process. There are several modelling algorithms are studied in the paper, each of them has the different ability in expressing the spatial object. Based on these statistical values, appropriate algorithm can be selected to build the model.2. A coarse algorithm is implemented based on the relationship between point and the existed facet under the rules of the outside normal direction and the optimize principle that the minimum angle is maximized. There are four relationships between the point which is waiting for inserting and the existed facets in facet list:point in the pyramid internal, point on the side facet, external point and collinear point. Although the expression ablity of the algorithm is limited, it can be effectively used in point cloud of single station and spherical point cloud by calculating the center coordinates of the3D laser scanner as the virtual center. This algorithm also can be used as the cornerstone in the process of hierarchical modeling.3. There are many problems of shape reconstruction in a random order of inserting points. An operation of optimization to the mesh facets can be introduced. According to the optimization moment, it can be partitioned into three phases:before modelling, modelling and modelling finished. Optimization in modelling and after can be seen as the level of local reconstruction among the basic meshes; the optimization before modelling actually is a sorting process to the input points. In order to measure the quality of the model, a variable which is used to describe the regular degree of the basic facet is introduced. The time delay is also another serious problem which is obviousily occured in point quering opreation without optimization. In order to improve the query efficiency the k-d tree is introduced. From the Euler's theorem, the nearest neighbor average number theory is studied for the follow-up using of the shape reconstruction algorithm based on the potential connection points set.4. Points are sampled from the surface of objects. Based on the principle that the point is closer together is possibily to be connectted topology together then the point is far way from each other, a modelling algorithm is studied. Theoretically, a support of reconstruction to the sampled points is provided from the view of the real varialble theory and functional analysis. There are three types of close neighbors:mathmatics neighbors, spatial orientation neighbors and natural neighbors. The advantages and disadvantages are studied respectively; the algorithm of building potential connection points set is also studied. A modelling algorithm with the potential connection points set is implemented based on the priciple of the neighbors. This algorithm has a stronger ability then the algorithm studied above.5. Convex hull is an important structure. The properties are studied from the point of view of the integral geometry, and a spatial convex hull construction algorithm is implemented. In convex hull, the details can easily be ignored the greater the area of the face and the side length of the longer face in the original object. There are potential conflicts between the largest surface and the side length of the longest side. A coordination mechanism is introduced to resolve this contradiction. An algorithm is implemented that the convex hull is treated as the core and other points are seen as the constraint. The initial grid model is constructed by contracting the space until meet the quit condition. The excess points are projected to its nearest plane, and then constructed the shape on the local projection plane with the DELAUNAY rule. The algorithm has a greater ability to express the space entity, but it can not be used effectively to the objects with holes.6. The hole is most a common element in spatial objects. Followed the aforementioned several reconstruction algorithms, it is necessarily needed to deeply study the features of the "holes" for building more general shapes. From the holes of the two dimensional plane, a two dimensional complex shape reconstruction is studied combined with the Voronoi diagram. Extend the concepts to the three dimensional space, an algorithm is studied in order to express the more common objects with holes. The ultimate experiments prove that the algorithm can be effectively used in objects with holes.7. With the rapid development of data acquisition technology, the precision of point cloud of target object becoming more and more sophisticated. It's possible to build a high accuracy virtual simulation of the real world with the high-density data, but for its modelling and analyzing, the time-consuming is also growing. The amount of the model's vertices is usually huger and an operation of simplification is necessarily needed. The spatial mesh model built through point cloud is treated as the studied object, and a parallel algorithm of simplification under the control of the parameter is studied. The steps are as follows:first, the K-adjacency table is established according to the topology of spatial mesh points; second, the independent set of points is calculated; third, the header element in each item of K-adjacency is taken as the center point, the projection plane is calculated with its neighbour points, then the K value is calculated; forth, the original model is transformed into the K value space, and the feature distribution of the model is studied; fifth, the model is simplified with the K value compared with the input parameter, loops until meet the condition; finally, the experiment is carried on series of spatial meshes. It's proved that the algorithm not only can simplify the model effectively, but also the degree of distortion is also under the control. This algorithm can take full use of the modern parallel chips such as GPU.