[💬] 겁나 깔끔한 직선 그리기 알고리즘

[점돌맨(drhubert)]

https://zingl.github.io/bresenham.html

Bresenham

무려 2012년에 나온 나름 따끈따끈한 논문.

브리젠햄이 1962년도에 나온거니까 상대적으로 엄청 최근 논문임. 라인만을 위한게 아니라 여러가지 곡선을 쉽게 그리기위한 알고리즘인데

코드 자체가 너무 간결하고 깔끔하다. 

void plotLine(int x0, int y0, int x1, int y1)

{ int dx = abs(x1-x0), sx = x0<x1 ? 1 : -1; int dy = -abs(y1-y0), sy = y0<y1 ? 1 : -1; int err = dx+dy, e2; /* error value e_xy */ for(;;){ /* loop */ setPixel(x0,y0); if (x0==x1 && y0==y1) break; e2 = 2*err; if (e2 >= dy) { err += dy; x0 += sx; } /* e_xy+e_x > 0 */ if (e2 <= dx) { err += dx; y0 += sy; } /* e_xy+e_y < 0 */ } }

이게 끝 

결국 abs(dx), abs(dy)로 항상 기울기가 양수가 되게 하고 현재점에 대해 위,대각선,오른쪽 3점중에 하나를 선택하게 하는 알고리즘인데

근본은 브리젠험처럼 에러 누적해서 적은 에러를 선택하는 것과 같음.

간단히 애기하면 저 비교문이랑 누적하는 부분은 대각선 에러값에 대해 위쪽 픽셀의 에러값이 대각선보다 더 크면  x+1,  오른쪽 픽셀도 마찬가지로 대각선 픽셀의 에러값과 비교해서 에러값의 절대값이 대각선이 더 적으면 y+1 해주는거임. 그걸 최적화 한다고 코드로 좀 꼬아놓은 것.

위 사이트 가보면 직선뿐만 아니라 여러가지 있는데 2D게임에서 Line 검색 같은거할 때 나름 유용하지 않을까 싶네.

브리젠험 싫은게 케이스마다 대응해야하는게 코드도 더러워져서 싫었는데 위 알고리즘은 너무 깔끔해서 맘에드네.

[익명(222.117)]

dda 알고리즘 아님? 2012년보다 더 오래됐을텐데

[점돌맨(drhubert)]

dda 아님. 위에 링크 걸어놨으니 관심있음 살펴봐

[점돌맨(drhubert)]

dda는 라인을 conservative하게 그림. 픽셀이 라인에 걸쳐 있으면 무조건 그리는데 브레젠험은 픽셀 가운데 값이 어디에 있느냐에따라 달라짐

[익명(222.117)]

아 브리젠햄을 일반화시킨 함수구나 근데 dda도 기본적으로는 걸친 픽셀을 무조건 그린 건 아닐텐데 코드 다시 읽어봐도 그럼

[정공개발자(firetruck4545)]

[불타는키보드(1bnmaker)]

[익명(14.45)]

코드 보고 한발 뺐다 고맙다