한양과기고 에듀테크 수업도구 대시보드

브레젠험 직선 알고리즘 (Bresenham's Line Algorithm)

모니터는 네모난 픽셀 격자다. 그런데 두 점을 잇는 직선은 대각선처럼 비스듬할 수 있다. "어느 픽셀을 켜야 가장 곧은 선처럼 보일까?"를 y = mx + b 로 풀면 매 칸마다 실수 곱셈·반올림이 필요하다. 1962년 브레젠험은 이걸 정수 덧셈·뺄셈·비교만으로 바꿨다. 오래된 GPU도, 오실로스코프 플로터도 쓰던 고전 알고리즘이다.

1. 격자 위에서 한 칸씩 그어보기

격자를 클릭하면 시작점 → 끝점을 새로 지정합니다.

현재 픽셀 (x, y)

–

누적 오차 D (2·err)

–

판정

–

켠 픽셀 수 / 실수 연산

0 / 0

속도 110ms

이상적인 직선(빨강) 겹쳐보기

초록 칸은 확정된 픽셀, 파란 테두리는 지금 검사 중인 후보다. 한 걸음마다 D 하나만 더하고, 부호를 보고 y를 올릴지 말지만 정한다. 실수 연산 카운터가 0에서 멈춰 있는 것에 주목하자.

2. 핵심 아이디어 — "오차를 정수로 들고 다니기"

기울기가 완만한 선(|dx| ≥ |dy|)을 생각하자. x를 한 칸씩 오른쪽으로 옮기며, 각 x에서 y를 그대로 둘지 / 1 올릴지만 결정하면 된다. 진짜 직선의 y값과 현재 찍은 y값의 차이(오차)를 들고 다니는데, 이 오차에 2·dx를 곱해 분수를 없애면 전부 정수가 된다.

연산	순진한 방법 `y = mx + b`	브레젠험
한 픽셀마다	곱셈 1 + 덧셈 1 + 반올림 1 (실수)	덧셈/뺄셈 1~2 (정수)
자료형	float / double	int
오차 누적	반올림 오차가 쌓임	정확히 최근접 픽셀

왜 2·err를 볼까? 다음 픽셀 중점이 직선 위/아래 중 어디에 더 가까운지는 err + dy 와 dx − (err + dy) 의 대소로 갈린다. 양변에 2를 곱하면 2·err ≥ dx 인지만 비교하면 되고, 분모가 사라져 정수 비교가 된다.

3. 모든 8방향을 한 번에 처리하는 버전

def bresenham(x0, y0, x1, y1):
    dx = abs(x1 - x0);  sx = 1 if x0 < x1 else -1
    dy = -abs(y1 - y0); sy = 1 if y0 < y1 else -1
    err = dx + dy                # = 2·실제오차 의 정수 버전
    while True:
        plot(x0, y0)             # 픽셀 켜기
        if x0 == x1 and y0 == y1: break
        e2 = 2 * err
        if e2 >= dy: err += dy; x0 += sx   # 가로로 한 칸
        if e2 <= dx: err += dx; y0 += sy   # 세로로 한 칸

절댓값·부호(sx, sy) 트릭 덕분에 기울기·방향에 상관없이 이 8줄이 전부다. 곱셈은 2 * err 딱 하나인데, 이것도 err + err 또는 err << 1 (비트 시프트)로 바꿀 수 있다. 위 데모의 코드 하이라이트가 지금 실행 중인 줄을 보여준다.

4. 스텝별 계산 로그

step	x	y	err	2·err ≥ dy ?	2·err ≤ dx ?

5. 한 걸음 더

중점 원 알고리즘

같은 "정수 오차" 아이디어로 원도 그린다. 8분원만 계산하고 대칭 복사(8-way symmetry).

안티에일리어싱

Wu's line algorithm은 경계 픽셀의 밝기를 조절해 계단 현상을 부드럽게 한다.

DDA와 비교

DDA는 매 스텝 +m 실수 덧셈. 브레젠험은 정수라서 더 빠르고 오차가 안 쌓인다.

지금도 쓰인다

게임의 시야 판정(라인 오브 사이트), 타일 맵 레이캐스팅, CNC·3D 프린터 경로.