# A Review on Triangular Mesh Generation

## IMAGES SHOWING TRIANGULAR MESH

## Review On Triangular Mesh and its generation

## 1. General Remarks

The primary concern of reverse engineering is to transit the original physical model into the conception of engineering design or digital model of production, which can obtain coordinate points of the shapes, and reconstruct 3D geometric model through some measurement equipment. In the last few years, reverse engineering has been developed and applied into manufacturing industry, such as mould, automobile, aerospace and so on. One of the most common model format is a triangular mesh, which consist of a large number of triangular faces. Triangular meshes play an important role in virtual reality (VR) applications. Nowadays most of the virtual objects in virtual environments are described by triangular meshes, because triangular meshes bring greater efficiency to VR systems to achieve real time interaction with the users. Also, triangular meshes are well suited for efficient collision detection algorithm. These models may have shape irregularities, caused either by the algorithms used to convert the CAD model into the mesh model, or by errors induced in the process of measuring object surfaces and then reconstructing the measured point clouds into triangular meshes.

**1.2. ****INTRODUCTION**

Reverse engineering (RE) refers to the process of creating a computer-aided design (CAD) model from an existing physical object, which can then be utilized as a design tool for producing a duplicate for engineering analysis, or re-engineering an existing part. In general, RE involves two major steps, i.e. data acquisition and surface reconstruction. For a stylist’s design model with complex surface features, the surface form is captured by using a 3-D vision system, that is capable of generating a cloud data points set. Triangular mesh, which is one of the most popular polygonal meshes, plays an important role in mesh simplification field. Triangle meshes are data representations with various advantages over the use of regular grids, including adaptability to data density, ease of manipulation and visualization of complex surfaces and organization of structures at different level of resolution.

Triangular meshes play an important role in virtual reality (VR) applications. Nowadays most of the virtual objects in virtual environments are described by triangular meshes, because triangular meshes bring greater efficiency to VR systems to achieve real time interaction with the users. First, modern graphics hardware are optimized to render triangular meshes, which leads to higher rendering speed for mesh models. Besides, triangular meshes enable level-of-detail management of object models, which helps VR engines to display highly complex scenes in real time. Also, triangular meshes are well suited for efficient collision detection algorithms, which are indispensable in VR applications. In a virtual environment, triangular mesh models are usually created by importing and tessellating CAD models, or by scanning real world objects with 3-D scanners. These models may have shape irregularities, caused either by the algorithms used to convert the CAD model into the mesh model, or by errors induced in the process of measuring object surfaces and then reconstructing the measured point clouds into triangular meshes.

Triangular mesh is a piece wise linear model that can be seen as a connected set of contiguous non- overlapping triangles. The objective of mesh generation is to cover the reduced point set with a continuous surface mesh of triangular facets. The triangulation algorithm is developed based on a set of heuristic rules. The main methods for generating triangular meshes can be classified into refinement and simplification. **Mesh refinement **initially construct a triangulation that approximates a small number of data points. At each iteration, a new point is inserted into the mesh, typically one that presents the largest approximation error in the current triangulation. Local adjustments are performed in the mesh and refinement process finishes when triangulation satisfies a given error tolerance. **Mesh simplification **consider a mesh with all or large number of points already belonging to triangulation and at each iteration eliminate the point with the smallest approximation error. The triangulation is then locally rebuilt. **Delaunay triangulation** is used to maintain the mesh, which has the property of maximizing the minimum angle of all triangles of the mesh, reducing the occurrence of long and narrow triangles that tend to cause undesirable defects.

## TECHNICAL DETAILS

**INTRODUCTION**

