On Complete Spherical Surface in ℤ3

Algorithm

S. Bera, P. Bhowmick, and B. B. Bhattacharya, A Digital-geometric Algorithm for Generating a Complete Spherical Surface in ℤ3, International Conference on Applied Algorithms (ICAA'14), Kolkata, January 13-15, 2014 (to appear in LNCS, Springer).

Our Contribution

Majority of works in 3D digital space are extended manifestations of similar works on characterization and generation of circles, rings, discs, and circular arcs in the digital plane. The reason of reconceptualization of these geometric primitives in the digital space is that their properties in the Euclidean/real space are often inadequate and inappropriate to efficiently solve the related problems in the digital space. Hence, with the emergence of new paradigms, such as digital geometry, proper characterization is required to enrich our understanding and hence enhance these paradigms as well. Our work is focused on such a characterization, which helps in designing an efficient algorithm for generation of spheres in the discrete space.

We show that the construction of a digital sphere by circularly sweeping a digital semicircle—acting as the generatrix—around its diameter results in appearance of absentee voxels in its spherical surface of revolution. This incompleteness calls for a proper characterization of the absentee voxels whose restoration in the surface of revolution can ensure the required completeness.

We first present a characterization of the absentee voxels using certain techniques of digital geometry and show that their count varies quadratically with the radius of the semicircular generatrix. Next, we design an algorithm to fill up the absentee voxels so as to generate a spherical surface of revolution, which is complete and realistic from the viewpoint of visual perception. The proposed technique will find many potential applications in computer graphics and 3D imaging.

Our theoretical analysis indicates that the ratio of the absentee voxels to the total number of voxels tends to a constant for large radius. Knowledge of geometric distributions of absentee voxels is shown to be useful for algorithmic generation of a digital sphere of revolution. An asymptotic tight bound for the count of absentees is given, but finding a closed-form solution on the exact count of absentees for a given radius still remains an open problem. Characterization of these absentees requires further in-depth analysis, especially if we want to generate a solid digital sphere with concentric digital spheres.

Apart from spheres, generation of various other types of surfaces of revolution, which should be free of any absentee voxels, has also many applications in 3D imaging and graphics, such as creation of interesting pottery designs, as shown in some recent works.

Figure above: A hemisphere of revolution for r = 10 containing absentee voxels.
Figure left: Correspondence of absentee voxels with those in a disc cover.