两级 Alpha 采样：如何用 (轮廓) 代替 (面积) 提取 2D 图片边界

在 2D 网格变形系统中，需要运行时分析图片 alpha 通道来自动生成贴合内容的三角网格。逐像素扫描 1024×2048 的图片意味着 200 万次采样——在 Lua 脚本层这会卡到无法接受。本文介绍一种两级采样算法，通过四角共享网格 + 边界格子精扫，将实际采样量降低一个数量级以上，同时保持轮廓精度。

场景一个 2D 纸娃娃角色系统，角色被拆分为 10 个 PNG 图层（头发、头部、身体、衣服等），每个图层画布大小统一为 1024×2048，但实际内容只占画布的一部分。运行时需要为每个图层自动生成网格（供 Delaunay 三角剖分 → 网格变形 → GPU 渲染），第一步就是从图片的 alpha 通道中提取：

为什么不能逐像素扫描最直觉的方案：遍历每一个像素，检查 alpha > 阈值。1024 × 2048 = 2,097,152 次 GetPixel 调用

在 C/C++ 层这不算什么，但这个项目跑在 Lua 脚本层——每次 GetPixel 都要跨 Lua/C++ 边界。实测在 WebGL 环境下，200 万次调用会冻住画面好几秒。而且不止一个图层。10 个图层 = 2000 万次采样，这显然不可接受。需要一种采样量与轮廓长度（而非图片面积）成正比的方法。

核心思路：大多数像素不在边界上观察一张典型图层（比如"后发"层，1024×2048 画布，内容区域约 1020×1000）：

第一级：四角共享网格采样将图片划分为 gridStep × gridStep（这里取 50px）的格子网格：1024 / 50 = 21 列  （向上取整）

2048 / 50 = 41 行

关键观察：每个格子有 4 个角，相邻格子共享角点。 不需要为每个格子独立采样 4 次，只需在角点网格上做一次遍历：角点网格 = (gridCols + 1) × (gridRows + 1) = 22 × 42 = 924 个采样点

对比逐像素的 200 万次，这里只需要 924 次 GetPixel 调用。lua

复制local gridStep = 50

local gridCols = math.ceil(w / gridStep)  -- 21

local gridRows = math.ceil(h / gridStep)  -- 41

local cornerCols = gridCols + 1           -- 22

local cornerRows = gridRows + 1           -- 42

-- 采样所有角点

local cornerMap = {}

for r = 0, cornerRows - 1 do

    cornerMap[r] = {}

    local py = math.min(r * gridStep, h - 1)

    for c = 0, cornerCols - 1 do

        local px = math.min(c * gridStep, w - 1)

        cornerMap[r][c] = image:GetPixel(px, py).a > 0.04

    end

end

然后根据每个格子四个角的采样结果，将格子分为三类：四角状态格子类型含义4 个角全部有内容interior完全在内容区域内部1~3 个角有内容border轮廓穿过此格子4 个角全部透明待定 → 需补充采样可能是空的，也可能有孤岛lua

复制if count == 4 then

    cellType[key] = "interior"

elseif count >= 1 then

    cellType[key] = "border"

else

    -- 四角全空：补一次中心点采样

    ...

end

补丁 1：孤岛检测四角全空的格子不一定真的是空的——如果图片内容恰好在格子正中间、不接触任何角点，四角采样会完全漏掉。解决方案：对四角全空的格子额外采样一次中心点：lua

复制if count == 0 then

    local cx = c * gridStep + gridStep / 2

    local cy = r * gridStep + gridStep / 2

    if image:GetPixel(cx, cy).a > 0.04 then

        cellType[key] = "border"  -- 孤岛，视为边界

    else

        cellType[key] = "empty"

    end

end

代价很低——一个格子只多 1 次采样。补丁 2：interior 降级四角全有内容的格子被标记为 interior，但如果它的四邻居中有 empty 格子，说明它实际上靠近轮廓边缘——应该降级为 border 以获得精扫：lua

复制for r = 0, gridRows - 1 do

    for c = 0, gridCols - 1 do

        if cellType[key] == "interior" then

            local hasEmptyNeighbor =

                (r == 0) or (r == gridRows - 1)

                or (c == 0) or (c == gridCols - 1)

                or not cellMap[r-1][c] or not cellMap[r+1][c]

                or not cellMap[r][c-1] or not cellMap[r][c+1]

            if hasEmptyNeighbor then

                cellType[key] = "border"

            end

        end

    end

end

这一步不增加任何采样，只是重新分类。第一级完成后，我们得到了一张格子分类图。 核心数据：哪些格子是 border。

边界格子精扫只对 border 类型的格子做高密度扫描。精扫步长 fineStep = gridStep / 6 ≈ 8px，做两件事：行扫描：找每行的左右 alpha 边界在格子内部，每隔 fineStep 选一行，从左到右逐像素扫描，记录第一个和最后一个 alpha > 阈值的像素位置：lua

