CN108765572B - Triangulation method and system of plane point set in 3D scanning - Google Patents

Abstract

The invention relates to the technical field of three-dimensional reconstruction, and discloses a triangulation method and a triangulation system for a plane point set in three-dimensional scanning, which are used for improving the triangulation speed of the plane point set in the three-dimensional scanning and better meeting the real-time requirement of the three-dimensional reconstruction; the method comprises the steps of obtaining three-dimensional coordinate points of a target object to be reconstructed, mapping the three-dimensional coordinate points into a plane point set, traversing the plane point set to construct a target triangle containing all points in the plane point set; and distributing side pointers for the triangles, searching a target triangle according to the relation between the insertion point and the side pointer of the triangle until all coordinate points are inserted, obtaining a final triangle net to realize triangulation on a plane point set in three-dimensional scanning, and then mapping the triangle net into a curved surface to fit the target object to be reconstructed.

Description

Triangulation method and system of plane point set in 3D scanning

technical field

The present invention relates to the technical field of three-dimensional reconstruction, in particular to a triangulation method and system of a plane point set in three-dimensional scanning.

Background technique

The purpose of three-dimensional reconstruction is to create a virtual three-dimensional object and give people a very real feeling. The three-dimensional reconstruction of images integrates knowledge of image processing and computer geometry. It has functions that two-dimensional graphics cannot compare. The 3D reconstructed object can be observed intuitively from any angle and has a very real feeling, which can achieve the function of real-time interaction. Faced with the rapid development and demands of modern production, 3D reconstruction can be used to reduce design costs, shorten design cycles, and bring huge economic benefits to the society. Therefore, 3D reconstruction is a very attractive research field with a wide range of applications and high research and use value.

Triangulation theory is the most indispensable part of 3D reconstruction technology. The triangulation theory of 3D space has been further enriched and improved under the influence of the rapid development of 3D reconstruction technology. At present, there are many different improvement specifications for triangulation, among which the commonly used triangulation improvement standards are circle specification, maximum/minimum interval specification, maximum/minimum angle specification, maximum/minimum height specification, Thiessen specification, etc. One of the basic points of these specifications is to minimize the occurrence of flat triangles that are too sharp. It is known from the approximation theory that the approximate difference of a triangular surface is related to the minimum interior angle of the triangle. It is particularly necessary to improve the accuracy of the approximation and reduce the appearance of excessively sharp triangles, which is very necessary in computational geometry. Delaunay triangulation obtains that the minimum value of all the interior angles of the triangle is larger than other triangulations, and the average shape is the most regular, so it is called the optimal triangulation by mathematicians. Delaunay triangulation is not only widely used in two-dimensional space, but also plays a very important role in three-dimensional space. At present, there are not many researches on Delaunay triangulation algorithm in three-dimensional space. Many traditional triangulation Algorithms can only solve problems in two-dimensional space, and in three-dimensional space, many problems of triangulation are not solved.

At present, the Delaunay triangulation in two-dimensional space has developed to a certain height, but when a large number of vertices need to be inserted, the execution time of the traditional Delaunay triangulation algorithm is too long, especially when processing too many scattered data. , which takes too long to meet the real-time requirements.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a triangulation method and system of plane point sets in three-dimensional scanning, so as to improve the triangulation speed of plane point sets in three-dimensional scanning, and better meet the real-time requirements of three-dimensional reconstruction.

In order to achieve the above object, the present invention provides a triangulation method for a plane point set in a three-dimensional scan, comprising the following steps:

S1: Obtain the three-dimensional coordinate points of the target object to be reconstructed, map the three-dimensional coordinate points to a plane point set, and traverse the plane point set to construct a target triangle including all points in the plane point set;

S2: Mark the first vertex, the second vertex, and the third vertex for the target triangle in a counterclockwise order, and then assign a first edge pointer to the edge connecting the first vertex and the third vertex, and assign a first edge pointer to the A second edge pointer is allocated for the connection between the second vertex and the third vertex, and a third edge pointer is allocated for the connection between the first vertex and the second vertex;

S3: Select a certain point in the plane point set as the insertion point, connect the insertion point and the vertices of the target triangle respectively, obtain new triangles arranged in sequence after the division, and complete the first triangulation to obtain Triangle net, delete the divided target triangle, then update the edge pointer of each new triangle according to the method described in step S2, and store the new triangle in the triangle linked list in sequence;

