11.1.1 Grid-plane intersection digitization

Using the approach in Section 2.3.5, the 3D grid-plane intersection digitization of γ in is where the following is true:

γ can intersect a grid plane in such a way that up to four grid points are closest to the intersection point. As is the case in 2D grid-intersection digitization, we exclude such cases by selecting one of these grid points using some decision rule. The resulting 3D DSL is the doubly infinite sequence …,q₋₁,q₀,q₁,… of center points (grid points in Z³) of the 3-cells in ).

A (26-) DSL segment (3D DSS or 26-DSS) is a finite subsequence of a 3D DSL. Evidently, a 3D DSS is a simple 26-arc. Arational 3D DSL is the digitization of a rational straight line γ = {(β_x +α_xt, β_y +α_yt, β_z +α_zt): t ∈ R}; here β = (β_x,β_y,β_z) ∈ R³ can be arbitrary, but the slopes α_x,α_y, and α_z must be rational.

The conditions for 2D straightness discussed in Chapter 9 can be extended to 3D. For example, S ⊆ Z³ has the chord property, iff for any p,q ∈ S, every point on the straight line segment pq ⊂ R³ is at L_∞ -distance < 1 from some point of S. (We recall that the Minkowski metric L_∞ coincides with d₂₆ on Z³.) It can be shown [511] that a simple 26-arc is a 3D DSS iff it has the chord property. In [511], the following theorem is also proved:

Either of these projections may be a single grid point; the third projection may not even be a simple 8-arc. Figure 11.1 illustrates projections of 26-DSSs.

Theorem 11.1 provides a straightforward method of recognizing 26-DSSs and, therefore, of segmenting a 26-arc into a sequence of maximum-length 26-DSSs. We project the given 26-arc onto the three planes and apply 8-DSS recognition to the projections; we continue as long as 8-DSS recognition is successful for at least two of the projections.

11.1.2 Arithmetic geometry

3D DSSs are defined in arithmetic geometry by linear Diophantine inequalities; see Section 9.2. A 3D digital line is characterized by relatively prime integers a, b, and c (where 0 ≤ c ≤ b ≤ a) that correspond to the coordinates x, y, and z in that order. For other orders of a, b, and c, we can permute the coordinates.

The parameters μ₁ and μ₂ are called the lower bounds of G, and the parameters ω₁ and ω₂ define its arithmetic thickness.

LetG be a 3D arithmetic line defined bya, b, c,μ₁,μ₂,ω₁,ω₂ ∈ Z where 0 ≤c < b <a. Then the following are true:

(11.1)

(11.2)

(11.3)

(11.4)

G is called a 3D naive line iff ω₁ = ω₂ = max{|a|, |b|, |c|} = a. When c = 0, G is a (2D) naive line, as in Chapter 9 If c> 0, in accordance with Equation 11.4, G is 26-connected. c ≤ b ≤ a corresponds to the following parameterization of G, using parameter x only:

Evidently, a 3D naive line is an unbounded simple 26-arc. It is provided in [203] that the following is true:

This theorem and Theorem 11.1 imply the following:

11.1.3 A linear online 3D DSS segmentation algorithm

Corollary 11.1 justifies the following 3D DSS segmentation algorithm, which uses the (C2.1a) approach that was defined in Chapter 9 (Theorem 9.4) and that was originally published in [256].

We consider a projection of the given 26-curve into one of the (x = 0)-, (y = 0)-, or (z = 0)-planes. Without loss of generality, assume an 8-curve in the (z = 0)-plane; this allows us to suppress the z-coordinate. The grid points (x, y) on a DSS must satisfy the following condition,

where a and b are relatively prime integers and μ is an integer. We describe the calculation of a, b, and μ.

11.1.4 MLPs of simple 2-curves

In this section, we consider DSLs in the 3D incidence grid. The outer 3D Jordan digitization of a straight line γ ⊂ R³ is a finite set of 3-cells. We also use grid vertices, edges, and faces in the following discussion. We assume that γ is not incident with any grid vertex; it follows that the DSL is a 2-arc in the 3D grid cell model.

