Rodrigo Minetto ,   Neri Volpato,    Jorge Stolfi ,   Rodrigo M. M. H. Gregori,    Murilo V. G. da Silva
Federal University of Technology - Paraná, DAINF, Curitiba, Brazil
University of Campinas, Institute of Computing, Campinas, Brazil
An Optimal Algorithm for 3D Triangle Mesh Slicing
R. Minetto, N. Volpato, J. Stolfi, R.M.M.H. Gregori and M.V.G. da Silva, pp. 1-10, 2017
Computer-Aided Design (CAD), Elsevier.
http://dx.doi.org/10.1016/j.cad.2017.07.001
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 log k + 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.