Comparison between this method and typical implicit methods.

## 1. Introduction

Surface reconstruction is an interesting and challenging task in extensively applied fields including rapid prototype manufacturing, computer vision, virtual reality and computer aided design (CAD). A typical reconstruction procedure begins with scanning, in which the point data are sampled from physical objects by digitizing measurement systems (such as laser-range scanners and hand-held digitizers). And then, the point data are generated as a smooth, water-tight and proper resulting surface by a suitable reconstruction method. In industry the most difficulty comes from the defective samples that are subject to the noise, holes and overlapping regions. The defective samples are often unavoidable due to the sampling inaccuracy, scan mis-registration and accessibility constraints of scanning device. They often make most existing reconstruction methods not practical for engineering application because the oriented or neighbour information of points, which the most methods are highly based on, are hard to evaluate. For instance, many methods rely on consistent normals, or pose the demand on triangular meshes generated from point data. However, the holes and overlapping samples confuse the point’s neighbour relationship, some jagged, self-intersect regions could exist in the corresponding triangular mesh or the estimation of consistent normals becomes an ill-posed problem. Only a few methods need not such specific information, but they have to resort to some complex or time-consuming steps, like re-sampling, distance-computing, mesh-smooth or deformable models. Even if these methods can generate a water-tight resulting surface, the reasonableness of fitting overlapping samples and holes is not guaranteed. In fact, such issues, especially “bad-scanning” data, often lead long scanning time, massive manual work and poor model quality.

Given these challenges, this paper propose a novel surface reconstruction method that takes as input defective point clouds without any specific information and output a smooth and water-tight surface. The main idea is that (1) this technique is based on implicit function, because implicit reconstruction is convenient to guarantee a water-tight result; (2) the approach is indirect, two off-set surfaces are generated to best fit the point clouds instead of direct approximation. As shown in Fig.1 (1D situation for simple expression), the point clouds are represented as origin of coordinates (Fig. 1 (a)). The space is divided into inside part (positive axis in Fig. 1 (a)) and outside part (negative axis in Fig. 1 (a)). If the point clouds are defective, it is very hard to reconstruct final implicit function with

The dual relative functions are built on volumetric grids by extending some sophisticated 2D grey image processing algorithms into 3D space, including morphology operation and weighted vector median filter algorithm. The method needs not any specific information and also has the advantages that (1) the implementation needs not time-consuming steps, like computing distances between each point which is performed normally by most existing methods; (2) the dual gradient functions provide global constrains to the resulting surface, the holes could be filled smoothly and the overlapping samples could be fitted much reasonably. (3) the method can successfully construct “bad-scanning” point data which could not be handled by many methods. The reminder of the paper is organized as follows, after the previous works are reviewed and compared in section 2, the process and details of this method is described in section 3. To demonstrate the effectiveness, extensive numerical implementations are discussed in section 4. Finally, the conclusion and future work is summarized in section 5.

## 2. Related work

The previous algorithms of surface reconstruction can be generally classified into two categories: explicit methods and implicit methods. Most explicit methods employ Delaunay-triangulation or Voronoi diagrams, like alpha shapes (Edelsbrunner & Mücke 1994), crust method (Nina et al. 1998), triangular-sculpting (Jean-Daniel 1984), mesh growing (Li et al. 2009) and their developed version(Veltkamp 1995; Baining et al. 1997; Attali 1998; Amenta et al. 2000; Amenta et al. 2001; Yang et al. 2009). But the noise and overlapping samples could make the resulting surface jagged. Smoothing (Ravikrishna et al. 2004), refitting (e.g. (Chandrajit et al. 1995; Shen et al. 2005; Shen et al. 2009)) or blending (LA Piegl 1997) of subsequent processing are required.

