Bresenham 과 DD알고리즘의 기본 원리

 

DDA 알고리즘

 

 이 함수는 DDA(Digital Differential Analyzer) 알고리즘을 구현한 것입니다. DDA 알고리즘의 주요 특징들을 잘 반영하고 있습니다:

1. 부동소수점 연산 사용: delta_x와 delta_y를 float 타입으로 선언하여 부동소수점 연산을 사용합니다.
2. 증분 계산: delta_x /= bigger_delta;와 delta_y /= bigger_delta;를 통해 각 단계별 x와 y의 증분을 계산합니다.
3. 선형 보간: 각 단계마다 start.x += delta_x;와 start.y += delta_y;를 통해 좌표를 선형적으로 증가시킵니다.
4. 반복 횟수 결정: bigger_delta를 사용하여 더 긴 축을 기준으로 반복 횟수를 결정합니다.
5. 픽셀 그리기: 각 단계마다 계산된 좌표에 픽셀을 그립니다.

추가로, 이 구현은 기본 DDA 알고리즘에 몇 가지 개선 사항을 포함하고 있습니다:

• 색상 보간: get_color 함수를 사용하여 선의 시작점과 끝점 사이의 색상을 보간합니다.
• 경계 검사: 화면 경계를 벗어나는 픽셀은 그리지 않도록 검사합니다.

따라서, 이 함수는 DDA 알고리즘의 기본 원리를 따르면서 색상 보간과 경계 검사 기능이 추가된 개선된 버전의 DDA 알고리즘이라고 할 수 있습니다.

 

그 외 Bresenham의 알고리즘은 컴퓨터 그래픽스에서 선을 그리는 데 사용되는 효율적인 방법입니다. 이 알고리즘은 정수 연산만을 사용하여 빠르고 정확하게 선을 그릴 수 있습니다. Bresenham 알고리즘의 작동 방식을 예시를 통해 상세히 설명해 드리겠습니다.

Bresenham 알고리즘의 기본 원리

Bresenham 알고리즘은 두 점 사이의 선을 그릴 때, 각 x 좌표에 대해 가장 가까운 y 좌표를 선택하는 방식으로 작동합니다. 이 과정에서 결정 변수(decision variable)를 사용하여 다음 픽셀의 위치를 결정합니다.

예시: (1,1)에서 (8,5)까지 선 그리기

이 예시를 통해 Bresenham 알고리즘의 단계별 과정을 살펴보겠습니다.

초기 설정

1. 시작점: (x1, y1) = (1, 1)
2. 끝점: (x2, y2) = (8, 5)
3. dx = x2 - x1 = 8 - 1 = 7
4. dy = y2 - y1 = 5 - 1 = 4
5. 초기 결정 변수: d = 2dy - dx = 2*4 - 7 = 1

알고리즘 실행

단계xyd선택된 픽셀

1	1	1	1	(1, 1)
2	2	2	-1	(2, 2)
3	3	2	3	(3, 2)
4	4	3	1	(4, 3)
5	5	3	5	(5, 3)
6	6	4	3	(6, 4)
7	7	4	7	(7, 4)
8	8	5	5	(8, 5)

 

단계별 설명

1. 시작점 (1, 1)에서 시작합니다.
2. d > 0이므로 x와 y를 모두 증가시킵니다. 새로운 d = 1 + 2dy - 2dx = 1 + 8 - 14 = -5
3. d < 0이므로 x만 증가시킵니다. 새로운 d = -5 + 2dy = -5 + 8 = 3
4. d > 0이므로 x와 y를 모두 증가시킵니다. 새로운 d = 3 + 2dy - 2dx = 3 + 8 - 14 = -3
5. 이 과정을 끝점에 도달할 때까지 반복합니다.

Bresenham 알고리즘의 장점

1. 정수 연산만을 사용하므로 빠른 실행 속도를 제공합니다
2. 부동 소수점 연산이 필요 없어 하드웨어 구현에 적합합니다.
3. 중복점 생성을 피할 수 있어 효율적입니다.

결론

Bresenham 알고리즘은 간단하면서도 효율적인 선 그리기 방법을 제공합니다. 이 알고리즘은 컴퓨터 그래픽스에서 널리 사용되며, 특히 하드웨어 제약이 있는 환경에서 유용합니다. 위의 예시에서 볼 수 있듯이, 알고리즘은 각 단계에서 간단한 결정을 통해 최적의 픽셀 위치를 선택하여 부드러운 선을 그릴 수 있습니다.

 

또다른 전개 

 

기본 정보
시작점: (1,1)
끝점: (8,5)
Δx = 8 - 1 = 7
Δy = 5 - 1 = 4
알고리즘 단계
결정 변수 초기화:
D = 2 * Δy - Δx
D = 2 * 4 - 7 = 1
각 x 좌표에 대해 반복:
D > 0이면 y를 증가시키고 D에서 2*Δx를 뺍니다.
D <= 0이면 y를 그대로 두고 D에 2*Δy를 더합니다.
실제 그리기 과정
text
(1,1) 시작점, D = 1
(2,1) D = 1 + 2*4 = 9
(3,2) D = 9 - 2*7 = -5
(4,2) D = -5 + 2*4 = 3
(5,3) D = 3 - 2*7 = -11
(6,3) D = -11 + 2*4 = -3
(7,4) D = -3 - 2*7 = -17
(8,5) 끝점
시각화
text
y
5               *
4           *
3       *   *
2   *   *
1 *   *
  1 2 3 4 5 6 7 8 x
설명
(1,1)에서 시작합니다. 초기 D = 1입니다.
x를 1 증가시켜 (2,1)로 이동합니다. D > 0이므로 y를 증가시키지 않습니다.
D가 9가 되어 0보다 크므로, 다음 점은 (3,2)입니다. D를 갱신합니다.
이 과정을 반복하여 최종적으로 (8,5)에 도달합니다.
이 방법으로 Bresenham 알고리즘은 부동소수점 연산 없이 정수 연산만으로 가장 근접한 픽셀을 선택하여 (1,1)에서 (8,5)까지의 직선을 그립니다. 각 단계에서 x는 항상 1씩 증가하고, y는 결정 변수 D에 따라 증가하거나 그대로 유지됩니다.