Wednesday, July 29, 2015

On circle rasterization algorithms: Bresenham's and Michener's

The idea to write this article came to me when I noticed virtually every page I came across in Google search results presented Michener's algorithm as Bresenham's. While Michener's algorithm is certainly easily and immediately derivable from Bresenham's, it might be useful to some to understand the steps involved.

A few words on Bresenham's algorithm

I will not derive the entire algorithm from scratch here, but rather present a few important points that define the original Bresenham's algorithm. Let's say we want do rasterize a circle of radius R. First and foremost, Bresenham's algorithm solves this problem by generating pixels for 1/4 of the circle, i.e. an arc inside a Cartesian quadrant. Let's assume we start from point (0, R) and proceed upwards and to the left from there until we reach point (R, 0) (Fig. 1).

Fig. 1

At each step, at point (x, y) the algorithm makes a decision which point to add next: point (x - 1, y), point (x - 1, y + 1) or point (x, y + 1) as shown in Fig. 2.

Fig. 2

In order to make that decision, the algorithm uses the following deviation function D(x, y, R)

D(x, y, R) = x2 + y2 - R2
The above function produces negative values for points that lie strictly inside the circle, and positive values for points strictly outside the circle (and, obviously, zero value for points that lie exactly on the circle). The idea is, naturally, to select the point closest to the circle, i.e. one out of three that minimizes the absolute value of the deviation function.

While standing at point (x, y), the algorithm first focuses its attention at the diagonal point (x - 1, y + 1). It considers value Δ, which represents the deviation of point (x - 1, y + 1) from the actual circle

Δ = D(x - 1, y + 1, R)
and acts in accordance with the following logic

  • If Δ is exactly zero, it means point (x - 1, y + 1) lies precisely on our circle. And Bresenham's algorithm immediately decides to proceed to point (x - 1, y + 1).

  • If Δ is negative, it means that point (x - 1, y + 1) leads us into the circle's interior (Fig. 3)

    Fig. 3

    In such cases Bresenham's algorithm performs an additional analysis in order to determine whether to proceed to point (x - 1, y + 1), or to "counteract" its tendency to lead into the circle by stepping to (x, y + 1) instead (the latter takes us closer to the outside of the circle). To perform such analysis, Bresenham's algorithm calculates an additional value δ

    δ = D(x - 1, y + 1, R) + D(x, y + 1, R)

    • If δ is negative or zero, it means that point (x, y + 1) leads to a smaller absolute error value than point (x - 1, y + 1). The algorithm decides to step to (x, y + 1).

    • If δ is positive, it means that point (x - 1, y + 1) offers a smaller absolute error value. The algorithm steps to (x - 1, y + 1).

    The clever part here is that δ is easily obtainable as δ = 2Δ + 2x - 1

  • If Δ is positive, then symmetrical logic applies: it means that point (x - 1, y + 1) leads us out of the circle (Fig. 4)

    Fig. 4

    Bresenham's algorithm performs an additional analysis in order to determine whether to proceed to point (x - 1, y + 1), or to bear towards the interior of the circle instead by stepping to (x - 1, y). To perform such analysis, Bresenham's algorithm calculates an additional value δ'

    δ' = D(x - 1, y, R) + D(x - 1, y + 1, R)

    • If δ' is positive or zero, it means that point (x - 1, y) leads to a smaller absolute error value than point (x - 1, y + 1). The algorithm decides to step to (x - 1, y).

    • If δ' is negative, it means that point (x - 1, y + 1) offers a smaller absolute error value. The algorithm steps to (x - 1, y + 1).

    Again, δ' can be easily calculated as δ' = 2Δ - 2y - 1

All that's left to add is that the value of Δ can be maintained incrementally from iteration to iteration (see the code below), i.e. there's no need to calculate D(x - 1, y + 1, R) directly on every iteration, which is what makes Bresenham's algorithm so efficient.

Here's a possible implementation of Bresenham's algorithm

