본문 바로가기
알고리즘

Anti-aliased 선 긋기 (Xiaolin Wu's line algorithm)

by hansoo.labs 한수댁 2020. 7. 28.

Bresenham 선 긋기 방법은 매우 빠르나 경계선이 드러나서 보기에 좋지 않다. Xiaolin Wu의 안티알리아스 선 긋기를 배워본다.

이 알고리즘은 한쌍의 픽셀을 연달아 찍어서 선을 그리는 것인데, 반복동작으로 선의 길이만큼 여러 쌍의 픽셀을 그리고 양 끝점을 따로 계산해서 픽셀을 찍는다.

위에서 보는 것처럼 선은 픽셀칸의 중심을 정확하게 지나가는 것이 아니기 때문에, 선분에 영향력을 미치는 2개의 픽셀칸의 밀도를 조절하여 블러가 된 선을 그릴 수 있다. 픽셀 칸의 밀도를 1로 보았을 때, 선분 위에 있는 칸은 1-a 의 농도를 갖고 선분 아래에 있는 칸은 1-b의 농도를 갖으면 된다.

우선 기울기가 1보다 작은 경우만 생각하자. 나머지의 경우는 대칭을 생각하면 쉽게 확장이 가능하다. 이 경우 x 좌표값을 독립변수로 하고, y를 종속변수로 두면, y 값은 일반적으로 실수 값을 갖는다. 이 y 값에 가까운 두 개의 정수 y 값에 해당하는 픽셀에 색을 칠하는데, 이때 농도는 거리의 차이에 반하도록 잡는다.

// 위치 (x,y)에 2개의 픽셀을 채울 경우
(x,y) -> (x, int(y))
         명암: 1 - (y - int(y))
      -> (x, int(y) + 1)
         명암: y - int(y)

처음과 끝 점은 좀 더 특별한 처리가 필요하다.

블러링 효과를 주기 위해서 x에 대한 가중치도 더한다. x가 정수값을 취할 경우 50퍼센트의 가중치를 주는 것을 기준으로 하면, x+0.5 를 기준으로 이것의 정수값이 벗어나는 정도를 취하면 된다. 그리고 x의 경우는 가장 가까운 정수에서부터 시작한다.

(x,y) -> (int(x+.5), int(y)), 
         명암: (1 - (y - int(y))) \* (1 - (x+.5 - int(x+.5)))
      -> (int(x+.5), int(y) + 1)
         명암: (y - int(y)) \* (1 - (x+.5 - int(x+.5)))

오른쪽 끝 점에서 x의 가중치는 왼쪽의 complement 이므로 x+.5-int(x+.5)로 바꾸어야 한다.

구현된 샘플. 클릭해 보아요.

p5js 로 선긋기 함수를 정리하면,


// fractional part of n
function fpart(n) {
  return n - int(n);
}

function drawPixel(x, y, b) {
  stroke(color(0, 0, 0, b * 255)); // r,g,b,a
  point(x, y);
}

function drawLine(x1, y1, x2, y2) {
  var dx, dy, temp;
  // lean of the line
  var grad;
  // 0~1
  var brightness;
  dx = x1 - x2;
  dy = y1 - y2;
  // if the slope is same or lower than 1
  if (abs(dx) > abs(dy)) {
    //if line is back to front
    if (x2 < x1) {
      temp = x1;
      x1 = x2;
      x2 = temp;
      temp = y1;
      y1 = y2;
      y2 = temp;
    }

    dx = x2 - x1;
    dy = y2 - y1;
    grad = dy / dx;
    // --
    // start point: integer more close to x1
    let xs = int(x1 + 0.5);
    // y position at xs
    let ys = y1 + grad * (xs - x1);
    let ixs = xs;
    let iys = int(ys);
    // effect from x1
    var xgap = 1 - fpart(x1 + 0.5);
    // draw pixel
    brightness = (1 - fpart(ys)) * xgap;
    drawPixel(ixs, iys, brightness);
    brightness = fpart(ys) * xgap;
    drawPixel(ixs, iys + 1, brightness);
    // --
    // end point : integer more closer to x2
    let xe = int(x2 + 0.5);
    // y position at xe
    let ye = y2 + grad * (xe - x2);
    xgap = fpart(x2 + 0.5);
    let ixe = xe;
    let iye = int(ye);
    brightness = (1 - fpart(ye)) * xgap;
    drawPixel(ixe, iye, brightness);
    brightness = fpart(ye) * xgap;
    drawPixel(ixe, iye + 1, brightness);
    // --
    // ixs + 1 ~~> ixe - 1
    // y position next to xs
    var yy = ys + grad;
    for (var i = ixs + 1; i < ixe; i++) {
      drawPixel(i, int(yy), 1 - fpart(yy));
      drawPixel(i, int(yy) + 1, fpart(yy));
      yy += grad;
    }
  }
  // if the slope is bigger than 1
  // handle the vertical lines in the same way as the horizontal ones
  // but swap the role of x and y
  else {
    // if line is back to front
    if (y2 < y1) {
      temp = x1;
      x1 = x2;
      x2 = temp;
      temp = y1;
      y1 = y2;
      y2 = temp;
    }

    dx = x2 - x1;
    dy = y2 - y1;
    grad = dx / dy;
    // --
    // start point: integer more close to y1
    let ys_v = int(y1 + 0.5);
    // x position at ys
    let xs_v = x1 + grad * (ys_v - y1);
    let iys_v = ys_v;
    let ixs_v = int(xs_v);
    // effect from y1
    var ygap = 1 - fpart(y1 + 0.5);
    // draw pixel
    brightness = (1 - fpart(xs_v)) * ygap;
    drawPixel(ixs_v, iys_v, brightness);
    brightness = fpart(xs_v) * ygap;
    drawPixel(ixs_v, iys_v + 1, brightness);
    // --
    // end point : integer more closer to y2
    let ye_v = int(y2 + 0.5);
    // y position at xe
    let xe_v = x2 + grad * (ye_v - y2);
    ygap = fpart(y2 + 0.5);
    let iye_v = ye_v;
    let ixe_v = int(xe_v);
    brightness = (1 - fpart(xe_v)) * ygap;
    drawPixel(ixe_v, iye_v, brightness);
    brightness = fpart(xe_v) * ygap;
    drawPixel(ixe_v, iye_v + 1, brightness);
    // --
    // iys_v + 1 ~~> iye_v - 1
    // x position next to ys_v
    var xx = xs_v + grad;
    for (var iy = iys_v + 1; iy < iye_v; iy++) {
      drawPixel(int(xx), iy, 1 - fpart(xx));
      drawPixel(int(xx) + 1, iy, fpart(xx));
      xx += grad;
    }
  }
}

참고 --

댓글2

  • BlogIcon salbang 2012.04.13 14:47

    다 좋은데 Wu 선생님 알고리즘은 수평선이나 수직선 때 가장 두껍게 보이고 45도짜리 대각선일 때 가장 얇게 보여요. Pixel density 문제가 있는데 각도가 다른 직선을 이어서 계속 그리면 눈에 거슬립니다.
    답글

    • 좋은 말씀이에요. 선긋기에 대해서는 더 깊이 들어가진 않아서 모르겠지만, 더 좋은 방법이 있겠죠~? Wu 알고리즘을 조금 보완해도 좋을 것 같해요.