Mesh surface reconstruction of spatial points is also called triangulation. Surface reconstruction is the process to achieve three dimensional complex surface model from three dimensional data collected. Three dimensional data collected by measuring device is usually dense so it is called Point Cloud data. Point cloud data considered as an aggregation of the points in three dimensional space, it has three coordinates x, y, z. The point cloud data can be divided into ordered and scattered point cloud Its purpose is to reconstruct the topology of each discrete point and obtain a linear surface (that is, mesh) in accordance with the original structure. Meshes can be used to model both solid shapes and surfaces. The object is solid if the faces fit together to completely enclose a space or a volume, this is called a closed surface. When the object is drawn so that all the edges are visible and the object is transparent, this is called a *wireframe*. For a mesh model a set of points in space are specified and then connect various pairs of these points to form edges. A set of three points (vertices) will form a triangle. A number of triangles may form a surface. And a number of surfaces will form an object. Numerous triangulation methods fall into two major categories:

Numerous triangulation methods fall into two major categories:

- Delaunay based
- Non-Delaunay based

Delaunay based triangulation method is traditional with features of uniqueness and local optimization but still needs to be improved.

**TRIANGULAR MESH GENERATION:**

Following methods are being used in the triangular mesh generation have been discussed below :-

A) Triangulation based on Incremental method

B) Boundary expansion technique

C) Intrinsic property driven algorithm for Triangular mesh

**Triangulation based on Incremental method:**

The incremental algorithms, which create the triangle by growing the mesh along its border starting from an initial element (a point, edge or triangle). The main advantage of these techniques are low complexity and memory requirement and the incremental algorithms can easily process large data set. The algorithm of triangulation based incremental methods was used , which can deal with a large amount of scattered points. Besides, the scattered points can be of certain non uniformity of distribution, so it can be used into constructing triangulation of point clouds for body surfaces.

**BASIC CONCEPTS AND DATA STRUCTURE :**Some correlative basic concepts of the incremental algorithm are given as:

- Free point: The point is not yet triangulated.
- Inner point: The point is triangulated, and located in the splitted region.
- Best point: The maximum of field angle of the edge is called the best point, Cosine value of which should be less than the given value.
- Boundary edge: The boundary edge is a triangle edge which must be between the spitted region and unsplit region.
- Boundary ring: The boundary edges are arranged end-to-end for constructing circular boundary edges by the way of anti-clockwise or clockwise.

Some correlative data structure of the incremental algorithm are given as:

**Point list**: There is no need for the inserting and deleting operations in the process of triangulation, and the primary operation is to retrieve the cube grid which contains any data points and the data points which are contained in any cube gird.**Triangle list**: Because each vertices and normal vector of triangles can be used to estimate corner dimension between two neighbor triangles, the storage structure of triangle list mostly consists of: triangle number, three vertex pointers toward a triangle and normal vector of triangle.**The list of boundary edge**: All the boundary edges in the process of triangulation are temporarily stored. The boundary ring is composed of the boundary edges in some orders. One boundary ring corresponds one boundary list. When the triangulation is finished, the list of boundary edge is blank.**The list of boundary ring**: Many boundary rings may be generated in the process of triangulation. When the triangle splitting is finished, the list of boundary ring is blank.

**THE IMPLEMENTATION OF ALGORITHM**

The key idea of incremental algorithm for triangulation is the expansion of boundary edge. Firstly, the initial constructed triangles are logged into the triangle list, and each edge of triangles is stored into the list of boundary edge in certain orders. Then, new constructed triangles are added into the triangle list one after another by searching the best neighbor point between double end points of each boundary edge. The whole process is that boundary edges expand gradually, and mostly includes: preprocess, construction of initial triangle and triangular growth.

**Preprocess :**After being taken the point clouds as a large data box, minimal rectangular space which contains every scattered data points is calculated, and the length of sub cube space is calculated. Then many small cubes are divided in accordance with certain criteria, and the point clouds are put in each sub cube space so that neighbour points of each data point can be searched through the algorithm for fast finding k- neighbours.

**Construction of initial triangle:**At first, the first vertex of initial triangle is established by selecting one point that has the maximum of z-coordinate values, and then one point which is the nearest neighbour point of first vertex is taken as the second vertex. At last, taken the double vertices as one edge of the triangle, the common neighbor point of both vertices is searched, and considered as the third vertex of initial triangle.**Growth of triangle:**The triangulation process of point clouds is the process that double vertices of current boundary edge and the best point are connected with each other to form new triangle. Besides, selection of the best point is important particularly, which determines the quality of generated triangle mesh directly.

