FDF(3)

Bresenham 알고리즘

필요성

2D 맵의 좌표를 window상의 좌표로 파싱하고 나면, 좌표와 좌표를 이어 그림을 그리면 된다.

화면상의 대각선들은 직선처럼 보이지만, 픽셀 단위로 확인해보면
무수히 많은 네모이 직선에 가장 가깝게 그려져있는 것이다.

시작픽셀로부터 목적픽셀까지, 직선에 가장 가깝게 픽셀을 그리는 알고리즘이 필요하다.

인트라에서 소개하는 FDF 영상을 보면, Bresenham 알고리즘에 대해 공부하라고 했다.

개요

Bresenham 알고리즘은 두개의 좌표를 잇는 하나의 직선을 그리기 위한 효율적인 알고리즘이다.

Bresenham 알고리즘은 크게 2개의 분기로 나뉜다.

• 양 끝점이 이루는 기울기가 1보다 큰 경우

• 양 끝점이 이루는 기울기가 1 이하인 경우

각 경우에 대해 알아보자.

기울기가 1보다 큰 경우

(0, 0)으로부터, (3, 5)의 픽셀까지 선을 귿는다고 생각해보자.

위 규칙을 적용해 (0, 0)부터 (3, 5)까지 픽셀을 그려보면,

기울기가 1 이하인 경우

(0, 0)으로부터, (5, 3)의 픽셀까지 선을 귿는다고 생각해보자.

위 규칙을 적용해 (0, 0)부터 (5, 3)까지 픽셀을 그려보면,