An optimal algorithm for 3D triangle mesh slicing

作者：Minetto Rodrigo^*; Volpato Neri; Stolfi Jorge; Gregori Rodrigo M M H; da Silva Murilo V G

来源：Computer-Aided Design, 2017, 92: 1-10.

DOI：10.1016/j.cad.2017.07.001

• Additive manufacturing
• Triangle-plane intersection
• Contour construction algorithm
• Algorithm complexity
• Process planning

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.

• 出版日期2017-11