In contrast, the implicit methods are much efficacious to infer topology of points, blend surface primitives, tolerate noise, and fill holes automatically. A popular algorithm is based on blending locally fitted implicit primitives, such as Radial basis functions (RBF) method (Carr et al. 2001; Greg & James 2002), multi-level partition of unity (MPU) method (Yutaka et al. 2003), products of univariate B-splines (Song & Jüttler 2009) and tri-cubic B-spline basis functions (Esteve et al. 2008) on voxelization. However they either need the consistent normals as aided information or the point clouds with fewer defective samples. The local primitives also include polynomial of point set surface (Alexa et al. 2001; Gael & Markus 2007) with moving least squares (MLS) approximation. MLS methods have to employ normal computation and projection operators, which could lead to low efficiency and need certain extra procedure to improve (Anders & Marc 2003; Marc & Anders 2004). Some methods need pre- or post-processing, like oriented estimation (Vanco & Brunnett 2004; David & Guido 2005), smooth operation (e.g. (Yukie et al. 2009)) or holes filling. For instance, the method proposed in (Davis et al. 2002) uses diffusion to fill holes on reconstructed surfaces. The approach essentially solves the homogeneous partial differential equation (PDE) given boundary conditions to create an implicit surface spanning boundaries. Poisson method (Michael et al. 2006) is also a PDE-based reconstruction algorithm with oriented point clouds. Several approaches use combinatorial structures, such as signed distance function and Voronoi diagram as (Boissonnat & Cazals 2002) (Hybrid method). But the normal information of point clouds is still required.

Only a few methods could demand little restriction on point data. Hoppe’s method (Hoppe et al. 1992) is a typical method of this category. It creates the object surface by locally fitting planes to generate a signed distance function and triangulate its zero-level set. The signed distance function can also be cumulated into volumetric grids as proposed in (Brian & Marc 1996). But the two methods are troubled by the noisy or sparse data, which make the connection relationship of these regions hard to confirm. The method proposed in (Alliez et al. 2007) employs Voronoi diagram to estimate the un-consistent normals and solves a generalized eigenvalue problem to construct resulting surface. However, it has to suffer from low computation efficiency. Level set method (Zhao et al. 2000), a typical deformable models, reconstructs the surface by solving corresponding level set equation defined on point data. It is a time-consuming method since it requires a process of re-initialization and needs updating all the nodes of compute grids in very time step. The reconstruction method also employ voting algorithm (Xie et al. 2004) to cluster points into local groups, which are then blended to produce a signed distance field using the modified Shepard’s method. But it needs to compute the medial axis transformation and perform an active contour growing process, like deformable models. The methods in (Esteve et al. 2005) proposes DMS operation on volumetric grids to fill holes by detecting the incursions to the interior of the surface and approximates them with a bounded maximum distance. It is an improvement of (Song & Jüttler 2009), but a post process has to be introduced to the low density data zones.

The typical implicit methods mentioned above are summarized in Table 1 with four respects that whether the methods need specific information and have the effectiveness of reducing noise, filling holes and merging overlapping samples. Although all the implicit methods can guarantee water-tight results that the holes could be filled, some methods (like Level set method) could not fill holes smoothly. Many methods have certain low efficient steps, like solving density matrix equation (e.g. RBF), projection procedure (e.g. MLS) and compute the distance function among all the point clouds for neighbor information. All the methods can reduce noise, but the effectiveness is not the same. For instance, MPU and Hoppe’s method could be influenced by noise more than others, if the noise is too much the resulting surface is still not smooth. All the methods do not address how to merge overlapping samples, especially the “bad-scanning” points, which is a common problem in practice.

Method name | Specific information | Reduce noise | Fill holes | Merge overlapping samples |

RBF (Carr et al. 2001; Greg & James 2002) | Yes | Yes | Yes | —— |

MPU (Yutaka et al. 2003) | Yes | Yes | Yes | —— |

MLS (Marc et al. 2001; Gael & Markus 2007) | No | Yes | Yes | —— |

Poisson method (Michael et al. 2006) | Yes | Yes | Yes | —— |

Hybrid method (Boissonnat & Cazals 2002) | Yes | Yes | Yes | —— |

Hoppe’s method (Hoppe et al. 1992) | No | Yes | Yes | —— |

Voronoi method (Alliez et al. 2007) | No | Yes | Yes | —— |

Level set method (Zhao et al. 2000) | No | Yes | Yes | —— |

