판 비교
1번째 줄 근처
추가: ## 개요
추가: 브레젠험 직선 알고리즘(Bresenham's line algorithm)은 래스터 디스플레이에서 두 점을 잇는 직선에 가장 가까운 픽셀들을 결정하는 선 그리기 알고리즘이다. 정수 덧셈, 뺄셈, 비트 시프트 연산만으로 동작하므로 과거 일반적인 컴퓨터 아키텍처에서 매우 저렴하게 실행할 수 있었으며, 비트맵 이미지에 선 기본 도형을 그리는 데 널리 쓰였다. 점진적 오류(incremental error) 알고리즘의 일종으로, 컴퓨터 그래픽스 분야에서 개발된 초기 알고리즘 중 하나다. 원래 알고리즘을 확장한 중점 원 알고리즘(midpoint circle algorithm)을 통해 원을 그리는 데도 활용된다. 우 알고리즘(Wu's algorithm) 같은 안티앨리어싱 지원 알고리즘이 현대 그래픽스에서 자주 쓰이지만, 브레젠험 알고리즘은 속도와 단순성 덕분에 여전히 중요하다. 플로터 같은 하드웨어, 최신 그래픽 카드의 GPU, 다수 소프트웨어 그래픽스 라이브러리에 구현되어 있으며, 펌웨어나 그래픽 하드웨어에 내장되기도 한다. 오늘날 "브레젠험" 명칭은 원 알고리즘을 확장·수정한 알고리즘 계열을 통칭하기도 한다.[1][2][3]
추가:
추가: ## 역사·유래
추가:
추가: 1962년 IBM 산호세 개발 연구소에서 잭 엘턴 브레젠험(Jack Elton Bresenham)이 개발했다. 당시 캘컴프(Calcomp) 플로터가 IBM 1401에 1407 타자기 콘솔을 통해 연결되어 있었고, 알고리즘은 1962년 여름(아마 그보다 한 달 정도 앞선 시점)부터 실무에 투입됐다. 당시 프로그램은 기업 간 자유롭게 공유돼 캘컴프(짐 뉴랜드, 캘빈 헤프테)에도 복사본이 전해졌으며, 브레젠험이 1962년 가을 스탠퍼드대로 복귀하면서 스탠퍼드 컴퓨팅 센터 라이브러리에도 사본을 비치했다. 1963년 덴버에서 열린 ACM 전국 대회에서 발표됐으나 그해는 논문집이 발간되지 않고 연사·주제 목록만 Communications of the ACM에 실렸다. 발표 후 IBM Systems Journal 관계자가 논문 게재를 요청해 1965년에 정식 출판됐다.[2][3]
추가:
추가: ## 작동 방식과 유형
추가:
추가: ### 좌표계와 기본 가정
추가:
추가: 좌상단을 원점 (0,0)으로 두고 x축은 오른쪽, y축은 아래쪽으로 증가한다. 픽셀 중심은 정수 좌표를 갖는다. 선분 양 끝점은 \((x_0, y_0)\)와 \((x_1, y_1)\)이며, 첫 번째 좌표는 열(column), 두 번째는 행(row)이다. 알고리즘은 우선 \(x_0 \le x_1\), \(y_0 \le y_1\)이고 수평 투영 \(x_1 - x_0\)이 수직 투영 \(y_1 - y_0\)보다 긴 제1팔분면(기울기 \(0 < m < 1\))만 다룬 뒤, 대칭·교환으로 나머지 팔분면으로 확장한다.[2][3]
추가:
추가: ### 핵심 아이디어: 오차 누적과 중간점 판정
추가:
추가: 이상적인 직선 방정식은
추가: \[
추가: \frac{y - y_0}{y_1 - y_0} = \frac{x - x_0}{x_1 - x_0}
추가: \]
추가: 로 쓰고, 열 \(x\)를 알 때 행 \(y\)는
추가: \[
추가: y = \frac{y_1 - y_0}{x_1 - x_0}(x - x_0) + y_0
추가: \]
추가: 를 가장 가까운 정수로 반올림해 구할 수 있다. 기울기 \(m = \Delta y / \Delta x\)는 끝점 좌표만으로 미리 계산 가능하며, \(y_0\)에서 시작해 \(x\)가 1 증가할 때마다 \(m\)을 더해 이상적 \(y\)를 얻는다.
추가:
추가: 실제 구현에서는 \(y\) 좌표를 직접 추적하지 않고 **오차(error) 변수**를 유지한다. 오차는 "선이 현재 픽셀을 벗어나는 지점"부터 "픽셀 상단 가장자리"까지 거리의 음수값으로 정의된다. 초기값은 \(y_0 - 0.5\)(픽셀 중심 기준)이며, \(x\)가 1 증가할 때마다 \(m\)을 더한다. 오차가 0.5를 초과하면 선이 위쪽으로 한 픽셀 이동했음을 의미하므로 \(y\)를 1 증가시키고 오차에서 1을 빼서 새 픽셀 상단으로부터의 거리로 갱신한다.[2][3]
추가:
추가: ### 정수 연산만으로 변환 (암시적 방정식)
추가:
추가: 기울기-절편 형태 \(y = mx + b\)는 수직선을 표현 못 하므로, 대수적 변형으로 정수 계수 암시적 방정식 \(f(x, y) = Ax + By + C = 0\)을 만든다. 여기서
추가: \[
추가: A = \Delta y = y_1 - y_0,\quad B = -\Delta x = -(x_1 - x_0),\quad C = (\Delta x)b
추가: \]
추가: 모두 정수이므로 \(x, y\)가 정수일 때 \(f(x, y)\)도 정수다. 선 위 점은 \(f=0\), 양쪽 반평면은 \(f>0\) / \(f<0\)로 구분된다.
추가:
추가: 예: \(y = \frac12 x + 1\) → \(f(x, y) = x - 2y + 2\). (2,2)는 \(f=0\)으로 선 위, (2,3)은 \(f=-2\), (2,1)은 \(f=2\)로 반대편에 위치.[2][3]
추가:
추가: ### 중간점 판정으로 픽셀 선택
추가:
추가: 현재 픽셀 \((x_0, y_0)\)에서 다음 열 \(x_0+1\)의 후보는 \((x_0+1, y_0)\)(동쪽)와 \((x_0+1, y_0+1)\)(북동쪽) 둘 중 하나다. 두 후보 중간점 \((x_0+1, y_0+\tfrac12)\)에서 \(f\)를 평가한다.
추가: \[
추가: f\left(x_0+1,\, y_0+\tfrac12\right) = A(x_0+1) + B\left(y_0+\tfrac12\right) + C
추가: \]
추가: 이 값이 양수면 이상적 선이 중간점 아래 → 북동쪽 픽셀 선택( \(y\) 증가), 음수면 동쪽 픽셀 선택( \(y\) 유지). 이 판정식을 정수 연산만으로 정리하면 결정 변수 \(d\) 또는 오차 항 \(e\)를 이용해 분기 없이 루프 안에서 갱신할 수 있다.[2][3]
추가:
추가: ### 나머지 팔분면·수직선 처리
추가:
추가: 제1팔분면 외 경우는 \(x\)와 \(y\) 역할 교환, 부호 반전, 끝점 스왑 등으로 동일 로직을 재사용한다. 수직선(\(\Delta x = 0\))은 \(x\) 고정, \(y\)만 증가시키는 별도 분기로 처리한다.[2][3]
추가:
추가: ## 사례
추가:
추가: 자료에 구체적 게임·소프트웨어명은 명시되지 않았으나, "최신 그래픽 카드의 그래픽 처리 장치", "플로터", "많은 소프트웨어 그래픽스 라이브러리", "펌웨어 또는 그래픽 하드웨어"에 구현돼 있다고 서술돼 있다.[2][3]
추가:
추가: ## 규제·논란·평가
추가:
추가: 자료는 규제·논란을 다루지 않는다. 평가 측면에서는 "속도와 단순성 때문에 여전히 중요하다", "우 알고리즘 등 안티앨리어싱 지원 알고리즘이 현대 그래픽스에서 자주 쓰이지만 브레젠험 알고리즘은 하드웨어·펌웨어·소프트웨어 라이브러리 전반에 널리 남아 있다"는 점이 언급된다.[2][3]
추가:
추가: 이 문서는 GGWiki AI가 공개 자료(아래 출처)를 조사해 새로 쓴 초안입니다. 틀린 내용은 편집하거나 이의 제기로 알려 주세요.