A 2-curve in C³ can be represented as an alternating sequence ρ = (f₀,c₀,f₁,c₁, …,f_n,c_n) of faces f_i and cubes c_i (0 ≤ i ≤ n) such that f_i and f_{i + 1} are sides of c_i and f_{n + 1} = f₀. A 2-arc ξ is a 2-connected subsequence of 3-cells starting at a face f_i and ending at a face f_j ≠ f_i. Evidently,ξ is a DSL (with respect to outer 3D Jordan digitization) iff there is a straight line segment in R³ that has endpoints in f_i and f_j and that is contained in the union of the 3-cells of ξ, so f_i is visible from f_j (and vice versa) in ξ.

The 3D DSL segmentation problem is defined as follows: starting at one 3-cell of a 2-curve ρ, segment the 2-curve into consecutive maximum-length 2-arcs that are DSSs, where the endvoxel of each DSS is the startvoxel of the next DSS. In the rest of this section, we discuss how to solve this problem by calculating an MLP “within ρ.”

We assume from now on that ρ is simple. This is equivalent to assuming that n ≥ 4, and, for any two cubes c and c_k in ρ such that |i – k| ≥ 2 (mod n + 1), if c_i ∩ c_k ≠ø, then either |i – k| = 2 (mod n + 1) and c_i ∩ c_k is an edge or |i – k| = 3 (mod n + 1) and c_i ∩ c_k is a vertex.

The union M_ρ of all of the cubes in ρ is called the tube of p; it is a compact polyhedron and is homeomorphic to a torus if ρ is simple.

A simple 2-curve is called complete in M_p iff it has a nonempty intersection with any cube of ρ. A nonplanar simple 2-curve in R³ determines exactly one MLP that is complete and contained in its tube. For planar simple 2-curves, the MLP is not uniquely determined, but such curves can be treated like 1-curves in [², ≤].

There is no straightforward way to extend 2D MLP algorithms to 3D. One reason is that the vertices of 2D MLPs are vertices of the given polygons, whereas a 3D MLP can have vertices with irrational coordinates, even if it is contained in a tube that has only grid point vertices.

Let ρ be a simple 2-curve, and let Π= (p₀,p_v…,p_m) (where p₀ = p_m) be a polygon that is complete and contained in M_p.

The curves on the left and right in Figure 11.5 are not contractible into single points in M_ρ, but the curve in the middle is contractible.

A simple curve γ passes through a face f iff there exist t₁,t₂, and T such that {γ (t): t₁ ≤ t ≤ t₂}⊆ f,γ(t₁ –) ∉ f and γ (t₂ +) ∉ f for all such that 0 < ≤ T. During a traversal of γ, we enter a cube c at γ(t₁) ∈ c if γ(t₁ –) ∉ c, and we leave c at γ(t₂) ∈ c if γ(t₂ +) ∉ c for all such that 0 < ≤ T. A traversal is defined by a starting vertex p₀ of γ and a direction.

Let C_ρ = (c₀,c₁,…,c_n) be the sequence of cubes of ρ in the order in which they are entered during curve traversal. If a polygon Π is complete and contained in M_ρ, C_ρ contains all of the cubes of ρ and no other cubes.

Let Π= 〈p₀,p₁,…,p_m〉 be a polygon contained in a tube M_ρ. A polygon Q is called an M_ρ-transform of Π iff Q can be obtained from Π by a finite number of steps, each of which is a replacement of a triple a, b, c of vertices by a polygonal arc a,b₁,…,b_k,c contained in the same set of cubes of ρ as a,b,c. (k = 0 means deletion of b; k = 1 means a move of b within M_ρ; and k ≥ 2 means replacement of two straight line segments with a sequence of k + 1 straight line segments that are all contained in M_ρ.)

An edge contained in a tube M_ρ is called critical iff the edge is the intersection of three cubes contained in ρ. Figure 11.6 illustrates critical edges of two 2-curves; only the left one is simple.

Note that simple 2-curves have edges that are contained in at most three cubes. For example, the curve consisting of four cubes only (an edge is contained in four cubes in this case) was excluded by the constraint n ≥ 4.

Note that this theorem also applies to planar simple 1-curves in [C², ≤]. It follows that MLP vertices on such a 1-curve can only be convex vertices of the inner frontier or concave vertices of the outer frontier, because these are the only vertices incident with three squares of the 1-curve.

11.1.5 The rubber band algorithm

This algorithm, which is from [148], is based on the following physical model. Suppose a rubber band passes through the tube M_ρ. If it can move freely, it will contract to the MLP, which is complete and contained in M_ρ, assuming it is smooth enough to slide over the critical edges of the tube.