Voting algorithm (Xie et al. 2004) | No | Yes | Yes | —— |

DMS method (Esteve et al. 2005) | No | Yes | Yes | —— |

This method | No | Yes | Yes | Yes |

Rather than constructing final surface directly, it is much easier to confirm the off-set surfaces of point clouds. Some methods have focused on the respect, like duplex fitting method (Liu & Wang 2009) or dual-RBF method (Lin et al. 2009). But they need the consistent normals for accurately fitting. Recently, some robust and efficient methods in other research areas (like image processing (Peng & Loftus 1998; Peng & Loftus 2001) and statistics (Roca-Pardinas et al. 2008)) have been introduced in reverse engineering. Inspired by the two ideas, this paper describes a novel reconstruction method using the dual off-set surface by extending morphology operation and weighted vector median filter algrithms. The comparison between this method and typical implicit methods is added in Table 1. This method provides a convenient and efficient manner for reconstruction and addresses the issues of overlapping points and “bad-scanning” samples.

## 3. Method description

The main process of the proposed method is illustrated in Fig.2. Let

by approximating the offset function

In the first step,

### 3.1. Generate off-set functions

The point data are first need divide into volumetric grids (voxelization). A best voxelization is that the size of voxel cooperates with the data density, where one grid only contains one point. As shown in Fig. 3, the black points represent defective points and the real line represents the reasonable resulting surface. If the point clouds are uniform, the voxel-building step is immediate. In industry, the uniform samples are common data because the original scanning data are numerous, a regular sampling for reduction are often needed before reconstruction. If the point data have a very irregular sampling density, the ratio, number of voxels which contain two or more points divided by the total number, should be calculated. If the valve is too high, the size of the volumetric grids is re-calculated by decreasing the length of grids. The most difficulty is how to guarantee off-surface,

To express simply, 2D uniform point clouds of arbitrary shape are designed (Fig.4 (a)). This shape contains lines, fillets and free curves according to the practical products. Some random noise, overlapping regions and holes are added. Fig.4 (b) shows the voxelization results. The node (white rectangles) of the grids within points (black points) is labeled as value 1 and other nodes are labeled as value -1. The dilation operation of morphology is then used to construct a rough crust (as shown in Fig. 4 (d)). Let

The best choice of

where

In this paper, it is generally set as median size

By the close crust, the inside and outside of the point data can be roughly separated. The inside part is then filled (see Fig. 4 (e)) by a simple flood-fill algorithm. It starts at a node (E.g. the middle gird node) known to be inside, those nodes accessible from initial node are labeled “inside”, and the remaining nodes are labeled “outside”. Each node of resulting image is therefore classified as lying inside the object (value 1) and outside/on the object (value -1). When sparse samples or large holes exist, the dilation should be executed for several times until a water-tight crust is constructed. The flood-fill step can check if the crust

is water-tight. If the crust is not close, the flood-fill operation could cover the whole space grids. Let

structuring element

The inside function

where

As shown in Fig.3 (b) the relative functions

Actually if many small details of points need to preserve,

### 3.2. Construct weighted gradient fields

The blurring results by Eq.(2) are shown in Fig. 6. It shows that noise influence still exist in some place.

Although the computation of Eq.(3) amplifies the noise influence, it is much suitable of weighted vector median filter to reduce the noise in function

The relationship between each vector, represented as

Usually,

where

The neighbor region

The details of the results demonstrate that the noise influence is effectively rejected according to the comparison of one noise region (on the right in Fig.7 (a) and Fig.7 (b)). The overlapping regions don’t lead any jagged errors or self-intersection. Actually, only one of the dual functions, either

### 3.3. Formulate and solve PDE

Based on the dual gradient functions, a minimal energy model is proposed. The gradient of resulting surface

where

The boundary condition is

To visualize the resulting surface, the level set valve of

where

The dual functions

## 4. Numerical examples and analysis

In this paper, the implementation employs PC CPU 2G Hz and 1G main RAM with the soft platform Matlab coupled with C++ API. To demonstrate the effectiveness and robustness, this paper takes the point clouds series sampled from a fan disk model (Fig. 9 (a)) as the examples. The point clouds (Fig. 9 (b)) are sampled with uniform density

