光栅矢量图像的通用算法

Question

光栅化矢量图像的一般算法是什么？我发现了许多光栅化基元的算法,如直线,圆,贝塞尔曲线等.但一般情况下,我该怎么办？简单地说,在矢量图片中找到矢量图,得到它的像素并将它们放入光栅图像中？或者是其他东西？

另一个问题是,如何使用并发性来改善处理时间？例如,我可以分离矢量图并同时获取它们的像素.但也许有其他方法可以做到这一点？

Answer 1

对于图像中的每个多边形，一般的光栅化算法是这样的。

\n\n

（多边形被定义为由直线段和参数样条线组成的一条或多条闭合曲线 - 在正常实践中，这些是二阶（二次曲线别名二次）和三阶（三次）B\xc3\xa9zier 样条线。这些闭合曲线被定义为使得在穿过曲线时内部始终位于左侧；因此普通形状逆时针运行，而孔顺时针运行。）

\n\n

(i)（投影）将多边形转换为与目标位图相同的坐标系。分辨率不必相同，对于抗锯齿图像来说，分辨率通常更大：例如，FreeType 使用 64 分之一的像素。

\n\n

(ii)（使 Y 中单调）如有必要，将多边形的每个线段分割成连续向上或向下延伸的更小的线段。仅曲线段需要此阶段，并且在使用 B\xc3\xa9zier 样条线时相对容易。通常的方法是重复平分直到实现单调性。丢弃所有水平段。

\n\n

(iii)（标记运行限制）将每个段绘制成临时位图。使用 Bresenham 的直线算法；对于曲线，将其一分为二，直到该线距离实际曲线不超过（例如）1/8 个像素，然后从起点到终点使用一条直线。绘图时，以某种方式标记像素以指示（a）它们是游程的起点还是终点——向下的线是起点，向上的线是终点；(b) 覆盖范围 - 形状内部像素的比例。这是算法在细节上有所不同的地方，也是区分缠绕规则（非零与偶奇）的地方。

\n\n

(iv)（扫描）逐行遍历临时位图。对于每一行，从左到右扫描。通过（例如）将存储在位图中的数字添加到存储的数字来维持指示当前位置是否在形状内部的状态。在简单的单色光栅化中，在前一阶段写入的这个数字在穿过边缘进入形状时将为+1，而在离开形状时将为-1。累积处于相同状态的像素运行。将运行发送到绘图模块：例如，FreeType 发出由 Y 坐标、起始和结束 X 坐标以及从 0 到 255 的覆盖范围组成的运行。绘图模块可以使用覆盖范围作为应用于当前绘图颜色的 alpha 值，或作为应用于纹理的蒙版。

\n\n

上面的内容过于简单化，但给出了总体思路。

\n\n

大多数开源程序使用源自以下项目之一的光栅化代码：

\n\n

FreeType - 一种字体光栅化器，包含单色和抗锯齿光栅化器模块，这些模块相对易于独立使用 - 也就是说，适用于任何形状，而不仅仅是字体。我已经在几个商业可移植 C++ 项目中成功地使用了这个系统。

\n\n

FreeType 的系统受到 Raph Levien 的Libart的启发。

\n\n

Anti-Grain是另一个流行且有影响力的 C++ 库。

\n\n

还有Kiia Kallio 实现的扫描线边缘标志系统，看起来很有前途，而且似乎比 Anti-Grain 更快。

\n\n

大多数但不是全部这些库接受由二次和三次 B\xc3\xa9zier 样条线以及直线段组成的形状。那些不采用直边多边形的库（例如 K. Kallio 的库）仅采用直边多边形；但将曲线“展平”为一系列比实际曲线的期望最大距离更近的线段是很容易的。FreeType 在内部执行此操作，并且可以在必要时借用其代码。

\n