An optimal algorithm for 3D triangle mesh slicing. (November 2017)

• Record Type: Journal Article
• Authors: Minetto, Rodrigo; Volpato, Neri; Stolfi, Jorge; Gregori, Rodrigo M.M.H.; da Silva, Murilo V.G.
• Is Part Of: Computer aided design. Volume 92(2017)
• Page Start: 1
• Page End: 10
• Publication Date: 2017-11
• Subjects: Additive manufacturing -- Triangle–plane intersection -- Contour construction algorithm -- Algorithm complexity -- Process planning; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2017.07.001
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: 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. Highlights: This paper describes novel algorithms for the triangle mesh slicing and contour construction problems. The slicing algorithm uses a sweeping plane strategy highly simplified and optimized for unstructured triangle sets. The contour construction algorithm uses a hash table strategy to assemble polygons in linear time. A remarkable improving in execution time was achieved in relation to other algorithms from the literature. Considerable contribution in the process planning for areas such as medicine where the meshes have large number of triangles.