Python 实现图形学光栅化的扫描线算法

引言

光栅化是图形学中非常重要的一个阶段，它将几何描述转换为图像描述，最终在屏幕上显示出来。光栅化过程将物体的几何形状转化为像素，而扫描线算法是其中的一种经典算法。本文将详细介绍扫描线算法的原理，并使用 Python 结合面向对象编程（OOP）的思想进行实现。

扫描线算法简介

扫描线算法是一种光栅化多边形的高效方法，特别适用于填充凸多边形。该算法通过逐行扫描整个屏幕，并检查每条扫描线与多边形的交点，确定每条扫描线上的哪些像素应该被填充。它的主要步骤如下：

1. 初始化：确定多边形的顶点，并计算每条边与扫描线的交点。
2. 构建边表 (Edge Table, ET)：记录每条边的起点和终点，按扫描线的顺序排列。
3. 构建活跃边表 (Active Edge Table, AET)：在每次扫描线到达某个顶点时，更新 AET 并计算当前扫描线的填充区域。
4. 填充扫描线：在当前扫描线中，AET 中的交点成对出现，确定要填充的像素范围。

几何概念

我们以二维平面上的多边形为例，多边形由多个顶点组成，并通过顶点之间的边相连。每条边可以与一条扫描线相交，这个交点是通过边的直线方程计算的。

直线方程：
一条边的直线可以用斜率公式表示：
$$y=mx+b$$
其中 (m) 是斜率，(b) 是截距。通过斜率可以确定扫描线与边的交点。

Python 实现

下面我们通过面向对象编程实现扫描线算法，包括边表（ET）和活跃边表（AET）的构建和使用。

1. 类结构设计

我们将实现如下几个类：

• Point2D：用于表示二维平面的点。
• Edge：表示多边形的边。
• Polygon：表示多边形，由多个点组成，并包含多边形的边信息。
• EdgeTable：用于记录多边形的所有边，并按扫描线顺序排列。
• ScanlineFill：主要负责执行扫描线填充算法。

2. 代码实现

import numpy as np

# 定义二维点类
class Point2D:
    def __init__(self, x, y):
        self.x = x
        self.y = y

# 定义边类
class Edge:
    def __init__(self, start, end):
        self.start = start  # Edge 起点
        self.end = end      # Edge 终点
        
        if self.start.y == self.end.y:  # 水平线不需要处理
            self.slope_inverse = 0
        else:
            self.slope_inverse = (self.end.x - self.start.x) / (self.end.y - self.start.y)
        
        # 以y小的为start，大的为end
        if self.start.y > self.end.y:
            self.start, self.end = self.end, self.start

# 定义多边形类
class Polygon:
    def __init__(self, vertices):
        self.vertices = vertices  # 顶点
        self.edges = self._create_edges()  # 创建边
    
    def _create_edges(self):
        edges = []
        num_vertices = len(self.vertices)
        for i in range(num_vertices):
            start = self.vertices[i]
            end = self.vertices[(i + 1) % num_vertices]  # 下一个顶点，首尾相连
            edge = Edge(start, end)
            edges.append(edge)
        return edges

# 定义边表类
class EdgeTable:
    def __init__(self, polygon):
        self.edges = polygon.edges
        self.edge_table = self._build_edge_table()
    
    def _build_edge_table(self):
        # 构建边表，按照扫描线的y坐标排序
        edge_table = {}
        for edge in self.edges:
            if edge.start.y == edge.end.y:  # 忽略水平边
                continue
            y_min = int(edge.start.y)
            if y_min not in edge_table:
                edge_table[y_min] = []
            edge_table[y_min].append(edge)
        return edge_table

# 定义扫描线填充类
class ScanlineFill:
    def __init__(self, polygon):
        self.polygon = polygon
        self.edge_table = EdgeTable(polygon).edge_table
        self.active_edge_table = []  # 活跃边表
    
    def fill(self, min_y, max_y):
        """根据扫描线填充区域"""
        for scanline in range(min_y, max_y + 1):
            # 1. 从边表加入新的边到活跃边表
            if scanline in self.edge_table:
                self.active_edge_table.extend(self.edge_table[scanline])
            
            # 2. 删除y_max等于当前扫描线的边
            self.active_edge_table = [edge for edge in self.active_edge_table if edge.end.y > scanline]
            
            # 3. 按照x坐标对活跃边表排序
            self.active_edge_table.sort(key=lambda e: e.start.x)
            
            # 4. 计算交点并填充像素
            self._fill_scanline(scanline)
            
            # 5. 更新x坐标
            self._update_active_edges()

    def _fill_scanline(self, scanline):
        """根据当前扫描线填充区域"""
        it = iter(self.active_edge_table)
        for edge1, edge2 in zip(it, it):  # 配对边
            x1 = edge1.start.x + (scanline - edge1.start.y) * edge1.slope_inverse
            x2 = edge2.start.x + (scanline - edge2.start.y) * edge2.slope_inverse
            print(f"Filling from x={x1} to x={x2} on scanline y={scanline}")

    def _update_active_edges(self):
        """更新活跃边表中的x坐标"""
        for edge in self.active_edge_table:
            edge.start.x += edge.slope_inverse

# 使用示例
if __name__ == "__main__":
    # 定义一个多边形
    vertices = [Point2D(10, 10), Point2D(20, 30), Point2D(30, 10)]
    polygon = Polygon(vertices)
    
    # 扫描线填充
    scanline_fill = ScanlineFill(polygon)
    scanline_fill.fill(min_y=10, max_y=30)

代码详解

1. Point2D 类：表示二维平面中的点，包含点的坐标。

2. Edge 类：表示多边形中的边，包含边的起点和终点，以及用于计算交点的反斜率 (slope_inverse)，用于在扫描线中逐步更新 x 坐标。

3. Polygon 类：用于表示多边形。它通过给定的点列表生成多边形，并自动计算边。

4. EdgeTable 类：生成边表，记录每条边与扫描线的交点，按扫描线的 y 值排序。

5. ScanlineFill 类：实现扫描线填充算法。每次处理一条扫描线，更新活跃边表，计算填充区域，并逐步更新每条边的 x 坐标。

6. _fill_scanline：根据当前的扫描线，查找活跃边表中配对的边，计算它们与扫描线的交点，并确定需要填充的像素区间。

7. _update_active_edges：更新活跃边表中每条边的 x 坐标，以便处理下一条扫描线。

使用示例

在使用示例中，我们定义了一个简单的三角形，并对其进行了扫描线填充。ScanlineFill 类会逐条扫描从 min_y 到 max_y 的所有扫描线，输出填充区域的信息。

扫描线算法的优点

• 高效：通过扫描线的逐条处理，可以减少冗余计算。
• 适用多边形：该算法适用于任意形状的多边形，尤其在凸多边形的填充上有很好的效果。
• 渐进更新：通过活跃边表，我们可以逐步更新边的 x 坐标，避免重复计算。

总结

扫描线算法是一种经典的光栅化方法，它通过逐条扫描线处理多边形的边界，计算出填充区域。本文通过 Python 的面向对象编程思想，详细展示了如何使用扫描线算法来填充多边形。通过类的分层设计，我们可以清晰地表示点、边和多边形，并实现灵