S4: Select another point in the plane point set as the insertion point, insert the insertion point into the corresponding triangle according to the edge pointer relationship between the insertion point and the first triangle in the triangle linked list, and view the inserted triangle as a For a new target triangle, connect the insertion point and each vertex of the target triangle respectively, complete the subdivision of the target triangle to obtain a new triangle, and delete the target triangle to update the triangle mesh, and update each The edge pointer of the triangle and the triangle linked list; then determine whether each of the new triangles conforms to the Delaunay empty circle rule in turn, if so, enter step S5, if not, adjust the connected sides of the new triangle until all After the new triangle conforms to the Delaunay empty circle rule, enter step S5;

S5: Repeat the above step S4 until the insertion of all coordinate points is completed, and a final triangular net is obtained to implement triangulation of the plane point set in the three-dimensional scanning.

Preferably, in the step S3, the sorting method of the new triangles is as follows: according to the order of the vertices of the original triangles, the order of each new triangle is arranged in a counterclockwise direction.

Preferably, in the step S3, inserting the insertion point into the corresponding triangle according to the edge pointer relationship between the insertion point and the first triangle in the triangle linked list specifically includes the following steps:

(31) judging whether the insertion point is located outside the first side pointer of the triangle, if so, search for a common triangle according to the first side pointer of the triangle, if not, judge whether the insertion point is located at the The outer side of the pointer of the second side of the triangle, if so, search for a co-lateral triangle according to the pointer of the second side of the triangle, if not, determine whether the insertion point is located outside the pointer of the third side of the triangle, if so , then according to the pointer of the third side of the triangle to find a common triangle;

(32) Judging whether the insertion point is located in the interior of the colateral triangle, if so, the colateral triangle is regarded as a target triangle, and the insertion point is inserted into the target triangle; if not, the steps are adopted The method in (31) continues to judge the relationship between the insertion point and the edge pointer of the co-edge triangle, until the target triangle of the insertion point is found.

Preferably, before the step (31), the method further includes the step of: judging whether the insertion point is located in the first triangle, if so, treating the first triangle as the target triangle; if not, executing all Step (31) described above.

Preferably, when the insertion point is located on the edge of the first triangle, all triangles where the insertion point falls into the edge are regarded as the target triangle.

Preferably, in the step S4, deleting the target triangle to update the triangle mesh, and updating the edge pointer of each triangle and the triangle linked list at the same time specifically includes updating the edge pointer of the new triangle, updating and deleting the target. The edge pointer of the triangle adjacent to the triangle, and the triangle stored in the updated triangle linked list; where:

The updating of the edge pointer of the triangle adjacent to the deleted target triangle specifically includes the following steps: deleting the target triangle, and pointing the edge pointer of the adjacent triangle that originally pointed to the deleted target triangle to the corresponding new triangle;

The updating of the triangles stored in the triangle linked list specifically includes the following steps: replacing the position of the deleted target triangle in the triangle linked list with the generated new triangles arranged in sequence in the triangle linked list.

Preferably, in the step S4, judging in turn whether each of the new triangles conforms to the Delaunay empty circle rule specifically includes the following steps:

According to the pointer of the third side of the new triangle, find the co-edge triangle. If the quadrilateral formed by the found co-edge triangle and the new triangle does not satisfy the Delaunay empty circle rule, delete the co-edge and connect another pair in the quadrilateral. To adjust the connecting edge of the new triangle, update the edge pointer and triangle linked list of the newly generated triangle at the same time, and then re-evaluate each new triangle.

In order to achieve the above object, the present invention also provides a triangulation system for a plane point set in a three-dimensional scan, comprising a memory, a processor, and a computer program stored in the memory and running on the processor, the processor executing the The steps of the above method are implemented when the computer program is described.

The present invention has the following beneficial effects:

The triangulation method and system for a plane point set in a three-dimensional scan provided by the present invention first obtain the three-dimensional coordinate points of the target object to be reconstructed, map the three-dimensional coordinate points into a plane point set, and traverse the plane point set to construct a The target triangle of all points is then divided into the target triangle by continuously searching for new target triangles in the target triangle; the present invention allocates corresponding edge pointers to the target triangle, according to the difference between the insertion point and the edge pointer of the corresponding triangle. The new target triangle is searched in a directional position relationship, which can quickly realize the division of the original target triangle, obtain a triangular mesh, and then map the triangular mesh into a curved surface to fit the object to be reconstructed. The method and system can improve the search efficiency. The speed of the new target triangle can better meet the real-time requirements of 3D reconstruction.

The present invention will be described in further detail below with reference to the accompanying drawings.

Description of drawings

