선 그리기 알고리즘: 정밀한 이미지 렌더링을 위한 마스터링 기법

By Fouad Sabry

선 그리기 알고리즘이란?

컴퓨터 그래픽에서 선 그리기 알고리즘은 픽셀 기반 디스플레이 및 프린터와 같은 개별 그래픽 미디어의 선분을 근사화하기 위한 알고리즘입니다. 이러한 매체에서 선 그리기에는 근사치가 필요합니다. 기본 알고리즘은 선을 한 가지 색상으로 래스터화합니다. 여러 색상 그라데이션으로 더 나은 표현을 위해서는 고급 프로세스인 공간 앤티앨리어싱이 필요합니다.

당신이 얻을 수 있는 혜택

(I) 다음 주제에 대한 통찰력 및 검증:

1장: 선 그리기 알고리즘

2장: 브레센햄의 선 알고리즘

3장: ξOlin W U의 선 알고리즘

4장: 디지털 차동 분석기(그래픽 알고리즘)

5장: 중간점 원 알고리즘

6장: 2D 컴퓨터 그래픽

7장: 디지털 기하학

8장: 허프 변환

9장: 레이 캐스팅

10장: 가우스 함수

(II) 선 그리기 알고리즘에 대한 대중의 주요 질문에 답합니다.

(III) 다양한 분야에서 선 그리기 알고리즘을 사용하는 실제 사례.

이 책은 누구를 위한 책인가

전문가, 학부 및 대학원생, 매니아, 취미생활자, 모든 종류의 선 그리기 알고리즘에 대한 기본 지식이나 정보를 넘어서고 싶은 사람들.

• Language: 한국어
• Publisher: 10 억 지식이 걸립니다 [Korean]
• Release date: May 5, 2024

Book preview

1 장 : 선화 알고리즘

컴퓨터 그래픽의 선 그리기 알고리즘은 픽셀 기반 화면 및 프린터와 같은 개별 그래픽 미디어의 선분을 근사화하는 알고리즘입니다. 이러한 표면에서 선을 그리려면 근사치가 필요합니다(사소한 경우). 간단한 알고리즘은 단일 색조의 선을 래스터화합니다. 공간 안티앨리어싱은 수많은 색상 그라데이션을 보다 정확하게 묘사하는 데 필요한 고급 절차입니다.

연속 매체에서는 선을 그리는 데 알고리즘이 필요하지 않습니다. 예를 들어, 음극선 오실로스코프는 아날로그 현상을 사용하여 선과 곡선을 만듭니다.

다음은 선화를 위한 알고리즘의 일부 목록입니다.

순진한 알고리즘

Digital Differential Analyzer(그래픽 알고리즘) — 몇 가지 약간의 차이점을 제외하고는 순진한 선 그리기 알고리즘과 비슷합니다.

Bresenham의 선 알고리즘은 덧셈 (즉, 나눗셈이나 곱셈 없음)만 사용하도록 조정되어 있으며 부동 소수점 계산을 피합니다.

공간 안티앨리어싱을 수행할 수 있는 Xiaolin Wu의 선 알고리즘은 선의 길이를 따라 밝기가 변동하기 때문에 끈적끈적한 것처럼 보입니다. 그러나 이 효과는 대상 디스플레이의 감마 곡선에 대한 픽셀 값을 미리 보정하여 크게 최소화할 수 있습니다(예: out = in (1/2.4)).

굽타-스프루일 공식

선을 결정하는 방정식을 직접 스케치하는 것이 가장 간단한 스크리닝 방법입니다.

dx = x2 − x1

dy = y2 − y1

x1 에서 x2까지 x do

y = y1 + dy × (x − x1) / dx

플롯(x, y)

포인트가 이미 정렬되어 있습니다 x_{2}>x_{1} .

