请为我解释这Bresenham线的绘图代码 [英] please explain this Bresenham Line drawing code for me

问题描述

我在整个互联网上搜索过，发现了数百个Bresenham的绘图算法的实现。但是，我发现有一件事很奇怪，其中只有两三个可以覆盖八个八位字节中的全部。尽管如此，它们还是被用于许多应用中。

例如，这位女士实施了Bresenham算法的这个版本（第415行）。但是，它并不涵盖整个360度。 这里这个人似乎正在开发一个图书馆。但它仍然无法正常工作。

你能告诉我为什么吗？

这家伙的实施正常。但是，我想这不是布雷森汉姆的算法。它与。

最后，我找到了 Bresenham的线条绘制算法的以下版本正常工作。

  #includeutils。 h
 
 void Bresenham（int x1，int y1，int const x2，int const y2，int color）
 {
 int dx = x2  -  x1; 
 // if x1 == x2，那么我们在这里设置的并不重要
 int ix（（dx> 0） - （dx< 0））; 
 
 dx = abs（dx）<< 1; 
 
 int dy = y2  -  y1; 
 // if y1 == y2，那么我们在这里设置的并不重要
 int iy（（dy> 0） - （dy< 0））; 
 dy = abs（dy）<< 1; 
 
 PlotPixel（x1，y1，color）; 
 
 if（dx> = dy）
 {
 //错误可能低于零
 int错误（dy  - （dx>> 1）） ; （x1！= x2）
 {
 if（（error> = 0）&&（error ||（ix> 0）））
 
 
 {
 error  -  = dx; 
 y1 + = iy; 
} 
 //否则不做任何操作
 
 error + = dy; 
 x1 + = ix; 
 
 PlotPixel（x1，y1，color）; 
 
 
 else 
 
 //错误可能低于零
 int错误（dx  - （dy>> 1））; （（错误> = 0）&&（错误||（iy> 0）））
 
 while（y1！= y2）
 {
 b $ b {
 error  -  = dy; 
 x1 + = ix; 
} 
 //否则不做任何操作
 
 error + = dx; 
 y1 + = iy; 
 
 PlotPixel（x1，y1，color）; 
 
 
 
 
 int main（）
 {
 int gm = DETECT; 
 int gd = DETECT; 
 
 initgraph（& gm，& gd，）; 
 
 double x1 = 0; 
 double y1 = 0; 
 double r = 50; 
 double x2 = 0; 
 double y2 = 0; 
 double signx = 0; 
 double signy = 0; （int theta = 0; theta <= 360; theta ++）
 {
 x2 = r * cos（DegreeToRad（（double）theta））; 
 
; 
 y2 = r * sin（DegreeToRad（（double）theta））; 
 
 x1 = 5 * cos（DegreeToRad（（double）theta））; 
 y1 = 5 * sin（DegreeToRad（（double）theta））; 
 
 Bresenham（x1，y1，x2，y2，YELLOW）; 
 
 //延迟（10）; 
} 
 
 getch（）; 
 closegraph（）; 
返回0; 
} 
  

原始代码很奇怪。所以，我需要你的帮助才能理解这一点。

• 为什么他会左移dx和dy，然后再计算对他们进行右移？

• /jsjtxx/zxkt/Chapter%203%20Scan%20Conversion.pdfrel =nofollow>理论谈论的是什么？根据这个理论，dt和ds应该在while循环的每一步都被测试过。但是，这段代码并没有这样做。为什么？



• 该理论似乎没有任何错误值处理的迹象。代码计算的错误的用途是什么？他如何计算错误？他是如何使用错误值的？




• 测试背后的逻辑 if（dx> = dy）？

解决方案我们从一条线的参数方程开始，（X +其中 t 是范围 [0，1]中的一个参数。终点显然是（X，Y）和（X + Dx，Y + Dy）。

为了将其转换为数字线，我们需要每行或每列只有一个像素，以确保实线连续。因此，定义 D = Max（| Dx |，| Dy |），我们将绘制 D + 1 小数 t ：（X + I.Dx / D，Y + I.Dy / D），其中 [0，D] 。

让我们假设一会儿 0 <= Dy < Dx = D ，并且该公式简化为（X + I，Y + I.Dy / Dx）。由于最后一项可能不是整数，我们将用 round（I.Dy / Dx）= floor（I.Dy / Dx + 1/2）= floor（（I.Dy + Dx / 2）/ Dx）。

后面的表达式是分数之后的数字商数，大于公差。因此，当您增加 I 时，比率要么保持固定，要么增加 1 。对于无分割的实现，我们使用一个技巧：保留分割的商和余数，让 Q 和 R I 时，更新这些。

让 N = I.Dy + Dx / 2 和 Q = N / Dx ， R = N％Dx 。然后增加 I ， I'= I + 1 ， N'= N + Dy ， Q'=（N + Dy）/ Dx ， R'=（N + Dy）％Dx 。正如你可以检查，以下规则成立：

 如果R + Dy> = Dx 
 Q'= Q + 1; R'= R + Dy  -  Dx 
 else 
 Q'= Q; R'= R + Dy 
  

现在我们将所有元素放在一起，调整符号，横向和更垂直的情况下（你会注意到，没有必要明确地表示 Q ）：

 ＃增量
 Sx = Sign（Dx）; Sy = Sign（Dy）
 
＃段长度
 Dx = | Dx |; Dy = | Dy |; D = Max（Dx，Dy）
 
＃初始余数
 R = D / 2 
 
如果Dx> Dy：
＃主循环
为I = 0..D：
设置（X，Y）
 
＃更新（X，Y）和R 
 X + = Sx; R + = Dy＃横向移动
如果R> = Dx 
 Y + = Sy; R- = Dx＃对角线移动
 else：
＃主循环
对于I = 0..D：
设置（X，Y）
 
 ＃更新（X，Y）和R 
 Y + = Sy; R + = Dx＃横向移动
如果R> = Dy 
 X + = Sx; R- = Dy＃对角线移动
  

C / C ++实现匿名）

  void Set（int x，int y，int color）
 {
 PlotPixel（x ，y，颜色）; 
} 
 
 int Sign（int dxy）
 {
 if（dxy <0）return -1; 
 else if（dxy> 0）return 1; 
 else返回0; 
} 
 void Bresenham（int x1，int y1，int x2，int y2，int color）
 {
 int Dx = x2  -  x1; 
 int Dy = y2  -  y1; 
 
 //＃增量
 int Sx = Sign（Dx）; 
 int Sy = Sign（Dy）; 
 
 //＃段长度
 Dx = abs（Dx）; 
 Dy = abs（Dy）; 
 int D = max（Dx，Dy）; 
 
 //＃初始余数
 double R = D / 2; 
 
 int X = x1; 
 int Y = y1; 
 if（Dx> Dy）
 {
 //＃主循环
 for（int I = 0; I  {
设置（X，Y，颜色）; 
 //＃更新（X，Y）和R 
 X + = Sx; R + = Dy; //＃横向移动
 if（R> = Dx）
 {
 Y + = Sy; 
 R- = Dx; //＃对角线移动
} 
} 
} 
 else 
 {
 //＃主循环
 for（int I = 0; I< D; I ++）
 {
 Set（X，Y，color）; 
 //＃更新（X，Y）和R 
 Y + = Sy; 
 R + = Dx; //＃横向移动
 if（R> = Dy）
 {
 X + = Sx; 
 R- = Dy; //＃对角线移动
} 
} 
} 
} 
  

I have searched throughout the Internet and found hundreds of implementation of Bresenham's line drawing algorithm. But, one thing I found strange is, only two or three of them can cover all of the eight octets. still, they are being used in many applications.

For example, this lady implemented this version (line 415) of Bresenham's algorithm. But, it doesn't cover the whole 360 degrees. This guy here seems to be developing a library. But still it doesn't work properly.

Can you tell me why?

This guy's implementation works fine. But, I suppose it is not Bresenham's Algorithm. It has a very few similarity with the theory.

Finally, I found the following version of Bresenham's Line Drawing Algorithm that works properly.

#include "utils.h"

void Bresenham(int x1, int y1, int const x2, int const y2, int color)
{
    int dx = x2 - x1;
    // if x1 == x2, then it does not matter what we set here
    int ix((dx > 0) - (dx < 0));

    dx = abs(dx) << 1;

    int dy = y2 - y1;
    // if y1 == y2, then it does not matter what we set here
    int iy((dy > 0) - (dy < 0));
    dy = abs(dy) << 1;

    PlotPixel(x1, y1, color);

    if (dx >= dy)
    {
        // error may go below zero
        int error(dy - (dx >> 1));

        while (x1 != x2)
        {
            if ((error >= 0) && (error || (ix > 0)))
            {
                error -= dx;
                y1 += iy;
            }
            // else do nothing

            error += dy;
            x1 += ix;

            PlotPixel(x1, y1, color);
        }
    }
    else
    {
        // error may go below zero
        int error(dx - (dy >> 1));

        while (y1 != y2)
        {
            if ((error >= 0) && (error || (iy > 0)))
            {
                error -= dy;
                x1 += ix;
            }
            // else do nothing

            error += dx;
            y1 += iy;

            PlotPixel(x1, y1, color);
        }
    }
}

int main()
{
    int gm = DETECT;
    int gd = DETECT;

    initgraph(&gm, &gd, "");

    double x1 = 0;
    double y1 = 0;
    double r = 50;
    double x2 = 0;
    double y2 = 0;
    double signx = 0;
    double signy = 0;

    for(int theta=0 ; theta<=360 ; theta++)
    {
        x2 = r * cos(DegreeToRad((double) theta));
        y2 = r * sin(DegreeToRad((double) theta));

        x1 = 5 * cos(DegreeToRad((double) theta));
        y1 = 5 * sin(DegreeToRad((double) theta));

        Bresenham(x1, y1, x2, y2, YELLOW);

        //delay(10);
    }

    getch();
    closegraph();
    return 0;
}

The original code is quite strange. So, I need your help to understand that.

• Why is he left shifting dx and dy and then, before calculation, again right-shifting them?

• Where are the dt and ds that the theory talks about?

• According to the theory, dt and ds should have been tested in every step of while loop. But, this code isn't doing so. Why?

• The theory seems to have no indication of any error value processing. What is the use of error that the code is calculating? How is he calculating the error? How is he using the error value?

• What is the logic behind the test if(dx >= dy)?

解决方案

Here is an explanation of my own version of Bresenham.

We start with the parametric equation of a line, (X + t.Dx, Y + t.Dy), where t is a parameter in range [0, 1]. The endpoints are obviously (X, Y) and (X + Dx, Y + Dy).

To turn it to a digital line, we want exactly one pixel per row or per column, whichever ensures a continuous line. So defining D = Max(|Dx|, |Dy|), we will draw D+1 points corresponding to fractional t: (X + I.Dx/D, Y + I.Dy/D), with I in [0, D].

Let us assume for a moment 0 <= Dy < Dx = D, and the equation simplifies to (X + I, Y + I.Dy/Dx). As the last term may not be an integer, we will round it with round(I.Dy/Dx) = floor(I.Dy/Dx + 1/2) = floor((I.Dy + Dx/2) / Dx).

The latter expression is the quotient of numbers following an arithmetic progression over a denominator larger than the common difference. Hence, when you increment I, the ratio either stays fixed or increases by 1. For a division-less implementation, we use a trick: keep the quotient and the remainder of the division, let Q and R, and every time you increase I, update these.

Let N = I.Dy + Dx/2, and Q = N / Dx, R = N % Dx. Then increasing I, I' = I + 1, N' = N + Dy, Q' = (N + Dy) / Dx, R' = (N + Dy) % Dx. As you can check, the following rule holds:

if R + Dy >= Dx
    Q' = Q + 1; R' = R + Dy - Dx
else
    Q' = Q; R' = R + Dy

We now put all elements together, adjust for signs and distinguish the more-horizontal and more-vertical cases (as you will note, there is no need to represent Q explicitly):

# Increments
Sx= Sign(Dx); Sy= Sign(Dy)

# Segment length
Dx= |Dx|; Dy= |Dy|; D= Max(Dx, Dy)

# Initial remainder
R= D / 2

if Dx > Dy:
    # Main loop
    for I= 0..D:
        Set(X, Y)

        # Update (X, Y) and R
        X+= Sx; R+= Dy # Lateral move
        if R >= Dx
            Y+= Sy; R-= Dx # Diagonal move
else:
    # Main loop
    for I= 0..D:
        Set(X, Y)

        # Update (X, Y) and R
        Y+= Sy; R+= Dx # Lateral move
        if R >= Dy
            X+= Sx; R-= Dy # Diagonal move

C/C++ Implementation (by @anonymous)

void Set(int x, int y, int color)
{
    PlotPixel(x, y, color);
}

int Sign(int dxy)
{
    if(dxy<0) return -1; 
    else if(dxy>0) return 1; 
    else return 0;
}
void Bresenham(int x1, int y1, int x2, int y2, int color)
{
    int Dx = x2 - x1;
    int Dy = y2 - y1;

    //# Increments
    int Sx = Sign(Dx); 
    int Sy = Sign(Dy);

    //# Segment length
    Dx = abs(Dx); 
    Dy = abs(Dy); 
    int D = max(Dx, Dy);

    //# Initial remainder
    double R = D / 2;

    int X = x1;
    int Y = y1;
    if(Dx > Dy)
    {   
        //# Main loop
        for(int I=0; I<D; I++)
        {   
            Set(X, Y, color);
            //# Update (X, Y) and R
            X+= Sx; R+= Dy; //# Lateral move
            if (R >= Dx)
            {
                Y+= Sy; 
                R-= Dx; //# Diagonal move
            }
        }
    }
    else
    {   
        //# Main loop
        for(int I=0; I<D; I++)
        {    
            Set(X, Y, color);
            //# Update (X, Y) and R
            Y+= Sy; 
            R+= Dx; //# Lateral move
            if(R >= Dy)
            {    
                X+= Sx; 
                R-= Dy; //# Diagonal move
            }
        }
    }
}

这篇关于请为我解释这Bresenham线的绘图代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！