The accompanying drawings constituting a part of the present application are used to provide further understanding of the present invention, and the exemplary embodiments of the present invention and their descriptions are used to explain the present invention and do not constitute an improper limitation of the present invention. In the attached image:

Fig. 1 is the method flow schematic diagram of the triangulation of the preferred embodiment of the present invention;

2 is an example diagram of an insertion point falling into a certain triangle in the triangulation of the preferred embodiment of the present invention;

Fig. 3 is the example diagram that the insertion point falls on the triangle edge in the triangulation of the preferred embodiment of the present invention;

FIG. 4 is a schematic diagram of judging the Delaunay empty circle rule in triangulation according to a preferred embodiment of the present invention.

Detailed ways

The embodiments of the present invention are described in detail below with reference to the accompanying drawings, but the present invention can be implemented in many different ways as defined and covered by the claims.

Example 1

Referring to FIG. 1 , this embodiment provides a triangulation method for a plane point set in a three-dimensional scan, including the following steps:

S1: Obtain the three-dimensional coordinate points of the target object to be reconstructed, map the three-dimensional coordinate points to a plane point set, and traverse the plane point set to construct a target triangle including all points in the plane point set;

S2: Mark the first vertex, the second vertex and the third vertex for the target triangle in a counterclockwise order, then assign the first edge pointer to the edge connecting the first vertex and the third vertex, and assign the first edge pointer to the edge between the second vertex and the third vertex. The second edge pointer is allocated for connecting the edge, and the third edge pointer is allocated for the connecting edge between the first vertex and the second vertex;

S3: Select a point in the plane point set as the insertion point, connect the insertion point and the vertices of the target triangle respectively, obtain new triangles arranged in sequence after division, complete the first triangulation to obtain a triangle mesh, delete the divided triangles divide the target triangle, then update the edge pointer of each new triangle according to the method of step S2, and store the new triangles in the triangle linked list in sequence;

S4: Select another point in the plane point set as the insertion point, insert the insertion point into the corresponding triangle according to the edge pointer relationship between the insertion point and the first triangle in the triangle linked list, and regard the inserted triangle as a new target Triangle, connect the insertion point and the vertices of the target triangle respectively, complete the subdivision of the target triangle to obtain a new triangle, delete the target triangle to update the triangle mesh, and update the edge pointer and triangle linked list of each triangle at the same time; then judge each triangle in turn. Whether the new triangle conforms to the Delaunay empty circle rule, if so, go to step S5, if not, adjust the connecting sides of the new triangle until the new triangle conforms to the Delaunay empty circle rule and go to step S5;

S5: Repeat the above step S4 until the insertion of all coordinate points is completed, and a final triangular net is obtained to implement triangulation of the plane point set in the three-dimensional scanning.

It should be noted that when constructing the target triangle for the first time, first traverse all the coordinate points in the plane point set, find the maximum abscissa value and ordinate value X _max , Y _max , take the larger of the two to get max , and construct a target triangle containing all points in the plane point set according to max, preferably, the coordinates of each point are:

V ₁ ={0, 4*max};

V ₂ ={-4*max,-4*max};

V ₃ ={4*max, 0};

Among them, V ₁ , V ₂ , V ₃ represent the three vertices of the constructed target triangle containing all points in the plane point set, respectively. This determination method can ensure that all the inserted scatter points fall inside the super triangle, and then all The point is inserted into the target triangle, and finally the points V ₁ , V ₂ , V ₃ and all the edges related to V ₁ , V ₂ , V ₃ are deleted, and finally a triangle mesh that satisfies the Delaunay triangle rule is obtained.

Specifically, in the actual implementation, after traversing the plane point set, the target triangle ABC is constructed. Referring to Figure 2, in a counterclockwise direction, the first side pointer is allocated to the side AC, the second side pointer is allocated to the BC side, and the AB side is allocated. Allocate the third side pointer, select the point E in the plane as the insertion point, connect AE, BE and CE, and divide the triangle ABC to obtain ABE, BCE, CAE in order. It is important to note that when naming the new triangle, name the insertion point as the last point. In addition, the order of the new triangles obtained by dividing the triangle ABC should start with the first vertex A to determine the first new triangle, then start with the second vertex B to determine the second new triangle, and then start with the third vertex C Start identifying the third new triangle. Then, new triangles ABE, BCE, CAE can be obtained in order, and then a corresponding edge pointer is allocated to each new triangle, and the triangles are stored in the triangle linked list in order. Among them, when assigning a corresponding edge pointer to each new triangle, the first edge pointer should be assigned to the connecting edge between the first vertex and the third vertex, and the first edge pointer should be assigned to the connecting edge between the second vertex and the third vertex. Two-edge pointer, allocates a third edge pointer for the connecting edge between the first vertex and the second vertex, taking triangle ABE as an example, then the first edge pointer is on the AE side, the second edge pointer is on the BE edge, and AB On the edge is the third edge pointer.