The algorithm consists of two subprocesses. The first is an initialization process that defines a simple polygonal curve Π₀ that is complete and contained in M_ρ and such that C_Π0 contains each cube of ρ just once (see Lemma 11.2). The second is an iterative process (a M_ρ-transform; see Lemma 11.3) in which each iteration transforms Π_t into Π_{t + 1} (t ≥ 0) such that l (Π_t) ≥ l(Π_{t + 1}). Thus the resulting polygon is also complete and contained in ρ.

The following are three methods of initializing the polygon. Init I: The vertices of the initial polygon are at the centers of the cubes that constitute the 2-curve. Init II: The vertices are at the midpoints of critical edges. Init III: The initial polygon connects only vertices that are endpoints of consecutive critical edges.

For Init III, we scan the curve until we find a pair (e₀,e₁) of consecutive critical edges that are not parallel or (if parallel) that are not in the same grid layer. (Figure 11.6 (right) shows a nonsimple 2-curve; searching for a pair of noncoplanar edges would be insufficient in this case.) For such a pair (e₀,e₁), we choose vertices (p₀,p₁), where p₀ bounds e₀ and p₁ bounds e₁ such that the line segment p₀p₁ has minimum length; note that (p₀,p₁) is not always uniquely defined. This is the first line segment of the initial polygon Π₀.

Suppose p_{i −1} p_i is the last line segment on the Π₀ specified so far, where p_i bounds e_i. Then there is a unique vertex p_{i + 1} on the next critical edge e_{i + 1} such that p_ip_{i + 1} has minimum length. (Length zero is possible if p_{i + 1} = p_i; in this case, we skip p_{i + 1}, which means that we do not increase i.) Note that this p_ip_{i + 1} will always be included in the tube, because the centers of all cubes between two consecutive critical edges are collinear. The process stops when we connect p_n (on e_n) with p₀. (Note that a minimum-distance criterion for this final step might prefer a line segment between p_n and the second vertex bounding e₀ [i.e., not p₀]). Table 11.1 shows the list of vertices for the curve on the left in Figures 11.6 and 11.8. The first row lists all of the critical edges shown in Figure 11.6. The second row contains the vertices of the initial polygon shown in Figure 11.8 (initialization = first iteration of the algorithm). Vertex b is on edge 2 and also on edge 3, so there is only one column (2/3) for these edges.

Initialization methods Init I through Init III construct polygons Π₀ that are always complete and contained in the given tube. Note that traversals in opposite directions or that start at different critical edges may lead to different initial polygons if Init III is used. For example, a “counterclockwise” traversal of the curve shown in Figure 11.6 (left) starting at edge 1 selects edges 11 and 10 as the first pair of consecutive critical edges; the resulting “counterclockwise” polygon differs from the one shown in Figure 11.8. Figure 11.9 shows a curve for which the final step does not return to the starting vertex.

The results of Init III are shown in Figure 11.8. The curve on the right is already an MLP for this nonsimple 2-curve. For a planar curve, the process may fail to find the first pair of critical edges; in this case, a 2D algorithm can be used to calculate the MLP.

In the iteration process, we move pointers (addressing three consecutive vertices of the polygonal curve found so far) around the curve until a complete iteration leads only to an improvement that is below a given threshold τ (i.e.,l(Π_t) –τ < l(Π_{t + 1})). We cannot wait until there is no change at all, because this may never happen. In all of the experiments reported in [149], the algorithm terminated quickly for a reasonable value of τ.

Let Π_t =(p₀,p₁,…,p_m) be a polygon with three pointers addressing the vertices at positions i −1, i, and i + 1. Three cases can occur that define specific M_ρ-transforms.

(O₁) p_i can be deleted iff p_{i + 1} p_{i + 1} is a line segment within the tube. Triple (p_i−1,P_i,P_{i + 1}) is then replaced by (p_i−1,p_{i + 1}), and we continue with vertices p_i−1, p_{i + 1},and p_{i + 2}.

(O₂) The closed triangular region Δ(p_i−1 p_ip_{i + 1}) intersects more than just the three critical edges of p_i−1, p_i, and p_{i + 1} (see Figure 11.10) (i.e., simple deletion of p_i would not be sufficient). This situation is handled by constructing a convex arc (the shortest curve that surrounds a given finite set of planar points is a convex polygon [155]) and replacing p_i with the sequence of vertices q₁,…,q_k between p_i−1 and p_{i + 1} on this arc iff the sequence of line segments p_i−1 q₁,…,q_kp_{i + 1} lies inside the tube. Because the vertices are ordered, we can use a linear-time convex hull algorithm. Barycentric coordinates with basis {p_i−1,p_i,p_{i + 1}} can be used to decide which of the intersection points are inside the triangle.¹ In this case, we continue with a triple of vertices that starts with q_k.