This paper gives all the situations of the defective samples as shown in the left row of Fig.10, including sparse point clouds (Fig.10 (a)), point clouds with random noise (

The numerical details of all the examples about fan disk are shown in Table.2. The time complexity of the method generally includes three main components, dilation-erosion (

Point clouds of fan disk | Number of points | Grid resolutions | Compute time (s) | Average errors (mm) |

Original points | 100448 | 75.6355 | 0.014 | |

Sparse points | 10908 | 48.6522 | 0.031 | |

Noisy points | 100448 | 74.9853 | 0.045 | |

Points with holes | 99155 | 75.6654 | 0.016 | |

Points with overlapping | 125567 | 76.1203 | 0.035 | |

Hybrid defective samples | 124221 | 75.2368 | 0.046 |

In fact, the length of voxel could not follow the density of point clouds strictly, but if it is not set suitably, the resulting surface becomes over-fit or over-smooth cases. Two examples with “bad” grid size are shown in Fig. 12, which are both the resulting surface of noisy point clouds (Fig. 10 (c)). Fig. 12 (a) is the over-fit resulting example with grid

Beside the theoretical model of fan disk, this paper also adopts some practical examples since in real case the overlapping regions and holes are complicated. The following practical point clouds are scanned by the hand-held digitizer (type number: Cimcore Infinite Sc2.4). Fig.13 (a) shows the point clouds of a mechanical part. It is the example containing much overlapping samples (details labeled in circles). The resulting surface (Fig.13 (b)) demonstrates the overlapping regions can be reasonably fitted and smoothed. The next example is the point clouds of piston rod. In the middle bottom of Fig.14 (a) is the points within a section plane, where overlapping samples exist. The detail of a hole is shown in the lower right (Fig.14 (b)). In practice, the sparse points often exist in un-uniform point data. Fig.15 (a), point clouds of engine outtake ports from an automobile in real case, shows the situation. Because the density is not uniform, this paper could adopt the average density to decide the grid size. The result of smooth and water-tight surface is shown in Fig.15 (b).

Fig.16 shows the example of an ancient cup which contains much free-form details for preserve. Since the point clouds have no holes, just little noise but many overlapping samples due to multi-scanning, the non-uniform grids are employed. Detail 3 in Fig.16 is the little noisy part, Details 1 and details 2 are the overlapping regions because the cup bottom is hard to scan within only once. The point clouds are density enough, the structuring element

Because this method needs not any triangulation, the efficiency is highly improved more than the methods which need triangulation. The mechanical part (Fig. 13 (a)) is taken as an example for comparison. This paper uses Geomagic (version 8.0) which is a widely used commercial software utility in reverse engineering domain. It performs reconstruction based on building triangular meshes, as most conventional methods do. The result is shown in Fig. 17 (a). As the influence by the noise and non-uniform regions in the point clouds, it is difficult to construct a water-tight triangular mesh (Fig. 17 (a)). Some holes and rough place exist (Fig. 17 (b)). Thus, the artificial work of filling holes has to be performed (Fig. 17 (c)). The time of triangulation and reconstruction by this method is given in Table 3, where the time of Goemagic contains no artificial filling time. The comparison demonstrates that if the number of point clouds increase, or much noise exist, the triangulation time increases more than the time of surface reconstruction by this method.

Number of points | Time of triangulation (s) | Reconstruction time of this method (s) |

60000 | 30.3324 | —— |

120000 | 66.5633 | —— |

250000 | 81.9623 | —— |

500000 | 171.9932 | —— |

550000 | 180.6897 | 76.5367 |

The proposed method is especially useful to deal with the point clouds of “bad-scanning” like the example shown in Fig.18. It is a resin mould of engine intake ports from an automobile in real case (Fig. 18 (a)) and the original CAD model is shown in Fig.18 (b). Because the resin mould is too soft to fix, the point clouds by multi-scanning have larger errors of mis-registration (e.g. labeled by circle 1 in Fig. 18 (c)) than all examples above. The holes (e.g. labeled by circle 2 in Fig. 18 (c)) are much large and the noise appears everywhere. The points are much disadvantageous to obtain the specific information, especially triangular mesh with high quality. This paper gives the results by two typical methods based on Delaunay triangulation. Fig.18 (d) is the triangular mesh reconstructed by Raindrop Geomagic. The defective samples obviously influence the results: the holes need to be filled by other artificial work and the overlapping regions lead to some jagged triangles. Fig. 18 (e) is the resulting surface by power crust method (Amenta et al. 2001). Although the resulting surface is watertight, the surface is rugged and overlapping regions are self-intersect. The two results need some complex post-process. Fig. 18 (f) shows the resulting surface by level set method(Zhao et al. 2000), which need no specific information. The resulting surface is much better, but the surface is not smooth enough, especially the regions of holes. The final surface by this method is shown in Fig. 18 (f). This method guarantees a smooth and water-tight surface, holes are filled flatly and no self-intersections in overlapping samples. The “bad-scanning” samples need more dilation-erosion operations, the resulting surface is acceptable and convenient for certain post-process. But if the input data have too large holes or serious overlapping samples, the details of the resulting surface may be blurred due to too many dilation-erosion times.

The numerical details of the practical examples are shown in Table. 4. Since the point data of engine intake ports contain so many defective samples, the resulting surface has the largest average errors than other examples. Even if the ancient cup example has nearly 1 million points, the compute time is only 90 seconds.

Name of point clouds | Number of points | Grid resolution | Average errors (mm) |

Mechanical part | 537925 | 0.022 | |

Piston rod | 412847 | 0.021 | |

Engine outtake ports | 98175 | 0.035 | |

Ancient cup | 999944 | 0.019 | |

Engine intake ports | 154890 | 0.087 |

## 5. Conclusions and future work

This paper presents a novel implicit surface reconstruction method based on dual off-set gradient functions. Its core idea is to construct the dual off-set functions and generate the resulting surface indirectly. Through the extensive examples, it is indicated that the proposed method is robust to reconstruct discrete point sets, especially practical point data or “bad-scanning” data. The method need not any specify information, thus it can skip complex pre-process and make the reconstruction process much efficient. The morphology operation is based on set calculation so it is much faster to make off-set surfaces water-tight. The weighted vector median filter algorithm is extended into 3D space for reducing the noise influence and making the final surface much smooth. The dual relative functions construct a minimal crust surrounding the points from dual side, which can guarantee the holds and overlapping samples are fitted reasonably.

In future research, the problem of preserving details from “bad-scanning” points would be well-studied. Some advanced hierarchical data structures would be discussed for more efficiency implementation. The choice of structuring elements in morphology is a world classic problem in the field of image processing. Some improved structuring elements would be discussed in future work, such as combinational shape of structuring elements. The method would also be improved to handle some complex non-manifold point clouds. Some other image processing methods would also be extended in surface reconstruction, like some adaptive filter algorithms. To generate a suitable surface from defective point data, it is much important to employ industry prior design knowledge. With such prior but general knowledge, the resulting surface could be much reasonable than what are reconstructed only based on geometric information. The research would also focus on this respect.

## Acknowledgments

The research work is supported by Dongfang Electric Corporation Research & Develop Centre, Intelligent Equipment & Control Technology Institute and the Natural Science Fund of China (NSFC) (Projects No. 50835004 and 50625516).

## References

- 1.
Alexa M. et al. 2001 Point set surfaces, - 2.
Alliez P. et al. 2007 Voronoi-based variational reconstruction of unoriented point sets, - 3.
Amenta N. et al. 2000 A simple algorithm for homeomorphic surface reconstruction, - 4.
Amenta N. et al. 2001 The power crust, unions of balls, and the medial axis transform. - 5.
Anders A. Marc A. 2003 Approximating and intersecting surfaces from points, - 6.
Attali D. 1998 r-regular shape reconstruction from unorganized points. - 7.
Baining G. et al. 1997 Surface Reconstruction Using Alpha Shapes. - 8.
Barner K. E. et al. 2001 Fuzzy ordering theory and its use in filter generalization. - 9.
Boissonnat J. D. Cazals F. 2002 Smooth surface reconstruction via natural neighbour interpolation of distance functions. - 10.
Brian C. Marc L. 1996 A volumetric method for building complex models from range images, - 11.
Carr J. C. et al. 2001 Reconstruction and representation of 3D objects with radial basis functions, - 12.
Chandrajit L. B. et al. 1995 Automatic reconstruction of surfaces and scalar fields from 3D scans, - 13.
David B. Guido B. 2005 An extended concept of voxel neighborhoods for correct thinning in mesh segmentation, - 14.
Davis J. et al. 2002 Filling holes in complex surfaces using volumetric diffusion, - 15.
Edelsbrunner H. Mücke E. P. 1994 Three-dimensional alpha shapes. - 16.
Esteve J. et al. 2008 Piecewise algebraic surface computation and smoothing from a discrete model. - 17.
Esteve J. et al. 2005 Approximation of a Variable Density Cloud of Points by Shrinking a Discrete Membrane. - 18.
Gael G. Markus G. 2007 Algebraic point set surfaces, - 19.
Greg T. James F. O. b. 2002 Modelling with implicit surfaces that interpolate. - 20.
Hoppe H. et al. 1992 Surface reconstruction from unorganized points. - 21.
Jean-Daniel B. 1984 Geometric structures for three-dimensional shape representation. - 22.
Piegl L. A. W. T. 1997 - 23.
Li X. et al. 2009 On surface reconstruction: A priority driven approach. - 24.
Lin Y. et al. 2009 Dual-RBF based surface reconstruction. - 25.
Liu S. Wang C. C. L. 2009 Duplex fitting of zero-level and offset surfaces. - 26.
Maragos P. et al. 1996 - 27.
Marc A. Anders A. 2004 On normals and projection operators for surfaces defined by point sets, - 28.
Marc A. et al. 2001 Point set surfaces, - 29.
Michael K. et al. 2006 Poisson surface reconstruction, - 30.
Nie Y. Barner K. E. 2006 The fuzzy transformation and its applications in image processing. - 31.
Nina A. et al. 1998 A new Voronoi-based surface reconstruction algorithm, - 32.
Peng Q. Loftus M. 1998 A new approach to reverse engineering based on vision information. International Journal of Machine Tools and Manufacture,38 8 881 899 - 33.
Peng Q. Loftus M. 2001 Using image processing based on neural networks in reverse engineering. - 34.
Ravikrishna K. et al. 2004 Spectral surface reconstruction from noisy point clouds, - 35.
Roca-Pardinas J. et al. 2008 From laser point clouds to surfaces: Statistical nonparametric methods for three-dimensional reconstruction. - 36.
Shen J. et al. 2005 Accurate correction of surface noises of polygonal meshes. - 37.
Shen J. et al. 2009 Spectral moving removal of non-isolated surface outlier clusters. - 38.
Song X. Jüttler B. 2009 Modeling and 3D object reconstruction by implicitly defined surfaces with sharp features. - 39.
Vanco M. Brunnett G. 2004 Direct segmentation of algebraic models for reverse engineering. - 40.
Veltkamp R. C. 1995 Boundaries through Scattered Points of Unknown Density. - 41.
William E. L. Harvey E. C. 1987 Marching cubes: A high resolution 3D surface construction algorithm, - 42.
Xie P. et al. 2004 Surface Reconstruction of Noisy and Defective Data Sets, - 43.
Yang Z. et al. 2 EOF 17 EOF 2009 Adaptive triangular-mesh reconstruction by mean-curvature-based refinement from point clouds using a moving parabolic approximation. - 44.
Yukie N. et al. 2009 Smoothing of Partition of Unity Implicit Surfaces for Noise Robust Surface Reconstruction. - 45.
Yutaka O. et al. 2003 Multi-level partition of unity implicits. - 46.
Zhao H. K. et al. 2000 Implicit and Nonparametric Shape Reconstruction from Unorganized Data Using a Variational Level Set Method.