Bresenham's algorithm

한국어 버전 보기

Bresenham's algorithm is an algorithm designed to draw straight lines only by counting integers, excluding real number calculations that make complex and slow calculations in computer graphics. The coordinates calculated using the formula of a straight line are rounded off or rounded to an integer in order to be displayed on the screen. Let's take a look at the process of converting these discarded complex calculations with decimals into simple integer operations using Bresenham's formula.

First, the equation of a straight line passing through two points is as follows:

y - y₁ = (x₂ - x₁) / (y₂ - y₁) * (x - x₁>)
y = (x₂ - x₁)/(y₂ - y₁) * (x - x₁) + y₁

For example, among the points on a straight line passing through (2, 1) and (6, 4), when x is 3, the value of y is..

y - 1 = (6 - 2) / (4 - 1) * (3 - 2)
y = 4 / 3 * 1 + 1
y = 2.333333...

It can come out like and is usually expressed as a formula like y = mx + n . where m is the slope of the line and n is the value of the y-intercept.

Numerous points on a straight line can be expressed as real values, but what can be displayed on the screen is an integer value.

When the two points on the y-axis are somewhere between y_i and y_i + 1, select the closest one. In the example above, 2.333... This means that you can specify the y-coordinate to the nearest 2 out of 2 and 3

d₁ = y - y_i
d₂ = y_i + 1 - y

If d₁ - d₂ is less than 0, it is closer to y_i, and if is greater than y It's closer to the _i + 1 side. What we need here is whether d₁ - d₂ is greater than or less than 0, not the actual value.

Let's go back to the Bresenham algorithm. The first step in Bresenham's algorithm is to select the axis with the largest displacement at the start and end of the straight line among the x-axis and y-axis. It is to find the nearest integer value of the value of the other axis, increasing by 1 from the start to the end based on the axis with the largest displacement.

In the above examples (2, 1) and (6, 4), the displacement on the x-axis is larger, so let's see how to find the y value by increasing by 1 on the x-axis. If the y-axis displacement is larger, you can think of x and y inversely.

d₁ = y - y_i
      = m((x_i + 1) - x₁) + y₁ - y_i

The reason why it became m(x+1) instead of mx is to find the y at the x-axis incremented by 1. And d₂ can be defined as follows.

d₂ = (y_i + 1) - y = y_i + 1 - (m((x_i + 1) -x₁) + y₁)
     = y_i - m((x_i + 1) - x₁) - y₁ + 1

반응형

Now let's find the difference between the two distances.

d₁ - d₂ = m((x_i +1) - x₁) + y₁ - y_i - (y_i - m((x_i + 1) - x₁) - y₁ + 1)
              = m((x_i + 1) - x₁) + y₁ - y_i - y_i + m((x_i + 1) - x₁) + y₁ - 1
              = 2m((x_i + 1) - x₁) + 2y₁ - 2y_i - 1

Also, as already mentioned above, m is the gradient dy/dx, so

d₁ -d₂ = 2(dy/dx)((x_i+1) - x₁) + 2y₁ - 2y_i - 1

is defined as above.

Above, dx represents displacement, so it is unconditionally positive, and what we are curious about is whether d₁ - d₂ is positive or negative. Even if the dx value is multiplied by both sides and eliminated from the right term, the result does not change, so we will remove the division part by multiplying both sides by dx.

dx(d₁ - d₂) = 2dy((x_i+1) -x₁) + 2dxy₁ - 2dxy_i - dx
                   = 2dyx_i + 2dy - 2dyx₁ + 2dxy₁ - 2dxy_i - dx
                   = 2dyx_i - 2dxy_i + 2dy - 2dyx₁ + 2dxy₁ - dx

In the above formula, I tried to organize the variable part into x_i or y_i part and the constant part that does not need to be recalculated once it is calculated. The part written in bold is the constant part that has the same value after one calculation. Since the constant part is C and only the sign is needed, not the actual value, I'll define it as dx(d₁ - d₂) is simplified variable p_i.

p_i = 2dyx_i - 2dxy_i + C

