선 그리기 알고리즘
Line drawing algorithm |
|
컴퓨터 그래픽스에서 선 그리기 알고리즘은 픽셀 기반 디스플레이 및 프린터와 같은 개별 그래픽 미디어 상의 선 세그먼트를 근사하는 알고리즘입니다.이러한 매체에서 선 그리기는 (자주 중요하지 않은 경우) 근사치를 필요로 한다.기본 알고리즘은 선을 한 색상으로 래스터라이즈합니다.여러 색상의 그라데이션으로 더 잘 표현하려면 고급 프로세스인 공간 안티에이리어싱이 필요합니다.
반면 연속 매체에서는 선을 긋는 데 알고리즘이 필요하지 않습니다.예를 들어, 음극선 오실로스코프는 아날로그 현상을 사용하여 선과 곡선을 그립니다.
선 그리기 알고리즘 목록
다음은 선 그리기 알고리즘의 일부 목록입니다.
- 순진한 알고리즘
- Digital Differential Analyzer(그래픽)알고리즘): Naigent Line Drawing 알고리즘과 비슷하지만 약간의 차이가 있습니다.
- 브레센햄의 선 알고리즘 - 덧셈(나눗셈이나 곱셈 없음)만을 사용하도록 최적화되어 부동소수점 연산을 회피합니다.
- Xiaolin Wu의 라인 알고리즘 - 공간 안티 앨리어싱을 수행할 수 있으며, 라인 길이를 따라 변화하는 밝기로 인해 "로피"한 것처럼 보이지만, 이 효과는 대상 디스플레이의 감마 곡선에 대한 픽셀 값을 사전 보정함으로써 크게 감소할 수 있다(예: out = in ^(1/2.4).[original research?]
- 굽타-스프룰 알고리즘
단순한 선 그리기 알고리즘
가장 간단한 선별 방법은 선을 정의하는 방정식의 직접 그리기입니다.
dx = x2 - x1 dy = x2 - y1 x1 do y = y1 + dy × (x - x1) / dx 그림(x, y)
서 x 2> 1 > 이 포인트가 이미 주문되어 있습니다.때 d)을 이 알고리즘은 잘 들^d y{\displaystyle dx>, =dy}(즉, 경사보다 또는 1이하인 경우), 하지만 만약 d=<>dy{\displaystyle dx<, dy}(즉, 경사보다 더 큰 1), 그 선이 꽤 희소로 많은 구멍에서 제한 사건의 d)=0{\displaystyle dx=0}, 한 부서 제로 예외입니다. 발생할 것이다.
순진한 선 그리기 알고리즘은 비효율적이기 때문에 디지털 컴퓨터에서는 속도가 느립니다.비효율성은 연산 횟수와 부동 소수점 계산 사용에서 비롯됩니다.대신 브레센햄이나 우와 같은 선 그리기 알고리즘이 선호됩니다.
