Subscribe Now Subscribe Today
Research Article

A New Rapid Triangulation Method of Space Closed Point Cloud

Zetao Jiang, Linghong Zhu and Qinghui Xiao
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail

Space point cloud triangulation is the research focus of 3D Stereo Vision field and the triangulation of space closed point cloud is difficult. In this study, firstly, divide the space closed point cloud into two or more parts separately triangulate, then extract the edge of each part. Finally, suture all parts according to the edge information. Completed the steps above, it can reach the purpose of the triangulation of the whole space closed point cloud. This study solve the problem that triangulation of the space closed point cloud in the process of 3D reconstruction which has practical significance. Experimental results show that the algorithm is simple, fast and the quality of triangular mesh is good.

Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

  How to cite this article:

Zetao Jiang, Linghong Zhu and Qinghui Xiao, 2011. A New Rapid Triangulation Method of Space Closed Point Cloud. Information Technology Journal, 10: 2476-2480.

DOI: 10.3923/itj.2011.2476.2480

Received: June 27, 2011; Accepted: August 09, 2011; Published: September 30, 2011


Always, there are two triangulation (Yong-Chun et al., 2003) methods of space point cloud, one is the point project to a plane, using plane triangulation algorithm to complete 3D points triangulation and the connection relations between the three points unchanged, this method is transform 3D into plane problem, can be described as the plane projection method; the second is to construct directly from the three point triangulation, known as the direct triangulation method. There are two types of this triangulation, the first is to the point of triangulation of the set of R, without changing the topology of the origin set, the real is the linear interpolation R; the other is to approximate the surface in a certain range of error, the vertices in the number and location are different from the origin set. Plane projection triangulation algorithm is relatively simple and fast but almost can not be directly triangulate of 3D closed point cloud. Because different surfaces may overlap after projection and most of the points have changed the topology of the original cloud. Although, the direct triangulation algorithm can be triangulate 3D points but the algorithm requires to find a three-dimensional point can see all the points of focus, so the determination of the first triangle is very important which in practice is more difficult. This study based on the study of the projection plane, the point cloud will be split into two parts (or multi-part) then triangulate all parts using the method of planar projection. Last triangles on the edge of the suture, forming a complete split.


To solve the problem of the plane triangulation can not wrap angle greater than 180 degrees for proper triangulation of space, this study will firstly segment the closed point cloud. Segmentation algorithm is divided into three steps.

Firstly, establish the minimum bounding box (Chunming, 2003). Bounding box which is to create a rectangular of all the point cloud data are included. Its size is Xmax-Xmin, Ymax-Ymin, Zmax-Zmin, Xmax, Xmin, Ymax, Ymin, Zmax, Zmin is the maximum and minimum in the point cloud of the coordinate of X, Y and Z. Secondly, compute the model’s center of gravity. According to the formula:

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud

where, Xi express the coordinate of x point set express the coordinate of y point set express the coordinate of z point set, n represent the number of points.

To the center of gravity as the origin to establish coordinate system, cut through the center of gravity to do X-Y or Y-Z or Z-Y plane, then the model have been cut into two parts. Of course, can be cut from three plane and the point cloud will be divided into eight parts. In order to reduce the time complexity of suture, only two segmentation in this study.

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud
Fig. 1: Point cloud segmentation

Completion of the initial split, the point cloud wrapping angle less than or equal to 180° (Fig. 1).

After above steps, have obtained two parts of point cloud data which wrapping angle is equal or less than 180°. The next step is triangulate the two-part point cloud (Xianhai et al., 2010).


Edge extraction is to find the boundaries of each region, to determine the 3D points which to be spliced. To achieve this goal, the study first use plane projection to triangulate various parts of the points cloud. Plane projection triangulate is to project 3D points to 2D plane, then using 2D triangulation method to do Delaunay (Xianhai et al., 2010; Fengmin et al., 2009; Xi and Jin, 2009; Qin et al., 2007) triangulation. Because the point cloud have been segmented, each part of the point cloud’s wrap angle has been less than or equal 180°. Therefore, the projector can guarantee the results of the horizontal distance between the point cloud and the original profile data topology unchanged (Fig. 2).

After these steps, the various parts of triangulation block has been formed, to be split to extract the edge of the point cloud can get based on the information of triangle side in Table 1.

Table 1 shows the index of triangular and edge information, Vertex (i, j, k) express the triangle which constitute by the point that index is i, j and k. Edge (i, j) represents the side which were connected by the vertices i and j. Obviously there are many side is a duplicate exists in the table, be sure the edges of these repeat the point is definitely not related to the edge points. This study firstly extract all the side information, assuming there are n triangles, then can get 3 * n edges; then delete all occurrences of two or more than two sides, the last to leave after the partition of the edge is the edge of each part.

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud
Fig. 2: Delaunay triangulation

Table 1: The edge information
Image for - A New Rapid Triangulation Method of Space Closed Point Cloud

So the edge of the above Table 1 is: Edge (0, 1), Edge (3, 0), Edge (3, 4), Edge (5, 4), Edge (5, 1), that means the 0, 1, 3, 4, 5 five points constitute the edge of this region (Fig. 3).


