栅格化矢量图像的通用算法

Question

栅格化矢量图像的通用算法

vector-graphicsrasterizingraster-graphics

8

如何将矢量图形转换成光栅图像的通用算法是什么？我找到了许多将基元（如线条、圆、贝塞尔曲线等）转换为光栅化的算法。但是对于通用的情况，我该怎么做呢？只需要遍历矢量图片中的每个矢量图形，获取其像素并将它们放入光栅图像中吗？还是有其他方法？

另外一个问题是，如何使用并发性能提升处理时间？例如，我可以分离矢量图形并同时获取它们的像素。但也许还有其他方法可以实现这一点吗？

- medvedNick

1

你目前使用哪种矢量图形环境？我所知道的任何框架都有现成的解决方案，可以在屏幕上或光栅位图上绘制矢量图形，为您解决光栅化问题。 - Doc Brown

我同意@DocBrown的观点。除非你已经尝试了所有可能的现有选项，否则不要重新发明轮子，即使这样做，也要尽可能多地利用其他无数人已经完成的工作，以便你所重复的工作尽可能少。 - cdeszaq

1

这是一个关于编程的内容，以下是翻译的文本：这是一个理论问题，没有具体的向量化或使用具体的框架。我感兴趣的是这些框架在使用什么算法，以及如何通过并发来改进这些算法 :) - medvedNick

关于第二个问题：这取决于您攻击问题的抽象级别。您的环境/框架的基本操作是什么（即使它是假设的）？只绘制单个像素还是绘制基本图形？如果是这样，那么是哪些图形？您的框架是否允许并行向光栅进行多个绘图操作？ - Doc Brown

使用这些作为入门的基础。它们是可移植的C语言光栅化器。 https://github.com/MalcolmMcLean/babyx/blob/master/src/common/bbx_graphicscontext.c https://github.com/MalcolmMcLean/babyx/blob/master/src/common/bbx_graphicscontext.h - Malcolm McLean

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Graham Asher · Accepted Answer

一般的光栅化算法如下，对于图像中的每个多边形：

（一个多边形被定义为由直线段和参数样条制成的一个或多个封闭曲线 - 在正常实践中，这些是二阶（圆锥体别名二次）和三阶（立方体）贝塞尔样条。这些封闭曲线被定义为内部始终在左侧，当遍历曲线时; 因此普通形状顺时针运行，孔运行逆时针。）

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

（ii）（在Y轴上使其单调）必要时，将多边形的每个线段分割成连续向上或向下运行的较小线段。此阶段仅需要用于曲线段，并且在使用贝塞尔样条时相对容易。通常的方法是重复地进行二等分，直到实现单调性。丢弃所有水平线段。

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

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

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

大多数开源程序使用从以下项目派生的光栅化代码： FreeType - 包含了单色和抗锯齿光栅化器模块的字体光栅化器，这些模块相对容易独立使用 - 也就是说，对于任何形状，而不仅仅是字体。我已经在几个商业便携式C++项目中成功使用了这个系统。

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

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

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

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