Research On Technology Of Surface Reconstruction Using Radial Basis Functions In Reverse Engineering

Reconstructing a smooth surface from the large scattered data is ubiquitous problems in reverse engineering, computer graphics and computer vision. Implicit surfaces reconstruction methods using radial basis functions have recently attracted attention because they can easily represent complex shapes with arbitrary topology, especially, radial basis functions is an stable and accurate method of solving multivariate scattered data interpolation, and have the quality of higher order continuous. The dissertation is concerned with research on technology of surface reconstruction using radial basis functions. The main contributions of our work contain several aspects as follows:1. Three valid measures are proposed aim at implementation of Turk's method. (1) We describe a new technique to uniformly filter scattered data. Firstly, we put the scattered data into a linear linked list, and set a bounding cell with radius r. Secondly, we traversal the linked list from the first element ( base point), if the distance between new point with base point less than r, then delete the new point from the linked list. The following pseudocode describes the procedure of the algorithm.Algorithm 1: uniformly filter scattered data.step 1: Put the scattered data {X_i}_i=1ⁿ into an original list L.step 2: for (Point ^*p1=LHead; p1!= NULL; p1 =p1→next) for(Point ^*p2= p1→next; p2!=NULL; p2 =p2→next) if distance(p1→element, p2→element)< r delete ^*p2 from L.step 3: Obtain an initial approximation set L of scattered data.We can obtain an sparse approximation of scattered data by Algorithm1. The numerical results show that the algorithm is very simple and easily feasible, and the algorithm is a base of other algorithm in this paper. (2) For the method of choosing normal constraints that are created by placing a positive constraint a small distance h in the direction of normal vector, we present an adaptive algorithm of choosing h based on error controlling. Firstly, we determine an interval of h, and discretize the interval with given a step valueλ. Secondly, we evaluate the normal contraint points decided by distinct h, then reconstruct surface using radial basis functions and evaluate the relative errorε_k; Finally, we choose a h make the error least. The following pseudocode describes the procedure of the algorithm.Algorithm 2: adaptive algorithm of choosing h based on error controlling.step 1: Given an interval [h₁, h₂] of h andλ,step 2: for(h = h₁, k = 1;h≤h₂; h = h +λ, k + +).2.1 evaluate the normal contraint points X'_i decided by X_i according to h;2.2 reconstruct surface f_k(x, y, z) = 0 using RBFs;2.3 evaluate relative errorε_k;step 3: Choose h make the errorε_k least.Given scattered data, the accurary of reconstructing surface decided by h is the highest according to algorithm 2. (3) The numerical results show that the accurary of reconstructing surface is mainly determined by the number of points lying on the surface. Combined with Algorithm 1, we unifromly choose some surface points where normal constraint points are created. Thus, the accurary of reconstructing surface can be improved when the total constraints reduction or invariant, according to decrease the number of normal constraint points and increase the number of suface points.2. We describe a new hierarchical technique for fitting scattered data using radial basis functions with global support. According to the algorithm of filtering scattered data with two different steps. Firstly, we can simple the data sets by characteristic of geometry continuous in neighborhood of given point. Then, we obtain the approximation sets of the scattered data by uniformly filtering algorithm. The following pseudocode describes the procedure of the algorithm.Algorithm 3: filter scattered data with two different steps.step 1: Put the scattered data {X_i}_i=1ⁿ into an original linear linked list L, set bounding cells with radiusÏ„andδ, and list Lnull.step 2: for (Point ^*p1=LHead; p1!=NULL; p1=p1→next) for(Point ^*p2= p1→next; p2!= NULL; p2=p2→next) if distance(p1→element, p2→element)<δdelete ^*temp2 from L Lnull=Lnull∪{temp2} else if distance(p1→element,p2→element)< r delete ^*temp2 from L .Step 3: Obtain an initial approximation sets L of the scattered data, Lnull is set of deleting point for ever,According to algorithm 3, we can obtain an initial approximation sets of the scattered data, and simple the data sets.Given scattered data S, we construct a hierarchy of S, {S¹ (?) S² (?)…(?) S^M = S} , S¹ builded by algorithm 3 is the first hierarchy of S . We interpolate the scattered data in S¹, because the number of point in S¹ is little, the accuracy of interpolating surface is not high. We interpolate the sets of the hierarchy, as an offsetting of the interpolation function computed at the previous level. The basis ideals of hierarchy algorithm is: firstly, we filter the scattered data, and obtain the initial approximation sets, secondly, we reconstruct the suface from the initial approximation sets, and compute the distance between interpolation function with points in the residual sets. For indentifing the feature points, we sort the points which distance beyond the controling error from big to small, and add the sets into the previous level sets afer filtering with aglorithm 3, then reconstruct the surface, as an offsetting of the interpolating function computed at the previous level.Algorithm 4: algorithm of hierarchy interpolation.step 1: Given list T,μ,ε. set a bounding cells with radius r andδ, obtain the approximation sets S¹ and L₁ according to algorithm 3. and let j =1.step 2: obtain the interpolation surface f_j{x,y,z) = 0 according to interpolating data sets S^j .step 3: compute the distance d_i between f_j and X_i = (x_i, y_i, z_i) in S -S^j -Lnull , if d_i >ε, add X_i into T , if all d_i <ε,then stop.step 4: sort d_i in T from big to small .step 5: let r =μ^j* r , filter the points in T with algorithm 3, then obtain T' ,L_j+1, let S^j+1= S^j∪T', j = j + 1, and goto step 2.According to our numerical experiments, the feature points can be indentified quickly only using less scattered data, thus, the higher fitting accuracy can be acquired by only solving the lower order equation during reconstructing surfaces, so the developed algorithm lead to economiacl, yet accurate surface reconstuction.3. We describe a new technique for fitting scattered data using radial basis functions. The fitting surface is determined as zero level isosurface of a trivatiate model which is an implicit least squares fit of the data based upon radial basis functions.Given a scattered data {d_j}_j=1ⁿ and associated real values {h_j}_j=1ⁿ. Let (?) , are n - k points lying on the reconstruction surface, and associated real values h_i = 0 , normal vectors (?),{s_i}_i=1^k are certain n - k points in {c_i}_i=1^n-k, the normal constraint points t_i are created by placing a positive constraint a small distance h in the direction in {s_i}_i=1^k , associated real values h_i =-1 , where k < n/2 . The plane (?) is determined with c_i and (?). We can find out the two distinct points (?) and (?) in the plane, and suppose the linear c_ia_i and c_ib_i are not parallel.The main ideals of algorithm is : using the implicit function f(x, y, z) to fitting scattered data, and making the value of f(x,y,z) at the point c_i approximating 0, the value of f(x, y, z) at the point {t}_i=1^k approximating -1, and the gradient (?)f(q_i) of f(x,y,z) at the points in {q_i}_i=1^n-2k approximating the normal vector of these points. The geometry background of algorithm is that the surface f(x, y, z) = 0 nearly pass through point sets {c_i}_i=1^n-k, and the tangent plane of surface f(x, y, z) = 0 at the points in {q_i}_i=1^n-2k nearly is plane determined by q_i and its normal vector. Let r = (x, y, z) , implicit function f(r) = f(x, y, z) = 0 is determined so as to minimize the errorwhere the weights u_i,v_i, can be used to reflect the relative importance or reliability of scattered data. ((?)f(d_i)·α_i) and ((?)f(d_i)·β_i) reprsent respectively inner product (?)f(d_i) withα_i and (?)f(d_i) withβ_i. In the condition of solving the same scale equations, the numerical results show that the higher accurary reconstuction surface can be obtained by adding the number of suface points, then according to add the gradient quality and redue correspondly the number of normal constraint points,4. We describe a new technique for fitting scattered data. Given 3D scattered data and associated normal vectors, our new method produces an implicit volume modelρ(p) which zero level isosurface interpolates the given points and associated normal vectors. We call an implicit model of this type, a radial Hermite interpolant. The term radial connotes that the weight functions of the model are only functions of distance from an arbitrary point of the domain. The term Hermite conveys that the interpolant functionρ(p) not only matches given dependent data values(S = {p :ρ(p_i)= 0}). but also some type of first order derivatives quantity ((?)(p_i) =N_i)). Our new method does not require the solution of linear systems of equations, and rather than require additional interior and exterior points, our new method only requires normal vectors. The main results is:Theorem 1 Given 3D scattered data p_i = (x_i,y_i,z_i) and associated normal vectors (?), i = 1,....n, p is arbitrary point, x =||p - p_i||, letthe valuesσ_i determine the radius of the sphere of support for the weight functions , S is the implicitly defined surface S = {p :ρ(p) = 0}. where,(?), then the surface S passes through the points p_i and has a normal vector at the point p_i equal to N_i.The new method does not the solution of equations , it allow us to model large scattered data. Especialy, the method does not require additional interior and exterior points, it is simple to perform.