Triangle Mesh Completer by Alexander Emelyanov - Mesh Repairing Tools

Triangle Mesh Completer


RHINOCEROS® plug-in & standalone program

Advanced Mesh Repairing. Theory

Alexander Emelyanov,
Institute of Computing for Physics and Technology
Protvino, Moscow region, Russia
ae@ae3d.ru
(Updated version of the paper presented on Graphicon 2010)



6. Overview of the implemented method

Using the theoretical basis described above a repairing method has been developed and implemented. It uses a composite AF that currently consists of BIAF and PRAF. The basic steps of the method are described in the next three subsections. These steps differ from each other in determining the characteristic value of A discontinuity (it used to adjust the distance function parameters of the AFs) and in determining the set of used elementary sources of BIAF. The set of used elementary sources of PRAF for these steps is the same and consists of all free points of a processed ICADM.

In the last subsection the basic properties of the method are considered.

6.1 Connection of islands

In the input of this step an ICADM of class ICM3 is assumed. Initially, for each island a set of bridges connecting it with the other ones is obtained in the following sequence:

  1. the averaged inter-island span in a neighborhood of the island is taken as the characteristic value of A discontinuity;
  2. the set of considered BIAF sources is defined as the set of all boundary points of all the other islands;
  3. at all boundary points of the island the AF attraction index is determined, and then the points of local maximums of the index are selected;
  4. from the selected points the corresponding AF force lines are traced, these force lines are considered as the required bridges.

After processing all the islands, the total graph of connections is obtained. In general case this graph can contain topologically conflicting bridges. Each detected conflict situation is resolved by eliminating the necessary number of bridges with the least values of the force line quality (see E4.2).

Then, in accordance with the concept of bridges, the corresponding set of holes is extracted from the graph.

6.2 Detecting and processing lost “tunnels”

If initially, or after the previous step, the processed ICADM can be referred to class ICMT and a case of this class is admitted a priori, then this step is performed. The used algorithm allows detecting and correctly processing an internal “tunnel” if it is represented by the corresponding pair of non-trivial boundaries.

At this step the averaged distance between all non-trivial boundaries is taken as the characteristic value of A discontinuity. All points of these boundaries are considered as sources of BIAF. At the same points the local AF attraction index is determined and then from the points of local maximums of the index the corresponding force lines are traced. When it is done, two of the boundaries are considered connected by an internal “tunnel” if two or more force lines connect them and each of these force lines has the quality higher than the quality of any other force line of these boundaries. In this case these force lines are considered as bridges. The finally obtained graph of connections is processed in the same way like in the previous step.

6.3 Decomposition of complicated holes

At this step the input consists of one coherent island with one or several complicated holes. Each of them is processed separately from other ones. Initially, the averaged size of the processed hole is taken as the characteristic value of A discontinuity. Then, considering all boundary points of the hole as sources of BIAF, the boundary point with the maximal value of the AF attraction index is determined. From this point the corresponding force line is traced. It splits the hole to two new ones. This algorithm is recursively applied until a set of only trivial holes is obtained.

6.4 General properties

In the software realization of the method, the declared above open architecture principle, when each AF instance interacts with the system kernel via the interface introduced in section 4, is implemented. It gives to the system flexibility and extensibility;

also it allows developing new AF implementations by remote teams of programmers.

Because the presented method works directly in regions of damage, its cost does not essentially depend on the square of A and as a consequence on the number of edges, triangles and points in the input. But it has a great dependence on the square and the topology of A. Such dependence can’t be expressed by one simple cost equation, at the same time a rough approximation can be obtained. Let’s use the fact that traced AF force lines finally forms a mesh of trivial holes (F3.3). Assuming for simplicity that all the force lines are traced with the same step and all the trivial holes have the same square we can conclude that the number of points, at which the AF indices should be calculated, is proportional to the total square of A. Assuming that the AF indices calculation cost at a point is constant as well, the cost behavior can be approximated by the following expression:

triangle mesh repairing cost behavior

where k is a positive constant.

It is the same dependence, like in our previous works [EM04, EAK08]. But unlike of them the actual cost value is essentially greater, because the presented method uses the quite costly algorithms described above. For example, the used force line tracing algorithm, when at each step the AF potential maximum is found, is 6-8 times costlier than the previous one. Modeling the shielding property (see 5.1) and the open architecture implementation increase the cost as well.

Fortunately, the base AF concept has good parallelization potential that allows compensating the mentioned above cost increasing. In the current implementation the following most costly operations are parallelized: the AF attraction index calculation along boundaries; the force line tracing.

© Alexander Emelyanov, 2011-2016     
eXTReMe Tracker