(O₃) p_i can be moved on its critical edge to a position p_new that minimizes the total length of p_i−1p_new and p_newp_{i + 1}. An O(1) algorithm for this move is given below. (p_i−1,p_i,p_{i + 1}) is then replaced by (p_i−1,p_new,p_{i + 1}), and we continue with the triple ^p new, p_{i + 1},p_{i + 2}.

In situation (O₃), suppose p_i lies on critical edge e and is not collinear with p_i−1p_{i + 1}. Let l_e be the line containing e. We first find the point p_opt ∈ l_e such that the following is true,

and where we also have the following:

If p_opt lies on the closed critical edge e, we simply replace p_i with p_opt; if not, we replace p_i with the vertex bounding e that lies closest to p_opt.

The following is a slightly simpler method of finding p_opt than the one described in [148]. Without loss of generality assume that l_e is parallel to the x-axis, where y_e and z_e are constants:

If x_i−1 = x_{i + 1}, we take p_opt = (x_i−1,y_e,z_e)^T. Otherwise, the following

leads to a quadratic equation in x_opt, where α_i = (y_e – y_i)² + (z_e – z_i)²:

Table 11.1 shows that the second run starts with the polygonal curve Π₁ = (a,b,c,d,e,f,g,h,i,j). For triple a,b,c, none of (O₁) through (O₃) leads to a better location of b. For triple b, c, d, we use (O₁) to delete c (symbol ‘D’). Triple b, d, e then leads to the deletion of d, and so on, and finally triple j, a, b does not delete or move a. In the following run, nothing changes.

The process stops if an entire cycle does not lead to a “significant modification” as defined by a threshold τ.² Experiments in [149] used τ s between l (Π_t)·10⁻⁵ and l(Π_t) · 10⁻⁷. In Figure 11.11, the initial polygon Π₀ is dashed, and the solid line is the final polygon. The short line segments are the critical edges of the tube.

We conclude this section by giving an estimate of the complexity of the rubber-band algorithm as a function of the number n of cubes of ρ.

The algorithm completes each run in O(n) time. A move of p_i on a critical edge requires constant time. In the experiments,τ was set to l(Π₀) · 10⁻⁶; this ensured that the measured time complexity was O (n) (i.e., the number of runs did not depend on n).

Figure 11.12 shows the time needed for the algorithm to stop as a function of the number of cubes n and the number of critical edges. The test set contained 70 randomly generated simple 2-curves. In Figure 11.12 (left), each error bar shows the mean convergence time and its standard deviation for a set of 10 digital curves.

The algorithm is iterative. Because l(Π_{t + 1}) < l (Πt) (if they are equal, the algorithm stops) and there is a lower bound on the length 1(Πt) of the MLP, the algorithm converges. However, it is not certain to what polygon it converges. Lemmas 11.2 and 11.3 give a partial answer: it always converges to a polygon that is complete and contained in M_ρ.

The algorithm provides a method of polygonal approximation and length measurement of simple 2-curves that has run time O(n). The method has been successfully used for a wider class of curves, including cases such as the curve on the right in

Figure 11.6 in which each cube in ρ has exactly two bounding faces in ρ. This simpler definition also allows for the simpler generation of test examples.

It would be desirable to prove that the time complexity of the algorithm is always O(n) and that it always converges to the MLP. Both of these statements can be conjectured from the experiments: the number of cycles was independent of the resolution of the 2-curve, and the minima found by the algorithm were independent of the initialization method.

11.2.1 3D grid-line intersection digitization

If we use 3D grid-line intersection digitization, under the above assumptions about α₁,α₂,β, we need to consider only grid lines parallel to the z-axis.

Let Γ(α₁α₂,β) intersect the vertical grid line (x = m,y = n)at p_m,n where m,n ≥ 0. Then the grid point closest to p_m,n is (m,n,I_m,n) where the following is true:

