边函数光栅化

发表于 2026-04-19 本文字数： 1.7k 阅读时长 ≈ 6 分钟

边函数光栅化 (Edge Function Rasterization)

算法简介

边函数光栅化，又称 Pineda’s Algorithm，由 Juan Pineda 于 1988 年 SIGGRAPH 论文 A Parallel Algorithm for Polygon Rasterization 提出。它是现代 GPU 硬件光栅化的基础算法。

核心思想：多边形的每条边将平面划分为两个半平面，点在多边形内部当且仅当它在所有边的内侧半平面内。

数学本质

“边函数”在数学上就是叉积（行列式）：

$$E_{ij}(Q) = \det(P_j - P_i, Q - P_i) = (P_j - P_i)_x \cdot (Q - P_i)_y - (P_j - P_i)_y \cdot (Q - P_i)_x$$

对于逆时针绕行的凸多边形，若所有边的边函数值 $\ge 0$，则该点在多边形内部。

“边函数”与”叉积”数学上完全等价，但”边函数”强调的是一种算法范式——半平面判定 + 增量求值 + 可并行化。

增量求值

这是边函数法效率的来源。相邻像素间的边函数值变化是常数：

移动方向	边函数变化量
向右移动一格 $(x+1, y)$	$E_{new} = E_{old} - Dy$
向上移动一行 $(x, y+1)$	$E_{new} = E_{old} + Dx$

其中 $Dx = (P_j - P_i)_x \cdot gridSize$，$Dy = (P_j - P_i)_y \cdot gridSize$。

这意味着从初始像素算出边函数值后，后续每个像素只需一次加减法即可更新，完全消除了乘法和除法。

容忍度

边函数法天然支持引入容忍度参与叉积后的负号对比。容忍度的物理含义是：对任意一个边E，判断某点Q是否在其左侧时，Q可以在x和y方向分别调整 $\pm{Tolerance}$ 个格子，以满足在其左侧的要求。用更具体的例子：

t = 0：严格模式，Q 点必须在边的左侧才算覆盖
t = 0.5：Q 点可以在 ±0.5 格范围内找到一个满足”在边左侧”的位置——恰好等于一个格子的半宽，也就是说只要格子的任意一角碰到了边，就算覆盖（标准的多边形沾上就算覆盖）
t = 1.0：Q 点可以在 ±1 格范围内找到合法位置——相当于把覆盖判定扩大到了相邻格子

容忍度

上图中右图就是保守覆盖的效果，这也是我觉得该算法很巧妙的点，在之前写射线检测法的时候，我就考虑过如何实现保守覆盖，朴素的想法是对四个角进行检查，但是不行会漏检，还要对四个边进行相交判定，非常麻烦。

但是边函数本身就概括了包含与否的关系，我们不需要考虑下一步要往哪个方向试探，只需要给函数一个正的值，这个值是原先 $Q$ 分别朝x某方向和y某方向移动了 $Tolerance$ 格子

$$
E(Q+δ)
= E(Q)+\cfrac{\partial{E}}{\partial{g_x}}\cdot{\Delta{g_x}}+\cfrac{\partial{E}}{\partial{g_y}}\cdot{\Delta{g_y}}
= E(Q)+D_x\cdot{\Delta{g_y}}-D_y\cdot{\Delta{g_x}}
$$

在格子这个方形区域 $(|\Delta g_x| \leq d,\ |\Delta g_y| \leq d)$ 上求 $(E)$ 的最大值，这是一个线性函数在凸集上求极值——极值一定在顶点取到。而最大偏移量的上界恰好是：

$$
|\Delta{E}_{max}|=|D_x|\cdot{d}+|D_y|\cdot{d}
$$

所以 $(E(Q) + T \geq 0)$ 这个单一判断，本质上是对四个角做了一次性的最大值聚合。

实现代码

代码仅用作学习实验，存在可以优化的地方，比如Tolerance完全不需要数组，直接初始计算后加入到FirstDet；不要用List而是用数组等等。

public static class EdgeFunction
{
    public static void GetCoveredGrid(MapGrid mapGrid, Polygon polygon, float tolerance, List<int> grids)
    {
        var vertices = polygon.vertices;
        var n = vertices.Count;
        var minPoint = new Vector2(float.MaxValue, float.MaxValue);
        var maxPoint = new Vector2(float.MinValue, float.MinValue);
        for (var i = 0; i < n; i++)
        {
            var point = vertices[i];
            minPoint.x = Mathf.Min(minPoint.x, point.x);
            minPoint.y = Mathf.Min(minPoint.y, point.y);
            maxPoint.x = Mathf.Max(maxPoint.x, point.x);
            maxPoint.y = Mathf.Max(maxPoint.y, point.y);
        }

        var relaMinPoint = minPoint - mapGrid.min;
        var relaMaxPoint = maxPoint - mapGrid.min;
        var minCol = Mathf.Max(Utilities.FloorToInt(relaMinPoint.x * mapGrid.GridSizeInv), 0); // 闭区间
        var minRow = Mathf.Max(Utilities.FloorToInt(relaMinPoint.y * mapGrid.GridSizeInv), 0); // 闭区间
        var maxCol = Mathf.Min(Utilities.CeilToInt(relaMaxPoint.x * mapGrid.GridSizeInv), mapGrid.Col); // 开区间
        var maxRow = Mathf.Min(Utilities.CeilToInt(relaMaxPoint.y * mapGrid.GridSizeInv), mapGrid.Row); // 开区间
        Core(mapGrid, vertices, minCol, minRow, maxCol, maxRow, tolerance, grids);
    }
    