이 알고리즘은 {\displaystyle dx\geq dy} (즉, 그래디언트가 1보다 작거나 같 dx

선을 그리는 기본 알고리즘은 비효율적이며 결과적으로 디지털 컴퓨터에서 느립니다. 연산의 양과 부동 소수점 계산의 사용은 비효율성에 기여합니다. 대신 Bresenham의 선 알고리즘 또는 Xiaolin Wu의 선 알고리즘과 같은 알고리즘이 선호됩니다.

Bresenham의 선 알고리즘을 기반으로 하는 굽타-스프롤 알고리즘은 앤티앨리어싱을 추가합니다.

Gupta-Sproull 알고리즘의 최적화된 형태에 대한 의사 코드는 다음과 같습니다.

DrawLine(x1, x2, y1, y2) {

x = x1;  y = y1;  dx = x2 − x1;  dy = y2 − y1;  d = 2 * dy − dx; 판별자

선(부호 있음)에서 점(x,y)까지의 유클리드 거리

디 = 0;  점 (x1, y1)과 (x2, y2) 사이의 유클리드 거리

길이 = sqrt(dx * dx + dy * dy);  sin = dx / 길이;  cos = dy / 길이;  동안 (x <= x2) {

IntensifyPixels(x, y − 1, D + cos);  IntensifyPixels(x, y, D);  IntensifyPixels(x, y + 1, D − cos);  x = x + 1

if (d <= 0) {

D = D + 죄;  d = d + 2 * dy;  } 또 다른 {

D = D + 죄 − cos;  d = d + 2 * (dy − dx);  y = y + 1; } }}

IntensifyPixel(x,y,r) 함수는 방사형 선 변환을 수행하고, 픽셀과 선의 거리 r에 따라 값이 달라지는 3차 다항식으로 픽셀의 (x,y) 농도를 설정합니다.

{챕터 1 종료}

챕터 2: Bresenham의 선 알고리즘

Bresenham의 선 알고리즘은 두 점 사이의 직선을 근사화하기 위해 선택해야 하는 n차원 래스터 점을 식별하는 선 그리기 절차입니다. 비트맵 이미지(예: 컴퓨터 화면)에 선 프리미티브를 그리는 데 자주 사용되는데, 이는 정수 덧셈, 뺄셈 및 비트 시프트만 필요하기 때문이며, 이는 모두 역사적으로 널리 퍼진 컴퓨터 아키텍처에서 상당히 저렴한 작업입니다. 컴퓨터 그래픽 분야에서 만들어진 초기 알고리즘 중 하나이며 증분 오류 알고리즘입니다. 원래 알고리즘을 수정하여 원을 만들 수 있습니다.

Wu의 알고리즘과 같은 앤티앨리어싱이 가능한 기술도 현대 컴퓨터 그래픽에서 널리 사용되지만, Bresenham의 선 알고리즘은 속도와 단순성으로 인해 여전히 중요합니다. 이 알고리즘은 플로터와 최신 그래픽 카드의 그래픽 칩에 사용됩니다. 또한 수많은 소프트웨어 그래픽 라이브러리에도 있습니다. 알고리즘의 단순성으로 인해 현재 그래픽 카드의 그래픽 하드웨어 또는 펌웨어에서 자주 구현됩니다.

오늘날 Bresenham이라는 용어는 Bresenham의 원래 접근 방식을 확장하거나 변경하는 알고리즘 제품군을 나타냅니다.

Bresenham의 선 알고리즘은 1962년에 이 알고리즘을 만든 IBM 직원인 Jack Elton Bresenham의 이름을 따서 명명되었습니다. 2001년 Bresenham은 다음과 같이 발표했습니다.

저는 IBM San Jose 개발 연구소의 컴퓨팅 연구소에서 일하고 있었습니다. 1407 타자기 터미널을 통해 Calcomp 플로터가 IBM 1401에 연결되었습니다. 이 알고리즘은 1962년 여름, 또는 한 달 전에 생산에 사용되었습니다. Calcomp(Jim Newland와 Calvin Heft)는 당시 기업들이 공개적으로 공유했기 때문에 프로그램의 사본을 가지고 있었습니다. 1962년 가을에 스탠퍼드 대학으로 돌아왔을 때, 나는 스탠퍼드 컴퓨터 센터의 도서관에 한 권을 기증했다. 콜로라도 주 덴버에서 열린 1963년 ACM 전국 대회에서 선 그리기 루틴에 대한 설명이 발표되었습니다. 그 해에 연사와 주제의 의제만 ACM의 커뮤니케이션 호에 게시되었습니다. 내 발표가 끝난 후, IBM Systems Journal의 누군가가 그 논문을 출판할 수 있는지 문의했다. 나는 기꺼이 동의하였고, 그 책은 1965년에 발행되었다.

Bresenham의 접근 방식은 원, 타원, 3차 및 2차 베지어 곡선뿐만 아니라 이러한 곡선의 기본 앤티앨리어싱 버전을 생성하도록 확장되었습니다.

후속 규칙이 활용됩니다.

왼쪽 위 좌표는 (0,0)이며, 픽셀 좌표는 오른쪽 및 아래쪽 방향으로 커지고(예: (7,4)의 픽셀은 (7,5)의 픽셀 바로 위에 있음) 오른쪽 아래 좌표는 (1,1)입니다.

픽셀의 중심은 정수 좌표를 갖습니다.

선의 끝점은 와 의 픽셀이며 (x_{0},y_{0}) (x_{1},y_{1}) , 여기서 첫 번째 좌표는 열을 나타내고 두 번째 좌표는 행을 나타냅니다.

알고리즘은 처음에 세그먼트가 아래쪽과 오른쪽( x_{0}\leq x_{1}