Jan 25, 2010

Bresenham's line drawing algorithm on a hexagonal grid

1. Introduction

There is a lot of comprehensive resources available regarding Bresenham's line algorithm on a rectangular grid. Hexagonal grids case, however, is rarely described in a friendly to a beginner way. This article is an attempt on explaining the hexagonal grids case, with pictures and verbose explanations.

We will start with a brief look at the classic algorithm, then introduce hexagonal grid, coordinate system, and build Bresenham's line drawing algorithm for it, step-by-step.

2. Rectangular grid

First of all, let us grok the basics of the algorithm on rectangular grid. Consider the following example of drawing of a 1st quadrant, horizontally-biased line (i.e. 0°≤α<45°) from point (0,0) to point (3,2) in cartesian coordinates:

Figure 1. Bresenham algorithm on a rectangular grid


To draw a line, we move "current" pixel to the right pixel by pixel, and determine which one of two adjacent pixels to fill: (1) a pixel to the right or (2) a diagonal pixel to the up-right. To do this, we keep track of a deviation from the ideal line for each step, shown on the picture asεn (index n denotes subsequent values of ε). Deviation increases to the value of k=ΔY/ΔX for every "horizontal" step, and as soon as it exceeds 0.5 (half the pixel size), we know we should make a "diagonal" step (and decrease ε by 1.0, naturally).

Now, despite k can be fractional, it is actually possible to perform all calculations in integer math and without division, by applying a simple trick (namely, taking 2*ΔX as a unit). Also, it should be obvious that drawing of negative-slope lines as well as vertically-biased ones is essentially similar. More details could be found, for example, here. Or just keep reading, since we are going to dig into all this for hexagonal grid case.

3. Hexagonal grid

On a hexagonal grid, the algorithm is very similar. All calculations will still be performed in cartesian coords, but we will scale X and Y axes differently.

3.1. Coordinate system and units

Let's choose some grid orientation and a simple coordinate system on a hexagonal grid, just to introduce common terminology for addressing hexes.

Figure 2. Hexagonal coordinate system we're going to use


In the picture above, a set of hexes having the same X coordinate is highlighted. This also introduces 6 directions on the grid.

3.2. Bresehnam algorithm

Now, since hexagonal grids have different type of symmetry than rectangular ones, we will consider vertically-biased and horizontally-biased lines separately.

Similarly to rectangular case, if we consider only the 1st quadrant (i.e. 0°≤α<90°), then a line is horizontally-biased when we only have to choose between R and UR hexes while drawing the line from left to right. In other words, in the 1st quadrant, 0°≤α<60° defines horizontally-biased line, and 60°≤α<90° defines vertically-biased line (for which we will choose between UL and UR hexes while drawing upwards).

Figure 3. ΔX and ΔY when checking if a line is horizontally-biased


In the above picture, X-axis and Y-axis have different scales. Using these units of measurement, checking for a line to be horizontally-biased is simple. If (i0,j0) is a starting hex in hexagonal coords, and (i1,j1) - ending hex, then line is horizontally-biased if ΔY<2*ΔX. Where ΔY=j1-j0, and ΔX is cartesian distance between start and end hexes. Both ΔY and 2*ΔX are always integer. Blue line is an example of border case between horizontally-biased and vertically-biased lines (i.e. α=60°).

Here is a way to calculate 2*ΔX:

2*ΔX = 2*(i1-i0)+abs(j1 mod 2)-abs(j0 mod 2)

where (i0,j0) and (i1,j1) are start and end hexes in hexagonal coords, abs() returns absolute value.

Note

Now, given start and end points in hexagonal coords, we can determine if a line is horizontally-biased using integer-only, no-division math.

3.2.1. Horizontally-biased lines

Let's try to draw a line between (0,0) and (3,1) step-by-step and devise a general algorithm for it in the process. First, I'd like to choose hexagon side as new unit of measurement:

Figure 4. Horizontally-biased line on a hexagonal grid


This re-scales both X and Y axes differently. For the blue line in the picture above, in this new coordinates we have:

k = tan(α) = 1.5 / (3.5 * sqrt(3)) = sqrt(3)/7

Or, if we name axes from section 3.2 as Xold and Yold, and note that transformation to new measurement units is Xnew=Xold*sqrt(3), Ynew=Yold*1.5, we can get same result by using ΔX and ΔY from 3.2 (marking them ΔXold and ΔYold):

