Algorithm for dividing a polyhedron with holes into constrained Delaunay tetrahedrons

To solve the problem of poor calculating efficiency caused by mass data existed in tetrahedral growth algorithm, the concept of a separating-plane is introduced while a separating-plane theorem, and theorems for segment-plane and triangle-plane disjoint tests are established. By transforming the segment-triangle disjoint test into the easier disjoint test between a separating-plane and triangle, a large amount of triangles to be intersected with a segment are eliminated efficiently, greatly shortening testing time. On the basis of the above theorems, a complete algorithm for a direct constrained-Delaunay tetrahedralization based on the boundaries of a polyhedron is presented. Experimental results show that the algorithm runs stably and correctly, has a higher level of automation because of less artificial intervention, and possesses higher efficiency compared with other similar algorithms.