An approach for surface reconstruction of 3D CAD models.

Tiwari, Amod ; Pathak, V. ; Chatterjee, A. 等

Abstract

This paper proposes the algorithm to repair 3D artifact/model for which no data is available for the missing part. It presents an efficient healing algorithm that exploits information about the curvature (k) versus arc length (s) of the neighborhood point cloud data available around the missing part. The k-s information of the missing part is estimated using this information of the neighboring regions. After getting k-s information about the missing data, Intrinsic LINear Curvature Element (LINCE) Model is used to calculate the x-y information of the missing part.

Key words: Healing algorithm, LINCE model, K-s information, Stl format

Introduction

Due to recent technological development in scanning process (laser and optical), it has become easy to get point cloud data for a given artifact or an object. The artifacts scanned may be broken and may require the reconstruction work. Different algorithms are available for reconstruction of given object from its point cloud data

An object surface can be viewed as a family of the curves. If the surface has a hole in it, the curves forming it will also be broken in between (Fig. 1(a) and Fig 1(b)). This paper presents an algorithm, which uses the polar geometry and concept of Polar Radial Angle model [1] of curves. Using this geometry, a relationship for the curvature (k) and arc-length (s) can be obtained from which the rate of change of curvature with respect to arc length can be found. The proposed algorithm first finds out the k-s information of the near by region of the broken part and then it interpolates the k-s information's for the missing region. After estimating the k-s information for the missing region, intrinsic LINear Curvature Element (LINCE) Model of a curve is used to get the x-y values for the missing part. [1]

[FIGURE 1 OMITTED]

Related Previous Work

There exist several techniques to reconstruct surface from the point cloud data. This section deals with some of the well-known techniques that can be used in the field of surface reconstruction.

Hole Filling Using Triangulation of Each Connected Component

One technique is to triangulate each connected components of the surfaces boundary; thereby filling each hole with a patch that has the topology of a disc. This technique works well for simple holes in nearly flat surfaces. But on convoluted holes it is likely to result in self-intersecting geometry. In such case we would like mesh based reconstruction,

Mesh-Based Reconstruction with Hole Filling

This method creates a surface that bounds the maximum region of space consistent with the scans, so it is guaranteed to produce a watertight surface. However the method may lead to surfaces that are less plausible than smoothly extending the observed surfaces. Moreover, the method requires knowledge of scanner lines of sight, and it performs poorly if these lines of sight do not adequately cover the volume out side the object. Additional lines of sight can be obtained by scanning backdrops placed behind the object but still with in the scanner's working volume [2], [3], or by using a separate sensor to detect objects silhouettes [4]. However these solutions may be difficult to deploy out side the laboratory. This algorithm does not require any such information like type of scanner, line of sight etc.

Volumetric Diffusion

Volumetric diffusion algorithm is also a method used for the reconstruction of bad surfaces. It takes the time and memory proportional to [n.sup.2] where 'n' is the number of points in the data. This uses the diffusion to complete a volumetric representation of the surface. It produces a closed, manifold triangle mesh without self-intersection.

Although the algorithm is robust, it contains a number of free parameters. The distance at which we clamp source terms, the size of convolution filter, the distance from a hole boundary etc [5]. This boundary are curve base measure with the help of Serret Frenet Equations

Serret Frenet Equation

Consider a curve C as shown in Fig 2(a). Let r be the position vector of a generic Point P and let s, the arc-length of P from a reference point A, be the parameter describing the curve as r(s). The unit tangent vector, the curvature, the torsion, the normal and the binormal of the curve C at the point P are given as follows:

t = dr/ds (1)

dt/ds = kn (2)

dn/ds = -kt + [tau]b (3)

db/ds = -[tau]n .(4)

It is clear that t, n, b are mutually perpendicular each other. If we consider t, b, n are vectors quantity there for

b = t x n (i)

t = n x b (ii)

n = b x t (iii)