k = ΔYnew/ΔXnew = (ΔYold*1.5)/(ΔXold*sqrt(3)) = (ΔYold/ΔXold) * (sqrt(3)/2) = sqrt(3) * ΔYold / (2*ΔXold)

Now, we will start by filling pixel (0,0), and move to the right by the step s=sqrt(3)/2 at a time. On each step we choose which pixel to fill in, R or UR, and keep track of deviation ε of pixelized line from the ideal line (again, index n of εn in the picture shows subsequent changes of ε):

Example 1. Steps to build h-biased line from (0,0) to (3,1)

0)  ε0=0, color current pixel (0,0)
1)  move out: ε10+k*s
1a) decide where to move: ε1<=0.5, so we will move to the R hex
2)  color hex (1,0), and increase ε once more: ε21+k*s. Now hex (1,0) is the current one
3)  move out: ε32+k*s
3a) decide where to move: ε3>0.5, so we will move to the UR hex
4)  color hex (1,1), and adjust ε accordingly: ε43-1.5. Now hex (1,1) is current, and ε is negative (thus shown in red)
5)  move out: ε54+k*s, ε is still negative (and will remain such till the final hex)
5a) decide where to move: ε5<=0.5, hence R hex is next
6)  color hex (2,1), and increase ε once more: ε65+k*s. Now hex (2,1) is current
7)  move out: ε76+k*s
7a) decide where to move: ε7<=0.5, hence R hex is next
8)  color hex (3,1), and we are done

As a check, if we perform ε=ε+k*s after the last step, we should get 0.0. Indeed:

εfinalbegin + 7*k*sqrt(3)/2 - 1.5 = 0 + 7 * (sqrt(3)/7) * (sqrt(3)/2) - 3/2 = 0


All this doesn't look like integer math at all, so let's make the following observation:

k*s = k * sqrt(3)/2 = sqrt(3)*ΔYold/(2*ΔXold) * sqrt(3)/2 = (3*ΔYold)/(4*ΔXold)

So, k*s can be calculated purely in integer, but we also do not want division. Since everything we need to choose between R and UR is merely ε, let's multiply every formula in question by (4*ΔXold), and introduce new variable ε'=ε*(4*ΔXold). Then the algorithm for horizontally-biased lines in 1st quarter becomes:

Example 2. Bresenham's line algorithm for h-biased lines, 1st quadrant

current hex ← start hex
color current hex
ε' ← 0                                // step 0
while current hex ≠ end hex
  ε' ← ε' + 3*ΔYold                   // steps 1,3,5,7 "move out by increasing ε=ε+k*s"
  if ε' > 2*ΔXold then                // steps 1a,3a,5a,7a "decide by comparing ε>0.5"
    current hex ← get UP_RIGHT hex
    ε' ← ε' - 3*2*ΔXold               // step 4 "adjust ε after UR move, ε=ε-1.5"
  else
    current hex ← get RIGHT hex
    ε' ← ε' + 3*ΔYold                 // steps 2,6 "adjust ε after R move, ε=ε+k*s"
  end if
  color current hex                  // steps 2,4,6,8 "color current hex"
end while


Note

We know how to calculate 2*ΔXold using only integer math, and ΔYold is of course just (jend-jstart), where j is the 2nd hexagonal coordinate. Thus, the algorithm above requires only integer math, and doesn't use division.

3.2.2. Vertically-biased lines

