Bresenham 直线算法再探

• 下载源代码 - 6.04 KB

引言

本文演示了使用一些新的 C# 特性，以便使用经典的 Bresenham 直线算法和中点圆算法，采用迭代方法渲染直线和圆。

背景 - Bresenham 直线算法

此代码片段基于 维基百科 上展示的最流行的直线渲染算法，并公开了一个 IEnumerable<Point>，可用于图形或碰撞检测例程。

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;
            }
        }
    }
}

这个例程的一个陷阱是它实际上将我们的直线视为一个 x 值递增的向量。这意味着上面的代码片段只对 (x0 < x1 and dy < dx) 的最简单情况有效，如下图最左侧的图像所示。如果您阅读维基百科文章，您会发现文章底部有一个优化的算法，它结合了我们直线可能位于的所有向量象限的方法。

这个优化的算法看起来是个好主意，但如果您下载附件的代码文件，您会发现我实际上在四种不同的方法中实现了该算法，以解决不同的组合。

当比较迭代方法和维基百科文章底部的优化算法时，您应该花一分钟时间考虑为 {steep, reverse-X, reverse-Y} 的所有排列渲染的点的顺序。您可能会注意到，一旦在 x0、x1、y0 或 y1 上调用交换函数，您就会更改起点和终点，从而改变输出的顺序。

当您只是在屏幕上绘制一条将在一次传递中显示的直线时，您不需要担心您的点是从 A 开始还是以 B 结束。但是，我实现此算法的目的是在寻路算法中使用它，目的是引导实体从点 A 到 B。在这种情况下，按正确的顺序遍历这些点变得很重要，以便可以沿着路径正确评估条件，并尽快剔除任何错误的路径。

尽管将我编写的四种方法组合成一种方法当然是可能的，但将 BresLine 请求分发到适当的例程似乎对性能更有利。这是因为替代方案涉及在每次迭代期间对向量特性执行额外的检查，而不是在分发时执行一次。

使用代码

只需将示例静态类复制到您的项目中，并像对待任何其他 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());
}

您可能还想执行一些我已在以下代码片段中显示的功能

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)));

分解上面示例中的最后一行，您将看到我们正在执行一个相当复杂的计算，即使它以非常简洁的方式表示。对于不熟悉使用聚合函数和 lambda 表达式的用户来说，这个语句的简洁性可能会非常令人困惑，但是一旦您看到了这些语言结构的功能，就很难放弃它们了。

背景 - 中点圆算法

这部分代码基于 维基百科 上概述的<中点圆算法>。此算法不会按遍历顺序返回点，而是根据每次迭代中相对于每个基本方向的中点的恒定偏移量返回点。

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;
    }
}

您会在上面的代码中注意到，每次在对当前偏移量进行加减运算后，我们都会生成一个新点 - 每次都会生成一个沿不同对角弧的点。这种排序对于检测枚举之间的碰撞/交集已经足够好了，但其他人可能希望修改它以按您可能遍历组件弧的顺序返回点。

使用代码 - LINQ 示例

在源代码中，您将找到几个示例，说明如何利用 LINQ 和 C# 3.0 以简洁的方式执行一些复杂的运算。

// 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);

然后，在下一节中，我们将使用匿名函数、lambda 表达式中调用的辅助函数，以及最终的具有多个操作和显式返回的语句 lambda 表达式，对圆点的枚举执行聚合。

// 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));

关注点

我想在各种条件下进行一些性能测试，看看这种方法与典型的算法（您将为沿直线的每个点分配内存）有何不同。根据这些结果，将其他一些图形处理算法（例如这些）转换为类似的实现可能是一个有趣的练习。最新的下载包括有关数字差分分析器算法以执行插值的正在进行的工作。

历史

• 08/11/4 - 初稿提交以供审核。
• 08/12/1 - 使用中点圆算法和示例进行更新。