RHINOCEROS^{®} plug-in & standalone program

Triangle Mesh Completer Downloads

TMC Rhinoceros plugin Manual

TMC Standalone version Manual

Contact information

Frequently Asked Questions

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**)

Using the theoretical basis described above a repairing method has been developed and implemented. It uses a composite **A**F that currently consists of BI**A**F and PR**A**F. 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 **A**Fs) and in determining the set of used elementary sources of BI**A**F. The set of used elementary sources of PR**A**F 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.

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:

- the averaged inter-island span in a neighborhood of the island is taken as the characteristic value of
**A**discontinuity; - the set of considered BI
**A**F sources is defined as the set of all boundary points of all the other islands; - at all boundary points of the island the
**A**F attraction index is determined, and then the points of local maximums of the index are selected; - from the selected points the corresponding
**A**F 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.

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 BI**A**F. At the same points the local **A**F 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.

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 BI**A**F, the boundary point with the maximal value of the **A**F 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.

In the software realization of the method, the declared above open architecture principle, when each **A**F 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 **A**F 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 **A**F 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 **A**F indices should be calculated, is proportional to the total square of **A**. Assuming that the **A**F indices calculation cost at a point is constant as well, the cost behavior can be approximated by the following expression:

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 **A**F 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 **A**F 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 **A**F attraction index calculation along boundaries; the force line tracing.