Ok, now to the vertically-biased lines. Things are simpler if we go back to original coordinates introduced in section 3.2 (i.e. unit of measurement is the diameter of hex's inscribed circle). For the 1st quadrant, we will choose between UL and UR hexes while drawing upwards:

Figure 5. Vertically biased line on a hexagonal grid


In the picture above, we're drawing a vertically-biased line from hex (0,0) to hex (0,3). Similarly to the rectangular grid and horizontally-biased lines on a hexagonal grid cases, we keep track of a deviation εn on each step n. Red color means that ε is negative. On each step, we increase ε by k*s, where k=ΔXold/ΔYold, and s=1 (moving in Y direction), then decide between UL and UR hexes, and adjust ε by adding/substracting 0.5.

That is, the algorithm would be very similar to the previous one:

Example 3. Non-integer algorithm for v-biased lines, 1st quadrant

current hex ← start hex
color current hex
ε ← 0
while current hex ≠ end hex
  ε ← ε + ΔXold/ΔYold
  if ε > 0 then
    current hex ← get UP_RIGHT hex
    ε ← ε - 1/2
  else
    current hex ← get UP_LEFT hex
    ε ← ε + 1/2
  end if
  color current hex
end while


Again, let's multiply everything in the algorithm above by the factor of 2*ΔYold, and introduce new variable ε'=ε*2*ΔYold. This will once again get us integer-only, no-division algorithm:

Example 4. Bresenham's line algorithm for v-biased lines, 1st quadrant

current hex ← start hex
color current hex
ε' ← 0
while current hex ≠ end hex
  ε' ← ε' + 2*ΔXold
  if ε' > 0 then
    current hex ← get UP_RIGHT hex
    ε' ← ε' - ΔYold
  else
    current hex ← get UP_LEFT hex
    ε' ← ε' + ΔYold
  end if
  color current hex
end while


3.2.3. Remaining quadrants

So far, we have only considered the 1st quadrant. Due to symmetry, drawing of the lines in the remaining 3 quadrants can be performed using exactly same algorithms (for both h-biased and v-biased lines) but operating on absolute values of ΔX and ΔY, and choosing directions to move on each step accordingly. Consider the following picture of four quadrants:

Figure 6. Four quadrants and relative directions to move while drawing a line


In the picture above, green-ish sectors hold all vertically-biased lines, and red-ish ones hold all horizontally-biased lines.

For example, when we're drawing a horizontally-biased line in a red sector, we can "imagine" that we are drawing mirrored (over X or Y or both axes) line in the 1st quadrant. We will assign ΔX and ΔY their absolute values and track ε deviation as we have done previously, but use not original R/UR directions to move, but modify them accordingly. Here is one possible way to implement unified algorithm for h-biased lines:

Example 5. Bresenham's line algorithm for h-biased lines, all quadrants

2*ΔXold ← get doubled X delta between end hex and start hex
ΔYold   ← get Y delta between end hex and start hex

Xsign ← sign(ΔXold)   // -1 or +1
Ysign ← sign(ΔYold)   // -1 or +1

δY ← 3*abs(ΔYold)
δX ← 3*abs(2*ΔXold)

current hex ← start hex
color current hex
ε ← 0
while current hex ≠ end hex
  ε ← ε + δY
  if ε > abs(2*ΔXold) then
    current hex ← get DIRS[Xsign][Ysign] hex
    ε ← ε - δX
  else
    current hex ← get DIRS[0][Xsign] hex
    ε ← ε + δY
  end if
  color current hex
end while


It uses 2d table named DIRS to choose appropriate hexagonal directions:

Table 1. DIRS[i][j] table used in the algorithm above

i=-1 i=0 i=+1
j=-1 DOWN_LEFT LEFT DOWN_RIGHT
j=+1 UP_LEFT RIGHT UP_RIGHT

Note

While using a table is more illustrative, it might be wiser (from the performance point of view) to implement separate functions for each quadrant. But performance measurements of various methods to move around on a hex grid is a different topic...

Unified algorithm for vertically-biased lines can be constructed in a similar way:

Example 6. Bresenham's line algorithm for v-biased lines, all quadrants

2*ΔXold ← get doubled X delta between end hex and start hex
ΔYold   ← get Y delta between end hex and start hex

Xsign ← sign(ΔXold)   // -1 or +1
Ysign ← sign(ΔYold)   // -1 or +1

δY ← abs(ΔYold)
δX ← abs(2*ΔXold)

current hex ← start hex
color current hex
ε ← 0
while current hex ≠ end hex
  ε ← ε + δX
  if ε > 0 then
    current hex ← get DIRS[Xsign][Ysign] hex
    ε ← ε - δY
  else
    current hex ← get DIRS[-Xsign][Ysign] hex
    ε ← ε + δY
  end if
  color current hex
end while


4. Further reading

4.1. Rectangular grids

4.2. Hexagonal grids

3 comments:

  1. This helped me out quite considerably in exactly the areas I was struggling with - thanks a bunch!

    ReplyDelete
  2. Thanks you very much! You make it just simple as in rectangle coordinate.

    ReplyDelete
  3. The notation choice for the variable 2*ΔXold led to quite a bit of confusion for me. Readers can easily skip past the note which describes how this variable is calculated and assume it is literally "Two times ΔXold" which results in confounding errors in the algorithm because the column offset (staggered pattern) is not being accounted for.

    ReplyDelete

Google+ Badge