Institute of Computing for Physics and Technology
Protvino, Moscow region, Russia
(Updated version of the paper presented on Graphicon 2010)
Creating CAD-models from scanned point clouds is widely used in reverse engineering, prototyping, and many other fields of science, culture and industry. But because of various physical and technical reasons such point cloud often contains regions with poor point density that leads to holes and other kinds of gaps in the obtained triangle mesh model. So, the problem of filling such holes and gaps by proper triangle mesh patches is very topical.
A majority of recently developed mesh repairing methods can be related to two groups. Methods of the first one (let’s call it the rebuilding group), in general, rebuild all a triangle mesh model to be repaired [TJ04, EBV05, ZJH07]. But it means that they ignore the most part of the previous work to create the model. Their cost of work has weak dependence on the model's damage degree that leads to inefficient processing little damaged models. Methods of the second group (let’s call it the template-warping group) use warping of a suitable template triangle mesh patch from a database to fill a specified model's gap [ACP03, PMG05, SKR06]. They show impressive results, but are usable only for models corresponding to their template databases. Also, to provide proper fitting a chosen template triangle mesh patch to the corresponding model's damaged region such methods require manual setting a certain number of point matches between them.
To repair a damaged triangle mesh surface we need to estimate in some way the behavior of the missing one. Such estimation method is the base of each existing triangle mesh repairing strategy. But in spite of that a damaged triangle mesh model contains diverse kinds of information about its missing surface (the existing one behavior, location of unused sampled points, a supposition of symmetry, etc) each estimation method uses only the corresponding restricted part of it. So, using this information as entirely as it is possible promises significantly increasing the mesh repairing quality with comparison of the existing methods. But it is obvious, that it can't be realized using only one even very smart missing surface estimation method. Thus, we have to develop a concept that provides simultaneously using several ones with possibility of these methods to supplement each other during the mesh repairing process to achieve a better result. The presented paper is a continuation of our previous works in the mesh repairing field [EM04, EAK08]. Unlike of them, in this paper the required concept is proposed. It is a general concept of an abstract field whose force lines approximate the missing surface of a triangle mesh model to be repaired. This field is called the missing surface field. The main idea of the concept is that the estimation result of a missing surface estimation method can be expressed via tension indices of this field. These tension indices created by various estimation methods can be summed to obtain the resulting ones. It provides the mentioned mutual supplementing of the methods. But simultaneously using several estimation methods significantly increases the mesh repairing cost. Only way to solution this cost problem is parallelization of the mesh repairing process using modern hardware. Its abilities allow using approaches and algorithms which even in a near past were considered extremely costly. A presented repairing method based on the missing surface field concept is an example of it. The method uses our previously developed missing surface estimation algorithms, which are supplemented by several new quite costly ones to increase the mesh repairing quality and robustness. But its perfomace indices remain at an acceptable level, because the most costly operations are parallelized. From the architecture point of view the presented method implementation provides the open architecture principle that allows do develop additional missing surface estimation units by remote teams.
The paper is organized in the following way. In the next three sections the theoretical basis of our mesh repairing method is described. In section 2 a formalization of supposed input is made. Then there is a description of two theoretical concepts. Section 3 explains the previously developed [EM04] concept of bridges. This concept considers reducing a heavily damaged triangle mesh model to a model that is easy to repair. In section 4 the missing surface field concept is introduced. In section 5 there is a description of two developed implementations of the missing surface field. An overview of the developed mesh repairing method in general is placed in section 6. Some results of testing the mesh repairing method implementation and a discussion are in sections 7, 8.