    private static void Core(MapGrid mapGrid, List<Vector2> vertices, int minCol, int minRow, int maxCol, int maxRow, float tolerance, List<int> grids)
    {
        var n = vertices.Count;
        Span<float> firstDet = stackalloc float[n];
        Span<float> dx = stackalloc float[n];
        Span<float> dy = stackalloc float[n];
        
        
        var minAnchor = new Vector2(minCol, minRow);
        var minAnchorCenterX = (minAnchor.x + 0.5f) * mapGrid.gridSize;
        var minAnchorCenterY = (minAnchor.y + 0.5f) * mapGrid.gridSize;
        var minCenter = new Vector2(minAnchorCenterX, minAnchorCenterY) + mapGrid.min;
        for (int j = 0, i = n - 1; j < n; i = j++)
        {
            var pi = vertices[i];
            var pj = vertices[j];
            dx[j] = (pj.x - pi.x) * mapGrid.gridSize;
            dy[j] = (pj.y - pi.y) * mapGrid.gridSize;
            var toleranceFactor = (Mathf.Abs(dx[j]) + Mathf.Abs(dy[j])) * tolerance;
            firstDet[j] = Utilities.Det(pj - pi, minCenter - pi) + toleranceFactor;
        }
        IsInsideOptimized(mapGrid, vertices, minCol, minRow, maxCol, maxRow, firstDet, dx, dy, grids);
    }
    
    private static void IsInsideOptimized(MapGrid mapGrid, List<Vector2> vertices, int minX, int minY, int maxX, int maxY, 
        Span<float> firstDet, Span<float> dx, Span<float>dy, List<int> grids)
    {
        var n = vertices.Count;
        Span<float> curDet = stackalloc float[n];
        
        for (var y = minY; y < maxY; y++)
        {
            // 行初始叉积
            for (var i = 0; i < n; i++)
                curDet[i] = firstDet[i];
            
            for (var x = minX; x < maxX; x++)
            {
                var inside = true;
                for (var i = 0; i < n; i++)
                {
                    if (curDet[i] < 0)
                    {
                        inside = false;
                        break;
                    }
                }
                if (inside)
                    grids.Add(y * mapGrid.Col + x);

                // 右移：增量叉积
                for (var i = 0; i < n; i++)
                    curDet[i] -= dy[i];
            }
            
            // 上移：更新行初始叉积
            for (var i = 0; i < n; i++)
                firstDet[i] += dx[i];
        }
    }
}

效率对比

特性	边函数法	奇偶规则法
每格运算	加减法为主	含除法 + 乘法
提前退出	外部格平均 1-2 条边即 break	必须遍历全部 N 条边
堆分配	复用数组	零
综合速度	更快*	基准

在我本地测试500x500的网格，6个三角形覆盖大部分区域，测试结果如下：

方法	耗时（ms）
边函数法	5.10
奇偶规则	25.0
奇偶规则（优化版）	3.10

适用性对比

特性	边函数法	奇偶规则法
凸多边形	√	√
凹多边形	×	√
绕行顺序要求	仅限逆时针 (CCW)	无要求
顶点顺序要求	有序排列	任意顺序均可
保守覆盖	√（通过tolerace）	需要额外

局限性与注意事项

仅适用于凸多边形：凹多边形会导致内部点被错误排除。凹多边形必须使用奇偶规则法或非零环绕数法。
仅适用于逆时针 (CCW) 绕行：如果顶点是顺时针排列，所有点的判定结果会反转（全被判为外部）。
Tolerance 容差机制：tolerance 参数用于处理边界像素的浮点精度问题，按边长缩放 (|Dx|+|Dy|)*tolerance，使大边和小边有相近的相对容差。

总结

边函数光栅化是一种用空间换时间、用约束换速度的经典算法。它通过增量求值将每次迭代的计算复杂度从 O(N) 的乘除法降为 O(N) 的加减法，并支持提前退出优化。代价是失去了对凹多边形和任意绕行顺序的支持。在实际游戏开发中，如果你的多边形保证是凸的（如网格/寻路区域），边函数法是最优选择；如果需要处理任意形状，则退回到奇偶规则法。