Construction of 3D Orthogonal Cover

(A combinatorial algorithm to find the minimum-volume cover of a 3D voxel set using DCEL)


N. Karmakar, A. Biswas, P. Bhowmick, and B.B. Bhattacharya,
A Combinatorial Algorithm to Construct 3D Isothetic Covers, International Journal of Computer Mathematics, Vol. 90(8), pp. 1571-1606, 2013.

A preliminary version appeared in:
Construction of 3D Orthogonal Cover of a Digital Object, 14th International Workshop on Combinatorial Image Analysis: IWCIA'11, Madrid, Spain, Lecture Notes in Computer Science (LNCS), Springer, Vol. 6636, pp. 70-83, 2011.

The Idea:

The orthogonal cover of a 3D digital object is a minimum-volume 3D polytope having surfaces parallel to the coordinate planes, and containing the entire object so as to capture its approximate shape information. We have designed an efficient algorithm for construction of such an orthogonal cover imposed on a 3D background grid. A combinatorial technique is used to classify the grid faces constituting the polytope while traversing along the surface of the object in a breadth-first manner. The eligible grid faces are stored in a doubly connected edge list (DCEL), using which the faces are finally merged to derive the isothetic polygons parallel to the coordinate planes, thereby obtaining the orthogonal cover of the object. The complexity of the cover decreases with increasing grid size. The algorithm requires computations in integer domain only and runs in a time linear in the number of voxels constituting the object surface.

Theoretical Foundation:

3D digital space and 26N. Left: A 3-cell and its corresponding grid point. Right: Three pairs of α-adjacent 3-cells for α=0,1,2; α=0,1; α=0 (from left to right). The 3-cells in each of these three pairs are connected in 26N.

A voxel set A (left) and its corresponding orthogonal cover for g=2 (right).

Defining the start vertex from the top-left-front point (red).

Testing the eligibility of a face (g=3):
Left: fk intersects the object A;
Mid: The UGC between fk-g and fk has object occupancy but no object point is on fk;
Right: The UGC between fk and fk+g has object occupancy but no object point is on fk.

Some Results

Scrawl & click on the thumbnails below to see larger snapshots.

© Partha Bhowmick (April 2011)