=Paper=
{{Paper
|id=Vol-2608/paper54
|storemode=property
|title=Algorithm for fixing singular defects of polygon meshes based on half-edge data structure
|pdfUrl=https://ceur-ws.org/Vol-2608/paper54.pdf
|volume=Vol-2608
|authors=Danylo Sovhelia,Natalya Sokolova
|dblpUrl=https://dblp.org/rec/conf/cmis/SovheliaS20
}}
==Algorithm for fixing singular defects of polygon meshes based on half-edge data structure==
https://ceur-ws.org/Vol-2608/paper54.pdf
Algorithm for fixing singular defects of polygon meshes
based on Half-Edge Data structure
Danylo Shovhelia[0000-0003-0571-0899], Natalya Sоkоlоvа [0000-0002-2207-1884]
Oles Honchar Dnipro National University, Gagarina av., 72, Dnipro, 49005, Ukraine
dshovhelia@gmail.com, n.olegowna@gmail.com
Abstract. The problem of the occurrence of singular defects in the creation of
3D models in polygonal meshes due to the peculiarities of the Half-Edge Data
structure is considered. An algorithm for detecting defects in a model based on
half-edge structures and mesh recovery is proposed. Software implementation
of the method allows to create a model based on the source data without the
formation of new defects. Appropriate tools have been developed for bench-
marking, and results are presented.
Keywords. 3D printing, 3D models, polygonal mesh, singular defect, Half-
Edge Data Structure, non-manifold elements.
1 Introduction
Additive Technologies (for example, three-dimensional or 3D printing) is a form of
additive manufacturing technology where a three-dimensional object is created by
imposing consecutive layers of material (printing, growing) according to the digital
model. Digital 3D models are key components of this technology, and each specific
program that deals with a 3D geometry has its quality requirements that limit the class
of acceptable and supported models. In most cases, visualization is just one of many
steps that make up the life cycle of a digital 3D model. 3D models need to be ana-
lyzed and processed using advanced algorithms, which usually have strict require-
ments for the quality and integrity of their input data. Adapting imperfect 3D models
to these requirements is important.
Polygonal and triangular meshes are now a de facto standard in most 3D modeling
areas. Polygonal meshes are directly supported by accelerated graphics equipment,
which facilitated their expansion and use [1-4]. Most graphic formats commonly used
for 3D model sharing (OFF, VRML, PLY) encode the surface mesh using indexed
sets of faces. However, these file formats do not guarantee the proper simplicity com-
plex, since they can easily encode non-manifolds and/or non-oriented polygons, iso-
lated elements, and several other elements that are often the source of problems.
Copyright © 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
2 Formal problem statement
3D printing is one of the fastest growing technologies that captured many spheres
of human life and has become their indispensable core, in particular, such as architec-
ture, medicine and mechanical engineering. Models is a basis for 3D printing. Primi-
tive models cannot display the whole variety of printed products, and modeling of
more complex models based on a simplest one can cause a number of defects. The
latter, may lead to models that could not exist in the real world. The urgent issue is the
timely detection of such defects, development of algorithms for model fixation, meth-
ods restoration of polygonal meshes and their software implementation in existing
tools.
3 Literature review
3.1 Defects in the representation of three-dimensional models
Specialized computer-aided design (CAD) systems are used to model the objects,
which are based on a particular internal structure of the model representation. Move
an object from one system to another or changing their representation can be com-
pletely unpredictable, which leads to the appearance of topological defects (defects of
local connections) and consequently to geometric defects [1,5], without any possibil-
ity of their identification. Three-dimensional scanning of real-world objects can be
accompanied by many defects, which are for the most part classified as geometric [6].
Such situations are unacceptable because they lead to a violation of the integrity of
the printed object.
1. Local connectivity where a set of triangular polygons encoded in a file does not
form a combinatorial manifold simplex complex. Correcting such problems de-
pends largely on learning the available input geometry and most often involves
creating new geometry. The following defects include [1,5]:
Isolated Vertices where a vertex that is not an element of any other simplex of a
mesh. Such vertices can often be simply ignored and if necessary, be removed very
easily. Many existing tools provide manual or automatic procedures for this.
Dangling Edges where edges that do not have incident triangles. A common strat-
egy is to simply ignore or remove the edges. Edges may also be used by some ap-
proaches as a useful source of information about the assumed basic geometry to re-
cover.
Singular (complex, non-manifold) Edges where more than two polygons have a
common edge. Since the condition of the combinatorial set is required in several ap-
plication contexts, there is a strong call for solutions that transform such a mesh into a
combinatorial manifold. This problem is not as easy to solve as in a case of isolated
vertices or edges because of the inherent ambiguity.
Singular Vertices where the vertex is not manifold in the topology of the abstract
simplicial complex. Detecting such vertices is more difficult than detecting singular
edges. If it is very important to calculate the number of incident triangles for the edg-
es, then it is necessary to calculate the number of connected components in the vicin-
ity for the vertices. Solutions to this kind of problem are usually based on the duplica-
tion of one vertex, after which each component of the neighborhood should be re-
assigned to one of the copies.
2. Global Topology (general topological characteristics of the surface, including the
number connected components, the genus, the number of cavities and orientation)
[1,5]:
Topological Noise [7] represents a situation when reconstructing a surface, starting
with point clouds or when removing an isosurface from 3D images, tiny "tunnels" that
were not present in the original object are introduced into the constructed digital mod-
el due to the effects of overlay or discrete noise basic data.
Inconsistent Orientation where the order of the sequences of vertex indices indi-
cates the orientation of the polygon. To ensure full visibility across all imaging sys-
tems, it is necessary to provide a unique consistent orientation for all mesh polygons
by selecting a seed surface and extending the orientation to adjacent faces. However,
some configurations are essentially not oriented, which means that, the system must
necessarily cut the surface for consistent orientation.
3. Geometric defects where the geometric realization of an abstract simplicial com-
plex is considered. Geometric defects also relate to the characterized position of
the vertices. This family is further complicated by the need to handle continuous
coordinates and intersections, which (for efficiency reasons) must be expressed and
processed with finite precision arithmetic, which usually leads to reliability prob-
lems. The geometric effects include the following [1,5]:
Surface Holes and Gaps. When scanning an object using standard scanners and de-
signing a surface using standard CAD systems, adjacent patches are separated by
unwanted holes due to the features of the equipment and displacement of tessellation
patches, which must be compensated. Such steps are known as closing the gap (the
area between two triangulated surface spots that must be permanently connected but
not associated with the gap) and filling the holes (undesirably missing part of the
surface in the triangulated patch). The main difference between the two cases is the
connection of their boundaries. The boundary of the gap usually consists of two (or
more) disconnected chains of edges. The border of the hole usually consists of one or
more closed edge loops.
Degenerate Elements. Degenerate triangles are zero-area triangles, and they are a
source of many problems for many applications, since many useful objects (ordinary
vectors, circles, bar-centric coordinates) cannot be calculated on such triangles. Ap-
plications that specialize in calculating the above objects (for example, finite element
analysis or Delaunay refinement implemented in the freely available Triangle package
[5,8]) fail when the mesh contains degenerate triangles or becomes unstable when it
contains nearly degenerate triangles.
Self-intersections. In several application contexts, it is assumed that the input mesh
represents the boundary of some solid volume, and therefore cannot self-intersect.
Although it is relatively easy to test the mesh for self-intersections, solving them is a
difficult problem due to inherent ambiguities. Self-intersecting meshes are typically
generated by multi-patch mosaics, mesh deformation, assembly of many parts without
care, or by combining trays reconstructed from partial scanning of a 3D object. Due to
ambiguity, there is no common strategy for solving this problem.
Sharp Feature Chamfering. Most restoration and contouring methods limit each
sample or vertex to a specific line or curve, the position of which is completely de-
termined by the pre-set pattern. In most cases, such a pattern cannot be adjusted so
that it coincides with the sharp edges and angles of the model and, therefore, virtually
none of the specimens rests on such sharp features. This leads to the imposition of
artifacts, where sharp edges and angles of the original shape are removed by the sam-
pling process and replaced by unevenly triangulated chamfers, which in turn leads to
poor visualization and high distortion;
Data Noise. Each scan tool has a finite precision. Thus, the output of the sample
model contains additive noise from different sources. The main problem is to remove
noise while maintaining the morphology of the main sampling surface, with particular
attention to high-frequency details such as angles, edges, or other sharp features.
3.2 Methods of mesh repairing
Non-manifold meshes, which contain singular edges and vertices, can be classified
into two classes: those that bind so-called regular sets and those that do not have regu-
lar sets [5, 9]. The former are still well defined by the continuous volume, down to the
singular contacts on the non-manifold edges and vertices. Singular edges and vertices
are often deliberately created to avoid duplication of vertices and for the continued
need to hold these duplicate vertices sequentially. In a general case (for example,
meshes containing singular edges with an odd number of incident faces), which usu-
ally has ambiguities, specialized or global methods are required.
The two algorithms proposed by Gueziec at Al. [10, 11] transform meshes that re-
strict non-manifold regular sets into sets of combinatorially manifold meshes. Strictly
speaking, a closed-mesh mesh can be a regular set only if it has no self-intersections.
However, they are only bonded and therefore can also handle self-intersecting mesh-
es. After identifying a singular edge having 2n incident faces, it splits into n multi-
row edges having 2 faces each. Such representation of marginal diversity may still
contain separate vertices that must be identified and duplicated.
Rossignac and Cardoze [12] proposed a strategy for performing the minimum
number of such duplications. The approach introduces additional operations to merge
the edge edges of the mesh section along singular edges or by simply joining the bor-
der (clamping) or stitching adjacent curves, and thus reducing the number of locking
connected components.
Extensions of these works have been studied for higher dimensions by De Floriani
et al. [13-16], who propose to retain some of the innocuous features as long as the
model remains a initial quasi-manifold model, which is a weaker condition than a
manifold one. For the individual case of three dimensions, Attene [1] performed a
detailed analysis of existing algorithms of restoring all types of defects for polygonal
meshes, according to efficiency and proposed two algorithms for removing features
from tetrahedral meshes. One algorithm offers combinatorial manifolds and the other
prioritizes geometry. Any non-degenerate mesh that restricts regular recruitment can
be tetrahedroned and processed.
Wang Zengbo [17] presents algorithms for the rapid recovery of triangular meshes
imported from STL files.
Jixin Tan and Jianxun Chen [18] describe generalized algorithms for eliminating
singular defects. The latter approach involves splitting models connected by singular
vertices or complex edges into two independent objects.
However, it should be kept in mind that due to topology, a half-edge data structure,
does not allow the creation of singular defects, which leads to the formation of defects
of another type and the inability to determine the initial ones.
3.3 Typical structures for description three-dimensional models
Objects created using polygonal meshes should store different types of elements
such as vertices, edges, faces, polygons and surfaces. Polygonal meshes can be repre-
sented in a variety of ways using different methods of storing vertices, edges, and
faces. These include the following [5]:
• List of faces: description of faces is made by pointers to the list of vertices.
• Winged View: Each point of an edge points to two vertices, two faces, and four
(clockwise and anti-clockwise) edges to which it belongs. Large memory is required
for storing mesh description data.
• Half-edged meshes: the method is similar to a winged view, except that only half
of the edge is traversed.
• Four-edged meshes that hold edges, half-edges, and vertices without any indica-
tion of polygons. Polygons are not explicitly expressed in the description, and can be
calculated bypassing the structure. Memory requirements are similar to half-edge
meshes.
• A table of angles that stores vertices in a predefined table, and the bypass of the
table implicitly specifies polygons. Table of angels do not feed the mesh completely.
Most meshes require multiple corner tables (triangles).
• Vertex description: Only vertices that point to other vertices are represented. The
edge and edge information are not explicit in this view. However, the simplicity of the
presentation allows to perform many effective operations over the mesh.
Each presentation has its advantages and disadvantages.
The choice of data structure is determined by the application, required perform-
ance, size of the data, and operations that to be performed. Compact, simple structures
are required for hardware rendering. Low-end APIs such as DirectX and OpenGL
usually include a table of angles (triangles).
Half-Edge Data structure is based on a principle of splitting an edge into two mul-
tidirectional halves. Each of these halves is a basic element and stores a topology in
itself, which allows to manipulate a polygonal mesh. According to the definition of
this structure, a model should not contain singular vertices and/or complex edges,
since creating a connection between such elements is impossible with a basic interpre-
tation [5].
Singular defects often occur in the following situations:
1. The process of folding vertices.
2. Boolean operations on objects.
3. Errors of tessellation algorithms (faceting of a solid-state model).
4. Changing the structure of the presentation from a more primitive (vertex repre-
sentation) to a more complex (half-edge data structure).
5. Duplicate elimination in trivial data structures.
One common representation of data structures in CAD systems is the spreadsheet,
which has advantages in terms of memory savings and ease of rendering. Such an
implementation is presented in OpenMesh [19]. However, due to the lack of connec-
tion in such a structure, it can contain defects of any type, and attempting to create
such a model in a half-edge structure can lead to its destruction. Each polygon con-
sists of half-edges and contains so-called pointers to half-edges from the general table
structure.
4 An algorithm for creating a polygon model in OpenMesh
The development team of OpenMesh uses the following algorithm to create a pol-
ygon model:
1. For a set of triple coordinates:
1.1. Add three coordinates to the structure.
1.2. Return the unique triangle ID.
2. From a set of identifiers to create a polygon:
2.1. For a pair of vertex ID, check that there is a half-edge associated with that
vertex, if so proceed to 2.4.
2.2. If a half-edge has not yet been created, then create one and add it to the face.
2.3. Select the next pair of vertices, if any, and return to item 2.1, otherwise go
to item 2.7.
2.4. Check whether a given half-edge belongs to the face. If not, return to 2.2.
2.5. Check for the opposite half-edge of the face. If not, return to item 2.2.
2.6. Record an attempt to attach a new polygon to a pair of connected polygons
or separate it completely.
2.7. Add the triangle ID to the data structure.
3. Return the generated polygon ID.
The disadvantage of this algorithm is that it is capable of replacing one defect with
another. Instead of creating a singular edge, the resulting model will contain a hole
and an island polygon. Such polygons can be evaluated as garbage and removed along
with isolated vertices and hanging edges. In the end, further processing of such a
model may lead to unexpected results.
It is important to consider that the sequence of polygon creation plays a large role
in this algorithm.
5 Modified algorithm for model polygon creation
One of the peculiarities of implementing a half-edge data structure in Open-Mesh
is the presence of edges that allow iterating over pairs of half-edges, although the
edges themselves do not exist. If the general method requires counting the falling
edges of a selected edge, is it possible to create an edge that will not be a structural
unit of the model but will retain a link between all contenders? In other words, it is a
bridge that connects all contenders for a given edge. It is an edge-bridge that stores
the pointers of each half-edge attached to it.
Suppose that there is an edge between two points along which two half-edges pass
(Fig. 1). In that case, the edge knows about its pair of half-edges, or a contender con-
tainer consists of 2 half-edges. In this case, when trying to add one more half-edge, ie,
to combine more than two polygons in one edge, the outer half-edge of the attached
polygon will be added to the claim container (Fig. 2).
Fig. 1. Modified representation of edges
Fig. 2. Bonding of pairs
Given the fact that each half-edge can have only one partner, in that case, every 2n
contender will form n pairs. From all of the above, the following changes can made to
the algorithm of creating a polygon:
1. For a set of triple coordinates:
1.1. Add three coordinates to the structure.
1.2. Return a unique vertex ID.
2. Create a polygon from a set of vertex identifiers:
2.1. For a pair of vertex identifiers, to check if there is a half-edge associated
with that vertex, if so proceed to 2.4.
2.2. If a half-edge has not yet been created, then create one and add it to the face.
2.3. Select the next pair of vertices, if any, and go to item 2.1, otherwise go to
item 2.7.
2.4. Check whether the given half-edge belongs to the face: if not, go to item
2.2.
2.5. Check if the opposite half-edge contains the faces: if not, go to item 2.2.
2.6. Invite a container of contenders for a given half-edge.
2.7. If the number of contenders is not even, then find a pair by method of elimi-
nation of already created pairs; otherwise, add the ID to a container. Go back to
item 2.3.
2.8. Add the triangle ID to the data structure.
3. Return the generated polygon ID.
6 Implementation of the modified algorithm
Object-oriented bridge implementation based on modified algorithm and imple-
mentation of this bridge in OpenMesh allows to eliminate defects in models based on
half-edge data structure [20]. Many algorithms for preliminary analysis of meshes, at
the stage of determining the integrity of the model, as well as cleaning it from debris,
can lead to holes.
Let's look at the example of building an OpenMesh model. The original model was
created in Solid Works 2018 SP3 (Fig.3,a). As can be seen in a figure, the model has
stiffeners. The model loaded as a Triangle Soup model does not carry any information
other than visual shape and cannot be used for 3D printing (Fig.3,b.).
Stiffener
a) b)
Fig. 3. Model # 1. a) Created in Solid Works 2018 SP3; b) 3D printing model loaded as Trian-
gle Soup
When trying to create a model using OpenMesh, defects arise that are unacceptable
with 3D printing (Fig.4).
Fig. 4. A model that uses a basic Half-Edge Data Structure OpenMesh implementation.
This model is non-manifold and contains two types of defects (Singular Edges &
Singular Vertices) created by Stiffener. The holes are highlighted in green (deter-
mined by the boundary edges). Because the base implementation does not support
communication between more than two faces through one edge, all subsequent "con-
tenders" for this edge will be disconnected with duplication of the corresponding
points. The final analysis of a loaded model shows that the number of objects is great-
er than one, which is also inadmissible in some environments.
Using the modified algorithm based on the preservation of the connection between
non-manifold elements gives the following result (Fig.5):
Fig. 5. Implementation of the approach with keeping the connection between non-manifold
elements (Singular Edges are highlighted in red)
Another illustration compare the implementation of basic and modified algorithms.
a) b)
Fig. 6. Model # 2. a) Created in Solid Works 2018 SP3; b) Model for 3D printing, loaded as a
Triangle Soup.
This model consists of 24 triangular prisms. In the absence of communication be-
tween all the elements, it can be exploded into 24 separate parts respectively (Fig.7).
Fig. 7. Splitting the model into separate prisms in absence of communication between the ele-
ments
One solution to this problem is to replace singular defects with separate faces. Af-
ter the orphaned triangles are removed, the result shown in Fig.8.
Based on the specifics of the model, about 1/8 faces will be removed. After loading
this kind of object, it becomes impossible to trace the original source of data loss.
Fig. 8. Substitution of Singular Defects by Separate Edges (highlighted in green the boundary
edges)
Using the algorithm of preserving the connection between the non-manifold faces
and the software implementation of the bridge, the following results (Fig.9):
Fig. 9. Removal of singular defects by maintaining the connection between non-manifold faces
(singular edges are red highlighted)
Keeping the connection between singular elements allows to load the original data
without loss, as well as provide the necessary information to determine the defects of
non-manifold edges and vertices.
7 Conclusion
A basic algorithm of the polygon creation implemented in OpenMesh leads to the
destruction of the model if there is an attempt to create singular elements.
The newly proposed modified algorithm allows the connection between singular
elements to be identified, and the overall structure of the model is preserve.
The advantage of the proposed algorithm is the simplicity and expansion of mesh
recovery capabilities based on the earlier discussed algorithms.
The result of the proposed approach is the preservation of the connection in the to-
pology during the formation of defects on polygonal meshes, which will enable detec-
tion and will make it possible to carry out various kinds of manipulations at the same
time.
The disadvantage of this approach is in high memory requirements for storing
links.
Further research will be devoted to improvement of the algorithm to ensure com-
munication between all topological elements and its software implementation.
References
1. Atenne, M., Campen, M., Kobbelt, L.: Polygon Mesh Repairing: An Application Perspec-
tive : ACM Computing Surveys (scheduled to appear), 45(2):1-38. (2013).
doi:10.1145/2431211.2431214
2. Lyon, M., Campen, M., Bommes, D., Kobbelt, L.: Parametrization Quantization with Free
Boundariesfor Trimmed Quad Meshing. ACM Transactions on Graphics (TOG), Vol. 38,
Issue 4, Article No.: 51, pp 1–14 (2019). doi:10.1145/3306346.3323019 51:1-51:14.
3. Trettner1and, P., Kobbelt, L. Fast and Robust QEF Minimization using Probabilistic
Quadrics. EUROGRAPHICS 2020 Volume 39 , Number 2 (2020).
4. Schmidt, P., Born, J., Campen, M., Kobbelt, L.: Distortion-Minimizing Injective Maps Be-
tween Surfaces ACM Trans. Graph., Vol. 38, No. 6, Art. No.: 156, pp 1–15 (2019).
doi:10.1145/3355089.3356519
5. Botsch, M., Kobbelt, L. Pauly, M., Alliez,P., L´evy B.: Polygon Mesh A K Peters, Ltd.
Natick, Massachusetts, (2010)
6. Ju, T.: Fixing Geometric Errors on Polygonal Models: A Survey. J. Comput. Sci. Technol.
24, 19–29 (2009). doi:10.1007/s11390-009-9206-7
7. Guskov, I., Wood, Z. 2001. Topological noise removal. GI '01: Proceedings of Graphics
Interface 2001, pp.19–26, (2001). doi: 10.20380/GI2001.03
8. Shewchuk,J.R. Triangle:Engineering a 2D Quality Mesh Generator and Delaunay Triangu-
lator. WACG 1996: Applied Computational Geometry Towards Geometric Engineering pp
203-222 (1996). doi:10.1007/BFb0014497
9. Ying, L., Zorin, D.N.: Nonmanifold subdivision. VIS '01: Proceedings of the conference
on Visualization, pp.325–332, (2001)
10. Gueziec, A., Taubin, G., Lazarus, F., Horn, B.: Cutting and Stitching: Converting Sets of
Polygons to Manifold Surfaces. IEEE TRANSACTIONS ON VISUALIZATION AND
COMPUTER GRAPHICS, Vol. 7, NO. 2,pp. 136-151(2001)
11. Gueziec, A., Taubin, G., Lazarus, F., Horn, B.: Converting sets of polygons to manifold
surfaces by cutting and stitching. SIGGRAPH '98: ACM SIGGRAPH 98 (1998).
doi:10.1145/280953.281628
12. Rossignac, J., Cardoze, D.: Matchmaker: manifold BReps for non-manifold r-sets. SMA
'99: Proceedings of the fifth ACM symposium on Solid modeling and applications, pp. 31–
41 (1999). doi:10.1145/304012.304016
13. De Floriani, L., Hui, A.: A Scalable Data Structure for Three-dimensional Non-manifold
Objects. In: Proc, of the Symp. on Geom. Proc., pp. 72-82 (2003)
14. De Floriani, L., Magillo, P., Puppo, E., Sobrero, D.: A Multi-resolution Topological Rep-
resentation for Non-manifold Meshes. CAD Jour. 36(2), pp.141-159 (2004).
doi:10.1145/566282.566307
15. De Floriani, L., Greenfieldboyce, D., Hui, A.: A data structure for non-manifold simplicial
d-complexes. SGP '04: Proceedings of the 2004 Eurographics/ACM SIGGRAPH sympo-
sium on Geometry processing, pp. 83–92 (2004). doi:10.1145/1057432.1057444
16. De Floriani, L., Hui, A.: Data Structures for Simplicial Complexes: an Analysis and a
Comparison. In: Proc, of the Symp. on Geom. Proc., pp. 119-128 (2005)
17. Zengbo, W.: Fast topological reconstruction algorithm for a STL file. Journal of Computer
Applications, 34(9), pp.2720—2724 (2014).
18. Tan, J., Chen, J.: Research and Application on Model Repairing Algorithm of 3D Model-
ling Technology. 6th International Conference on Mechatronics, Computer and Education
Informationization (MCEI 2016). doi: 10.2991/mcei-16.2016.48
19. OpenMesh https://www.graphics.rwth-aachen.de/software/openmesh/
20. Shovgelia, D.G., Sokolova, N.O.: Obnaruzhenie defektov v trekhmernykh geomet-
richeskikh modelyakh, predstavlennykh na osnove Half-Edge Data Structure. Prykladni
Pytannia Matematychnoho Modeliuvannia 1(2), pp.155-161 (2019). doi:
https://doi.org/10.32782/2618-0340-2019-3-14