The selection of best point needs to follow some criteria:

- The best point must be the k-neighborhoods of both end points which locate the boundary edge.
- The best point must be the inner point, which guarantees that the boundary edge of new triangle does not overlap with former triangles and makes the boundary edges outward expand quickly.
- The field angle of the edge for best point is the maximum of the field angle of all the common neighbor points, which is related to the Cosine absolute value of the edge field angle. Suppose the field angle of common neighbor points is γ , the best point can be chosen by cosγ . Theoretically, the bigger absolute value is, the better best point is. But if the cosine value is too big, the slight triangles are easily generated, which impacts the generation quality of triangle mesh.

**Boundary expansion technique:**

The objective of mesh generation is to cover the reduced point set with a continuous surface mesh of triangular facets. The triangulation algorithm is developed based on a set of heuristic rules. It starts with a selected seed triangle, formed by randomly selecting three neighboring points. The three edges form the initial boundary edge-list of the mesh. The mesh grows by interrogating the geometric and topological information in the neighborhood of the boundary edge-list through application of a set of heuristic rules in order to connect a new point to form a new triangle of the expanding mesh. A neighbouring point to the boundary edge list of meshed area is selected based on a set of constraints described below. The process is repeated until all the points in the set are meshed. The details of this algorithm are described in the following sections.

**The initial triangular facet: **Firstly, three neighboring points are randomly selected to form the first triangle facet. There should be no point “inside” this triangle. As shown the edges of the triangle are defined as vectors { AB , BC and CA }, following the counter-clockwise direction. The normal of the triangle N points away from the surface patch. Every boundary edge forms a vector with a starting and ending point. For instance, edge AB has starting point A and the ending point B.

**Triangular mesh expansion: **To expand the mesh, a point is selected from the remaining points in the set for each boundary edge. A new triangle is thus formed by a boundary edge and its selected point. A new boundary edge list is then formed for the meshed area, following the counter- clockwise direction.

**Triangulation constraints: **During the triangulation process described above, a new point needs to be identified from the remaining cloud data in each round. The rules for identifying such a point for a given edge are described as follows:

**Search space**: The scope of the search for the new point for a boundary edge is limited within the 26 neighbouring voxels of both ending points of the boundary edge.**Minimum triangular facet angle**: The smallest angle within any triangular facet must be larger than the minimum angle, ϕ. This prevents nearly co-linear vertices from forming long, narrow triangular facets. Such facets are unwanted because their surface normal may not accurately match the object’s local surface curvature.**Maximum angle between two neighbouring facets:**The angle between any two neighbouring triangular facets must be within a specific scope. This angle, θ, is defined as the angle between the normal vectors of two neighbouring triangle facets . It must be greater than 0° and less than a specific value.**Being nearest to the middle of the edge:**There may be more than one point satisfying all the rules mentioned above, but only one point should be selected. Based on experience, the one, which is the nearest to the middle of the boundary edge at hand, can lead to achieving an evenly distributed triangular mesh.

In every step of forming a triangle, only one point satisfying the constraints described above is selected to form a new triangle. This point is called the ‘suitable point’ and the edge used in the search is called the ‘searching edge’. The location of a suitable point may fall into the following condition:

- There is no suitable point. This means the triangulation reaches the boundary of the image (internal or external).
- The suitable point is within the boundary of the image .This is the most common situation in triangulation.

**Construction of triangle meshes from images at multiple scales based on median error metric**

The method for constructing triangle meshes proposed in this work initially generates a minimal approximation consisting of two triangles over the data domain. This coarse mesh is then refined by iteratively adding new points, updating the triangulation after each point is inserted, until either a specified error tolerance is achieved or a given number of points is reached. An incremental Delaunay triangulation is used to generate the mesh. The vertex selection criterion is crucial during the triangulation process since it determines the degree of fidelity between the original data and its approximation. The magnitude of the error can be computed over a limited region to estimate local error or over the entire domain to measure global error. Global error measures usually produce better approximations. However, the resulting algorithms are significantly slower than those using local metrics.

