Rasterization Using Bresenham Algorithm and Scanline Algorithm

1. Overview

• Bresenham algorithm is the fastest algorithm for drawing straight lines on a pixel grid (using only integers).
• Scanline Algorithm is commonly used to fill the interior of polygons by drawing horizontal scanlines between edges.
• In this project, I implemented basic rasterization techniques in Python using Pygame by applying Bresenham Algorithm and the Scanline Algorithm.
• The goal was to manually draw geometric shapes using lines and fill their interiors with color.
• I learned how rendering and polygon filling work internally in graphics systems.

2. Development Process

core code

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

    stepX = 1 if x1 < x2 else -1
    stepY = 1 if y1 < y2 else -1

    error = dx - dy

    x = x1
    y = y1

    while True:
        surface.set_at((x, y), color)

        if x == x2 and y == y2:
            break

        e2 = 2 * error

        if e2 > -dy:
            error -= dy
            x += stepX

        if e2 < dx:
            error += dx
            y += stepY

• This is the Bresenham Algorithm function.
• Calculates difference between the x axis and the y axis (dx, dy) and uses the error value to determine at what point to move horizontally or vertically.
• Efficient line rendering is possible because pixel positions are gradually updated through integer based error correction.

# fill triangle
def FillTriangle(surface, vertices, color):
    # sort vertices by y
    vertices.sort(key=lambda vertex: vertex[1])

    x1 = vertices[0][0]
    y1 = vertices[0][1]
    x2 = vertices[1][0]
    y2 = vertices[1][1]
    x3 = vertices[2][0]
    y3 = vertices[2][1]

    # interpolate x values between two points
    def Interpolate(yStart, xStart, yEnd, xEnd):

        if yStart == yEnd:
            return []

        xValues = []

        deltaX = (xEnd - xStart) / (yEnd - yStart)

        currentX = xStart

        y = yStart

        while y < yEnd:
            xValues.append(currentX)

            currentX += deltaX

            y += 1

        return xValues

    # create edge lists
    xShort = Interpolate(y1, x1, y2, x2)
    xShort += Interpolate(y2, x2, y3, x3)

    xLong = Interpolate(y1, x1, y3, x3)

    # get minimum length
    length = len(xShort)

    if len(xLong) < length:
        length = len(xLong)

    # fill triangle
    i = 0

    while i < length:

        y = y1 + i

        xa = int(xShort[i])
        xb = int(xLong[i])

        if xa > xb:
            temp = xa
            xa = xb
            xb = temp

        # draw horizontal line
        DrawLine(surface, xa, y, xb, y, color)

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

        i += 1

• This function is the Scanline Algorithm.
• First, align the vertices of the triangle with y axis, then use the Interpolate() function to interpolate the x coordinates of each side.
• Afterwards, rendering is performed by calculating the left and right positions for each horizontal scanline and filling in the spaces between them.

# fill rectangle using 2 triangles!
def FillRectangle(surface, vertices, color):
    # 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)

• This function fills a rectangle.
• I implemented it by adapting the triangle filling function without the need for complex code.

3. Result

• I implemented line and surface rendering myself.
• When I thought about how I implemented the function to fill a rectangle using the function to fill a triangle, I felt like I had written efficient code.

---

Preview gif

Full Video

YouTube Video

Github Repository

Github - Graphics