光栅化矢量图像的一般算法

Question

光栅化矢量图像的一般算法是什么？我发现了许多栅格化基元的算法，例如线条，圆，贝塞尔曲线等。但是对于一般情况，我该怎么做？简单地说，向矢量图中的矢量图中添加foreach，获取其像素并将其放入光栅图像中？或者是其他东西？

另一个问题，我该如何提高使用并发处理的时间？例如，我可以分离矢量图并同时获取像素。但也许有其他方法可以做到这一点？

Answer 1

一般的光栅化算法就是这样，对于图像中的每个多边形。 （一个多边形定义为由直线段和参数样条构成的一个或多个闭合曲线 - 在正常实践中，这些曲线是二阶（二次曲线）和三阶（三次）Bézier样条曲线。这些闭合曲线被定义为内部总是在左侧，因为曲线是通过的;所以普通形状逆时针运行并且孔顺时针运行。）

（i）（投影）将多边形转换为与目标位图。分辨率不必相同，对于消除锯齿的图像往往更大：例如，FreeType使用64像素。 （ii）（使Y单调）必要时，将多边形的每个分段分成连续向上或向下运行的较小段。这个阶段仅适用于曲线段，并且在使用贝塞尔样条时相对容易。通常的方法是反复平分直到达到单调性。丢弃所有水平段。 （iii）（标记运行限制）将每个段绘制到临时位图中。使用Bresenham的直线算法;对于曲线，平分线直到线距离实际曲线的1/8像素（比如说），然后从头到尾使用一条直线。绘制时，以某种方式标记像素以指示（a）它们是开始还是结束运行 - 向下的线开始，向上的线结束; （b）覆盖率 - 形状内像素的分数。这是算法细节不同的地方，以及缠绕规则（non-zero与even-odd）之间的区别。 （iv）（扫描）逐行遍历临时位图。对于每一行，从左到右扫描。通过（例如）将存储在位图中的数字添加到存储的数字来维护指示当前位置是否在形状内部的状态。在简单的单色光栅化过程中，在前一阶段编写的这个数字将在边缘进入形状时为+1，在形状出来时为-1。在相同的状态下累积像素运行。将运行发送到您的绘图模块：例如，FreeType发出包含Y坐标，开始和结束X坐标以及覆盖范围从0到255的运行。绘图模块可以使用coverage作为应用于当前绘图颜色的Alpha值，或作为应用于纹理的蒙版。

以上是一个伟大的过度简化，但给出了一般的想法。

大多数开放源代码程序使用从下列项目之一衍生光栅化代码：

FreeType - 一字形生成它包含了相对容易使用单机单声道和抗锯齿光栅模块 - 即对于任何形状而言，不仅仅是字体。我已经在几个商业可移植的C++项目中成功地使用了这个系统。

FreeType的系统灵感来自于Raph Levien的Libart。

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

还有由Kiia Kallio实施的scan-line edge flag system，它看起来很有前途，似乎比反谷物更快。

大多数但不是全部这些库接受由二次和三次贝塞尔样条以及直线段组成的形状。那些没有的（例如K. Kallio的图书馆）只能使用直边多边形;但是很容易将曲线“平坦化”成比距实际曲线的期望最大距离更近的一系列线段。 FreeType可以在内部执行此操作，并且可以在必要时借用它的代码。