Finding the largest empty cuboid inside a 3D digital object

doi:10.1007/s11042-020-10490-8

2021-02-05

PRE

Sharmistha Mondal *

Arindam Biswas

Apurba Sarkar

DOI：10.1007/s11042-020-10490-8

原文链接

原文求助

摘要

En 中文

The largest empty cuboid (LEC) which is axis-parallel, placed inside a 3D digital object against the background grid, captures the characteristics of the object and depicts the centrality of its shape. An efficient algorithm to determine the LEC inside a 3D digital object has been proposed here. The LEC, analogous to the largest rectangle (LR) in a 2D polygon, reveals the structure of an object in 3D. Primarily, we find the intersection polygon of the slice polygons, which are obtained from the isothetic inner cover of the digital object, at two or more consecutive levels. Starting with the bottom-most slice polygon, first we find its intersection polygon with the slice polygon at the next higher level, then the intersection of the resulting intersection polygon with the next higher level is obtained, and so on, until we reach the topmost slice. Each time, the largest rectangle inscribed inside the intersection polygon is determined and the volume of the corresponding candidate LEC is obtained by multiplying the area with the corresponding height. The above procedure is repeated starting with the slice polygon at each level. The maximum of these candidate LECs is reported. The best case computational complexity of the proposed algorithm is O(n(3/2)), where n is the number of voxels on the surface of the object. The experimental results on a variety of objects demonstrate that the central portion of the shape is captured by the LEC. Apart from the digital object, the algorithm can be used to find the LEC where we deal with isothetic polytope like 3D printing and modular construction.

Keyword:

Isothetic inner cover

Slicing

Intersection polygon

Largest rectangle

Largest empty cuboid