브레젠험 직선·원 래스터화 계산기

두 점을 잇는 선을 정수 덧셈과 부호 판정만으로 픽셀에 찍는 방법입니다. 1962년 잭 브레젠험이 IBM 플로터용으로 만들었고, 곱셈·나눗셈·소수를 전혀 쓰지 않아 지금까지도 그래픽스와 임베디드에서 쓰입니다.

되지만 느립니다. 칸마다 나눗셈과 반올림이 필요하고, 값을 누적하면 부동소수점 오차가 쌓입니다. 브레젠험은 「지금까지 실제 선에서 얼마나 벗어났는가」를 정수 하나에 담아 두고 더하고 빼며 부호만 보므로 오차가 쌓일 자리가 없습니다.

정확히 반 칸인 자리에서만 갈리고 나머지는 모두 같습니다. 예를 들어 실제 선이 y = 3.5를 지나는 칸에서 위로 붙일지 아래로 붙일지는 관례의 문제라 구현마다 다릅니다. 그 밖의 자리에서는 두 방법이 언제나 같은 픽셀을 고릅니다.

기울기와 방향에 따라 나뉘는 여덟 가지 경우입니다. 원래 브레젠험은 오른쪽 위로 완만하게 올라가는 한 경우만 다루고 나머지는 좌표를 뒤집어 처리했습니다. 지금 널리 쓰이는 꼴은 x·y의 부호를 따로 빼 두어 여덟 경우를 한 번에 처리합니다 — 이 도구도 그 꼴입니다.

중점 원 알고리즘을 씁니다. 「다음 픽셀의 중점이 원 안인가 밖인가」를 정수 판정값 하나로 가르는데, 원리는 직선과 같습니다. 8분원만 그린 뒤 나머지는 대칭으로 찍어 계산이 8분의 1로 줍니다.

씁니다. 안티앨리어싱을 하는 요즘 렌더러는 다른 방법을 쓰지만, 픽셀 단위로 확실하게 찍어야 하는 곳 — 임베디드 디스플레이, 픽셀 아트, 격자 위의 시야 판정, 지도 타일 위의 선분 훑기 — 에서는 여전히 이 방법이 기본입니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.