Algorithm of Triangulation in 3D

In this algorithm, you will need list of points of polygon in sequence and you will also need a normal value of the plane with which you will able to know the direction of the plane in 3D.

Step 1:

First of all you have to rotate the plane to make it parallel to XZ plane. For doing so you need to find the angle of plane with X- Axis (say xAng) and Y- Axis (say yAng). Angle can be found using normal value of the plane. Then rotate the plane on X-Axis up to degree xAng and same way rotate the plane on Y-Axis up to degree yAng so that it will be parallel to XZ plane.

Step 2:

Start the loop from first point of polygon up to last point. In each loop you need to take 2 lines i.e. three points (say pt1, pt2, pt3) which will make two lines (pt1, pt2) and (pt2, pt3). We will call these lines as line1 and line2 for convenience.

Step 3:

For making the decision that these two lines will create the triangle or not you need two confirm two things:

The interior angle created by these two lines is convex.
There is no any other point which lies inside of the triangle generated by these two lines

Step 4:

If both these situation are valid then add all three points as one triangle into final list of triangle and replace points of line1 and line2 with new single line created from points (pt1, pt3) in the original list of points.

Step 5:

If any of the two situations is false then go back to step 3 taking new points as pt2, pt3 and pt4 making two lines. Here, we skip line1 as it is and again process with line2 which will become line1 in step 3 and a new line which will become line2 in step 3.

Step 6:

Continue these steps until there are less than 3 points in the original list which are insufficient for making a triangle. So, finally you will get a list of points in which number of points will be multiple of 3 as for each triangle we added three points.

This algorithm is similar to the ear clipping algorithm, but the limitation of this algorithm is that it is not able to triangulate the polygon with overlapping lines.

-
About the Author:
Software Developer,(MCA)
Gujarat,
India.
Article Source