Digital lines

Digital lines are yet another way to think of line of sight... they're closest in spirit to the definition of permissive field of view.

The simplest way to describe a digital line is probably as a sub-line of a line created by Bresenham's Algorithm. However, this description doesn't make any of the nicer properties of digital lines clear. There are at least two other useful descriptions of digital lines which aid the intuition: one uses balanced words, and the other uses geometry.

Chain Codes

To simplify the discussion, we'll discuss lines with slope between 0 and 1. If we think of a line in terms of the squares of the grid it passes through, we can encode the line as a sequence of 0s and 1s as follows: if the line moves to the right, we write down a 0, and if it moves diagonally up and to the right, we write down a 1.

Examples:

         #
       ##
    ### 
  ##    
##

corresponds to

010100101

while

     #####
    #   
   #    
  #     
##      

corresponds to

011110000

This method of representing digital lines is called chain coding.

Balanced Words

Now the question arises: which sequences of 0s and 1s correspond to actual lines? The first example made a pretty good line, while the second one is quite clearly not a line. Just looking at the encoding of the second line, we can see that it had four 1s in a row, and later, had four 0s in a row. On the other hand, the first example had very evenly distributed 0s and 1s. We would like to formalize the intuitive concept of "very evenly distributed".

Some quick definitions: A binary word is a sequence of 0s and 1s. The height of a word is defined as the number of 1s in the word. A factor of a word is basically a substring of it (subword has a different meaning, unfortunately). A balanced word is a word such that for any two factors of the same length, their height differs by at most one. The second example is not balanced, because it contains two factors - 1111 and 0000 - the first having height four and the second having height zero. On the other hand, the first example is balanced - for example, all factors of length three have height between one and two.

Now we're going to turn around and define a digital line as a line whose chain code is a balanced binary word.

The complete list of Digital Lines

One way to generate digital lines is the Bresenham Line Drawing Algorithm. For a line of slope p/q, we keep a variable eps, and add p to eps at each step. If eps is less than q, we write down a 0, and if eps is more than or equal to q, we write down a 1 and subtract q from eps. The chain codes generated like this are guaranteed to be balanced, for obvious reasons.

But this doesn't give us all possible digital lines! Even if it did, it isn't clear that a digital line of length n generated from a fraction of the form, say, 2n/(3n+5) wouldn't give us a new line not coming from fractions with smaller denominators.

Luckily, we do know that every digital line can be generated by using a slight modification to the Bresenham Algorithm, in which eps can be started off with any value between 0 and q-1. In fact, every digital line of length n can be described by a fraction p/q and an initial eps, with the denominator q equal to the minimal period of the word (a period of a word doesn't have to divide its length, for example, two is a period of 01010).

Alternatively, every digital line appears as a sub-line of something generated by Bresenham's Algorithm.

Examples:

n = 7, p = 2, q = 5, initial eps = 0
chain code: 0010100
     ###
   ##
###

n = 7, p = 2, q = 5, initial eps = 2
chain code: 0101001
       #
    ###
  ##
##

n = 7, p = 1, q = 4, initial eps = 2
chain code: 0100010
      ##
  ####
##

Geometric Interpretation

"Great," you're thinking, "now we have this abstract definition of a digital line. But, geometrically, it's completely meaningless!" You point your finger at this so called "digital line" between A and B in fury (this time, #s represent obstructions):

     ####.B
   ###...##
####..####
#A..###

"There is no way you can get a line to pass through all those corners without bending it, or, worse, letting the line pass through the walls!"

It's OK. Calm down. I'm going to explain the geometry right now. The truth is, I hate sharp edges. In order to protect adventurers from cuts and scrapes, I beveled all of the corners of my dungeon. Since my adventurers (as well as monsters, items, etc.) are perfectly diamond shaped, this allows them to squeeze through corners perfectly! Also, I assume that the eyes of my adventurers can be located on whatever part of their diamond shaped bodies they like, and even the smallest glimpse of another diamond shaped being is enough to guess what they are.

It's a fun exercise to show that this geometrical interpretation is equivalent to the existence of digital lines connecting the two locations. (Hint: if you restrict to one octant, diamonds might as well be line segments)

One can also define a three dimensional version of digital lines (and even digital planes!), but I'm not sure how that would be interpreted geometrically (my guess is beveled cubes, but these are a little less intuitive than diamonds).

Useful properties of Digital Lines

• If there is a digital line connecting A to B, there is a digital line connecting B to A. This is obvious from the definition of balanced words.
• If two digital lines connect the same points A and B, their heights cannot differ by more than 1 at an intermediate point. This is easiest to prove using the geometric interpretation.
• The number of distinct digital line segments of length N is O(N³). This makes sense from the description in terms of Bresenham's Algorithm.

Relationship with Permissive Field of View

Permissive Field of View can be described in terms of digital lines. The corresponding definition of chain code is slightly different - for simplicity, we will restrict to the first quadrant, and abolish diagonal movement (don't worry, we'll allow diagonal movement again later). A way to encode such a line as a sequence of 2s and 0s is to encode a movement to the right as a 0, and a movement upwards as a 2:

       ###
    ####
  ###
###

corresponds to

002002000200

If we now define a Permissive Line as a line producing a balanced chain code (in terms of 0s and 2s), we see that geometrically it corresponds to a line from the start square to the destination square, that doesn't touch any obstructing squares, even at the corners. However, we want to allow permissive lines to touch squares at the corners for aesthetic reasons, so we'll make a slight modification to our definition. We allow a diagonal movement to be encoded as (02), such as in the following case:

        ####
      ###
   ###
####

corresponding to

000200(02)002000

Now, here's the modification we have to make to our definition of balanced word: a chain code with (02)s allowed is called balanced if it is balanced after each of the substitutions sending the first k (02)s to 02 and the rest of the (02)s to 20, or vice versa (this corresponds to wiggling the line by an infinitesimal amount). This definition of permissive line is then equivalent to the preferred geometric definition.

For instance, the example given above (of a digital line that doesn't make geometric sense in the permissive definition) corresponds to

001010010 -> 00(02)0(02)00(02)0

The reason that this is not balanced under our new definition is that sending the first (02) to 02 and the last two (02)s to 20 produces

000202000200

which is not balanced. Thus, we easily see that digital lines are strictly more permissive than permissive lines.

Further Reading

These papers back up most of the things I just said:

1. Digital straightness, a review. By Reinhard Klette and Azriel Rosenfeld.
2. Discrete Straight Line Segments: Parameters, Primitives, and Properties. By Leo Dorst and Arnold W.M. Smeulders.
3. On the Number of Digital Straight Line Segments. By Carlos A. Berenstein and David Lavine.
4. Random Generation of Finite Sturmian Words. By Jean Berstel and Michel Pocchiola.

There's also a great book at http://www-igm.univ-mlv.fr/~berstel/Lothaire/ChapitresACW/, for those of you interested in the more mathematical side of balanced words.