It proposes a new measure for inserting points into the mesh. In each triangle, the point with median error, calculated between the original and the approximate surface. Then, the point with the highest median error for all triangles is added to the mesh. This strategy provides adequate adaptability to the data and is superior to the vertical error measure for noisy images. To insert a new point *p *into the mesh, its containing triangle is located, or if *p *lies on an existing edge, that edge is deleted and *p *is connected to the four vertices of the containing quadrilateral. New edges are created to connect *p *to the vertices of the containing polygon. All edges defining the containing polygon are checked to verify whether they satisfy the Delaunay property, that is, the circumcircle of any triangle in the triangulation must contain no other data points in its interior. If the property is satisfied, the edge remains unchanged. If it is violated, the edge is swapped with the other diagonal of its quadrilateral. In this case, two more edges become candidates for inspection. The process continues until no more candidate edges remain, resulting a Delaunay triangulation.

A priority queue is used to maintain the candidate point of each triangle, that is, the point with the highest median error. The median error is calculated by taking into the account the median absolute difference between the actual elevation data and the surface approximation for each triangle. At each refinement step, the point with the highest error within all triangles is extracted from the queue and inserted into the current mesh.

__ALGORITHM 1: Mesh refinement (from a single scale image)__

1: Input: image *I*, set of points *P _{1}*, maximum number of points

*N*, and tolerance error

*€*

2: Output: subset *P *of data points and its triangulation *T*

3: *P *= *P _{1} U *four corners of

*I*

4: *T *= IncrementalDelaunayTriangulation(*P*)

5: create priority queue *Q *with errors associated with *T*

6: while (highest median error in *Q > €*) and (number of points *< N*) do

7: begin

8: select point *p *with highest median error in *Q*

9: *P *= *P U {p}*

10: *T *= IncrementalDelaunayTriangulation(*P*)

11: update *Q *for the points affected by the insertion of point *p*

12: end

13: return *P *and *T*

__ALGORITHM 2: Mesh refinement ( from multiple scale representation of an image)__

1: Input: set of images *I _{t}*at scales

*t*=

*t*

_{0}

*; t*

_{1}

*; : : : ; t*, maximum number of points per

_{s}scale, and tolerance error *€*

2: Output: subset *P *of data points and its triangulation *T*

3: for each image *I _{t}*,

*t*=

*t*

_{s}; : : : ; t_{1}*; t*

_{1}do

4: begin

5: (*P _{t} ; T*)

*←*Algorithm 1 with input parameters

*I*,

_{t}*P*,

*M*, and

*€*

6: *P *= *P U P _{t}*

7: end

8: return *P *and *T*

**VARIOUS DEFECTS IN TRIANGULAR MESH**

Polygon meshes are representations of three-dimensional models. A polygon mesh consists of a collection of geometric elements including vertices, edges, and triangles. A triangle mesh is a special type of polygon mesh where all the faces are triangles. Mesh defects are the erroneous geometry in a polygon mesh, and can be divided into two categories:

**Geometric defects****Topological defects**.

**Geometric defects** are the errors within a triangle mesh that against the requirements for being geometrically correct. For example one of the requirements says that a polygon mesh must represent a closed surface. If a polygon mesh represents a surface that is not closed, this mesh is not geometrically correct/valid.

**Topological defects** such as undesired handles are the unnecessary geometry that wrongly describe the shapes of an object. For instance, a torus has only one handle; and if a torus mesh has two or more handles, then it is not topologically correct because it does not represent the shape it is supposed to be representing, although the mesh may be geometrically correct.

Geometric correctness/validity is especially important in practical applications. A geometrically correct/valid mesh must have none of the above-described geometric defects. In fact, a polygon mesh should be closed, manifold and free of self-intersections to be used in most applications. By definition, each point of an n-dimensional manifold has a neighborhood that is homeomorphic to the Euclidean space of dimension. Each point of a manifold polygon mesh should have a neighborhood that is homeomorphic to a two-dimensional Euclidean surface summarizes that a non-manifold geometric elements include non-manifold edges that are not contained in exactly two polygons and non-manifold vertices that are not contained in a disk-like neighborhood. Topological correctness further ensures that a polygon mesh does not misrepresent the shape of an object. Topological correctness is a criterion from the shape point of view. Geometric correctness, on the other hand, focuses on geometric details and ensures that every single vertex and every single triangle follow geometric requirements.

