Bresenham 알고리즘과 Scanline 알고리즘을 이용한 래스터화

Source: Dev.to

Overview

Bresenham 알고리즘은 정수 연산만을 사용하여 픽셀 그리드에 직선을 그리는 가장 빠른 방법입니다.
Scanline 알고리즘은 일반적으로 다각형의 내부를 채우기 위해 가장자리 사이에 수평 스캔라인을 그리는 데 사용됩니다.

이 프로젝트에서는 Bresenham 알고리즘을 이용한 선 그리기와 Scanline 알고리즘을 이용한 다각형 채우기를 Python과 Pygame으로 구현했습니다. 목표는 선을 사용해 기하학적 도형을 직접 그리고, 내부를 색으로 채워 그래픽 시스템에서 렌더링 및 다각형 채우기가 내부적으로 어떻게 동작하는지 이해하는 것이었습니다.

Development Process

Bresenham line drawing

# draw line
def DrawLine(surface, x1, y1, x2, y2, color):
    dx = abs(x2 - x1)
    dy = abs(y2 - y1)

    stepX = 1 if x1  -dy:
            error -= dy
            x += stepX

        if e2  xb:
            xa, xb = xb, xa
        # draw horizontal line
        DrawLine(surface, xa, y, xb, y, color)

        # optional visualization delay
        pygame.display.update()
        pygame.time.delay(15)

알고리즘은 먼저 삼각형 정점들을 y‑좌표 기준으로 정렬합니다. 그런 다음 각 스캔라인의 왼쪽과 오른쪽 경계를 이루는 두 변을 따라 x‑좌표를 보간합니다. 매 스캔라인마다 왼쪽(xa)과 오른쪽(xb) 위치 사이에 수평선을 그려 삼각형을 효과적으로 채웁니다.

Rectangle filling using two triangles

# fill rectangle using 2 triangles!
def FillRectangle(surface, vertices, color):
    # vertices order: 0 = top‑left, 1 = top‑right,
    # 2 = bottom‑right, 3 = bottom‑left
    triangle1 = [vertices[0], vertices[1], vertices[2]]
    triangle2 = [vertices[0], vertices[2], vertices[3]]

    FillTriangle(surface, triangle1, color)
    FillTriangle(surface, triangle2, color)

사각형을 두 개의 삼각형으로 나누고, 각각을 FillTriangle 루틴으로 채워 별도의 사각형‑채우기 구현이 필요 없도록 합니다.

Result

이 프로젝트는 내장된 Pygame 프리미티브에 의존하지 않고 사용자 정의 선 그리기와 다각형 채우기를 구현함을 보여줍니다. 사각형‑채우기 함수가 삼각형 채우기 코드를 재사용함으로써 코드 재사용성과 효율성을 강조합니다.

• Preview GIF – (여기에 GIF 삽입)
• Full video – (동영상 링크)
• YouTube video – (YouTube 링크)
• GitHub repository – (저장소 링크)