Above, if 'd₁ - d₂ is less than 0, it is closer to y_i, and if is greater than It's closer to the y_i + 1 side'. If p_i is negative, then y becomes y_i , if positive, then y_i + 1.

The following p_i+1 can be obtained as 2dyx_i+1 - 2dxy_i+1 + C .

But here x increases by 1. Therefore, the previous x_i+1 - x_i becomes 1, so it is possible to change the above 2dyx_i+1 part to just dy . And now we are solving the equation. Equations need only satisfy the condition that both terms in the middle are equal. So we replace the previous formula '2dyx_i - 2dxy_i + C' with '2dyx_i+1 - 2dxy_{i+1< /sub> + C' and subtract pi from pi+1 to fit the equation. This way we can simplify the expression. The resulting formula is below.}

p_i+1 - p_i = 2dyx_i+1 - 2dxy_i+1 + C - (2dyx_i - 2dxy_i + C)
             = 2dyx_i+1 - 2dxy_i+1 + C - 2dyx_i + 2dxy_i - C
             = 2dy(x_i+1 - x_i) - 2dx(y_i+1 - y_i)

As already said above

x_i+1 - Since x_i is 1, it can be arranged as follows.

p_i+1 - p_i = 2dy(x_i+1- x_i) - 2dx(y_i+1- y_i)
             = 2dy - 2dx(y_i+1- y_i)

Now, if we only get the value of p_i+1,

p_i+1 = p_i + 2dy - 2dx(y_i+1- y_i)

p_i+1 = 2dyx_i+1 - 2dxy_i+1 + C is the formula p_{i+1</sub > = pi + 2dy - 2dx(yi+1- yi) It still looks complicated, but if you recall that the screen coordinates are integers and the difference between yi+1 and yi is 0 or 1.}

• If the value of i is positive, d2 is closer, so the next point will have a value 1 greater than the current yi. So,
  pi+1 = pi + 2dy - 2dx
  becomes,
• If the value of pi is negative, d1 is closer, so the next point equals the value of yi and yi+1 - yi equals 0, so
  pi+1 = pi + 2dy

It will be something like

 

The p_i+1 value calculated above becomes the p_i value of the next loop, so if you keep using it in the loop , find the first p0, substitute it with the next p_i value, find the location, and dot the dots.

using System;
using System.Collections;

public class Bresenham2D : IEnumerable
{
    Position start; // http://kukuta.tistory.com/185
    Position end;
        
    public Bresenham2D(Position start, Position end)
    {
        this.start = start;
        this.end = end;
    }
    
    public IEnumerator GetEnumerator()
    {
        int dx = Math.Abs(end.x - start.x); // 시작 점과 끝 점의 각 x 좌표의 거리
        int dy = Math.Abs(end.y - start.y); // 시작 점과 끝 점의 각 y 좌표의 거리
        
        if (dy <= dx)
        {
            int p = 2 * (dy - dx);
            int y = start.y;
            
            int inc_x = 1;
            if (end.x < start.x)
            {
                inc_x = -1;
            }
            
            int inc_y = 1;
            if (end.y < start.y)
            {
                inc_y = -1;
            }
            
            for (int x = start.x; (start.x <= end.x ? x <= end.x : x >= end.x); x += inc_x)
            {
                if (0 >= p)
                {
                    p += 2 * dy;
                }
                else
                {
                    p += 2 * (dy - dx);
                    y += inc_y;
                }
                yield return new Position(x, y);
            }
        }
        else
        {
            int p = 2 * (dx - dy);
            int x = start.x;
            
            int inc_x = 1;
            if (end.x < start.x)
            {
                inc_x = -1;
            }
            
            int inc_y = 1;
            if (end.y < start.y)
            {
                inc_y = -1;
            }
            
            for (int y = start.y; (start.y <= end.y ? y <= end.y : y >= end.y); y += inc_y)
            {
                if (0 >= p)
                {
                    p += 2 * dx;
                }
                else
                {
                    p += 2 * (dx - dy);
                    x += inc_x;
                }
                yield return new Position(x, y);
            }
        }
    }
 }