There are such fairing techniques as local fairing techniques. Mesh defects are the geometry that violate these rules. The types of mesh defects as below:

a) Duplicate Vertex: two vertices are duplicate if they are in the same position in 3D space.

b) Duplicate Triangle: two triangles are duplicate if they are composed of the same vertices.

c) Isolated Vertex: a vertex that is not used by any mesh triangles is an isolated vertex.

d) Isolated Triangle: a triangle that is not connected with the core part of a mesh is an isolated triangle.

e) Self-intersection: self-intersections are two or more faces that intersect with each other.

f) Boundary Edge: a boundary edge is an edge that is only used by one mesh triangle.

g) Hole: a hole is a collection of boundary edges; these edges form a closed cycle in 3D space.

__Mesh cleaning and hole filling:__

Mesh repairing is a general process of removing geometrical defects. It has two subprocess:

- Mesh cleaning
- Hole filling

Most geometric defects are removed during the mesh cleaning process. Holes are the only defects left after the mesh cleaning process and will be fixed during the hole filling process. In general, fixing holes is much more difficult than fixing other geometric errors because the shape of the holes could be very irregular and unpredictable.In the past decade, various mesh smoothing techniques have been developed to optimize the shape of a mesh. Usually these techniques perform their tasks by changing the positions of mesh vertices without affecting their connectivity. Mesh smoothing has two different goals. The first one is to eliminate noises in mesh data. For example, meshes acquired by range scanners usually have high frequency noises in the vertex positions. And mesh smoothing methods are applied to smooth out these noises while preserving the overall shape of the model. Such mesh smoothing methods are referred to as mesh denoising.

The other goal of mesh smoothing is to produce high quality surface that satisfies certain aesthetic requirements. Such methods are called mesh fairing. Among these techniques, some tries to improve the shape quality of the whole mesh surface. Other mesh fairing techniques only modify part of the mesh surface, which is usually inside a region specified by the user.

**APPLICATIONS OF TRIANGULAR MESH**

The various applications of triangular mesh are:

1) In computer graphic areas like CAGD, CAD – CAM

2) Earth Sciences

3) Computer vision in robotics

4) Image reconstruction from satellite

5) Radar information

6) In visual C++ language

7) Open GL technology in the microcomputer

8) In Unigraphics environment employing its internal application programming tool.

## APPLICATION OF TRIANGULAR MESH

*BENEFITS OF USING MESH:*

- can be used to model almost any object
- they are easy to represent (as collections of vertices)
- easy to transform
- easy to draw on a computer screen.

*CONCLUSION:*

The objective of this article was to study about the triangular meshes used in reverse engineering. . A polygon mesh consists of a collection of geometric elements including vertices, edges, and triangles. A triangle mesh is a special type of polygon mesh where all the faces are triangles. Triangular mesh is a piecewise linear model that can be seen as a connected set of contiguous non- overlapping triangles. The objective of mesh generation is to cover the reduced point set with a continuous surface mesh of triangular facets. The triangulation algorithm is developed based on a set of heuristic rules. The main methods for generating triangular meshes can be classified into refinement and simplification. The generated algorithms can deal with great deal of scattered point clouds and construct triangular meshes. They can satisfy the requirements of surface construction of reverse engineering and establish substantial foundation for later surface smoothness. The constructed triangular mesh should be geometrically correct and if it is geometrically incorrect then various measures are taken to remove the discrepancies in triangular mesh. Thus, we obtain a geometrically correct triangular mesh.

**FUTURE WORK:**

The future work will include investigation of new schemes for generating meshes and new criteria for selection and insertion of data points to build the mesh. The main focus would be on generating triangular meshes which are geometrically and topologically correct with minimum error.