If there are two closest grid points, we choose the lower one. The set I_α1,α₂,β uniquely determines both the slopes α₁ and α₂ and the intercept β if α₁ or α₂ is irrational. If both α₁ and α₂ are rational, I_α1,α2,× uniquely determines α₁ and α₂ but determines β only up to an interval. This can be proved by a straightforward generalization of the proof of Theorem 9.2

In analogy with the chain codes in Chapter 9, we define step codes, starting with i_α1,α2,β(0,0) = I_0,0 ∈{0,1}:

In addition to these “initial values,” we define column-wise step codes:

We also define row-wise step codes:

The values in the 0th row and 0th column are used in both the column-wise and rowwise step codes; see Figure 11.13. The assumptions 0 ≤α₁ ≤ 1 and 0 ≤α₂ ≤ 1 guarantee that codes 0 and 1 are sufficient. It follows that where m,n ≥ 0. On the basis of the additional assumption α₁ ≤α₂, we will use only row-wise step codes in the sequel, and we will omit the superscript (r).

If we do not require m and n to be nonnegative integers, we obtain digital planes i_α1,α2,β. For D ⊇ R, let . If α₁ or α₂ is irrational, we speak about irrational digital planes and otherwise about rational digital planes.

Analogously to the translation-equivalence of rational DSLSs with the same slope α [675], we have translation-equivalence of rational digital planes with the same slopes α₁ and α₂ [134]. This implies that the intercepts β do not influence translation-invariant properties of rational digital straight lines; we can therefore study translation-equivalence classes i_α1,α2 of rational digital planes.

Using Definition 7.5 of digital surfaces (and digital surface patches) in adjacency grids, we have the following:

11.2.2 Self-similarity

Obviously, a simple digital surface that satisfies the chordal property cannot be bounded.

Defining evenness with respect to the xy-plane is consistent with our previous assumptions about digital planes. By requiring a one-to-one mapping into the xy-plane, we consider only unbounded sets S ⊆ Z³ as being even. The following theorem does not make use of the assumption α₁ ≤α₂ about a digital plane.

11.2.3 Supporting and separating planes

A supporting plane of S ⊆ Z³ divides R³ into two (closed) halfspaces such that S is completely contained in one of them.

11.2.4 Arithmetic planes

Arithmetic geometry as suggested by S. Forchhammer in [332] and developed by J.-P. Reveill ès in [848] provides a uniform approach to the study of digitized hyperplanes in n dimensions. We discuss here only the 3D case. Let a, b, and c be relatively prime integers, and let μ and ω be integers.

Arithmetic planes are a generalization of arithmetic lines D_a,b,μ,ω= ∈ Z² :μ ≤ ai + bj <μ +ω}. From Theorem 9.4, we know that naive lines (ω = max{|a|, |b|}) are the same as rational DSSs and that standard lines (ω = |a| + |b|) are the same as rational 4-DSSs. If ω = max{|a|, |b|, |c|}, the arithmetic plane D_a,b,c,μ,ω is called a naive digital plane; if ω = |a| + |b| + |c|, it is called a standard plane.

In other words, for any digital plane i_α1,α2,_β with rational α₁ and α₂, there exist relatively prime integers a, b, and c and an integer μ such that i_α1,α2,β = D_{a,b,c,μ,max{|a|,|b|,|c|}}. In addition, for any D_{a,b,c,μ,max{|a|,|b|,|c|}}, there exist rational slopes α₁ and α₂ and an intercept β such that D_{a,b,c,μ,max{|a|,|b|,|c|}} = i_α1,_α2,β.

Now assume 0 < a≤ b ≤ c, and consider digitizations of Euclidean planes that are incident with the origin (e.g., by assuming μ = 0). If D_a,b,c,0,ω is a naive plane, each voxel (x,y,z) ∈ D_a,b,c,0,c projects into exactly one pixel (x,y) in the xy-plane. From the assumption 0 < a≤ b ≤ c, it follows that there is at least one voxel (x,y,z) ∈ D_a,b,c,0,ω for every (x, y) ∈ Z².The height map H_a,b,c,ω is defined on Z² by assigning the maximum value z to (x,y) such that (x,y,z) ∈ D_a,b,c,0,ω.

