Scattered Datas Reconstruction

Approximating three-dimension unorganized points with meshes is widely used in practice. In the medical science large amounts of data are obtained through probing into the human body organ with the convenient laser, and with these data the human organ's shape is restored, then pathology analysis is proceeded. In addition, such problems appear in CAD/CAM and reverse project: some existing objects' surface is digitized by detector and unorganized points are got, then from these data real objects are reconstructed.Three-dimension reconstruction is a typical research point in many fields such as calculator vision, mode identify and video technique. Reconstruction is to reconstruct object's original shape from the above unorganized points by making use of the multi-media technique. Different equipments are adopted in different fields, the reconstruction is too different, As a result, rebuilding methods are different. For example, in solid vision the strong sign of the environment can be acquired by using vidicon. The purpose of reconstruction is to reconstruct the three-dimension object from the images that are shoot from different angles.There are already several perfect methods about reconstructing. Because of good scale precision and high intelligence, three dimension COMERO is widely used in manufacturing CAD/CAM's manufacture inspecting and quality control. Scaling uncontrolled surface by three-dimension COMERO, the gained data are not the contact point's coordinate of the scaling head and the workpiece but that of the scaling head center. So retrieving scaling head radius is needed. Now micro-plane method and two-dimension retrieving are adopted in most scale software of COMERO. In these literatures two-three-degree B-spline interpolate surface and Coons surface are used to fit scaling data and contrail surface of scaling head center is gained. And retrieving scaling head radius is needed at unit vectors of sampling. At last real surface is generated. In 1972 Lawson proposed a principle of triangular the largest angle , the least . The triangles which are in agreement with the principle are called local symmetrical. Subsequently, Sibon proved that Delaunay triangulation technique is the only way is accord with the principle. Greenand Sibon followed realized calculating the two-dimension Voronoi graphics and Delaunay triangular technique. Bowyer and Watson generalized the result to arbitrary dimension. Later many documents appeared realizing Voronoi graphics and Delaunay triangulation technique with various methods. Because Delaunay triangulation's result are two-dimension or three- dimension protrude wrap in which contains many illegal triangles or tetrahedron ,it doesn't show the real surface of original object. Boissonnat introduced a new method, through peel off the illegal tetrahedrons making the unorganized data points visioned. Edelsbrunner put forward the concept of α-shape in 1994.α-shape method reconstructed a surface by deleting tetrahedrons or triangles and borders which envelop spheres are larger than α.. Later,Based on α-shape ,Bajaj generalized C1-continuity interpolated surface 0f scattered points. As for symmetrical and consistent points, α-shape method is very efficient. But for the asymmetry or discontinuity of points, it is difficult to choose suitable α and delete unnecessary elements. In this thesis, a new algorithm is put forward, which substitutes the original surface by approximating three-dimension unorganized points with triangular meshes. Because the data of given points usual great ,we should delete some redundance points (it can based on density)before reconstructing the surface. In the process of calculating the neighbor points, the surround box's thought is applied in order to avoid the overall search. Firstly dividing the surround box into a certain number of boxes — small interspace metres. Go all through the unorganized points, and distribute it to a small interspace box according to its three coordinates. While seeking neighbor poin...