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(nlogk+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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.cad.2017.07.001 | Computer-Aided Design |
Keywords | Field | DocType |
Additive manufacturing,Triangle–plane intersection,Contour construction algorithm,Algorithm complexity,Process planning | Line segment,Discrete mathematics,Combinatorics,Polygon,Algorithm complexity,Slicing,Algorithm,Time complexity,Asymptotically optimal algorithm,Mathematics,Triangle mesh | Journal |
Volume | ISSN | Citations |
92 | 0010-4485 | 1 |
PageRank | References | Authors |
0.36 | 8 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Rodrigo Minetto | 1 | 178 | 15.01 |
Neri Volpato | 2 | 1 | 1.37 |
Jorge Stolfi | 3 | 1559 | 296.06 |
Rodrigo M. M. H. Gregori | 4 | 1 | 0.36 |
Murilo V.G. da Silva | 5 | 29 | 6.03 |