复制for ly = 0, cellH - 1, fineStep do

    local py = cellY + ly

    local left, right = nil, nil

    for lx = 0, cellW - 1 do

        if image:GetPixel(cellX + lx, py).a > 0.04 then

            if not left then left = cellX + lx end

            right = cellX + lx

        end

    end

    if left then

        edgePts[#edgePts + 1] = { x = left, y = py }

        edgePts[#edgePts + 1] = { x = right, y = py }

    end

end

列扫描：找每列的上下 alpha 边界同理，每隔 fineStep 选一列，从上到下扫描，记录第一个和最后一个非透明像素：lua

复制for lx = 0, cellW - 1, fineStep do

    local px = cellX + lx

    local top, bot = nil, nil

    for ly = 0, cellH - 1 do

        if image:GetPixel(px, cellY + ly).a > 0.04 then

            if not top then top = cellY + ly end

            bot = cellY + ly

        end

    end

    if top then

        edgePts[#edgePts + 1] = { x = px, y = top }

        edgePts[#edgePts + 1] = { x = px, y = bot }

    end

end

行扫描和列扫描交叉使用，确保轮廓的水平段和垂直段都被捕获到。每行/列扫描的范围限制在格子内部（50px），所以每次扫描最多 50 个像素。

采样量分析用一个实际图层来算。以"后发"层为例（bbox 约 1020×1000，占画布面积约 50%）：第一级角点采样：22 × 42 = 924 次

中心补充采样（四角全空的格子）：约 400 次（画布一半是空的）

合计约 1,324 次

border 格子数取决于轮廓长度。头发轮廓相对复杂，假设有 ~120 个 border 格子。每个 border 格子的精扫量：行扫描：(50/8) 行 × 50 像素 ≈ 6 × 50 = 300 次

列扫描：(50/8) 列 × 50 像素 ≈ 6 × 50 = 300 次

每格子合计 ≈ 600 次

120 个 border 格子 × 600 = 72,000 次

总计第一级：     ~1,300 次

第二级：    ~72,000 次

合计：      ~73,300 次

逐像素扫描：2,097,152 次

节省比例：  96.5%

对于内容区域更小的图层（比如"眉毛"层，bbox 仅 804×64），border 格子更少，节省更极端。实际运行日志印证了这个量级：[AutoMesh] corner-scan: grid=21x41(step=50), corners=924,

  fine=68742, total=70066 samples, 287 points

7 万次 vs 200 万次——采样量降低到 3.3%。

第一级和第二级的关系两级之间不是简单的"粗扫 + 细扫"关系，而是分类 + 定向精扫：第一级的输出不是"粗略的 bbox"

第一级的输出是"哪些格子需要精扫"（格子分类图）

第二级只在 border 格子内工作

interior 格子不需要精扫（它们完全在内容内部，用四角 + 中心点就够了）

empty 格子不需要精扫（它们没有内容）

这意味着：精扫的工作量与轮廓长度成正比，与图片面积无关。一张 4096×4096 的图片，如果内容轮廓和 1024×2048 的图片差不多长，精扫量几乎一样。增加的只是第一级的角点采样数（从 924 到几千，依然很小）。

顶点放置策略精扫完成后，需要把这些边界信息转化为控制点集（供 Delaunay 三角剖分使用）。对不同类型的格子使用不同策略：格子类型顶点来源理由border精扫得到的边缘点 + 格子中心轮廓处需要高密度点interior四角 + 中心（5 个点）内部不需要过多细节empty不放点没有内容所有顶点经过去重——距离小于 gridStep × 0.12 ≈ 6px 的点合并，避免三角剖分产生退化三角形。lua

复制local dedupDist = math.max(3, math.floor(gridStep * 0.12 + 0.5))

local function addPoint(px, py)

    for _, p in ipairs(points) do

        if math.abs(p.x - px) < dedupDist

           and math.abs(p.y - py) < dedupDist then

            return  -- 太近，跳过

        end

    end

    points[#points + 1] = { x = px, y = py }

end

最终输出 200~400 个控制点，这个密度足够三角剖分产生贴合轮廓的网格。

设计决策回顾做这个算法时有几个岔路口，记录一下选择和理由：为什么不用 marching squares？Marching squares 也是处理二值化网格的经典算法，但它的目的是生成等值线（连续的轮廓路径），而我需要的是散点集（供 Delaunay 使用）。用 marching squares 先生成路径再在路径上采样，多了一层间接，且路径连接逻辑在复杂轮廓（多个不连通区域）上容易出 bug。直接在精扫阶段输出边界点更简单直接。为什么 gridStep 取 50？实验过几个值：gridStep角点数典型 border 格子数精扫量效果205,000+300+20 万+过密，接近逐像素50924~120~7 万轮廓精度足够100231~60~6 万角点太稀疏，孤岛漏检风险高50px 是精度和性能的平衡点。对于 1024 宽的图片，50px 格子意味着轮廓定位误差最大 ±50px（但精扫会把误差降到 ±1px）。为什么不用采样金字塔 / mipmap？先在低分辨率版本上找到大致区域，再回到原图精扫——这个思路可行，但依赖图片的缩小版本。在这个场景中，图片是作为纹理资源加载的，获取 mipmap 级别需要额外的 API 调用。而格子采样不依赖任何图像预处理，只需要 GetPixel，实现更简单。精扫阶段为什么要逐像素而不是继续分级？边界格子只有 50×50 像素。在这个尺度上再做分级（比如 5×5 的子格子）反而增加逻辑复杂度，且节省的采样量有限（从 2500 降到 ~600 已经够了）。直接逐行/逐列扫描代码最简单，且采样结果直接就是边界点坐标，不需要额外转换。

逐像素扫描两级采样采样次数200 万~7 万与图片面积的关系线性 O(W×H)第一级 O(W×H / gridStep²)，第二级 O(轮廓长度 × gridStep)轮廓精度像素级像素级（精扫阶段恢复）实现复杂度极低中等（格子分类 + 精扫 + 去重）适合场景C/C++ 层，小图片脚本层，大图片，多图层核心思想只有一句话：先用极少的采样点把图片分成"不需要看"和"需要仔细看"两类区域，然后只仔细看需要看的部分。这个思路不限于 alpha 采样。任何"大面积数据中只有边界处的细节有意义"的场景都可以用类似的两级策略——比如地形碰撞检测、可见性剔除、LOD 区域划分等。