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.
POINT CLOUD SEGMENTATION
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 models center of gravity. According
to the formula:
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.
|| 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 clouds
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.
|| Delaunay triangulation
|| The edge information
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).
SPLICING EACH TRIANGULATION BLOCK
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:
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').
|| 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:
According to the formula:
Solving for plane equation which take AB as normal vector and cross midpoint of AB. According to the formula:
|| LOP optimization
Solving for plane equation which take AC as normal vector and cross midpoint of AC. According to the formula:
Solving for the normal vector n of ABC. ABC's plane equation is:
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.
|| Experimental procedure
|| 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).