Bresenham's Line Algorithm Revisited

• Download source code - 6.04 KB

Introduction

This article demonstrates the use of some of the new C# features in order to take an iterative approach to rendering a line using the classic Bresenham Line Algorithm and rendering a circle with the Midpoint Circle Algorithm.

Background - Bresenham Line algorithm

This code snippet is based on the most popular line rendering algorithm displayed at Wikipedia, and exposes an IEnumerable<Point> that can be used for graphics or collision detection routines.

public static class BresLine
{
    /// <summary>
    /// Creates a line from Begin to End starting at (x0,y0) and ending at (x1,y1)
    /// * where x0 less than x1 and y0 less than y1
    ///   AND line is less steep than it is wide (dx less than dy)
    /// </summary>
    public static IEnumerable<Point> BresLineOrig(Point begin, Point end)
    {
        Point nextPoint = begin;
        int deltax = end.X - begin.X;
        int deltay = end.Y - begin.Y;
        int error = deltax / 2;
        int ystep = 1;

        if (end.Y < begin.Y)
        {
            ystep = -1;
        }

        while (nextPoint.X < end.X)
        {
            if (nextPoint != begin) yield return nextPoint;
            nextPoint.X++;

            error -= deltay;
            if (error < 0)
            {
                nextPoint.Y += ystep;
                error += deltax;
            }
        }
    }
}

One of the pitfalls of this routine is that it actually treats our line as a vector with an increasing x value. This means that the code snippet above is only valid for the simplest case of (x0 < x1 and dy < dx) as shown in the leftmost image below. If you read the Wikipedia article, you will find that there is an optimized algorithm at the bottom of the article that combines approaches for all possible vector quadrants that our line would be in.

This optimized algorithm seems like a great idea, but if you download the attached code file, you will find that I've actually implemented the algorithm in four different methods to address the different combinations.

When comparing the iterative approach to the optimized algorithm at the bottom of the Wikipedia article, you should take a minute and consider the order of the points being rendered for all permutations of {steep, reverse-X, reverse-Y}. You may notice that as soon as the swap functions are called on x0, x1, y0, or y1, you change the start and end points, thereby altering the order of the output.

When you are simply drawing a line to the screen that will be displayed in one pass, you don't need to worry about whether your points start at A and end at B. However, I implemented this algorithm with the intent of using it in path finding algorithms with the purpose of navigating an entity from point A to B. In this case, it becomes important to iterate through the points in the proper order so that conditions can be properly evaluated along the path and any false paths can be culled as soon as possible.

Although it is certainly possible to combine the four methods I've written into a single one, it seems more beneficial to performance to perform comparisons in one place and dispatch the BresLine request to the appropriate routine. This is because the alternative involves performing additional checks on the vector characteristics during each iteration, instead of once at dispatch.

Using the code

Just copy the example static class into your project and enumerate over it like you would any other IEnumerable.

Point myStart = new Point(1, 20);
Point myEnd = new Point(20, 35);

IEnumerable<Point> myLine = BresLine.RenderLine(myStart, myEnd);
foreach (Point myPoint in myLine)
{
    Console.WriteLine(myPoint.ToString());
}

You might also want to perform some functions like I've shown in the snippet below:

IEnumerable<Point> longLine; // Represent an enumerable line
// This is an example of why I am using the iterative approach
// We'll draw a line from 0,0 to 5000000,900000--
longLine = BresLine.RenderLine(new Point(0, 0), new Point(5000000, 900000));
// Now iterate over the line and perform some operation
foreach (Point myPoint in longLine)
{
    double dummyVar = myPoint.X * Math.Sin(myPoint.X / 90);
    // Eventually our X will exceed the boundary value of 12345 in some direction
    if (Math.Abs(dummyVar) > 12345) break;
}

// Now output some strings
StringBuilder sb = new StringBuilder();
string totalString = longLine.Aggregate(sb, (acc, x) => 
                       sb.Append(x.ToString())).ToString();
// totalString is something like 98 million characters long at this point

if (totalString.Length < 1000)
{
    // We could print the 98 million character string... 
    // but you could expect an OutOfMemoryException
    Console.WriteLine(totalString);
}

// Accumulate the SIN of all y values for no reason in particular
Console.WriteLine("SIN(Y) aggregate: " + 
  longLine.Aggregate(0d, (acc, pointN) => acc += Math.Sin(pointN.Y)));

Breaking down the last line in the example above, you will see that we are performing a fairly complex calculation, even though it is represented in a very concise manner. The concise nature of this statement can be extremely confusing to users that aren't familiar with the use of aggregate functions and lambda expressions, but once you've seen the power of these language constructs, it becomes pretty hard to dismiss them.

Background - Midpoint Circle algorithm

This section of my code is based on the Midpoint Circle Algorithm outlined on Wikipedia. This algorithm does not return points in the order of traversal, but instead returns points in the order of a constant offset against the midpoint in each cardinal direction for each iteration.

