{"id":3315,"date":"2024-12-23T17:52:26","date_gmt":"2024-12-23T17:52:26","guid":{"rendered":"https:\/\/www.byteblueprints.com\/?p=3315"},"modified":"2025-05-05T14:24:12","modified_gmt":"2025-05-05T14:24:12","slug":"how-computers-draw-lines-part-2-math-behind-breshenham-algorithm","status":"publish","type":"post","link":"https:\/\/www.byteblueprints.com\/?p=3315","title":{"rendered":"How Computers Draw Lines Part 2 (Math Behind Breshenham Algorithm)"},"content":{"rendered":"\n

In mathematics, a straight line is represented by the equation $y = mx + c$:<\/p>\n\n\n\n

where m<\/em><\/strong> is the slope and c<\/em><\/strong> is the y-intercept<\/em><\/strong>. On paper, this equation allows us to draw a line smoothly, as points on the line can have continuous values (including decimals).<\/p>\n\n\n\n

However, in computer graphics, we face a challenge: displays consist of discrete pixels, so lines cannot be drawn with infinite precision. Instead, we must determine which pixels should be colored to best approximate the line. This process is called rasterization<\/em><\/strong>.<\/p>\n\n\n\n

Bresenham\u2019s line algorithm is a well-known method for rasterizing <\/strong><\/em>lines. Let\u2019s derive the key variables and equations for this algorithm using the basic line equation.<\/p>\n\n\n\n

Note:<\/em> A line can fall into one of eight octants, as shown in the image. To derive the equations for the Breshenham line drawing algorithm, we will focus on a line in the first octant, where the slope satisfies 0 \u2264 m \u2264 1<\/em><\/strong>.<\/em> Later, we can extend this to derive the equations for other octants.<\/em><\/strong><\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Figure 1<\/em><\/strong><\/p>\n\n\n\n

Assumption 1: In computer displays, pixel counting starts from the top-left corner. The x-coordinate increases to the right, and the y-coordinate increases downward. However, for simplicity in deriving equations, let\u2019s assume x and y follow the behavior of standard cartesian coordinates<\/em><\/strong>:<\/p>\n\n\n\n

Assumption 2: Assume the center of a pixel represents its continuous value. This means the length of the $y_{k}$ pixel is the distance from the bottom-most point of the display to the center of the $y_{k}$<\/em><\/strong> pixel.<\/em><\/strong> (See Figure 2<\/em><\/strong>)<\/p>\n\n\n\n

Understanding Pixel Selection<\/h4>\n\n\n\n

When drawing a line between two points, the line may pass between pixels. Consider the following situation<\/p>\n\n\n\n

As shown in the image below, let\u2019s assume we are currently at the k-th<\/em><\/strong> position for both x<\/em><\/strong> and y<\/em><\/strong>. Our task is to predict the next pixel to draw. Since we are in the first octant, we know the next x-coordinate<\/em><\/strong> will be $x_{k}$+<\/strong>1. However, we need to decide whether to color the current $y_{k}$<\/em><\/strong><\/em><\/strong> pixel or the next $y_{k}$<\/em><\/strong> +<\/em><\/strong>1<\/em> pixel.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Figure 2<\/em><\/strong><\/p>\n\n\n\n

To make this decision, we need to calculate two values, d1<\/em><\/strong> and d2<\/em><\/strong>, and choose the pixel that is closer to the actual line to minimize visual error.<\/p>\n\n\n\n

We will define this decision as a parameter d<\/em><\/strong>, and our goal is to derive d<\/em><\/strong> from the line equation $y = mx + c$<\/em><\/strong>. Using this parameter, we can determine which y-value<\/em><\/strong> to color next.<\/p>\n\n\n\n

Derivation of Decision Variable(d)<\/h4>\n\n\n\n

The line equation is given as $y = mx + c$:<\/p>\n\n\n\n

Let the y-coordinate<\/em><\/strong> of the current pixel be $y_{k}$<\/em>\u200b, and the next consecutive pixel in the y-direction<\/em><\/strong> be $y_{k}$+1($y_{next}$)<\/em>\u200b<\/em><\/strong>.<\/p>\n\n\n\n

Let the x-coordinate<\/em><\/strong> of the current pixel be $x_{k}$<\/em>\u200b<\/em><\/strong>, and the next consecutive pixel in the x-direction<\/em><\/strong> be $x_{k}$+1($x_{next}$)<\/em><\/em>.<\/p>\n\n\n\n

Define key variables:<\/p>\n\n\n\n

$\\text{current x} = x_{k}$
$\\text{current y} = y_{k}$
$\\text{next x} = x_{next} = x_{k} + 1 \\text{ always }$
$\\text{next y} = y_{next} = y_{k} + 1 \\text{ or } y_{k}$<\/p>\n\n\n\n

The distances d1<\/em><\/strong>\u200b and d2<\/em><\/strong>\u200b are defined as:<\/p>\n\n\n\n

$y = y_{k} + d_{1}$
$d_{1} = y \\text{ } – \\text{ } y_{k}$
$y_{k} + 1 = y + d_{2}$
$d_{2} = y_{k} + 1 \\text{ } – \\text{ } y$<\/p>\n\n\n\n

Using the line equation $y = mx + c$<\/em><\/strong><\/p>\n\n\n\n

$d_{1} = y \\text{ } – \\text{ } y_{k }$
$\\text{since } y = mx_{\\text{next}} + c $
$d_{1} = mx_{\\text{next}} + c \\text{ } – \\text{ } y_{k}$
$d_{2} = y_{k} + 1 \\text{ } – \\text{ } y$
$\\text{since } y = mx_{\\text{next}} + c$
$d_{2} = y_{k} + 1 \\text{ } – \\text{ } (mx_{\\text{next}} + c)$
$d_{2} = y_{k} + 1 \\text{ } – \\text{ } mx_{\\text{next}} \\text{ } – \\text{ } c$<\/p>\n\n\n\n

Subtracting d1<\/em><\/strong>\u200b from d2<\/strong><\/em>:<\/p>\n\n\n\n

$d_{1} \\text{ } – \\text{ } d_{2} = mx_{next} + c \\text{ } – \\text{ } y_{k} \\text{ } – \\text{ } (y_{k} + 1 \\text{ } – \\text{ } mx_{next} \\text{ } – \\text{ } c) $
$d_{1} \\text{ } – \\text{ } d_{2} = mx_{next} + c \\text{ } – \\text{ } y_{k} \\text{ } – \\text{ } y_{k} \\text{ } – \\text{ } 1 + mx_{next} + c $
$d_{1} \\text{ } – \\text{ } d_{2} = 2mx_{next} \\text{ } – \\text{ } 2y_{k} + 2c \\text{ } – \\text{ } 1$<\/p>\n\n\n\n

Removing the Slope (m)<\/h3>\n\n\n\n

We need to remove the slope (m)<\/em><\/strong> in Bresenham\u2019s Line Algorithm because:<\/p>\n\n\n\n

    \n
  1. Avoid Floating-Point Calculations<\/strong>:
    The slope \\(m = \\dfrac{\\nabla y}{\\nabla x}\\) often results in fractional values, requiring floating-point arithmetic. Floating-point operations are slower and less efficient compared to integer arithmetic, especially on older or resource-constrained systems.<\/li>\n\n\n\n
  2. Use Only Integers<\/strong>:
    By eliminating m<\/em><\/strong>, we can reformulate the decision-making process entirely using integers. This makes the algorithm faster and avoids precision errors that can occur with floating-point numbers.<\/li>\n\n\n\n
  3. Simplify Computations<\/strong>:
    Removing m<\/em><\/strong> simplifies the math by focusing only on differences (\u0394x and \u0394y)<\/em><\/strong> between pixel coordinates. This makes the algorithm easier to implement and more computationally efficient.<\/li>\n<\/ol>\n\n\n\n

    <\/em>\\(m = \\dfrac{\\nabla y}{\\nabla x}\\)<\/p>\n\n\n\n

    Substituting m <\/em><\/strong>into the equation:<\/p>\n\n\n\n

    \\(\\nabla x \\times (d_{1} – d_{2}) = (2 \\dfrac{\\nabla y}{\\nabla x} x_{next} – 2y_{k} + 2c – 1) \\times \\nabla x \\)
    \\(\\nabla x \\times (d_{1} – d_{2}) = 2 \\nabla y x_{next} – 2y_{k} \\nabla x + 2c\\nabla x – \\nabla x \\)
    \\(\\nabla x \\times (d_{1} – d_{2}) = 2 \\nabla y (x_{k} + 1) – 2y_{k} \\nabla x + 2c\\nabla x – \\nabla x \\)
    \\(\\nabla x \\times (d_{1} – d_{2}) = 2 \\nabla y x_{k} + 2 \\nabla y – 2y_{k} \\nabla x + 2c\\nabla x – \\nabla x \\)
    \\(\\nabla x \\times (d_{1} – d_{2}) = 2 \\nabla y x_{k} – 2\\nabla xy_{k} \\textcolor{red}{ + (2 \\nabla y + 2c\\nabla x – \\nabla x)} \\)<\/p>\n\n\n\n

    Ignoring constant terms (as they do not affect the decision-making):<\/p>\n\n\n\n

    \\(\\nabla x \\times (d_{1} – d_{2}) = 2 \\nabla y x_{k} – 2\\nabla xy_{k} \\)
    \\(\\text{Here we need to know about } (d_{1} – d_{2}) \\text{ is } >0 \\text{ or } < 0 \\)
    \\(\\text{Then we can ignore } \\nabla x \\)
    \\(\\text{We will take } \\nabla x \\times (d_{1} – d_{2}) \\text{ as } d_{k} (\\text{Decision variable k})\\)
    \\(d_{k} = 2 \\nabla y x_{k} – 2\\nabla xy_{k}\\)<\/p>\n\n\n\n

    \\(\\text{So } d_{next} = 2 \\nabla y x_{next} – 2\\nabla xy_{next} \\)<\/p>\n\n\n\n

    Updating the Decision Variable<\/h3>\n\n\n\n

    For the next step, the decision variable \\(d_{next}\\)\u200b<\/em> is calculated as:<\/p>\n\n\n\n

    \\(d_{next} = 2 \\nabla y x_{next} – 2\\nabla xy_{next} \\)
    \\(\\text{Lets’s subtract } d_{k} \\text{ from } d_{next}\\)
    \\(d_{next} – d_{k} = (2 \\nabla y x_{next} – 2\\nabla xy_{next}) – (2 \\nabla y x_{k} – 2\\nabla xy_{k}) \\)
    \\(d_{next} – d_{k} = 2 \\nabla y x_{next} – 2\\nabla xy_{next} – 2 \\nabla y x_{k} + 2\\nabla xy_{k} \\)
    \\(d_{next} – d_{k} = 2 \\nabla y x_{next} – 2 \\nabla y x_{k} – 2\\nabla xy_{next} + 2\\nabla xy_{k} \\)
    \\(d_{next} – d_{k} = 2 \\nabla y (x_{next} – x_{k}) – 2\\nabla x (y_{next} – y_{k}) \\)
    \\(d_{next} = [2 \\nabla y (x_{next} – x_{k}) – 2\\nabla x (y_{next} – y_{k})] + d_{k} \\)<\/p>\n\n\n\n

    Depending on the value of \\(d_{k}\\)\u200b:<\/p>\n\n\n\n

    \\(\\textcolor{black}{\\text{If }} \\textcolor{red}{d_{k}} < 0 \\)
    \\(y_{next} = y_{k} \\)
    \\(d_{next} = [2 \\nabla y (x_{next} – x_{k}) – 2\\nabla x (y_{next} – y_{k})] + d_{k} \\)
    \\(d_{next} = [2 \\nabla y (x_{k} + 1 – x_{k}) – 2\\nabla x (y_{k} – y_{k})] + d_{k} \\)
    \\(d_{next} = 2 \\nabla y + d_{k} \\)<\/p>\n\n\n\n

    \\(\\textcolor{black}{\\text{If }} \\textcolor{red}{d_{k}} \\geq 0 \\)
    \\(y_{next} = y_{k} + 1 \\)
    \\(d_{next} = [2 \\nabla y (x_{next} – x_{k}) – 2\\nabla x (y_{next} – y_{k})] + d_{k} \\)
    \\(d_{next} = [2 \\nabla y (x_{k} + 1 – x_{k}) – 2\\nabla x (y_{k} + 1 – y_{k})] + d_{k} \\)
    \\(d_{next} = 2 \\nabla y – 2 \\nabla x + d_{k} \\)<\/p>\n\n\n\n

    Initializing the Algorithm<\/h3>\n\n\n\n

    To start the algorithm, we calculate the initial decision variable \\(d_{1}\\)\u200b:<\/p>\n\n\n\n

    \\(d_{1} = 2 \\nabla y x_{1} – 2\\nabla xy_{1} \\textcolor{red}{ + (2 \\nabla y + 2c\\nabla x – \\nabla x)}\\)
    \\(d_{1} = 2 \\nabla y x_{1} – 2\\nabla xy_{1} + 2 \\nabla y + 2c\\nabla x – \\nabla x\\)
    \\(\\textcolor{black}{\\text{Now we have to get rid of }} \\textcolor{red}{c} \\textcolor{black}{\\text{ because it is unknown}} \\)
    \\(d_{1} = 2 \\nabla y x_{1} – 2\\nabla xy_{1} + 2 \\nabla y + 2c\\nabla x – \\nabla x\\)
    \\(\\textcolor{black}{\\text{According to }} y = mx+c\\)
    \\(c = y -mx \\)
    \\(m = \\dfrac{\\nabla y}{\\nabla x}\\)
    \\(c=y-\\dfrac{\\nabla y}{\\nabla x}x\\)
    \\(d_{1} = 2 \\nabla y x_{1} – 2\\nabla xy_{1} + 2 \\nabla y + 2c\\nabla x – \\nabla x \\textcolor{black}{\\text{ Let’s apply it here,}}\\)
    \\(d_{1} = 2 \\nabla y x_{1} – 2\\nabla xy_{1} + 2 \\nabla y + 2(y_{1}-\\dfrac{\\nabla y}{\\nabla x}x_{1})\\nabla x – \\nabla x \\)
    \\(d_{1} = 2 \\nabla y x_{1} – 2\\nabla xy_{1} + 2 \\nabla y + 2\\nabla x(y_{1}-\\dfrac{\\nabla y}{\\nabla x}x_{1}) – \\nabla x \\)
    \\(d_{1} = 2 \\nabla y x_{1} – 2\\nabla xy_{1} + 2 \\nabla y + 2\\nabla xy_{1}-\\dfrac{\\nabla y}{\\nabla x}x_{1}2\\nabla x – \\nabla x \\)
    \\(d_{1} = 2 \\nabla y x_{1} – 2\\nabla xy_{1} + 2 \\nabla y + 2\\nabla xy_{1}-
    2\\nabla yx_{1} – \\nabla x \\)
    \\(d_{1} = 2 \\nabla y – \\nabla x \\)<\/p>\n\n\n\n

    Summary of the Algorithm<\/h3>\n\n\n\n
      \n
    1. Start at the initial pixel (x0,y0\u200b)<\/em><\/strong>.<\/li>\n\n\n\n
    2. Compute the initial decision variable: \\(d_{1} = 2 \\nabla y – \\nabla x \\)<\/em><\/strong><\/li>\n\n\n\n
    3. At each step, update the decision variable:<\/li>\n<\/ol>\n\n\n\n