It should be noted that each edge pointer points to the coedge triangle of the edge. According to the pointing direction of the edge pointer, the co-edge triangle with the edge where the edge pointer is located can be quickly found, which provides a basis for quickly finding the target triangle. For example, referring to FIG. 2, after the insertion point E, the first side pointer of the new triangle ABE points to the colateral triangle CAE, and the second side pointer points to the colateral triangle BCE.

Then, pick another point D in the plane as the insertion point. First, it is judged that the point D is not located inside the first triangle ABE in the triangle linked list, and then the judgment is made according to the edge pointer relationship between the point D and each side of the first triangle ABE in the triangle linked list. Specifically, according to Fig. 2, it can be seen that the point D is located outside the side AE corresponding to the first side pointer of the triangle ABE, then the common triangle CAE that shares the side AE with the triangle ABE is found, and it is judged that the point D is not located in the common side triangle CAE. Inside, then judging that the point D is located outside the side CE corresponding to the first side pointer of the common triangle CAE, then find the common triangle BCE, and judge that the point D is inside the common triangle BCE, then insert the point D into the common side In the triangle BCE, the co-edge triangle BCE is regarded as the target triangle, and the vertexes of the point D and the target triangle BCE are connected to obtain new triangles BCD, CED and EBD arranged in sequence. Delete the target triangle BCE, then assign the corresponding edge pointer to each new triangle, and update the triangle linked list to be ABE, BCD, CED, EBD, CAE. Specifically, when assigning a corresponding edge pointer to each new triangle, the edge pointer assignment method adopted is the same as the assignment method used for generating the new triangle ABE described above. At the same time, when the point D is inserted, the target triangle BCE is deleted, and at this time, the pointers of the triangles adjacent to the target triangle BCE, such as the triangle ABE, should also be updated. Specifically, in the triangle ABE, the pointer on the side BE adjacent to the target triangle BCE originally points to the triangle BCE. After the triangle BCE is deleted, the pointer on the side BE points to the newly generated triangle EBD.

Insert the point P into the triangle CED in the same way, and then get the new triangles CEP, EDP, DCP arranged in sequence. Then delete the target triangle CED, assign the corresponding edge pointer to each new triangle, and update the triangle linked list to ABE, EBD, BCD, CEP, EDP, DCP, CAE. Further, the point X is inserted. Similarly, the point X is judged not to be inside the triangle ABE, and the point X is judged to be outside the side AE corresponding to the first side pointer of the triangle ABE, then the common side of the triangle ABE is found. Triangle CAE, judge that the point X is not located inside the triangle CAE, judge that the point X is outside the pointer CE of the first side of the triangle CAE, find the common triangle CEP that has the same side CE with the triangle CAE, and judge that the point X is on the same side Inside the triangle CEP, the co-edge triangle CEP is regarded as the target triangle. In this example, according to the edge pointer-based search method, the target triangle can be found after 3 times. If the traditional algorithm (finding the triangle linked list in turn) is used, it takes the 4th time to find the target triangle, and with the insertion point As the number of points increases, the speed of the edge-pointer search-based method is significantly more pronounced.

As a preferred implementation of this embodiment, when the insertion point is located on the edge of the first triangle, the triangle where the insertion point falls into the edge is regarded as the target triangle. Specifically, in the above insertion process, it is assumed that the point P falls on the edge CE, as shown in Figure 3, when the triangle CDE is found, it is first judged that the point P is on the edge CE, and then the colateral triangle of the triangle CED is searched. The pointer above is directly obtained, that is, the triangle AEC. After finding the common triangle, insert the point P into the edge CE, generate the triangles EDP, DCP, AEP, CAP, and update the pointers of the edges AE, CA, DE and CD (the bold part in Figure 3, the AE edge pointer originally points to the triangle ACE, now points to triangle AEP, similarly DE side pointer points to triangle EDP, CD side pointer points to triangle CDP, CA side pointer points to triangle CAP; update the dotted line part in Figure 3, so that triangle EDP, CDP, AEP, CAP can pass through the edge The pointer to find the adjacent coedge triangles), the pointers of the edges EP, DP, CP and AP point to the adjacent coedge triangles, then the triangles CDE and ACE are the target triangles, and the triangles CDE and ACE are deleted.