void BresenhamCircle(int cx, int cy, int radius)
{
  int x = radius;
  int y = 0;

  int D = 2 * (1 - radius);
  // 'D' is the error value for '(x - 1, y + 1)' point. I.e.
  //   D = D(x, y) = (x - 1)^2 + (y + 1)^2 - radius^2
  // Substitute initial values of 'x = radius' and 'y = 0' to obtain the above initial 
  // value for 'D'

  while (x >= 0)
  {
    // Draw pixels in each quadrant
    draw_pixel( x + cx,  y + cy);
    draw_pixel( y + cx, -x + cy);
    draw_pixel(-x + cx, -y + cy);
    draw_pixel(-y + cx,  x + cy);

    // We are currently at point '(x, y)', while 'D' is maintained as the error value for 
    // point '(x - 1, y + 1)'

    if (D < 0)
    { // Taking '(x - 1, y + 1)' step leads into the circle. Decide whether we should go
      // to '(x - 1, y + 1)' or to '(x, y + 1)'
      int d = 2 * D + 2 * x - 1;
      // 'd' is sum of error values for '(x - 1, y + 1)' and '(x, y + 1)' 
      //   d = D(x - 1, y + 1) + D(x, y + 1)
      if (d <= 0)
      { // Error value for '(x, y + 1)' is smaller - go in that direction
        ++y;
        D += 2 * y + 1;
        continue;
      }
      // Otherwise, proceed to '(x - 1, y + 1)'
    }
    else if (D > 0)
    { // Taking '(x - 1, y + 1)' step leads out of the circle. Decide whether we should go
      // to '(x - 1, y + 1)' or to '(x - 1, y)'
      int d = 2 * D - 2 * y - 1;
      // 'd' is sum of error values for '(x - 1, y)' and '(x - 1, y + 1)'
      //   d = D(x - 1, y) + D(x - 1, y + 1)
      if (d >= 0)
      { // Error value for '(x - 1, y)' is smaller - go in that direction
        --x;
        D -= 2 * x - 1;
        continue;
      }
      // Otherwise, proceed to '(x - 1, y + 1)'
    }

    // Take a step to '(x - 1, y + 1)'
    --x;
    ++y;
    D += 2 * y - 2 * x + 2;
  }
}

Michener's algorithm

Even a quick look at Bresenham's algorithm immediately reveals obvious optimization opportunities:

  • Firstly, it is obvious that as long as we are generating points of the first octant, point (x - 1, y + 1) always lies inside the actual circle (Fig. 3). But once we cross the 45 degree line and start generating points of the second octant, point (x - 1, y + 1) always lies outside the circle (Fig. 4). In other words, for the first half of the arc Δ is always non-positive, while for the second half of the arc it is always non-negative (Fig. 5).

    Fig. 5

    For this reason, there's not much point in calculating and analyzing the value of Δ on each iteration. We can simply split the main cycle in two sequential cycles - for the first octant and for the second one - and implement Δ ≤ 0 branches of the code in the first cycle and Δ ≥ 0 branches in the second cycle.

    Of course, in the original algorithm we also need the value of Δ in order to calculate the values of δ or δ'. But these values can also be calculated incrementally, i.e. there's a simple formula that allows us to update the value of δ from the current iteration to obtain the value of δ for the next iteration (see the code below). Same is true for δ', but as the next bullet point states, we don't event need δ'.

    Thus we can get rid of Δ and corresponding branching entirely.

  • Secondly, we don't even need to generate the second octant. Once we learned to generate circle arc points in the first octant, we can use reflections across 45 degree bisectors and coordinate axes in order to immediately generate corresponding points in remaining seven octants.

So, all we need is an algorithm for the first octant. And in order to build such algorithm all we need is to maintain the proper value of δ on each iteration. The branching on Δ disappears, the rest of the logic remains unchanged. Bresenham's algorithm optimized in this fashion is also known as Michener's algorithm, although as you can easily see, the changes from the original are relatively superficial.

Here's a possible implementation of Michener's algorithm

void MichenerCircle(int cx, int cy, int radius)
{
  int x = radius;
  int y = 0;

  int d = 3 - 2 * radius;
  // 'd' is sum of error values for '(x - 1, y + 1)' and '(x, y + 1)' 
  //   d = D(x - 1, y + 1) + D(x, y + 1)
  // Substitute initial values of 'x = radius' and 'y = 0' to obtain the above initial 
  // value for 'd'

  while (y <= x)
  {
    // Draw pixels in each octant
    draw_pixel( x + cx,  y + cy);
    draw_pixel( y + cx,  x + cy);
    draw_pixel(-x + cx,  y + cy);
    draw_pixel(-y + cx,  x + cy);
    draw_pixel(-x + cx, -y + cy);
    draw_pixel(-y + cx, -x + cy);
    draw_pixel( x + cx, -y + cy);
    draw_pixel( y + cx, -x + cy);

    if (d <= 0)
    { // Error value for '(x, y + 1)' is smaller - go in that direction
      d += 4 * y + 6;
      ++y;
    }
    else
    { // Otherwise, proceed to '(x - 1, y + 1)' point
      d += 4 * (y - x) + 10;
      --x;
      ++y;
    }
  }
}

