Computer Graphics Algorithm Test

1. Brensenham's Line Drawing Algorithm

brensenham.hpp에 구현되어 있음.

구현 방식

두 점이 주어진다.(start, end) 해당 점을 start에서 end로 그린다고 생각한다.

원점 = start이고 end가 $xy$평면 상에 존재한다.

xy 평면을 $x$축, $y$축, $y=x$축, $y=-x$축으로 8등분 하였을 때, 각 구역을 3가지 특징(x축 증가 방향, y축 증가 방향, x와 y축 역할 변경 여부)으로 구분하여 값들을 미리 조정한다.

$x$축의 상단 부분부터 반시계방향으로 1~8번으로 이름붙였다.

1, 2번 구역: 1사분면으로 x축과 y축 모두 양수로 움직인다.

3, 4번 구역: 2사분면으로 x축은 음수, y축은 양수로 움직인다.

5, 6번 구역: 3사분면으로 x축과 y축 모두 음수로 움직인다.

7, 8번 구역: 4사분면으로 x축은 양수, y축은 음수로 움직인다.

이를 dx=end.x-start.x, dy=end.y-start.y의 부호로 판단한다.

그리고 $y$축에 가까운 경우(dy>dx)에 대해서는 가파른 경우로 판단, 이는 $x$축과 $y$축의 역할을 바꾸어 알고리즘을 실행한다.

칠해지는 점은 o, 아닌 점은 x로 출력된다.

2. Scanline Algorithm - scan 1 polygon

점이 주어지면 순서대로 에지로 변환. (단, 수평 에지는 필요 없음.)

에지에서 ymax, ymin을 추출하고, 이를 바탕으로 scanline의 높이에 따라 어떤 에지가 탐색 대상일 지 선정한다.(activated)

이후, 이를 복사한다.(active)

현재 scanline 안에서 x를 0부터 끝까지 순차적으로 움직이며 어떤 에지에 대해 에지 우측의 좌표로 탐색되는 순간, 해당 에지를 active에서 제거하고, inout을 1 증가시킨다. (inout: 몇 개의 에지를 지나갔는지?)

해당 inout이 짝수면 바깥쪽인 픽셀, 홀수면 안쪽인 픽셀을 뜻한다.