As a preferred implementation of this embodiment, in step S4, judging in turn whether each new triangle conforms to the Delaunay empty circle rule specifically includes the following steps:

According to the pointer of the third side of the new triangle, search for a colateral triangle. If the quadrilateral formed by the found colateral triangle and the new triangle does not satisfy the Delaunay empty circle rule, delete the diagonal connection line of the quadrilateral and connect the quadrilateral in the quadrilateral. Another diagonal line of , update the edge pointer and triangle linked list of the newly generated triangle at the same time, and then re-evaluate each new triangle.

Specifically, when determining the Delaunay empty circle rule, as shown in Figure 4, assuming that the triangle ABP is determined by the Delaunay rule, the co-edge triangle DBA can be found through the edge pointer on the AB side, and then the three vertices of the triangle are judged whether the The positional relationship (DBA or ADB or BAD) of the triangle ADB is determined according to the counterclockwise direction. Then it is judged whether the triangles ABP and ADB are in the same circumcircle. If they are not in the same circle, it conforms to the Delaunay empty circle characteristic rule, otherwise it does not conform to the Delaunay empty circle characteristic rule. If it does not meet the characteristics of the empty circle, delete the dashed part in Figure 4, re-split the quadrilateral APBD into triangles ADP and BPD, and update the edge pointer related to the newly generated triangle according to the positional relationship of the triangles. The black arrows in Figure 4 still point to the triangles with common sides, so that the triangles ADP and BPD can find the adjacent common-sided triangles through the edge pointer. The bold part in Figure 4 originally points to the triangles ADB and ABP, but now points to the triangles ADP and BPD. . Finally, delete the co-edge triangles ABP and ADB, and then judge whether the newly generated triangles ADP and BPD conform to the Delaunay rule.

In the same way, similar to the case of inserting the insertion point on the common edge of the triangle, Delaunay's rule determines that different positional relationships of the co-sided triangle will also generate triangles ADP and BPD, but the edge pointers that need to be updated will be different. For example, if the original coedge triangle is ABP and ADB, then for triangle ADB, the pointer on the AD side should be the third side pointer; if the original coedge triangle is ABP and DBA, then for triangle DBA, the pointer on AD side should be For the first side pointer, at the same time, the other side pointers are also different. Other situations are similar, with different positional relationships, although the triangles generated by splitting are the same, the update of the edge pointers will be different. Among them, since the positional relationship of the tested triangle ABP is determined, it is not exactly the same as the positional relationship of inserting the insertion point on the common side of the triangle.

Example 2

Corresponding to the above method embodiments, this embodiment provides a triangulation system for a plane point set in a three-dimensional scan, including a memory, a processor, and a computer program stored in the memory and running on the processor, the The steps of the above-mentioned methods are implemented when the processor executes the computer program.

As described above, the triangulation method and system for a plane point set in a three-dimensional scan provided by the present invention firstly obtains the three-dimensional coordinate points of the target object to be reconstructed, maps the three-dimensional coordinate points to a plane point set, and traverses the plane point set to construct a The target triangle of all points in the plane point set, and then realize the division of the target triangle by continuously searching for new target triangles in the target triangle; the present invention allocates corresponding edge pointers to the target triangle, according to the insertion point and the corresponding triangle. The positional relationship of the edge pointers can find new target triangles in a directional manner, which can quickly realize the division of the original target triangles, obtain a triangular mesh, and then map the triangular mesh into a curved surface to fit the object to be reconstructed. The method and The system can improve the speed of finding new target triangles, and can better meet the real-time requirements of three-dimensional reconstruction.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. For those skilled in the art, the present invention may have various modifications and changes. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included within the protection scope of the present invention.

Claims (7)

1. The triangulation method of the plane point set in the three-dimensional scanning is characterized by comprising the following steps:

s1: acquiring three-dimensional coordinate points of a target object to be reconstructed, mapping the three-dimensional coordinate points into a plane point set, and traversing the plane point set to construct a target triangle containing all points in the plane point set;

s2: marking a first vertex, a second vertex and a third vertex for the target triangle according to a counterclockwise sequence, then allocating a first edge pointer to a connecting edge of the first vertex and the third vertex, allocating a second edge pointer to a connecting edge of the second vertex and the third vertex, and allocating a third edge pointer to a connecting edge of the first vertex and the second vertex;