public static IEnumerable<Point> rasterCircle(Point midpoint, int radius)
{
    Point returnPoint = new Point();
    int f = 1 - radius;
    int ddF_x = 1;
    int ddF_y = -2 * radius;
    int x = 0;
    int y = radius;

    returnPoint.X = midpoint.X;
    returnPoint.Y = midpoint.Y + radius;
    yield return returnPoint;
    returnPoint.Y = midpoint.Y - radius;
    yield return returnPoint;
    returnPoint.X = midpoint.X + radius;
    returnPoint.Y = midpoint.Y;
    yield return returnPoint;
    returnPoint.X = midpoint.X - radius;
    yield return returnPoint;

    while (x < y)
    {
        if (f >= 0)
        {
            y--;
            ddF_y += 2;
            f += ddF_y;
        }
        x++;
        ddF_x += 2;
        f += ddF_x;
        returnPoint.X = midpoint.X + x;
        returnPoint.Y = midpoint.Y + y;
        yield return returnPoint;
        returnPoint.X = midpoint.X - x;
        returnPoint.Y = midpoint.Y + y;
        yield return returnPoint;
        returnPoint.X = midpoint.X + x;
        returnPoint.Y = midpoint.Y - y;
        yield return returnPoint;
        returnPoint.X = midpoint.X - x;
        returnPoint.Y = midpoint.Y - y;
        yield return returnPoint;
        returnPoint.X = midpoint.X + y;
        returnPoint.Y = midpoint.Y + x;
        yield return returnPoint;
        returnPoint.X = midpoint.X - y;
        returnPoint.Y = midpoint.Y + x;
        yield return returnPoint;
        returnPoint.X = midpoint.X + y;
        returnPoint.Y = midpoint.Y - x;
        yield return returnPoint;
        returnPoint.X = midpoint.X - y;
        returnPoint.Y = midpoint.Y - x;
        yield return returnPoint;
    }
}

You will notice in the code above that we yield a new point each time after we perform some combination of addition and subtraction of the current offset against the midpoint--yielding a point along a different diagonal arc each time. This ordering was good enough for my purposes of detecting collisions/intersection between enumerations, but others may want to modify this to return points in the order you might traverse along the component arcs.

Using the code - LINQ examples

Within the source code, you will find several examples of how you can leverage LINQ and C# 3.0 to perform some complicated operations in a concise manner.

// Let's get the sum of all X values
int xAvg = circlePoints.Aggregate(0, (acc, pt) => acc += pt.X);
// ...and the sum of all Y values
int yAvg = circlePoints.Aggregate(0, (acc, pt) => acc += pt.Y);

// Print out the result averages
Console.WriteLine("Avg X: " + (xAvg / circlePoints.Count()).ToString());
Console.WriteLine("Avg Y: " + (yAvg / circlePoints.Count()).ToString());

// The average of all points along a well-formed circle should be the origin
Debug.Assert(xAvg == circleOrigin.X);
Debug.Assert(yAvg == circleOrigin.Y);

Then, in the following section, we will perform aggregation on the enumeration of circle points using an anonymous function, a helper function called within a lambda expression, and finally, a statement lambda expression with multiple operations and an explicit return.

// In the following section we will accumulate on X and Y at the 
// same time using a few different methods
Point newPoint;

// Accumulate using an inline anonymous function:
//   Although the LINQ Aggregate wasn't yet available, we would've 
//   been inclined to use a delegate like this back in C# v2.0...
newPoint = circlePoints.Aggregate(new Point(), delegate(Point point1, Point point2) 
           { point1.X += point2.X; point1.Y += point2.Y; return point1; });
Console.WriteLine("anonymous function Aggregation result: " + newPoint.ToString());

//We could use an addPoint helper function 
//if the operations are significantly complex
newPoint = circlePoints.Aggregate(new Point(), (acc, x) => addPoint(acc, x));
Console.WriteLine("addPoint Aggregation result: " + newPoint.ToString());

// Because the operation is trivial we can use this inlined
// 'statement lambda expression' with an explicit return
newPoint = circlePoints.Aggregate(new Point(), 
    (acc, x) => { acc.X += x.X; acc.Y += x.Y; return acc; });
Console.WriteLine("statement lambda function Aggregation result: " + 
                  newPoint.ToString());

// Now find the maximum combination of X and Y in the circle
Console.WriteLine("Max X+Y point: + " + circlePoints.Max(i => i.X + i.Y));

Points of interest

I would like to do some performance testing under various conditions to see how this approach differs with typical algorithms where you would allocate memory for each point along a line. Based on those results, it might be an interesting exercise to convert some other graphics processing algorithms such as these to a similar implementation. The latest download includes some work-in-progress on a Digital Differential Analyzer algorithm to perform interpolations.

History

• 11/4/08 - Initial submission for draft review.
• 12/1/08 - Updated with Midpoint Circle Algorithm and examples.