A Mesh Generation Algorithm From Unorganized Points

Reverse engineering is a new technique developing with the development of Computer Science and the progress of data measuring technology. Its appearance has in fact changed the design mode of producing material objects in CAD system from drawing.It designs and offers a new way for fast production and rapid prototyp-ing.Meshing is the most important issue in Reverse Engineering,The question refers to the sampling data points from the known objects and construct the geometric model.this is the most important basis of object analysis,computing and mapping.Chapter 1 introduces the the way to acquisition the cloud points.The two major equipments for acquisition are Non-contact equipment and contact equip-ment,usually we use Non-contact equipment.Then introduces some algorithms for registration and some optimization methods.ICP algorithm is usually used for registration,there have some other algorithms like Pulli algorithm,Turk algorithm,Levoy algorithm.the main optimization methods are these categories:(1)Carving method, (2)Subdivision method,(3)Regional Growth method.Chapter 2 introduces some algorithms from three different ways according the kinds of points organization.For unorganized points,Boissonant had been done some innovative works,his algorithm are:(1)Based on surface (2)Based on volume;Hoope purposed a method based on surface/volume;Edelsrunner and Mucke defined theαshape of points and got the mesh of the surface.Nina defined the quality of the points,apply Voronoi and Delaunay Triangulation.he got the method called Voronoi Filtering.For range images,Levoy combined some range images to single polyhedron meshing; Hilton first defined a implicit surface and then triangulated using March- ing Cube.For volume data and profile curve,Marching Cube algorithm,which was purposed by W.Lorensen,is considered to be the most popular algorithm,the nature of it is iso-surface extraction from 3-d data;Blinn purposed generalized algebraic modeling method,he used iso-surface in scalar field to express 3-d object.in fact, the three kinds can exchange for each other.Chapter 3 introduces our own mesh generation algorithm from unorganized points in detail. Our method mesh the points from the local.First,choose a point and its k ncighbor,construct a tangent-plane which is the most fit these k points. Let O_i is these k points's centroid,then the question is:For given points Q = {Qi_i= 1,2,...,k}that are near O_i,we can obtain normal vector n_i that minimize (1)Because of least squares method,we can get a 3×3 matrix C,the eigenvector according to smallest eigenvalue of Cis the normal vector n_i. And we get the tangent-plane.For arbitrary point P∈R³,its projection point is P' = P—(P—O_i)n_i,now we get these 2-d projection points according to these 3-d points.let p₁ is one of these 2-d points,and its coordinate is (0,0),choose another point p₂, we can calculate the distance d₁ between p₁ and p₂ because we know the 3-d coordinate.then the coordinate of P₂ is (d₁,0).For arbitrary points p₃, let v₁ isθis the angle between v₁ and v₂.sinθ= (1-cosθ²)^1/2,the coordinate of p₃ is(|v₂| cosθ, |v₂|sinθ) And then,we get the 2-d coordinate of these points in tangent-plane.Next we get the connections of these 2-d points using Delaunay triangulation,we think these connections are still the connections of 3-d points.Because we start with local points,it is importance to solve the connection relations between different tangent-plane.In meshing optimization,we first define three location relationship:(l)Intersection,(2)Tangent,(3)Deviation. we can convert Intersection and Deviation to Tangent through pretreatment.the method is:Let neighbor 1 has been triangulated,we get a border point,then get this point's neighbor points (neighbor 2),in neighbor 2,we remove all points in neighbor 1 but border point,then Delaunay triangulation neighbor 2,repeat the above steps until all points are solved.Now,the location relationship between neighbor 1 and neighbor 2 is tangent.For tangent,we consider the tangent-planes which all through the border point, when the projection plane have illegal triangles,it is the line between two border points in one k neighbor go through some triangles in another k neighbor,we cancel the line and line the two points to the nearest points in the triangles. After optimization,we must contain all the normal vectors belong to every tangent-plane.we use the method of traversing minimal spanning tree to contain the consist normal vector.Let one tangent-triangle is a particle,there have a border between different particles,the weight on the border is 1 - |n_i? n_j|(n_i,n_j are normal vectors),we get a Rieman-nian graphic.then traverse the graphic,during traversing,let present tangent-plane is Tp(x_i),present normal vector is n_i,the next tangent-plane is Tp(x_j),if n_i·n_j < 0 then n_j change to—n_j,or no change.so we get the consist normal vectors.In Chapter 4,we get some graphics by experiment,and discuss the time complexity of this algorithm.Also we discuss the bottleneck in the algorithm.