Figure 11.14 illustrates two height maps of naive planes D_a,b,c,0,c. Let L_a,b,c(z₀) = {(x,y) ∈ Z² :(x,y,z₀) ∈ D_a,b,c,0,c} where z₀ ∈ Z. Then La, b,c(z₀) is an arithmetic line D(a,b,μ,ω) with μ = −cz₀ and ω = c. D(a,b,μ,ω) is standard if c = a + b, “thicker than standard” if c > a + b, and “thinner than standard” but “thicker than naive” if c <a + b. The arithmetic lines L_a,b,c(z₀) with z₀ ∈ Z partition Z² into equivalence classes that are all translation equivalent³ iff a and b are relatively prime [134]. Figure 11.14 shows height maps for a case in which a and b are relatively prime (left) and a case in which they are not relatively prime (right).

0 < a ≤ b ≤ c implies that the projections (where x₀,y₀ ∈ Z) are naive lines with approximate intercepts μ = − ax₀ and μ = − by₀, respectively. The arithmetic lines , where x₀ ∈ Z, partition Z² into translation-equivalent equivalence classes. The same is true for the arithmetic lines for y₀ ∈ Z; see [253, 255].

Naive planes can also be represented by arrays of remainders [253]. Let (x,y,z) ∈ D_a,b,c,0,c. We assign value ax + by + cz to grid point (x,y) (i.e., its remainder modulo c). This results in a remainder map R_a,b,c. Figure 11.15 shows two examples. On the left, we have a = 6 and b = 7 (i.e., the integers are relatively prime, which results in remainders in the entire range 0,…, 15 for c = 16). On the right, we have a = 6 and b = 9 (i.e., the remainders in each equivalence class of the depth map are all equal modulo gcd(6,9) = 3).

11.2.5 Periodicity

A position (i,j) in an array X = (X(i, j))_{0≤i 0≤j} is defined by a row i and a column j; X(i,j) is the element of X at position (i, j). The elements of X are letters in an alphabet A. We continue to assume 0 ≤α₁,α₂ ≤ 1; hence, in a digital plane quadrant, we have A = {0,1}.

Let . The restriction X[S] of X to positions in S is called a factor of X on S.

An infinite array X on is called 2D-periodic iff there are two linearly independent vectors u and v in Z² such that w = iu + jv is a period for X for any (i, j)∈ Z² and . X is called 1D-periodic iff all periods of X are parallel vectors.

Let X be a 2D-periodic infinite array on . The set of symmetry vectors of X defines (by additive closure) a subgrid Λ of Z². Any basis of Λ is a basis of X.

We say that an infinite array X on is tiled by a (finite) rectangular factor W if X is a pairwise disjoint repetition of W. Evidently, any 2D-periodic array on can be tiled.

11.2.6 Connectivity of arithmetic planes

An arithmetic line becomes 8-disconnected iff ω < max{|a|, | b|}. Similarly, an arithmetic plane D_a,b,c,μ,ω no longer has grid points on all of the vertical grid lines iff ω < max{|a|, |b|, |c|}.

A standard arithmetic plane is 26-separating and gapfree; it has no 6-, 18-, or 26-gaps. A naive arithmetic plane is 6-separating but not necessarily 18- or 26-separating; it can have 18- or 26-gaps. Note that, if S is not α-connected, any of its subsets is α-separating in S.

In Chapter 9, we formulated equivalences between 8-gap-freeness and 4-connectedness (4-gap-freeness and 8-connectedness) for arithmetic lines; this cannot be done for arithmetic planes. Connectivity is a translation-invariant property. Without loss of generality, we consider grid-line intersection digitizations of rational planes ax + by + cz = 0 that are incident with the origin. Let D_a,b,c,ω be the corresponding arithmetic plane with thickness ω ∈ Z₊ where a,b,c ∈ Z and gcd(a,b,c) = 1. In the case of a naive plane (ω = max{|a|, |b|,|c|}), we simply write D_a,b,c.

ω = Ω_α(a, b, c) + 1 is the smallest integer such that D_a,b,c,0,ω is α-connected. Evidently,α ≥β (α,β ∈{6,18,26}) implies Ω_α(a,b,c) ≤Ω_β(a,b,c). Naive planes are always 26-connected (i.e., Ω₂₆(A,b,c) ≤ max{|a|,|b|,|c|}), and standard planes are always 6-connected (i.e., Ω₆(a, b, c) ≤|a| + |b| + |c|). Connectivity numbers remain unchanged when a, b, and c are permuted (e.g., Ω_α, (a,b,c) = Ω_α, (b,c,a)).

