Construction of 3D Orthogonal Cover(A combinatorial algorithm to find the minimumvolume cover of a 3D voxel set using DCEL)Algorithm: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. 15711606, 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. 7083, 2011. The Idea:The orthogonal cover of a 3D digital object is a minimumvolume 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 breadthfirst 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 3cell and its corresponding grid point. Right: Three pairs of αadjacent 3cells for α=0,1,2; α=0,1; α=0 (from left to right). The 3cells 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 topleftfront point (red). Testing the eligibility of a face (g=3): Left: f_{k} intersects the object A; Mid: The UGC between f_{kg} and f_{k} has object occupancy but no object point is on f_{k}; Right: The UGC between f_{k} and f_{k+g} has object occupancy but no object point is on f_{k}. 
Some ResultsScrawl & click on the thumbnails below to see larger snapshots.


© Partha Bhowmick (April 2011) 