[Cub3D] DDA 알고리즘 vs Bresenham 알고리즘

DDA (Digital Differential Analyzer) 알고리즘

DDA는 컴퓨터 그래픽에서 직선, 삼각형 또는 다각형을 형성하기 위해 직선을 그리는 데 사용된다. DDA는 한 좌표의 일정한 간격으로 라인을 따라 샘플을 정수로 분석하고 다른 좌표에 대해서는 라인에 가장 가까운 정수를 반올림한다. 따라서 선이 진행됨에 따라 첫 번째 정수 좌표를 스캔하고 두 번째 정수를 가장 가까운 정수로 반올림한다. 따라서 x 좌표에 DDA를 사용하여 그린 선은 x0 ~ x1이지만 y 좌표의 경우 y = ax + b가되고 함수를 그리려면 Fn (x, y 반올림)이된다.

 

Bresenham 알고리즘

Bresenham Algorithm은 1962 년 J.E. Bresenham에 의해 개발되었으며 DDA보다 훨씬 정확하고 훨씬 효율적이다. 좌표를 스캔하지만 반올림하지 않고 더하거나 빼서 증분 값을 고려하므로 원과 곡선을 그리는 데 사용할 수 있다. 따라서 두 점 x와 y 사이에 선을 그리면 다음 좌표는 (xa + 1, ya) 및 (xa + 1, ya + 1)이된다. 여기서 a는 다음 좌표의 증분 값과 이들의 차이입니다. 2는 방정식을 빼거나 더함으로써 계산된다.

 

DDA 알고리즘과 Bresenham 라인 알고리즘의 가장 큰 차이점은 DDA 알고리즘 규칙이 부동 목적 값을 사용하는 반면 Bresenham에서는 구형 OFF 함수를 사용한다는 것이다.

DDA 알고리즘 규칙은 분할뿐만 아니라 곱셈도 수반하는 반면 브레센햄 알고리즘 규칙에서는 덧셈과 뺄셈이 가장 많이 수행된 연산이다.

 

DDA 알고리즘	Bresenham line 알고리즘
DDA 알고리즘은 브레센햄 라인 알고리즘보다 효율성이 떨어진다.	DDA 알고리즘보다 효율적
DDA 알고리즘의 계산 속도는 브레센햄 라인 알고리즘보다 적다.	브레센햄 라인 알고리즘의 계산 속도는 DDA 알고리즘보다 빠르다.
DDA 알고리즘은 브레센햄 선 알고리즘보다 비용이 많이 든다.	반면 브레센햄 선 알고리즘은 DDA 알고리즘보다 저렴하다.
DDA 알고리즘은 정밀도나 정확도가 낮다.	더 정밀하거나 정확도가 높다.
DDA 알고리즘에서는 계산의 복잡성이 더 복잡하다.	계산이 간단하다.
DDA 알고리즘에서는 최적화가 제공되지 않는다.	최적화가 제공된다.