Algorithm for Dividing a Polyhedron with Holes intoConstrained Delaunay Tetrahedrons

Objective To solve the problem of poor calculating efficiency caused by mass data existed in tetrahedralgrowth 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 thesegment-triangle disjoint test into the easier disjoint test between a separating-plane and triangle,alarge amount of triangles to be intersected with a segment are eliminated efficiently,greatly shorten-ing 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 re-sults show that the algorithm runs stably and correctly,has a higher level of automation because ofless artificial intervention,and possesses higher efficiency compared with other similar algorithms.