Elsevier

Graphical Models

Volume 73, Issue 6, November 2011, Pages 323-334
Graphical Models

Connected distance-based rasterization of objects in arbitrary dimension

https://doi.org/10.1016/j.gmod.2011.06.002Get rights and content

Abstract

In this paper we investigate an approach for constructing a connected digitization of an object SRn by taking the integer points within an offset of S of a certain radius. We consider the cases when S is a curve, surface, and an arbitrary path-connected object. We determine the minimal value of the offset radius which guarantees connectivity of the digitization. We also derive conditions under which the offset digitization of a disconnected object is always connected.

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 R2 or R3), 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 Rn” 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 n/2, then the obtained digital curve features maximal connectivity. We also demonstrate that the radius value n/2 is the minimal possible value which always guarantees such a connectivity. Moreover, we prove that a radius length greater than or equal to n-1/2 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 Zn, together with the related topology. In this model, a regular orthogonal grid subdivides Rn 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 Cn(n). These are usually called hypervoxels, or voxels, for short. Let Cn(k) 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 SRn be a Jordan surface and D(S, r) its r-offset digitization. By the Jordan theorem for surfaces [28], S partitions Rn 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 Rn,n2. 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 Rn. 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)

  • F. Anton et al.

    The offset to an algebraic curve and an application to conics

  • G. Beer

    Topologies on Closed and Closed Convex Sets

    (1993)
  • J.E. Bresenham

    Algorithm for computer control of a digital plotter

    ACM Transaction on Graphics

    (1965)
  • D. Coeurjolly et al.

    Segmentation and length estimation of 3D discrete curves

  • R. Engelking

    General Topology

    (1989)
  • D. Cohen-Or et al.

    3D line voxelization and connectivity control

    IEEE Computer Graphics & Applications

    (1997)
  • D. Cox et al.

    Using Algebraic Geometry

    (1998)
  • I. Debled-Rennesson, Etude et reconnaissance des droites et plans discrets, Ph.D. thesis, Université Louis Pasteur,...
  • Cited by (0)

    View full text