Connected distance-based rasterization of objects in arbitrary dimension
Graphical abstract
Highlights
► We consider the cases when the digitized set is a curve, surface, and an arbitrary pathconnected object. ► We determine the minimal value of the offset radius which guarantees connectedness of the digitization. ► We also derive conditions under which the offset digitization of a disconnected object is always connected.
Introduction
An important problem in computer graphics is obtaining a reasonable rasterization of an object (a subset of or ), such as a curve or a surface, by selecting pixels (in 2D) or voxels (in 3D) along the curve or the surface, so that the obtained discrete set properly approximates the original one, and a specific connectivity of the approximation is guaranteed.
The first ideas and results date back to C.F. Gauss (see, e.g., [30]). Another early contributor is Jordan [24]. Since then, a substantial body of literature impossible to report here has been developed on the subject. In modern times, one of the earlier contributions is Gouraud’s method for line rasterization [20]. For other basic contributions the reader is referred to [10], [13], [25], [26]. Considerable amount of work has been devoted to algorithms for rasterization of special classes of objects, such as straight lines (both in 2D and 3D), circles, ellipses, planes, and spheres [2], [15], [16], [18], [23], [27], [33]. In all these, assuring connectivity of a digital curve/surface is paramount.
A basic approach to modeling curves and surfaces in computer-aided geometric design is the one based on computing the offset of a curve/surface Γ – the locus of points at a given distance d from Γ (see, e.g., [6], [8], [22] and the bibliography therein). As a rule, these sorts of considerations resort to results from algebraic geometry, such as Grobner basis computation (see, e.g., [5], [14]). Note, however, that usually, when looking for a curve/surface offset defined by a distance d, one is not concerned with the properties of the set of integer points enclosed by the offset. Exceptions (in 2D) are provided, e.g., by some recent works that define digital conics [16], [19].
In view of the above, it would indeed be quite natural to define a digital curve or surface through a distance-based rasterization, which consists of the integer points within an offset of a continuous curve/surface. In fact, this is the idea behind the definitions of a digital (arithmetic) line and plane, which consists of the integer points that belong to a strip determined by two parallel lines/planes at an appropriate distance from each other, so that the obtained sets of pixels/voxels are connected. The offset approach has also been used to define digital circles and spheres, whose connectivity properties have been studied as well [1], [4]. It would certainly be useful to know more about the pros and cons of digital curves and surfaces obtained by the offset approach.
We remark at this point that the related terminology used in different research disciplines is far from uniform. For example, what is known as “object rasterization” in computer graphics and related engineering fields, is called “object digitization” in digital geometry and “the set of integer points in a subset of ” in mathematics. We will use these terms interchangebly according to the specific context (e.g., proof of a theorem or discussion about applications). Since in spirit and content the present paper is closest to the area of digital geometry, we will mainly conform to the term “object digitization.” We will also interchangebly use the terms “distance-based rasterization” and (more often) “offset digitization” (for short).
In the present paper we first provide a complete answer (from a digital geometry point of view) to the most fundamental theoretical questions concerning offset digitization of a curve. We show that, in dimension n, if the offset radius is greater than or equal to , then the obtained digital curve features maximal connectivity. We also demonstrate that the radius value is the minimal possible value which always guarantees such a connectivity. Moreover, we prove that a radius length greater than or equal to guarantees 0-connectivity, and that this is the minimal possible value with this property. All results apply to digitizations of arbitrary curves in an arbitrary dimension. Thus, we answer the question about the minimal offset size that guarantees maximal or minimal connectivity of an offset digital curve. As a corollary, we obtain a similar result for the case of an arbitrary path-connected set.
We consider the special cases of hypersurfaces and hyperplanes in view of the questions about their connectivity and presence of gaps and tunnels. We also consider the case of an arbitrary (not necessarily path-connected) set and derive conditions under which its offset digitization is always connected.
The paper is organized as follows. In the next section we recall some basic notions of digital geometry to be used in the sequel. We also prove some subsidiary lemmas. In Section 3 we present the main results about offset digitization of a curve and of an arbitrary path-connected set. In Section 4 we extend the results to hypersurfaces and hyperplanes. In Section 5 we present results on connected offset digitization of a disconnected set. We conclude with some final remarks in Section 6.
Section snippets
Some definitions and notations
Throughout we conform to terminology used in [28] (see also [29], [34]).
Our considerations take place in the grid cell model which consists of the grid cells of , together with the related topology. In this model, a regular orthogonal grid subdivides into n-dimensional hypercubes (e.g., unit squares for n = 2 or unit cubes for n = 3, also considered as n-cells) defining a class . These are usually called hypervoxels, or voxels, for short. Let be the class of all k-dimensional cells
Offset digitization of curves
Digital curves appear to be basic primitives in digital geometry. They have been used in volume modeling as well as in certain algorithms for image analysis, in particular in designing discrete multigrid convergent estimators [11], [17], [35]. In this section we investigate the offset approach to curve digitization.
First we provide a dynamic geometric interpretation of the concept of offset. It will be instrumental to the proof of the main results which are presented afterward.
Offset digitization of a Jordan surface: gaps and tunnels
A Jordan surface is defined by a parametrization Γ(u, v) = (x(u, v), y(u, v), z(u, v)), where x, y, and z are continuous functions. This parametrization establishes a homeomorphism with the surface of a unit sphere. So, a Jordan surface is a closed, hole-free surface. See [28] (Section 7.4) for a more detailed discussion.
Let be a Jordan surface and D(S, r) its r-offset digitization. By the Jordan theorem for surfaces [28], S partitions into two sets: interior int(S) and exterior ext(S) with
Connected offset digitizations of disconnected sets
In this section we consider the general case of arbitrary (not necessarily connected) sets.
Let M be a closed disconnected subset of . Let Mi, i ∈ Λ, be the connected components of M, where Λ = {1, 2, … , m} for some positive integer m. Denote by Δj(M), j = 0 or n − 1, the minimal value of an offset radius for which D(M, Δj(M)) is j-connected. We call Δj(M) the radius of offset j-connectivity of M. The rest of this section will be devoted to Δj(M) estimation. As Fig. 10 (left) demonstrates, given a
Concluding remarks
In this paper we investigated an offset approach for obtaining a connected digitization of a subset of . We obtained exact bounds on the radius length that guarantees connectivity of the digitization. The results apply to objects of different types, such as curves, surfaces, path-connected or disconnected objects.
An interesting theoretical question is whether there is a more efficient way to compute the radius of offset connectivity in view of the considerations of Section 5. Computer
Acknowledgments
The authors thank an anonymous referee and Jarek Rossignac for some useful remarks and suggestions. Some of the results presented in this paper have been reported at the 2nd International Symposium “Computational Modeling of Objects Represented in Images: Fundamentals, Methods, and Applications, May 5–7, 2010, Buffalo, NY, USA, and the 15th IAPR International Conference on Discrete Geometry for Computer Imagery, September 30–October 2, 2009, Montreal, Canada.
References (36)
Discrete circles, rings and spheres
Computers & Graphics
(1994)Discrete linear objects in dimension n: the standard model
Graphical Models
(2003)- et al.
Discrete analytical hyperplanes
Graphical Models Image Processing
(1997) - et al.
Skeletons of planar patterns
- et al.
Genus formula for generalized offset curves
Journal of Pure and Applied Algebra
(1999) - et al.
Linear segmentation of discrete curves into blurred segments
Discrete Applied Mathematics
(2005) - et al.
Digital representation schemes for 3D curves
Pattern Recognition
(1997) - et al.
Topological simplification of isosurfaces in volumetric data using octrees
Graphical Models
(2008) - et al.
The discrete analytical hyperspheres
IEEE Transactions on Visualization and Computer Graphics
(1997) - F. Anton, Voronoi diagrams of semi-algebraic sets, Ph.D. thesis, The University of British Columbia, Vancouver, British...