An optimal algorithm for 3D triangle mesh slicing

We describe an algorithm for slicing an unstructured triangular mesh model by a series of parallel planes. We prove that the algorithm is asymptotically optimal: its time complexity is O(n logk + k + m) for irregularly spaced slicing planes, 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 time complexity 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 algorithm for constructing a set of polygons from the unsorted lists of line segments produced by the slicing step. The proposed algorithms are compared both theoretically and experimentally against known methods in the literature. (C) 2017 Elsevier Ltd. All rights reserved.