Exercise 7 in Section 11.5 defines “jumps” and shows that they exist in naive planes if c <a + b. Figure 11.16 illustrates such a naive plane in which 8-connected sets of pixels in the height map may be projections of 26-disconnected sets of voxels in the plane. The Symmetry Lemma (Proposition 11.1) allows us to transform such naive planes into symmetric (in the sense of the Lemma) naive planes for which c <a + b is no longer true. This implies the following:

11.4.1 An incremental DPS algorithm

We will next describe an incremental algorithm [550]. Typical timing results for these three algorithms are shown in Figure 11.19 for a polyhedrized digital ellipsoid at grid resolutions ranging from 10 to 100.

11.4.2 DPS generation algorithms

Consider the task of obtaining a gap-free digitization of the surface of a simple polyhedron “face-by-face.” If every polygonal patch on the surface of the polyhedron is approximated (digitized) individually (!) by a naive plane, gaps may result “near the edges” of the polyhedron.

A method from [62] for solving this problem is based on reducing the 3D problem to a 2D one by projecting the polygonal patches onto suitable coordinate planes, digitizing the resulting 2D polygons (in the thinnest way possible, in the terminology of arithmetic geometry), and then finally calculating the 3D digital polygons as subsets of naive planes.

Another method [135] approximates every 3D polygon by a digital polygon, again in the thinnest way possible, and approximating the edges of the polygons by 3D DSSs. The resulting digitization is “optimally thin” in the sense that removing any voxel from the digital surface produces a gap. A third method [133] is based on using graceful planes and lines, respectively, to approximate the surface polygons and their edges. The algorithms in the cited references run in times that are linear in the number of generated surface voxels.

1. Prove statements 11.1 through 11.4.

2. If the projections of a 26-DSS are an 8-DSS with normal (x₁,x₂) in the (x = 0)-plane and an 8-DSS with normal (y₁,y₂) in the (y = 0)-plane, what is the normal of the 26-DSS?

3. Generate the following circles γ(t) in R³, where R_x and R_z are 3 × 3 matrices of rotations around the x- and z-axes, respectively:

    The angles η₁,η₂, and η₃ and the radius r are randomly chosen from uniform distributions in [0,2π) and [0.5,1], respectively. Perform grid-plane intersection digitization of each generated circle using varying grid sizes (e.g., between 100³ and 1000³). Implement 3D DSS segmentation and 3D MLP approximation, and compare their run times.

4. (Open problem) Is there a simple 2-curve such that none of the vertices of its 3D MLP is a grid vertex (i.e., none of these vertices is an endpoint of a critical edge)?

5. Give an example of a 2-curve with a 3D MLP that has at least one vertex that has an irrational coordinate.

6. A straight line in 3D space can be represented as the intersection of two planes a_ix + b_iy + c_ic + d₁ = 0(i = 1,2). Give an example in which the intersection of two digital planes (i.e., two naive planes) obtained by grid-line intersection digitization of two distinct planes is 26-disconnected.

7. Two voxels p = (i,j, k) and q = (i + 1, j + 1, k + 2) in the grid cell model (see the following figure) define a jump. Show that a naive plane D_a,b,c,μ,c (where c = max{a, b,c}) has a jump iff c <a + b.

8. There are four possible factors of size 2 × 2 of a digital plane quadrant for which 0 ≤α₁,α₂ ≤ 1, and α₁ ≤α₂. Which pairs of these factors can be contained in the same rational digital plane quadrant?

9. Prove that a rational digital plane quadrant has at most mn distinct factors of size m × n.

10. Implement algorithm KS2001 and test it on digitized ellipsoids with varying semiaxes 0 < a,b,c ≤ 1 for different grid resolutions, for example, h = 100,…,1000. Study the impact of different search strategies and search depth thresholds on the run time and on the resulting DPS segmentation.

11. Design a DPS approximation algorithm along the following lines: incrementally calculate the 3D convex hull of a set of grid points to which one 6-connected grid point is added at a time, and incrementally update the minimum width of the convex hull as long as the minimum width is below a predefined threshold (e.g., or larger, allowing for “minor variations”).

12. Prove that the connectivity number Ω₂₆ satisfies (i) Ω₂₆ (a, a, a) = 0, (ii) Ω₂₆ (0,b,c) = c − 1, (iii) Ω₂₆(a,b,b)= b − 1, (iv) Ω₂₆(a,a,c) = c – a − 1, and (v) Ω₂₆(a,b,2b) = b − 1, where a, b, and c are relatively prime integers such that 0 < a ≤ b ≤ c.