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

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

引言

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

扫描线算法简介

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

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

几何概念

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

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

Python 实现

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

1. 类结构设计

我们将实现如下几个类：

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

2. 代码实现

python">import numpy as np# 定义二维点类
class Point2D:def __init__(self, x, y):self.x = xself.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 = 0else:self.slope_inverse = (self.end.x - self.start.x) / (self.end.y - self.start.y)# 以y小的为start，大的为endif 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.edgesself.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:  # 忽略水平边continuey_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 = polygonself.edge_table = EdgeTable(polygon).edge_tableself.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_inversex2 = edge2.start.x + (scanline - edge2.start.y) * edge2.slope_inverseprint(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)

代码详解

Point2D 类：表示二维平面中的点，包含点的坐标。
Edge 类：表示多边形中的边，包含边的起点和终点，以及用于计算交点的反斜率 (slope_inverse)，用于在扫描线中逐步更新 x 坐标。
Polygon 类：用于表示多边形。它通过给定的点列表生成多边形，并自动计算边。
EdgeTable 类：生成边表，记录每条边与扫描线的交点，按扫描线的 y 值排序。
ScanlineFill 类：实现扫描线填充算法。每次处理一条扫描线，更新活跃边表，计算填充区域，并逐步更新每条边的 x 坐标。
_fill_scanline：根据当前的扫描线，查找活跃边表中配对的边，计算它们与扫描线的交点，并确定需要填充的像素区间。
_update_active_edges：更新活跃边表中每条边的 x 坐标，以便处理下一条扫描线。

使用示例

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

扫描线算法的优点

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

总结

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