This can be proved with the help of vector cross product method.

[FIGURE 2 OMITTED]

Where t is the unit tangent vector, b is the unit binormal vector and n is the unit binormal vector; k is the curvature and [tau] is the torsion. Point P(x, y, z, s, [kappa], [??]) having six co-ordinates known as frame of reference. Equation (2), (3) and (4) are known as Serret Frenet Equations. If the curve is planer then [tau] = 0 and above equation can be written as follows

r = [x (s)]/[y (s)] (5)

Where x(s) and y(s) are the length of arc about the axis of x and axis of y respectably

t = dr/ds And n.t = 0 (6)

The problem of finding the co-ordinates of x and y as a function of arc length parameter s can be solved using Serret Frenet Equations (2) through (4). Rewrite Equation (6) as follows:

t = d r/d s = [[d x (s)/d s d y (s)/d s].sup.T] Where T is transformation (7)

n = [-dy(s)/ds dx(s)/ds] Since n.t=0 (8)

dt/ds = [[d.sup.2] x(s)/d[s.sup.2] [d.sup.2] y(s)/d[s.sup.2]] (9)

Substituting Equations (8) and (9) in Equation (2) yields:

[[d.sup.2] x(s)/d[s.sup.2] [d.sup.2] y(s)/d[s.sup.2]] = k -dy (s)/ds dx (s)/ds] (10)

Compare Equation (10) both side as in matrices form yields Equation (11) and Equation (12)

[d.sup.2]x(s)/d[s.sup.2] = -k dy(S)/ds (11)

[d.sup.2] y(s)/d[s.sup.2] = k dx (s)/ds (12)

Now putting in Equation (11) dx (s)/ds = Cos[[psi].sub.([sigma])], and putting in Equation (12) dy (s)/ds = Sin [[psi].sub.([sigma])], yield new Equation (13) and (14). Where [[psi].sub.([sigma])] is the radial angle

d/ds (Cos [[psi].sub.([sigma])]) = - k dy (s)/ds (13)

d/ds (Sin [[psi].sub.([sigma])]) = k dx (s)/ds (14)

Integrate both sides Equation no (13), (14). Where [[s.sub.0], s] are interval of given boundary

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

LINCE Model

Let a curve pass through the points [P.sub.0] ([x.sub.0], [y.sub.0]) and [P.sub.n] ([x.sub.n], [y.sub.n]) in a 2-D space (Fig2b). Let the directions of tangent at [P.sub.0] and [P.sub.n] have been specified by [[PSI].sub.0] and [[PSI].sub.n] and arc lengths from a reference point O as [s.sub.0] and [s.sub.n] respectively. If k is the curvature at any point P, then it is assumed that the variation of k as a function of the arc length as the parameter k=k(s) has been specified. It can be seen that k(s) defines the shape of the curve.

The curvature k(s) can be defined as a series of piecewise continuous linear functions with curvature [k.sub.0] and [k.sub.n] at the initial and final points. The intrinsic equation of curve pass through two point can be written as:

k(s) = [k.sub.1] - [k.sub.0]/[s.sub.1] - [s.sub.0] (s - [s.sub.0]) + [k.sub.0] Where [s.sub.0] [less than or equal to] s [less than or equal to] [s.sub.1]

k(s) = [k.sub.2] - [k.sub.1]/[s.sub.2] - [s.sub.1] (s - [s.sub.1]) + [k.sub.1] Where [s.sub.1] [less than or equal to] s [less than or equal to] [s.sub.2]

k(s) = [k.sub.n] - [k.sub.n-1]/[s.sub.n] - [s.sub.n-1] (S - [S.sub.n-1]) + [k.sub.n-1] Where [s.sub.n] - 1 [less than or equal to] s [less than or equal to] [s.sub.n] (18)

Where are k(s), [k.sub.0], [k.sub.1], [s.sub.0], and [s.sub.1] [k.sub.n-1], [s.sub.n-1] are intrinsic co- ordinate.

