The Surface Reconstruction For Scattered Point-Cloud Based On The Topology Neighbors Of Sampling Point

As the core technology in reverse engineering, the surface reconstruction of scattered point-cloud is the important link between reverse engineering and the advanced manufacturing technologies such as CAD/CAE/CAM, rapid prototyping and so on. Two interpolation algorithms of surface reconstruction based on the topology neighbors are proposed. The main research contents and achievements are as follows:1) The spatial index structure named AMBB (Approximate Minimum Bounding Box) tree is proposed.The physical units are expressed by their AMBB and the interrelated geometric operations of AMBB are realized. At last the AMBB tree is constructed through combining the AMBB and N-cross tree. Experiments show that the spacial index structure has many strong points such as strong data suitability, high spatial operating factor and fast quering efficiency.2) An efficient algorithm generating Voronoi diagram of scattered point-cloud is proposed, which takes the data structure named "point-face-polyhedron" to store Voronoi cell, initializes the Voronoi cell of the first point, and the Voronoi cell of the new inserted point is generated after whose adjacent cells are changed accordingly through fission and reconstitution of cells, and it is proved that can generate Voronoi diagram of scattered point-set efficiently.3) An algorithm inquiring topology neighbors of sampling point is proposed. The k-nearest neighbors of the sampling point are gain according to the algorithm of expanding hollow ball by self-adapting based on the AMBB tree of the scattered point-cloud; The topology neighbors reference data of the sampling point are obtained through eccentric and adaptive expansion; Then the Voronoi topology neighbors inquiring is realized according to Voronoi Diagram of topology neighbors reference data. It is proved that this algorithm can obtain the topology neighbors accurately and guarantee to realize the surface reconstruction of arbitrary complicated scattered point-cloud.4) Two interpolate algorithms of surface reconstruction based on the topology neighbors of sampling point are proposed:a) A new expanding algorithm by increment through getting the matching points from the topology neighbors, which can improve the quality of the triangular mesh surface reconstruction on the basis of high efficiency; b) The algorithm named Cocone is improved based on the algorithm quickly generating Voronoi diagram proposed and its useless holes are mended based on the topology nerghbors, so its efficiency and quality are both improved.