The above variant of Michener's algorithm updates the value of δ before updating x and/or y. One can swap these steps and adjust the formulas for δ accordingly, obtaining a slightly different variant of the implementation. Also, in order to reduce the magnitude of δ, one can just divide all formulas for δ by 2 (rounding towards negative infinity). Whatever loss of precision occurs after such division does not affect the sign-switching behavior of δ and, therefore, does not break the algorithm.

The following implementation of the same algorithm includes both of the modifications mentioned above

void MichenerCircle2(int cx, int cy, int radius)
{
  int x = radius;
  int y = 0;

  int d = 1 - radius;

  while (y <= x)
  {
    // Draw pixels in each octant
    draw_pixel( x + cx,  y + cy);
    draw_pixel( y + cx,  x + cy);
    draw_pixel(-x + cx,  y + cy);
    draw_pixel(-y + cx,  x + cy);
    draw_pixel(-x + cx, -y + cy);
    draw_pixel(-y + cx, -x + cy);
    draw_pixel( x + cx, -y + cy);
    draw_pixel( y + cx, -x + cy);

    if (d <= 0)
    {
      ++y;
      d += 2 * y + 1;
    }
    else
    {
      --x;
      ++y;
      d += 2 * (y - x) + 1;
    }
  }
}

This latter version of the implementation seems to be the one most often presented on the Net as "Bresenham's circle algorithm".

Friday, January 30, 2015

Resolving "missing One Drive overlay icons" issue

This question is asked many times over Microsoft support forums, but I'm yet to see a meaningful answer to it, even though the reason for this failure is rather simple.

First, a few words about what actually happens here. With OneDrive Microsoft made a rather unorthodox decision to have this piece of software installed on per-user basis. This is a major deviation from the "traditional" Windows software installation practices, when software is installed once through Administrator account and then becomes accessible from all user accounts on the computer. What it means in case of OneDrive is that each user account on the given computer has to install OneDrive independently and separately, just for themselves.

And this almost works. Most of OneDrive's functionality is successfully installed into each user's personal folders, except for one piece: icon overlay support in Explorer. The icon overlay functionality currently requires making modifications to HKLM area of the system registry, namely

HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\Explorer\ShellIconOverlayIdentifiers

A normal user account (i.e. an account without administrative rights) is not able to perform such system-wide modifications. Windows immediately blocks any attempts to write into HKLM area in the registry. This is the reason the icon overlay functionality simply fails to install from under normal user accounts. When installed in this fashion, OneDrive still works correctly, it properly syncs the files, but there are no icon overlays in Explorer.

Now, how to solve this problem and make these icon overlays to work:

Method 1 - Primitive
Log into Administrator account on your computer and install OneDrive for Administrator. You probably don't really need OneDrive for Administrator, but doing this will make the necessary system-wide changes to the registry. Once you install OneDrive for Administrator account, icon overlays should start working for all normal user accounts on that computer.

Method 2 - Smart
1. Uninstall OneDrive from all user accounts
2. Log into Administrator account
3. Enter "Local Users and Groups" applet in "Computer Management". Make each normal user a member of "Administrators" group, i.e. give all of your users full administrative rights. (You can also use "User Accounts" entry in "Control Panel" for that purpose).
4. Log off from Administrator account.
5. Log into your normal user account (which now has administrative rights) and perform fresh installation of OneDrive.
6. Repeat step 5 for all user accounts that need OneDrive
7. Go back into Administrator account. Reverse step 3, i.e. take away administrative rights from all normal user accounts.
You are done. Now all users should see normal icon overlays in their OneDrive folders.

Method 3 - Hackish
Log into Administrator account on your computer and merge the following data into your registry (i.e. save it as a .reg file, right click it and execute the "Merge" command). Backing up your registry before performing any modifications is strongly recommended
Windows Registry Editor Version 5.00
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\ShellIconOverlayIdentifiers\ SkyDrive1]
@="{F241C880-6982-4CE5-8CF7-7085BA96DA5A}"
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\ShellIconOverlayIdentifiers\ SkyDrive2]
@="{A0396A93-DC06-4AEF-BEE9-95FFCCAEF20E}"
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Explorer\ShellIconOverlayIdentifiers\ SkyDrive3]
@="{BBACC218-34EA-4666-9D7A-C78F2274A524}"


Now all users should see normal icon overlays in their OneDrive folders.