On the characterization of absentee-voxels in a spherical surface and volume of revolution in \({\mathbb Z}^3\).(English)Zbl 1386.68187
Summary: We show that the construction of a digital sphere by circularly sweeping a digital semi-circle (generatrix) around its diameter results in the appearance of some holes (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. In this paper, we 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 semi-circular 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. We also show how the proposed technique for absentee-filling can be used to generate a variety of digital surfaces of revolution by choosing an arbitrary curve as the generatrix. We further show that covering a solid sphereby a set of complete spheres also results to an asymptotically larger count of absentees, which is cubic in the radius of the sphere. A complete characterization of the absentee-voxels that aids the subsequent generation of a solid digital sphere is also presented. Test results have been furnished to substantiate our theoretical findings.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Software:
DDSCATCite
Full Text:DOI
References:
| [1] | Andres, E.: Discrete circles, rings and spheres. Comput. Graph. 18(5), 695-706 (1994) ·doi:10.1016/0097-8493(94)90164-3 |
| [2] | Andres, E., Jacob, M.: The discrete analytical hyperspheres. IEEE Trans. Visual. Comput. Graph. 3(1), 75-86 (1997) ·doi:10.1109/2945.582354 |
| [3] | Andres, E., Roussillon, T.: Analytical description of digital circles. In: Proceedings of the Discrete Geometry for Computer Imagery—16th IAPR International Conference, (DGCI’11), LNCS, vol. 6607, pp. 235-246 (2011) ·Zbl 1272.68349 |
| [4] | Bastl, B., Kosinka, J., Lávicka, M.: Simple and branched skins of systems of circles and convex shapes. Graph. Models 78, 1-9 (2015) ·doi:10.1016/j.gmod.2014.12.001 |
| [5] | Bera, S., Bhowmick, P., Bhattacharya, B.B.: A digital-geometric algorithm for generating a complete spherical surface in \[{\mathbb{Z}}^3\] Z3. In: Proceedings of the International Conference on Applied Algorithms (ICAA’14), LNCS, vol. 8321, pp. 49-61 (2014) ·Zbl 1259.65039 |
| [6] | Bera, S., Bhowmick, P., Stelldinger, P., Bhattacharya, B.B.: On covering a digital disc with concentric circles in \[{{\mathbb{Z}}^2}\] Z2. Theor. Comput. Sci. 506, 1-16 (2013) ·Zbl 1301.68235 ·doi:10.1016/j.tcs.2013.07.036 |
| [7] | Bhowmick, P., Bhattacharya, B.B.: Number theoretic interpretation and construction of a digital circle. Discret. Appl. Math. 156(12), 2381-2399 (2008) ·Zbl 1143.68614 ·doi:10.1016/j.dam.2007.10.022 |
| [8] | Biswas, R., Bhowmick, P.: On finding spherical geodesic paths and circles in \[{\mathbb{Z}}^3\] Z3. In: Proceedings of the Discrete Geometry for Computer Imagery, LNCS, vol. 8668, pp. 396-409. Springer (2014) ·Zbl 1417.68228 |
| [9] | Biswas, R., Bhowmick, P.: Layer the sphere—for accurate and additive voxelation by integer operation. Visual Comput. 31(6-8), 787-797 (2015) ·doi:10.1007/s00371-015-1101-3 |
| [10] | Biswas, R., Bhowmick, P.: On different topological classes of spherical geodesic paths and circles in \[{\mathbb{Z}}^3\] Z3. Theor. Comput. Sci. 605, 146-163 (2015) ·Zbl 1337.53048 ·doi:10.1016/j.tcs.2015.09.003 |
| [11] | Biswas, R., Bhowmick, P.: From prima quadraginta octant to lattice sphere through primitive integer operations. Theor. Comput. Sci. doi:10.1016/j.tcs.2015.11.018 ·Zbl 1338.68256 |
| [12] | Biswas, R., Bhowmick, P., Brimkov, V.E.: On the connectivity and smoothness of discrete spherical circles. In: Combinatorial Image Analysis—17th International Workshop, IWCIA, LNCS, vol. 9448, pp. 86-100 (2015) ·Zbl 1486.68205 |
| [13] | Biswas, R., Bhowmick, P., Brimkov, V.E.: On the polyhedra of graceful spheres and circular geodesics. Discret. Appl. Math. doi:10.1016/j.dam.2015.11.017 ·Zbl 1370.68295 |
| [14] | Brimkov, V.E., Barneva, R.P.: Graceful planes and lines. Theor. Comput. Sci. 283(1), 151-170 (2002) ·Zbl 1050.68147 ·doi:10.1016/S0304-3975(01)00061-5 |
| [15] | Brimkov, V.E., Barneva, R.P.: On the polyhedral complexity of the integer points in a hyperball. Theor. Comput. Sci. 406(1-2), 24-30 (2008) ·Zbl 1151.52010 ·doi:10.1016/j.tcs.2008.07.014 |
| [16] | Brimkov, V.E., Barneva, R.P., Brimkov, B.: Connected distance-based rasterization of objects in arbitrary dimension. Graph. Models 73, 323-334 (2011) ·doi:10.1016/j.gmod.2011.06.002 |
| [17] | Brimkov, V.E., Barneva, R.P., Brimkov, B., Vieilleville, F.: Offsetapproach to defining 3d digital lines. In: Proceedings of the 4th International Symposium on Advances in Visual Computing, ISVC ’08, pp. 678-687. Springer, Heidelberg (2008) |
| [18] | Brimkov, V.E., Coeurjolly, D., Klette, R.: Digital planarity—a review. Discret. Appl. Math. 155(4), 468-495 (2007) ·Zbl 1109.68122 ·doi:10.1016/j.dam.2006.08.004 |
| [19] | Chamizo, F.: Lattice points in bodies of revolution. Acta Arith. 85(3), 265-277 (1998) ·Zbl 0919.11061 |
| [20] | Chamizo, F., Cristobal, E.: The sphere problem and the \[L\] L-functions. Acta Math. Hung. 135(1-2), 97-115 (2012) ·Zbl 1294.11172 ·doi:10.1007/s10474-011-0144-9 |
| [21] | Chamizo, F., Cristóbal, E., Ubis, A.: Visible lattice points in the sphere. J. Number Theor. 126(2), 200-211 (2007) ·Zbl 1132.11051 ·doi:10.1016/j.jnt.2006.11.010 |
| [22] | Chamizo, F., Cristóbal, E., Ubis, A.: Lattice points in rational ellipsoids. J. Math. Anal. Appl. 350(1), 283-289 (2009) ·Zbl 1254.11092 ·doi:10.1016/j.jmaa.2008.09.051 |
| [23] | Chan, Y.T., Thomas, S.M.: Cramer-Rao lower bounds for estimation of a circular arc center and its radius. Graph. Models Image Process. 57(6), 527-532 (1995) ·Zbl 0853.68151 ·doi:10.1006/gmip.1995.1043 |
| [24] | Cheng, H.L., Shi, X.: Quality mesh generation for molecular skin surfaces using restricted union of balls. Comput. Geom. 42(3), 196-206 (2009) ·Zbl 1158.65014 ·doi:10.1016/j.comgeo.2008.10.001 |
| [25] | Christ, T., Pálvölgyi, D., Stojakovic, M.: Consistent digital line segments. Discret. Comput. Geom. 47(4), 691-710 (2012) ·Zbl 1259.65039 ·doi:10.1007/s00454-012-9411-y |
| [26] | Chun, J., Korman, M., Nöllenburg, M., Tokuyama, T.: Consistent digital rays. Discret. Comput. Geom. 42(3), 359-378 (2009) ·Zbl 1174.52008 ·doi:10.1007/s00454-009-9166-2 |
| [27] | Cochran, J.K.: Ceramic hollow spheres and their applications. Curr. Opin. Solid State Mater. Sci. 3(5), 474-479 (1998) ·doi:10.1016/S1359-0286(98)80010-7 |
| [28] | Davies, E.R.: A hybrid sequential-parallel approach to accurate circle centre location. Pattern Recognit. Lett. 7, 279-290 (1988) ·doi:10.1016/0167-8655(88)90068-2 |
| [29] | Doros, M.: On some properties of the generation of discrete circular arcs on a square grid. Comput. Vision Graph. Image Process. 28(3), 377-383 (1984) ·doi:10.1016/S0734-189X(84)80015-8 |
| [30] | Draine, B., Flatau, P.: Discrete dipole approximation for scattering calculations. J. Opt. Soc. Am. A 11, 1491-1499 (1994) ·doi:10.1364/JOSAA.11.001491 |
| [31] | Ewell, J.A.: Counting lattice points on spheres. Math. Intell. 22(4), 51-53 (2000) ·Zbl 1052.11508 ·doi:10.1007/BF03026771 |
| [32] | Feschet, F., Reveillès, J.P.: A generic approach forn-dimensional digital lines. In: Proceedings of the 13th International Conference on Discrete Geometry for Computer Imagery, DGCI’06, pp. 29-40. Springer, Heidelberg (2006) ·Zbl 1136.68570 |
| [33] | Fiorio, C., Jamet, D., Toutant, J.L.: Discrete circles: an arithmetical approach with non-constant thickness. In: Longin Jean Latecki, A.Y.W., David M. Mount (eds.) Vision Geometry XIV, Electronic Imaging, SPIE, vol. 6066, p. 60660C. San Jose, USA (2006) ·Zbl 1119.11046 |
| [34] | Fiorio, C., Toutant, J.L.: Arithmetic discrete hyperspheres andseparatingness. In: Proceedings of the 13th international conference on Discrete Geometry for Computer Imagery, DGCI’06, pp. 425-436. Springer, Heidelberg (2006) ·Zbl 1136.68571 |
| [35] | Foley, J.D., Dam, A.V., Feiner, S.K., Hughes, J.F.: Computer Graphics—Principles and Practice. Addison-Wesley, Reading (1993) ·Zbl 0875.68891 |
| [36] | Fomenko, O.: Distribution of lattice points over the four-dimensional sphere. J. Math. Sci. 110(6), 3164-3170 (2002) ·Zbl 1005.11043 ·doi:10.1023/A:1015484630940 |
| [37] | Fukshansky, L., Henshaw, G., Liao, P., Prince, M., Sun, X., Whitehead, S.: On integral well-rounded lattices in the plane. Discrete & Computational Geometry 48(3), 735-748 (2012) ·Zbl 1285.11098 ·doi:10.1007/s00454-012-9432-6 |
| [38] | Ghahramani, M., Garibov, A., Agayev, T.: Production and quality control of radioactive yttrium microspheres for medical applications. Appl. Radiat. Isot. 85, 87-91 (2014) ·doi:10.1016/j.apradiso.2013.12.009 |
| [39] | Guo, L., Dong, X., Cui, X., Cui, F., Shi, J.: Morphology and dispersivity modulation of hollow microporous spheres synthesized by a hard template route. Mater. Lett. 63(1314), 1141-1143 (2009) ·doi:10.1016/j.matlet.2009.01.064 |
| [40] | Haralick, R.M.: A measure for circularity of digital figures. IEEE Trans. Syst. Man Cybern. 4, 394-396 (1974) ·Zbl 0277.68063 ·doi:10.1109/TSMC.1974.5408463 |
| [41] | Heath-Brown, D.R.: Lattice Points in the Sphere. Number Theory in Progress. Walter de Gruyter, Berlin (1999) ·Zbl 0929.11040 |
| [42] | Hiller, J., Lipson, H.: Design and analysis of digital materials for physical 3D voxel printing. Rapid Prototyp. J. 15(2), 137-149 (2009) ·doi:10.1108/13552540910943441 |
| [43] | Honsberger, R.: Circles, squares, and lattice points. Math. Gems I, 117-127 (1973) |
| [44] | Kawashita, M., Shineha, R., Kim, H.M., Kokubo, T., Inoue, Y., Araki, N., Nagata, Y., Hiraoka, M., Sawada, Y.: Preparation of ceramic microspheres for in situ radiotherapy of deep-seated cancer. Biomaterials 24(17), 2955-2963 (2003) ·doi:10.1016/S0142-9612(03)00094-2 |
| [45] | \[K \ddot{\text{ u }}\] u¨hleitner, M.: On lattice points in rational ellipsoids: an omega estimate for the error term. In: Abhandlungen Aus Dem Mathematischen Seminar Der Universitat Hamburg vol. 70(1), pp. 105-111 (2000) ·Zbl 1025.11032 |
| [46] | Kenmochi, Y., Buzer, L., Sugimoto, A., Shimizu, I.: Digital planarsurface segmentation using local geometric patterns. In: Proceedingsof the 14th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI’08, pp. 322-333. Springer, Heidelberg (2008) ·Zbl 1138.68599 |
| [47] | Kim, O.: Rapid prototyping of electrically small spherical wire antennas. IEEE Transactions on Antennas and Propagation 62(7), 3839-3842 (2014) ·doi:10.1109/TAP.2014.2317489 |
| [48] | Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Digital Picture Analysis. Morgan Kaufmann Series in Computer Graphics and Geometric Modeling. Morgan Kaufmann, San Francisco (2004) ·Zbl 1064.68090 |
| [49] | Klette, R., Rosenfeld, A.: Digital straightness: a review. Discret. Appl. Math. 139(1-3), 197-230 (2004) ·Zbl 1093.68656 ·doi:10.1016/j.dam.2002.12.001 |
| [50] | Kulpa, Z.: On the properties of discrete circles, rings, and disks. Comput. Graph. Image Process. 10(4), 348-365 (1979) ·doi:10.1016/S0146-664X(79)80043-X |
| [51] | Kulpa, Z., Kruse, B.: Algorithms for circular propagation in discrete images. Comput. Vision Graph. Image Process. 24(3), 305-328 (1983) ·doi:10.1016/0734-189X(83)90058-0 |
| [52] | Kumar, G., Sharma, N., Bhowmick, P.: Wheel-throwing in digital space using number-theoretic approach. Int. J. Arts Technol. 4(2), 196-215 (2011) ·doi:10.1504/IJART.2011.039845 |
| [53] | Lipson, H., Pollack, J.B.: Automatic design and manufacture of robotic lifeforms. Nature 406, 974-978 (2000) ·doi:10.1038/35023115 |
| [54] | Maehara, H.: On a sphere that passes through \[n\] n lattice points. Eur. J. Combin. 31(2), 617-621 (2010) ·Zbl 1186.68507 ·doi:10.1016/j.ejc.2009.03.034 |
| [55] | Magyar, A.: On the distribution of lattice points on spheres and level surfaces of polynomials. J. Number Theor. 122(1), 69-83 (2007) ·Zbl 1119.11046 ·doi:10.1016/j.jnt.2006.03.006 |
| [56] | Mignosi, F.: On the number of factors of Sturmian words. Theor. Comput. Sci. 82(1), 71-84 (1991) ·Zbl 0728.68093 ·doi:10.1016/0304-3975(91)90172-X |
| [57] | Montani, C.; Scopigno, R.; Glassner, AS (ed.), Spheres-to-voxels conversion, 327-334 (1990), San Diego ·doi:10.1016/B978-0-08-050753-8.50070-X |
| [58] | Nagy, B.: Characterization of digital circles in triangular grid. Pattern Recognit. Lett. 25(11), 1231-1242 (2004) ·Zbl 1065.92047 ·doi:10.1016/j.patrec.2004.04.001 |
| [59] | Nakamura, A., Aizawa, K.: Digital circles. Comput. Vision Graph. Image Process. 26(2), 242-255 (1984) ·doi:10.1016/0734-189X(84)90187-7 |
| [60] | Pal, S., Bhowmick, P.: Determining digital circularity using integer intervals. J. Math. Imaging Vis. 42(1), 1-24 (2012) ·Zbl 1255.68262 ·doi:10.1007/s10851-011-0270-6 |
| [61] | Roget, B., Sitaraman, J.: Wall distance search algorithm using voxelized marching spheres. J. Comput. Phys. 241, 76-94 (2013) ·Zbl 1349.76643 ·doi:10.1016/j.jcp.2013.01.035 |
| [62] | Rossignac, J., Whited, B., Slabaugh, G., Fang, T., Unal, G.: Pearling: 3D interactive extraction of tubular structures from volumetric images. In: MICCAI Workshop on Interaction in Medical Image Analysis and Visualization (2007) ·Zbl 1206.65111 |
| [63] | Sene, F.F., Martinelli, J.R., Okuno, E.: Synthesis and characterization of phosphate glass microspheres for radiotherapy applications. J. Non Cryst. Solids 354(4244), 4887-4893 (2008) ·doi:10.1016/j.jnoncrysol.2008.04.041 |
| [64] | Stelldinger, P.: Image Digitization and its Influence on Shape Properties in Finite Dimensions. IOS Press, Amsterdam (2007) ·Zbl 1170.68044 |
| [65] | Thomas, S.M., Chan, Y.T.: A simple approach for the estimation of circular arc center and its radius. Comput. Vision Graph. Image Process. 45(3), 362-370 (1989) ·doi:10.1016/0734-189X(89)90088-1 |
| [66] | Toutant, J.L., Andres, E., Roussillon, T.: Digital circles, spheres and hyperspheres: from morphological models to analytical characterizations and topological properties. Discret. Appl. Math. 161, 2662-2677 (2013) ·Zbl 1291.68412 ·doi:10.1016/j.dam.2013.06.001 |
| [67] | Tsang, K.M.: Counting lattice points in the sphere. Bull. Lond. Math. Soc. 32, 679-688 (2000) ·Zbl 1025.11033 ·doi:10.1112/S0024609300007505 |
| [68] | Wang, C., Liu, Z., Liu, L.: As-rigid-as-possible spherical parametrization. Graph. Models 76(5), 457-467 (2014) ·doi:10.1016/j.gmod.2014.03.016 |
| [69] | Woo, D.M., Han, S.S., Park, D.C., Nguyen, Q.D.: Extraction of 3d line segment using digital elevation data. In: Proceedings of the2008 Congress on Image and Signal Processing, CISP’08, vol. 2, pp. 734-738. IEEE Computer Society, Washington, DC, USA (2008) ·Zbl 1301.68235 |
| [70] | Yuen, P.C., Feng, G.C.: A novel method for parameter estimation of digital arc. Pattern Recognit. Lett. 17(9), 929-938 (1996) ·doi:10.1016/0167-8655(96)00050-5 |
| [71] | Zheng, M., Cao, J., Chang, X., Wang, J., Liu, J., Ma, X.: Preparation of oxide hollow spheres by colloidal carbon spheres. Mater. Lett. 60(24), 2991-2993 (2006) ·doi:10.1016/j.matlet.2006.02.030 |
| [72] | Zubko, E., Petrov, D., Grynko, Y., Shkuratov, Y., Okamoto, H., Muinonen, K., Nousiainen, T., Kimura, H., Yamamoto, T., Videen, G.: Validity criteria of the discrete dipole approximation. Appl. Opt. 49(8), 1267-1279 (2010) ·Zbl 1187.62108 ·doi:10.1364/AO.49.001267 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
