Rasterization Using Bresenham Algorithm and Scanline Algo...

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.

推荐订阅源

DEV Community

1. Overview

2. Development Process

core code

3. Result

Preview gif

Full Video

Github Repository