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
(Updated version of the paper presented on Graphicon 2010)

4. Missing surface field concept

In the beginning, note that A can be reconstructed only with some probability to be correct and the task of repairing a given ICADM has infinity number of acceptable solutions.

Let’s suppose that in an area containing a considered ICADM there is a field of some nature. It can be considered as an instance of the missing surface field (AF) introduced above, if it provides obtaining the following indices at each point of the area:

Of course, if Ψ = 0 (for example, at a point ∈ A) then | F | = 0 , Ω = 0 and | N | = 0 as well.

From the programming point of view the missing surface field can be represented by the following interface:

interface IMissingSurfaceField {

virtual void set_point(const VECTOR& point);

virtual real get_potential() const;

virtual void get_force(VECTOR& force) const;

virtual real get_attraction_indexl() const;

virtual void get_normal(VECTOR& normal) const;


Each instance of AF is implemented on the base of the corresponding missing surface estimation method. To determine the AF indices this method can require the corresponding set of extra parameters that is called the state context of the method.

Let’s call an instance of AF a complete AF, if it provides obtaining all the AF indices at a point or an incomplete AF otherwise. An AF can be implemented as a linear composition of several ( k ) other AFs with the corresponding weights (w):

missing surface field superposition property

Let’s call such AF a composite AF. Components of a complete composite AF can be incomplete AFs, with condition that obtaining each AF index is provided by at least one of its components.

Thus, the concept of AF provides joint using various missing surface estimation methods to achieve better repairing result. In general, the relationship between the concept of AF and the concept of bridges is similar like the relationship between dynamics and kinematics in physics. Using AF we can answer to the question: “what probability of that a correct bridge passes through a specified point and what the trajectory of this bridgeA” Presence of the force index allows considering AF as a force field and bridges as its force lines. But there is one fine point. From the definitions of the potential and the force vector it follows that the force vector should be collinear with the potential gradient (except several degenerated cases). But if in a used instance of AF the force vector and the potential value are determined by different estimation methods (for example, if this instance is a composite AF), then these vectors can be non-collinear in general. To keep adequate force line behavior in this situation, assume that a force line of AF is a curve such that at each point of it: all the AF indices are defined; the attraction factor isn’t less than a specified threshold; the tangent vector to the curve is directed in accordance with the force vector and has a restricted deviation from it in the plane defined by the force and the normal vectors to be as close as it is possible to the potential gradient vector.

missing surface field force line tracing step

From this definition it follows that any AF force line starts and ends at the corresponding boundary points of A. A force line can be iteratively traced from a specified boundary point until the corresponding opposite boundary point is reached. Each tracing iteration is performed in accordance with the following algorithm (F4.1).

At a specified beginning point (P0 ) the attraction factor value ( Ω0 ) is determined. If this value is less than a specified threshold then the tracing process is terminated as unsuccessful. Otherwise the force vector ( F0 ) is determined at the point. Using this vector and a specified tracing step ( s ) the first approximation of the next force line point ( P'1 ) is obtained. At this point the acting normal vector ( N'1 ) is determined. Using this vector and a specified deviation limit ( d ) the segment of the next point searching (P'10,P'11 ) is determined. The point of the potential maximum on this segment is assumed as the next force line point (P1).

In this way each force line can be traced independently on other ones. Moreover, the AF indices at a point can be determined independently on these indices at other points. It provides good parallelization abilities of implementations which use the AF concept.

In the end of this concept explanation let’s define the quality index ( q ) of an AF force line:

bridge quality

where L is the total force line length.

© Alexander Emelyanov, 2011-2016     
eXTReMe Tracker