s3: selecting a certain point in the plane point set as an insertion point, respectively connecting the insertion point with each vertex of the target triangle to obtain new triangles which are sequentially arranged after subdivision, completing the first triangulation to obtain a triangle network, deleting the subdivided target triangle, then updating the side pointer of each new triangle according to the method in the step S2, and sequentially storing the new triangles in a triangle chain table;

s4: selecting another point in the plane point set as an insertion point, inserting the insertion point into a corresponding triangle according to the side pointer relationship between the insertion point and the first triangle in the triangle chain table, regarding the inserted triangle as a new target triangle, respectively connecting the insertion point and each vertex of the target triangle, completing subdivision on the target triangle to obtain a new triangle, deleting the target triangle to update the triangle network, and simultaneously updating the side pointer of each triangle and the triangle chain table; then, sequentially judging whether each new triangle accords with a Delaunay empty circle rule, if so, entering a step S5, and if not, adjusting a connecting edge of the new triangle until the new triangle accords with the Delaunay empty compasses, and then entering a step S5;

s5: repeating the step S4 until all coordinate points are inserted, and obtaining the final triangular net to realize triangulation on the plane point set in the three-dimensional scanning;

in step S3, the inserting the insertion point into the corresponding triangle according to the edge pointer relationship between the insertion point and the first triangle in the triangle chain table specifically includes the following steps:

(31) judging whether the insertion point is positioned at the outer side of a first side pointer of the triangle, if so, searching a triangle with common sides according to the first side pointer of the triangle, if not, judging whether the insertion point is positioned at the outer side of a second side pointer of the triangle, if so, searching a triangle with common sides according to the second side pointer of the triangle, if not, judging whether the insertion point is positioned at the outer side of a third side pointer of the triangle, and if so, searching a triangle with common sides according to the third side pointer of the triangle;

(32) judging whether the insertion point is positioned in the triangle with the same side, if so, regarding the triangle with the same side as a target triangle, and inserting the insertion point into the target triangle; if not, adopting the method in the step (31) to continuously judge the relation between the insertion point and the edge pointer of the triangle sharing the edges until finding the target triangle of the insertion point.

2. The triangulation method for the plane point set in the three-dimensional scan according to claim 1, wherein in the step S3, the new triangle is sorted by: and arranging the sequence of each new triangle according to the sequence of the vertexes of the original triangle and the anticlockwise direction.

3. The triangulation method of the plane point set in the three-dimensional scan according to claim 1, characterized by, before the step (31), further comprising the steps of: judging whether the insertion point is positioned in the first triangle, if so, regarding the first triangle as a target triangle; if not, the step (31) is executed.

4. The triangulation method of the plane point set in the three-dimensional scan according to claim 3, wherein when the insertion point is located on the edge of the first triangle, all triangles where the insertion point falls on the edge are considered as the target triangle.

5. The triangulation method of the plane point set in the three-dimensional scan according to claim 4, wherein in the step S4, the deleting the target triangle to update the triangle mesh, and the updating the edge pointer of each triangle and the triangle chain table specifically comprises updating the edge pointer of the new triangle, updating the edge pointer of the triangle adjacent to the deleted target triangle, and updating the triangles stored in the triangle chain table; wherein:

the updating of the edge pointers of the triangles adjacent to the deleted target triangle specifically comprises the following steps: deleting the target triangle, and pointing the side pointer of the adjacent triangle which originally points to the deleted target triangle to the corresponding new triangle;

the updating of the triangles stored in the triangle linked list specifically comprises the following steps: and replacing the positions of the deleted target triangles in the triangular linked list by the generated new triangles arranged in sequence in the triangular linked list.

6. The triangulation method of the plane point set in the three-dimensional scan according to claim 5, wherein the step S4, sequentially determining whether each of the new triangles conforms to the Delaunay space compasses, comprises the following steps:

searching a triangle with common edges according to the third pointer of the new triangle, if the quadrangle formed by the searched triangle with the new triangle does not meet the Delaunay empty circle rule, deleting the common edges, connecting another diagonal line in the quadrangle to adjust the connecting edges of the new triangle, updating the edge pointer of the newly generated triangle, the edge pointer of the triangle adjacent to the deleted triangle and the triangle chain table, and judging each new triangle again.

7. Triangulation system of a set of planar points in a three-dimensional scan, comprising a memory, a processor and a computer program stored on the memory and executable on the processor, characterized in that the processor realizes the steps of the method of any of the preceding claims 1 to 6 when executing the computer program.

Images