Suture: Suture at the border, the key is to make the various parts of the boundary points constitute a scattered to the list. In the previous section, have g all the edges and stored in the array of structures but these edges are unordered. The algorithm first to take the first element in the structure array as a list head, to determine the list direction (clockwise or counterclockwise) and then take the end of the first side edge as the starting point of the second to traverse the rest of the elements, until you find the edge that contains the first side end, recursively, until all the edge point only has a predecessor and a successor. Finally, the edge formed a list which is circular and have direction. The next step is to determine the first triangle, according to the Euclidean distance formula:

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud

First of all, find out the nearest point V0' from V0 in other parts, ascertain the first triangle’ first side, Then take the point V0' as a starting point to look for the point V1 on the boundary. At this point, the first index of a triangle is (V0,V0',V1) secondly, take V1 as the starting point to connect the second point V1' which in the lower boundary. The second triangle is defined as the index (V1, V0',V1').

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud
Fig. 3: Extract edge of 3D mode

According to this rule cycle, until the last triangle contains the starting point, then judge the suture ends.

Optimization: Delaunay triangle is the “closest to the rules” (Xianhai et al., 2010) of the triangulation. It can be seen from the previous section, each of the two partial closure can be a surface (surface composition by the four 3D points) but the initial triangle formed by stitching may not be optimal, that is not optimal Delaunay triangulation. This section in the suture using a local optimization process LOP (Local Optimization Procedure) (Pav and Walkington, 2005) to process, to ensure that a Delaunay triangulation. Specific approach for the surface of the suture is to be the largest empty circle criterion for inspection, to see whether the fourth vertex of the triangle circumcircle, if it is, the diagonal swap, local optimization process to be completed. LOP process is as follows.

Optimization process is as follows (if A, B, C, D four points are not coplanar, the plane after projection, that is z-axis coordinates of each point is 0 (Fig. 4):

According to the three vertices of a triangle calculate the coordinates of the center and radius of the circle. Suppose the triangle vertices are A, B and C:

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud

According to the formula:

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud

Solving for plane equation which take AB as normal vector and cross midpoint of AB. According to the formula:

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud
Fig. 4: LOP optimization

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud

Solving for plane equation which take AC as normal vector and cross midpoint of AC. According to the formula:

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud
(5 )

Solving for the normal vector n of ABC. ABC's plane equation is:

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud

Place the actual footnote at the bottom of the column in which it was cited, as in this column. See first page footnote for an example.

Solving system of equations can be drawn from the center coordinates (x, y, z) of the circumcircle:

According to the Euclidean distance formula (1) Find the center point to the D distance Dd and radius R
Optimization: Comparing Dd and R , if Dd>R point is in the internal of the triangle circumcircle, this time to do optimization in Fig. 4.

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud
Fig. 5: Experimental procedure

Image for - A New Rapid Triangulation Method of Space Closed Point Cloud
Fig. 6: Splicing result

Through this optimization process, it can ensure that the Delaunay triangulation maximizes the minimum angle characteristics, that means two adjacent triangles in the convex quadrilateral diagonal, in exchange, the six angles of the minimum angle no longer increases.


The method divided the whole scatter closed space into two parts (or more part). Firstly, use the method of triangulation of plane to do parts separately triangulate, get a break 3D model; then by extracted the edge of the model to find the edge points of the model; finally, according to the edge points to suture the 3D model thus, completing the entire triangulation of the space point cloud. Experimental procedures are summarized in (Fig. 5).

Experimental results show that the method of the spatial point cloud triangulation has a good effect (Fig. 6).


Based on plane triangulation, this study deal with triangulation problem for scattered data of space closure with sub-rule principle. There is a significant advantage that it solve problem of correct triangulation for wrap angle greater than 180° of space point cloud which the plane triangulation can not achieve. Although, this algorithm is more complicated over other triangulation algorithm but it is faster and easier on the whole. This method of can triangulated the point cloud of process space closure but while mistakes may occur when it triangulated with one side of rapid change, continuous point cloud. So, the method needs further improvement.


This study is sponsored by Nature Science Foundation of China (60673055) and Nature Science Foundation of Jiang Xi province in China (0611094).

1:  Yong-Chun, Z., D.A. Fei-Peng and S. Wen-Zhong, 2003. Surface triangulations based on 3D arbitrary point-sets. J. Image Graphics, 8: 34-36.

2:  Chunming, L., 2003. The Auto-Classification of Unorganized Points in Surface Reconstruction. Qingdao University Press, Qingdao, China..

3:  Xianhai, M., L.I. Jigang, Y. Qin, C. Qiang and C. Qiming, 2010. The algorithm of complex conforming delaunay triangulation. Sci. Sin., 4: 78-79.

4:  Fengmin, T., X.U. Dingjie and L.I. Ning, 2009. A node refinement algorithm for inserting feature constraints in delaunay triangulation. Geomatics Inform. Sci. Wuhan Univ., 3: 12-14.

5:  Xi, G. and T. Jin, 2009. Delaunay triangulation algorithm in dishevelled points of planar domain. Microcomput. Inform., 26: 72-75.

6:  Qin, Y., L. Ruigang, M. Xianhai, Z. Junan, 2007. The algorithm of 2D complex conforming delaunay triangulation. J. Comput. Aided Design Comput. Graphics, 2: 56-57.

7:  Pav, S.E. and N.J. Walkington, 2005. Delaunay refinement by corner lopping. Proceedings of the 14th International Meshing Roundtable, Sept.’05, California, pp: 165-181.

©  2021 Science Alert. All Rights Reserved