The area under the curvature equation represents the change in the tangent angles of the initial and final points of the 2D curve. So from Equation (17)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (19)

Putting the value k(s) in Equation (19), from Equation (18) there for

[[PSI].sub.n] - [[PSI].sub.0] = [k.sub.0] + [k.sub.1]/2 ([s.sub.1] - [s.sub.0]) + [k.sub.1] + [k.sub.2]/2 ([s.sub.2] - [s.sub.1]) + ... + [k.sub.n-1] + [k.sub.n] ([s.sub.n] - [s.sub.n - 1]) (20)

Similarly from Equation (15) and (16)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (21)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (22)

Substituting the value k(s) from Equation (18) in Equation (21) and (22)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Where [C.sub.1], [C.sub.2], .... [C.sub.n] are constants. Note [C.sub.1] = [[PSI].sub.0]. The other constants can be expressed in terms of [k.sub.i], [s.sub.i], I = 0, ..., n and [[PSI].sub.0] using following relation.

[C.sub.j] = [C.sub.j-1] + [k.sub.j-1] - [k.sub.j-2]/[s.sub.j-1] - [s.sub.j-2] ([s.sub.j-1] * [s.sub.j-1]/2 - [s.sub.j-1] * [s.sub.j-2]) + [k.sub.j-2] * [s.sub.j-1] + [k.sub.j] - [k.sub.j-1]/[s.sub.j] - [s.sub.j-1] ([s.sub.j-1] * [s.sub.j-1]/2) - [k.sub.j-1] * [s.sub.j-1] (23)

Where j = 2,3, ..., n (23)

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

Computation of Cross-Section

The step of computation of cross-sections of each hole by taking cross-sectional planes perpendicular to the hole. Let 'p' be a set of 3D points defined as p = {[x.sub.i], [y.sub.i], [z.sub.i] | i [member of] [0, n], n [member of] N} and a 3-D cross-sectional plane P with equation A x + B y + C z + D = 0 Where A, B, C are the direction ratio of a cross-sectional plane

If L, M, N are the direction cosine of cross-section plane there for

L = Cos [alpha] (24)

M = Cos [beta] (25)

N = Cos [gamma] (26)

Relation between Direction cosine and direction ration

A

L = (27)

[([A.sup.2] + [B.sup.2] + [C.sup.2]).sup.1/2]

B

M = (28)

[([A.sup.2] + [B.sup.2] + [C.sup.2]).sup.1/2]

C

N = (29)

[([A.sup.2] + [B.sup.2] + [C.sup.2]).sup.1/2]

There for the relation between Direction cosine [L.sup.2] + [M.sup.2] + [N.sup.2] = 1

Distance of point [p.sub.i] from the plane P can be achieved as

[D.sub.i](P, [p.sub.i]) = A * [x.sub.i] + B * [y.sub.i] + C * [z.sub.i+] D/[square root of [A.sup.2] + [B.sup.2] + [C.sup.2]] i [member of] [0,n] (30)

Where points ([x.sub.i], [y.sub.i], [z.sub.i]), i [member of] [0, n] for which [D.sub.i] [approximately equal to] 0 are the cross-sectional points and A, B, C are coefficient of ([x.sub.i], [y.sub.i], [z.sub.i]). To get more cross-sections other parallel planes are taken. Number of cross sections taken for a hole depends on the size of the hole. Fig: 5 show a triangulated point cloud data with a hole, some cross sectional plane for the hole and Fig: 6 show the cross sectional data obtained from one cross sectional plane.

[FIGURE 5 OMITTED]

[FIGURE 6 OMITTED]

Projection of 3-D Cross-Sectional Data on to 2-Plane:

This step is to project cross sectional 3-D point cloud data on to a 2-D plane. Let ([x.sub.1], [y.sub.1], [z.sub.1]) be a point on plane

