An Optimal Algorithm for 3D Triangle Mesh Slicing and Loop-Closure

We describe in this paper an asymptotically optimal algorithm for slicing an unstructured triangular mesh model by a series of parallel planes, which is the most time-consuming step in the process planning for 3D printing. The algorithm allows arbitrary variable spacing between the slicing planes. Its running time is proportional to O(n log k + k + m), where n is the number of triangles, k is the number of slicing planes, and m is the number of triangle-plane intersections segments. The running time reduces to O(n + k + m) if the planes are uniformly spaced or the triangles of the mesh are given in the proper order. We also describe an asymptotically optimal linear time loop-closure algorithm for constructing a set of polygons from the resulting unsorted list of line segments. The proposed algorithms are compared both theoretically and experimentally against known methods in the literature