Overview
Computer-aided geometric design and computer-aided manufacturing systems are used in numerous industries to design and create physical objects from digital models. However, the reverse problem, that of inferring a digital description from an existing physical object, has received much less attention. We refer to this problem as reverse-engineering or, more specifically, 3D scanning. There are various properties of a 3D object that one may be interested in recovering, including its shape, its color, and its material properties. Our solution addresses the problem of recovering 3D shape, also called surface reconstruction.
Decomposing a mesh into smaller pieces is helpful in many applications such as morphing, compression, simplification, 3D shape retrieval, collision detection, texture mapping and surface reconstruction. In general, decomposing a shape into appropriate simpler pieces is very useful in many areas of computation geometry and computer graphics.
A hard problem might become easier if only the objects at hand could be cut up into smaller and easier to handle sub-objects. In computational geometry, solid convex decomposition has been exhaustively investigated. Similarly, in image processing, image segmentation has been considered a fundamental problem, which is a necessary pre-processing step for many higher-level computer vision algorithms. The last few years have witnessed a growing interest in mesh decomposition for computer graphics applications.
Mesh decomposition benefits many applications. In metamorphosis, mesh decomposition is used for establishing a correspondence. Compression and simplification use decomposition for improving their compression rate. In 3D shape retrieval, a decomposition graph serves as a non-rigid invariant signature. In collision detection, decomposition facilitates the computation of bounding-volume hierarchies. In texture mapping, parameterization is applied to each component.
Several approaches have been discussed in the past for decomposing meshes. In convex decomposition schemes are proposed, where a patch is called convex if it lies entirely on the boundary of its convex hull. Convex decompositions are important for applications such as collision detection. However, small concavities in the objects result in over-segmentation, which might pose a problem for other applications. In watershed decomposition is described. In this case, a post-processing step resolves over-segmentation. One problem with the algorithm is the dependency on the exact triangulation of the model. Furthermore, the meaningful components, even planar ones, might get undesirably partitioned. Face clustering is proposed so that the clusters may be well approximated with planar elements. This algorithm is useful for simplification and radiosity, and less for applications seeking the meaningful components. Skeletonization and space sweep are used. Nice-looking results are achieved with this algorithm. However, smoothing effects might cause the disappearance of features for which it is impossible to get a decomposition. K-means based clustering algorithm is proposed. The meaningful components of the objects are found. However, the boundaries between the patches are often jagged and not always correct.
Modern industry is spending more and more efforts in the exploitation of 3D acquisition devices for diverse applications, including reverse engineering and medical imaging, while producers of precise acquisition tools such as recent laser scanners are focusing on improving the quality and flexibility of their products. As a consequence, we can now deal with huge volumes of rather precise data representing 3D shapes. In many contexts, however, it is important to understand the data acquired in order to fully exploit its potential. Unfortunately, in most cases the process of associating high level information to raw 3D data is hard to automate, and a time-consuming manual annotation work is required. In a reverse engineering scenario, for example, the user is typically required to track lines on the surface to subdivide it into simple regions which will be eventually approximated by fitting primitives. Sometimes such features can be detected automatically or semi-automatically, but in most cases the user is required to manually post-process the results to fill gaps or track features missed by the algorithm. In the case of free-form 3D models the approximating primitives are typically NURBS whose parameters are determined through an automatic fitting procedure. When the model is built by a given set of primitives, these primitives are typically fitted to the data.
Math Background
The goal of surface reconstruction can be stated as follows: Given a set of sample points (or surface-mesh) X assumed to lie on or near an unknown surface U, create a surface model S approximating U.
Our work examines the surface reconstruction problem in a general form that makes few assumptions about the sample X and the unknown surface U. In the general surface reconstruction problem we consider, the points X may be noisy, and no structure or other information is assumed within them. The surface U (assumed to be a manifold1) may have arbitrary topological type2, including boundaries, and may contain sharp features such the creases and corners present in the surface. Since the points X may be a noisy sampling, we do not attempt to interpolate them, but will instead find an approximating surface.
Of course, a surface reconstruction procedure cannot guarantee recovering U exactly, since it is only given information about U through a finite set of sample points. The reconstructed surface S should have the same topological type as U, and be everywhere close to U. In this work we will evaluate the reconstruction method by considering examples where the true underlying surface U is known and can be compared visually and quantitatively to the reconstruction.
Mesh hierarchical clustering
The algorithm proposed in our work is a variation of the hierarchical face clustering (HFC) method. The basic idea in the HFC approach is to merge neighboring triangles into representative clusters. Here a cluster is a connected set of triangles, not necessarily simply connected, which can be approximated by a simple primitive. For example, clusters are approximated by fitting planes computed through principal component analysis (PCA), and the cost of merging a set of triangles into a single representative cluster is the integral distance of its vertices from the fitting plane. The method produces a hierarchy which can be represented by a binary tree of clusters.
Approximation
Based on the existing binary tree of clusters, the library uses a recursive algorithm for approximating the clusters in the direction of reducing the size of the clusters.
With a pre-determined accuracy, the algorithm tries to approximate each cluster of each type of surface from the available list. If cluster can be approximated by surface, then the "division" of this cluster stops.
At this moment represented library has follow available list of approximation-surfaces:
Surface bounding
After receipt of parametric surfaces (approximating mesh’s clusters), they must be brought to the form when they are bounded by the curves connections between each other.
First, we tried to use the crossing surfaces for joint lines between adjacent surfaces. But this was not an effective solution. Therefore, at this stage of development, we decided to use the most simple in terms of implementation and effectiveness of the method of achieving a satisfactory outcome - to bounding the surfaces by polylines that were taken from clusters and projected onto a surfaces.
Blender-3d script
Based on represented library we have prepared the Python-script for work with Blender3d application. Now we deal with Blender3d version 2.49, but using another version should not be a problem.
Because Blender3d does not provide bounded surfaces we have prepared export geometry to the 3dm-file format version 4. It is a current native Rhino3d file format, besides there is free library OpenNURBS which provide access to it.
Script's logic. Step by step
- Script puts selected mesh from Blender3d to Library;
- Library reconstruct geometry surfaces
- Library export created surfaces to Rhino’s 3DM-file.
Start Blender
Import/Create some mesh
Mesh elements could be as triangles as quads.
Ensure that all neighbor mesh elements are connected via common vertices.
In Object-mode select required mesh-object (only one mesh-object could be processed in this version of library) and navigate to special script:
"File/Export/JAZZROS Surface Reconstructor".
Script will provide setup dialog where user could prepare and run process of surface reconstruction
Setup fields table
| Field name | Description |
| Use Analytics | On/Off using of the analytic surfaces for approximation. Spline surfaces will be processed anyway. Default value is Off. |
| Approx Tolerance | Permissible error value between approximated mesh and surfaces. Default value calculated runtime and is a half of minimum edge’s length in the processed mesh. |
| Geometry Tolerance | Permissible error value of elementary geometric operations. Default value is 1.e-6. |
Examples
Analytic surfaces
Spline surfaces
Conclusion
As a result of the research we have developed a software library that allows to perform surface reconstruction on the basis of the existing surface mesh. To perform this tasks, there are used methods of approximation of various types of surfaces, clustering of the surface mesh, curve projecting.
As an example, the use of the library, as well as to implement the possibility to test it, this library has been integrated into the application Blender3d.
More info and download Blender3d-addin You can here.
