픽셀 위에 직선 그리는 알고리즘 - 1. Digital Differential Analyzer (DDA) 알고리즘

화면에 직선을 그리기 위해 고려할 것들

- 현대 모니터들은 전부 픽셀로 이루어져 있습니다.

- 이 위에 직선을 그린다면 최대한 직선에 가깝게 표현되어야 합니다.

   이 뜻은 픽셀들의 연속으로 되어야 하며 끊기지 않아야 한다는 것입니다.

- 픽셀의 중심이 좌표의 정수 부분이 됩니다.

 

 

Digital Differential Analyzer - DDA 알고리즘

 DDA 알고리즘은 양 끝점이 주어졌을 때 화면 위 직선을 그릴 수 있는 알고리즘입니다. 원리는 아래에 있으며 아주 간단합니다.

 

양 끝점을 이용해서 X, Y의 증분을 구합니다.
이후 X 가 1 증가할 때 Y가 어느정도로 증가하는지를 계산,
좌표를 구하고 해당 좌표의 픽셀을 채워줍니다.

위 정의의 경우 X가 +1 될때 Y가 어느정도로 증가하는지를 구하는 것으로 기울기가 1 이하임을 전제하고 있습니다. 

위 그림을 보면 만약 기울기가 1 이상일때 X가 1 증가하면 Y 좌표는 급격하게 늘어나게 됩니다. 이전에 (x, y) 좌표에 픽셀을 칠했다고 하면 x+1에서는 (x+1, 2y + 2) 같은 점을 찍게 되므로 직선이 끊길 우려가 있습니다. 이때는 간단하게 x 관점에서 진행하던 알고리즘을 y관점에서 진행해준다면 해결이 되는 문제입니다.

 

void Set_Pixel(int x, int y){
    // x, y 좌표에 색을 칠함
}

void DDA(int x1, int y1, int x2, int y2){
    // x, y축의 증분
    int dx = x2 - x1;
    int dy = y2 - y1;
    // 총 칠해야 할 픽셀의 가로(y의 경우 세로) 길이
    int steps;
    // 시작점 지정
    float x = x1, y = y1;

    float x_incre, y_incre;

    if(fabs(dx) > fabs(dy))
        steps = fabs(dx);
    else 
        steps = fabs(dy);
    
    // step가 하나 증가할 때 x, y 좌표가 얼마나 증가할지 지정해준다
    x_incre = dx / steps;
    y_incre = dy / steps;

    // 시작 좌표 x(=x1), y(=y1)을 칠해준다
    Set_Pixel(round(x), round(y));

    for(int i = 0; i < steps; i++){
        x += x_incre;
        y += y_incre;

        Set_Pixel(round(x), round(y));
    }
}

 

위 이론을 코드상으로 나타낸 모습입니다. 다른 직선 그리기 알고리즘들에 비해 float의 연산들을 사용하는 등 성능상으로는 좋은 알고리즘이 아닙니다.

 

void Set_Pixel(int x, int y){
    // x, y 좌표에 색을 칠함
}

 

일단 위 코드에서 Set_Pixel 함수를 정의해 들어오는 (x, y) 좌표에 해당하는 픽셀에 색을 칠하는 함수가 있다고 가정합시다.

 

    // x, y축의 증분
    int dx = x2 - x1;
    int dy = y2 - y1;
    // 총 칠해야 할 픽셀의 가로(y의 경우 세로) 길이
    int steps;
    // 시작점 지정
    float x = x1, y = y1;
    
    float x_incre, y_incre;

 

 이후 직선의 방정식에서 기울기를 구하는 것처럼 x, y의 증분을 구해서 변수에 저장을 해 줍니다. 이후 x, y 변수에 시작 점을 지정해 주고 steps 변수를 정의해 줍니다. 

 steps 변수의 경우 얼마만큼 이 함수가 이동해야 하는지를 알려줄 변수입니다.

 위 그림을 보면 이해가 될겁니다. 위의 경우 기울기가 1 이하인 직선의 방정식을 나타내고 있으며 픽셀을 그릴 때 X 축이 기준이 되며 X 축으로 총 6번을 실행해야 합니다. 이 6 번을 뜻하는게 steps 변수가 됩니다.

 

    if(fabs(dx) > fabs(dy))
        steps = fabs(dx);
    else 
        steps = fabs(dy);

 

 그리고 기울기가 1 이상인 경우 y축을 기준으로 해 줘야 하기 때문에 위 if-else 문에서 x, y 를 바꿔주는 작업을 실행하게 됩니다.

 

    // step가 하나 증가할 때 x, y 좌표가 얼마나 증가할지 지정해준다
    x_incre = dx / steps;
    y_incre = dy / steps;

    // 시작 좌표 x(=x1), y(=y1)을 칠해준다
    Set_Pixel(round(x), round(y));

 

이후 step이 한번 증가하게 되면 x, y가 얼마나 증가할지를 결정해주며 시작 좌표에 픽셀을 칠해줍니다.

 

    for(int i = 0; i < steps; i++){
        x += x_incre;
        y += y_incre;

        Set_Pixel(round(x), round(y));
    }

 

 마지막으로 i를 선언해 steps가 될때까지 0부터 1씩 증가시키며 이 과정에서 step만큼 증가하는 x, y 양을 좌표에 더해줍니다. 그런 다음 구해진 픽셀에 색을 칠해주면 됩니다. 

---

 전체적으로 간단한 알고리즘으로 기울기를 구한 다음 x(기울기에 따라 y)가 증가할 때마다 어느 좌표에 점이 찍히는지 구하는 알고리즘입니다.

 

 보기에는 간단하고 이해하기 쉽지만 실제로 그래픽스에 적용하기에는 무거운 알고리즘인데요. 수많은 점들에 대해서 float 값을 선언하고 float 연산들을 진행하기 때문에 좌표들이 많아질수록 성능상의 문제가 생기게 됩니다. 그래서 이후 DDA 알고리즘의 개선판으로 Bresenham's Algorithm이 나오게 됩니다.