z = -A/C x+ -B/C y+ D/C or z = ax + by + c and after projecting it on X-Y plane ([x'.sub.1], [y'.sub.1]) is obtained. Normal vector to the plane is [??] = -a[??] - b [??] + c[??]. By inspection a vector perpendicular to the plane [??] = -b[??] + a[??] can be obtained. Cross product of these two vectors gives another vector on the plane and is given by [??] = -ac[??] + bc [??] - ([a.sup.2]- + [b.sup.2])[??]

[??] = 1/[square root of [a.sup.2] + [b.sup.2]] (-b[??] + a [??]) and [??] = 1/[square root of [(ac).sup.2] + [(bc).sup.2] + [([a.sup.2] + [b.sup.2]).sup.2] (ac[??] + bc [??] -([a.sup.2] + [b.sup.2])[??])

Where [??] and [??] are two orthogonal vectors in the fitted plane? Let the origin (o_i,o_j,o_k) be (0,0,C) on the plane. So a vector from origin to point ([x.sub.1],[y.sub.1],[z.sub.1]) is given by ([x.sub.1] - o_i)[??]+([y.sub.1]-o_j)[??]+([z.sub.1]-o_k)[??]. This vector lies in the plane of unit vector [??] and [??]. So it can be written as linear combination of [??] and [??] as follows: ([x.sub.1]-o_i)[??]+([y.sub.1],-o_j)j+([z.sub.1]-o_k) [??]=[x'.sub.1][??]+[y'.sub.1][??] (31)

By equating the i, j and k component of the equation (31), three linear equations are obtained. Solving these linear equations ([x'.sub.1], [y'.sub.1].) can be found.

Detection of Hole Boundary

Our algorithm takes the triangulated point cloud data in stl format ([PSI]). In a stl file, triangles can be divided into two categories. First category can be named as boundary triangles and second one as inner triangles. In figure given bellow, triangles with shaded colour are boundary triangle and others are inner triangle. In a correct .stl file, the sides of each inner triangle are shared by two triangles and in boundary triangles, there is at least on side, which is not shared by more than one triangle. These edges of the boundary triangles may be called the boundary edges. The property of boundary edges (i.e. it is shared by only one triangle) can be used to identify the holes in the triangulated 3D data. We can claim, the boundary edges are the edges, which form the hole boundary. In brief all the edges in a triangulated file, which are shared by only one triangle form the hole boundary.

[FIGURE 7 OMITTED]

Figure 7: Thick line shows the boundary of the triangulated cloud and Boundary triangle: with shaded colour Inner triangle:

 with plane colour

 Void GetHoleBoundry ()
 {
 While (triangles left)
 {
 SelectOne Triangle;
 For (I=0; I<3; I++)
 {
 If (Is BoundaryEdge (Edge))
 Write To BoundaryEdge (Edge))
 Edge = Edge [right arrow] next; /*Select next edge of boundary*/
 }
 }

Healing of Cross Sections

After getting the cross-sections projected on the 2-D plane, these broken cross-sections are healed. Here we have presented the steps to heal a cross-section. These are repeated to heal all cross-sections.

Step1: First step takes a cross-section and separates it into two parts. Separation is done as follows. By looking into the point cloud data, maximum distance between two neighboring points can be found. So if in a cross-sectional point cloud data, distance between two consecutive points is found more than the maximum allowed distance between two data points, this is considered as a break in the cross sectional point cloud data. The data points before break are considered as Part 1 and remaining as Part 2.

[FIGURE 8 OMITTED]

[FIGURE 9 OMITTED]

Step 2: This step takes data points of the two parts of the cross-section and fits quadratic curve separately to these data sets using least square method. Let us say y = [f.sub.1](x) and y = [f.sub.2](x) are the two quadratic curves for the data set of part 1 and part 2. Step 3 to step 9 heals the cross-section from left side taking point A as staring point

Step3: The curvature and arc-length (k-s) values are calculated for the two parts using equation (32) and (33) taking point A as starting point for Part 1 and Q as starting point for Part 2. Plot of the k-s data for the above said two parts of the cross-sectional data is shown in Fig: 9(a). Since the arc-length(s) for both the parts are calculated separately taking A and Q as starting point (Point where s = 0) for Part 1 and Part 2 respectively, k-s plot of the Part 1 and Part 2 is found overlapping.

k = [d.sup.2] y/d[x.sup.2]/[3th root of 1 + [(dy/dx).sup.2]] Where k is reciprocal radius of curvature (32)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Where x=a is starting point and x=b is last point. (33)

Step 4: To compute arc-length for both the part taking A as reference point, a constant have to be added to the each value of arc-length for Part 2. Let us say this constant is [DELTA]s (In further discussion [DELTA]s will be referred as the shift for Part 2). It includes the length of the curve Part 1 and the-length of the missing part from P to Q (Refer Fig 8).

Step 5: (Refer Fig 8) To calculate the shift As, a quadratic curve is fitted to both data set of Part 1 and Part 2 taking in one using least square method. The required shift is the arc length of the curve fitted between x=[x.sub.1] to x=[x.sub.2]. Let this curve be y=[f.sub.3](x). Now by integrating Equation 10 from x=[x.sub.1] to x=[x.sub.2] for y=[f.sub.3](x), the shift [DELTA]s can be found. After adding [DELTA]s to the s values of the Part 2 obtained in Step 3, new k-s values are obtained. Plot of these new k-s values are shown in Fig 9(b).

Step 6: (Refer Fig 9 (c)): This step computes the value of k and s for the missing part of the cross-section shown in Fig: 8 using the k-s estimated in step 5. Once the correct values of the k and s are known for missing part, using LINCE model missing x-y values can be estimated. The steps involved in the process are as follows

The procedure is as follows:

(a) Join the point A and B as shown in Fig: 9(c) by a line and then find out a line (Line 1) perpendicular to line AB. Assume that there exist point C on the Line 1 for which line segments AC and BC give the required values of k-s for the missing part of the curve.

(b) To search correct point C on Line1, binary search method is used which takes intersection of Line 1, Line 2 and intersection of Line1 and the tangent of part 1 at point A as boundary of the binary search. So the point C is searched between these boundary points and to check whether the obtained point is correct or not, each time x, y values from the k-s values are find out using the LINCE model.

(c) The values of x and y obtained in step 6(b) for point B are compared to the corresponding value of x, y for the original data of x-y.

(d) If the distance between these two points is nearly zero the algorithm terminates giving the final x-y for the missing part.

[FIGURE 10 OMITTED]

Fig: 10 Cross-section of Fig: 8 after reconstruction from left (Shown red) and right side (shown green)

Step 7: Repeat step 3 to 6 by taking point B (Fig 8)as starting point and estimate the missing point from the right side (Fig 10).

Step 8: Calculate the area under the part PQ (Fig 8) using the missing data estimated from both left and right side. Also find out the change in angle from point p to Q (Fig 8).

Step 9: The data sets (estimated from left and right) for which the area under curve is close to the change in the angle is used as the final missing data of the curve. (Area under a equal to the change in angle)

Projection Of Healed 2-D Data Points Back To 3-D

In this step 2-D healed data obtained in the previous section is projected back to 3-D. Consider the equation (31).

([x.sub.1]-o_i)[??]+([y.sub.1]-o_j)j+([z.sub.1]-o_k)[??]=[x'.sub.1] [??]+[y'.sub.1][??] Where ([x.sub.1], [y.sub.1], [z.sub.1]) is the point on 3-D and ([x.sub.1'], [y.sub.1']) is it's projection on 2-D plane taking origin at(o_i,o_j,o_k).

If (e1_i,e1_j, e1_k)and (e2_i, e2_j,e2_k) are the i, j and k component of the vector [??] and [??] then ([x.sub.1],[y.sub.1], [z.sub.1]) can be find as follows: [x.sub.1]=o_i+x * [e.sub.1]_i+[y.sup.*][e.sub.2]_i,[y.sub.1]=o_j+x*[e.sub.1_q]+y*[e.sub.2_j], [z.sub.1]=o_k+x*[e.sub.1]k+y*[e.sub.2_]k

Getting The Missed Data In Cross-Sections
 FindMissed_xy( )
 {
 while (there is cross section left)
 {
 ProjectTo2D (CrossSection (i);
 ReadXYDataOfBrokenCrossSectionalCurve( i);/* x, y */
 SeparateTwoParts (CrossSection(i) );/* [x.sub.1],[y.sub.1],
 [x.sub.2],[y.sub.z] */
 Get_ksForParts( CrossSection(i));/* [k.sub.1],[s.sub.1],
 [k'.sub.1],[s'.sub.2] */
 Fin dShift&New-ksFor2ndPart( );/* [k.sub.2],[s.sub.2] */
/*[x.sub.1], [y.sub.1], [x.sub.2], [y.sub.2] are known */
 FindInitia1Smid&Kmid() ;
/*[S.sub.mid], [K.sub.mid], [S.sub.low], [K.sub.low], [S.sub.high],
[K.sub.high] are known.
 get xy_for_missed_part([k.sub.1], [s.sub.1], [k.sub.2],
 [s.sub.2],[K.sub.mid],[S.sub.mid])
 while (y_f([x.sub.2] (1)) [not equal to] [y.sub.2])
 {if (y_f([x.sub.2] (1)) > [y.sub.2])
 K = ([K.sub.mid] + [K.sub.low])/2;
 S = ([S.sub.mid] + [S.sub.low])/2;
 [K.sub.high] = [K.sub.mid];
 [S.sub.high] = [S.sub.mid];
 [K.sub.mid] = k;
 [S.sub.mid] = s;
 else
 k = ([K.sub.mid] + [K.sub.high])/2;
 s = ([S.sub.mid] + [S.sub.high])/2;
 [K.sub.low] = [K.sub.mid];
 [S.sub.low] = [S.sub.mid];
 [K.sub.mid] = k;
 [S.sub.mid] = s;
 end;
 }/*end-while*/
 get_xy_for_missed_part([k.sub.1], [s.sub.1], [k.sub.2],
 [s.sub.2],[K.sub.mid],[S.sub.mid]); i++;
 }
 }

Let k and s values for the two parts are [k.sub.1],[s.sub.1],[k.sub.2],[s.sub.2] and the calculated values for the missed part are k', s'.

For a given curve in x-y, its arc length (s) and curvature (k) (i.e. k-s) plot can be obtained and vice-versa. In our approach this k-s theory is used. Here the k-s values for a given broken curve are calculated and using these k-s values the k-s values for the missing part is calculated. And finally the missing x-Y is calculated using the obtained K-S of the missing portion.

Case Study

Step1: Step1 takes the triangulated point cloud data file of an object and processes it for finding the holes. After finishing this step, all the holes in the data are identified. Following figures shows an object and detected hole in it.

[FIGURE 11 OMITTED]

Step2: After identifying the hole, each hole is processed separately for computing the cross-sections.

Step3: In the next step 3-D cross-sections are projected on the 2-D plane. Fig: 13(a) shows the projection of 3-D cross-sections x-y plane.

[FIGURE 12 OMITTED]

Step4: Step 4 heals the individual 2-D cross sections. The healed view of the cross-sections of Fig: 12(a) is shown in 12(b).

Step5. Healed data is projected back to 3-D and then it is triangulated using Delaunay triangulation. Triangulated point cloud

[FIGURE 13 OMITTED]

Results

Following figure shows the result obtained using our algorithm. In Fig 11(a) problem point cloud is shown and Fig 11(b) shows the point cloud after repairing it. Fig12 (a), (b) show the step involved in the healing process.

[FIGURE 14 OMITTED]

References

[1] Tavakkoli, S., Dhande, S.G., "Shape synthesis and optimization using Intrinsic Geometry" in Journal of Mechanical Design, December 1991, Vol. 113 pp. 379-386.

[2] Curless, B., Levoy, M., "A volumetric Method for Building Complex Models From Range Images", Proc. SIGGRAPH' 96, ACM, 1996.

[3] Curless, B., "New Method of surface reconstruction from range images", PhD desertion, Computer Science Dept., Stanford University, 1997.

[4] Wojciech, W., Buehler, C., Raskar, R., Gortler, S.J., McMillan, L., "Image Based Visual-Hulls", Proc. SIGGRAPH 2000, ACM, 2000.

[5] Davis, J., Marschner, S.R., Garr, M., Levoy, M., "Filling Holes in Complex Surfaces using Volumetric Diffusion". Proc. First International Symposium on 3D Data Processing, Visualization, Transmissions.

[6] Adams J. Alan, "The Intrinsic method for curve definition", US Naval Academy, Annapolis, Maryland, USA.

[7] Venketesh Jakka, "Shape optimization using intrinsic geometry and boundary elements method", Thesis submitted for Ph.D, Department of Mechanical Engg., IIT-Kanpur.

[8] H. Hoppe, T. Duchamp, J. McDonald, W.stuetzle. Surface reconstruction from unorganized points. In Computer Graphics (preceeding of ACM SIGGRAPH july 1992).

[9] H.Q. Dinh, G Slabaugh, and G. Turk. Reconstructing surfaces by antistropic basic functions. International conference on computer vision (ICCV) 2001.

[10] Amenti, M. Kamvysselis. A New Vornoi-based Surface Reconstruction Algorithm. SIGGRAPH'98 Proceedings, August, 1998.

[11] Fang, L. and D.Gossard Reconstruction of smoth parametric Surfaces from un organized data points. Curve AND surfaces in Computer vision and graphics 111, SPIE Vol- 1830, 1992.

[12] J. Wu and L.P. Kobbelt. Fast mesh decimation by multiple choice techniques. In vision, Modeling, Visulization 2002.

[13] J.C. Carr, R.K. Beatson, B.C. McCallum, W.R. Fright, T.J.Michell, Reconstruction and representation of 3D objects with radial basis functions. In proceeding of ACM GRAPHITE 2003.

[14] H. Zhao. and S. Osher. Visualization, analysis and Shape Reconstruction of Unorganized Data Set. In S. Osher And N. Paragios, editors, Geometric level set method in imaging, vision and graphics, Springer 2002

[15] S. Muraki. Volumetric Shape Description of Range Data using "blobby model". In computer graphics (preceeding of ACM SIGGRAPH 1991).

Amod Tiwari, V. Pathak, A. Chatterjee and S.G. Dhande

Cad Laboratory, Indian Institute of Technology, Kanpur, India

Dept. of Computer Science, HBTI, Kanpur,

Cad Lab, HT, Kanpur, India -208016

Cad Lab, IIT, Kanpur, India-208016

E-mails: amod@iitk.ac.in, vpathak@lycos.com, achat@iitk.ac.in, sgd@iitk.ac.in

Table 1
s 0.00 2.80 5.10 6.92 8.27
k 0.009 0.015 0.029 0.063 0.179

s 9.17 9.75 10.32 11.23 12.57
k 0.71 2.000 0.707 0.179 0.063

s 14.39 16.70 19.49
k 0.029 0.015 0.009

Table 2
x 2.00 3.00 2.50 3.00 3.50
y 0.00 - - - -
 2.75 5.00 6.75 8.00

x 4.00 4.50 5.00 5.50 6.00
y - - - - -
 8.75 9.00 8.75 8.00 6.75

x 7.00 7.50 8.00
y - - 0.00
 5.00 2.75