光栅矢量图像通用算法
矢量图像光栅化的一般算法是什么？我发现了很多光栅化图元的算法，例如直线、圆、贝塞尔曲线等。但是一般来说，我应该做什么？简单地说，查找矢量图中的每个矢量图形，获取其像素并将它们放入光栅图像中？还是别的什么？
还有一个问题，如何使用并发来提高处理时间？例如，我可以分离矢量图并同时获取它们的像素。但也许还有其他方法可以做到这一点？
What is the general algorithm of rasterizing vector image? I've found a lot of algorithms of rasterizing primitives such as lines, circles, Bezier curves etc. But for general, what should I do? Simply, go foreach vector figure in vector picture, get its pixels and put them into raster image? Or something else?
And another question, how can I improve the time of processing using concurrency? I can, for example, separate vector figures and concurrently get their pixels. But maybe there are other methods to do this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
对于图像中的每个多边形，一般的光栅化算法是这样的。
（多边形被定义为由直线段和参数样条线组成的一条或多条闭合曲线 - 在正常实践中，这些是二阶（二次曲线别名二次）和三阶（三次）贝塞尔样条线。这些闭合曲线的定义为：当穿过曲线时，内部始终位于左侧；因此普通形状逆时针运行，而孔顺时针运行。）
(i)（投影）将多边形转换为与目标位图相同的坐标系。分辨率不必相同，对于抗锯齿图像来说，分辨率通常更大：例如，FreeType 使用 64 分之一的像素。
(ii)（使 Y 中单调）如有必要，将多边形的每个线段分割成连续向上或向下延伸的更小的线段。仅曲线段需要此阶段，并且在使用贝塞尔样条线时相对容易。通常的方法是重复平分直到实现单调性。丢弃所有水平段。
(iii)（标记运行限制）将每个段绘制成临时位图。对直线使用 Bresenham 算法；对于曲线，将其一分为二，直到该线距离实际曲线不超过（例如）1/8 个像素，然后从起点到终点使用一条直线。绘图时，以某种方式标记像素以指示（a）它们是游程的起点还是终点——向下的线是起点，向上的线是终点； (b) 覆盖范围 - 形状内部像素的比例。这是算法在细节上有所不同的地方，也是缠绕规则（非零与偶-奇）是有区别的。
(iv)（扫描）逐行遍历临时位图。对于每一行，从左到右扫描。通过（例如）将存储在位图中的数字添加到存储的数字来维持指示当前位置是否在形状内部的状态。在简单的单色光栅化中，在前一阶段写入的这个数字在穿过边缘进入形状时将为+1，而在离开形状时将为-1。累积处于相同状态的像素运行。将运行发送到绘图模块：例如，FreeType 发出由 Y 坐标、起始和结束 X 坐标以及从 0 到 255 的覆盖范围组成的运行。绘图模块可以使用覆盖范围作为应用于当前绘图颜色的 alpha 值，或作为应用于纹理的蒙版。
上面的内容过于简单化，但给出了总体思路。
大多数开源程序使用源自以下项目之一的光栅化代码：
FreeType - 一种字体光栅化器，包含两者单声道和抗锯齿光栅化模块相对易于独立使用 - 也就是说，适用于任何形状，而不仅仅是字体。我已经在几个商业可移植 C++ 项目中成功地使用了这个系统。
FreeType 的系统受到 Raph Levien 的 Libart 的启发。
Anti-Grain 是另一个流行且有影响力的 C++ 库。
还有 Kiia Kallio 实现的扫描线边缘标记系统，看起来很有前途并且似乎比 Anti-Grain 更快。
大多数但不是全部这些库接受由二次和三次贝塞尔样条以及直线段组成的形状。那些不这样做的库（例如，K. Kallio 的库）仅采用直边多边形；但将曲线“展平”为一系列距离实际曲线比所需最大距离更近的线段是很容易的。 FreeType 在内部执行此操作，并且可以在必要时借用其代码。
The general rasterization algorithm is this, for each polygon in the image.
(A polygon is defined as one or more closed curves made from straight line segments and parametric splines - in normal practice these are 2nd-order (conic alias quadratic) and 3rd-order (cubic) Bézier splines. These closed curves are defined so that the inside is always on the left, as the curve is traversed; so ordinary shapes run anti-clockwise and holes run clockwise.)
(i) (projection) Convert the polygon to the same coordinate system as the destination bitmap. The resolution need not be the same, and for anti-aliased images is often greater: for example, FreeType uses 64ths of pixels.
(ii) (make monotonic in Y) Where necessary, split each segment of the polygon into smaller segments that run continuously upward or downward. This stage is needed only for curved segments, and is relatively easy when using Bézier splines. The usual method is to bisect repeatedly until monotonicity is achieved. Discard all horizontal segments.
(iii) (mark the run limits) Draw each segment into a temporary bitmap. Use Bresenham's algorithm for straight lines; for curves, bisect until the line is no further than (say) 1/8 of a pixel from the real curve, then use a straight line from start to end. When drawing, mark pixels in some way to indicate (a) whether they are starts or ends of runs - downward lines are starts, and upward lines are ends; (b) the coverage - the fraction of the pixel that's inside the shape. This is where algorithms differ in the details, and where winding rules (non-zero versus even-odd) are distinguished.
(iv) (scan) Traverse the temporary bitmap, row by row. For each row, scan from left to right. Maintain a state which indicates whether the current position is inside the shape or not by (for example) adding the number stored in the bitmap to a stored number. In simple monochrome rasterization this number, written in the previous stage, will be +1 when crossing an edge into the shape and -1 when coming out of the shape. Accumulate runs of pixels in the same state. Send the runs to your drawing module: for example, FreeType emits runs consisting of a Y coordinate, start and end X coordinates, and coverage from 0 to 255. The drawing module can using the coverage as an alpha value applied to the current drawing colour, or as a mask applied to a texture.
The above is a great over-simplification but gives the general idea.
Most open-source programs use rasterization code derived from one of the following projects:
FreeType - a font rasterizer which contains both mono and anti-aliasing rasterizer modules that are relatively easy to use stand-alone - that is, for any shape, not just for fonts. I have used this system successfully in several commercial portable C++ projects.
FreeType's system was inspired by Raph Levien's Libart.
Anti-Grain is another popular and influential C++ library.
There is also the scan-line edge flag system implemented by Kiia Kallio, which looks promising and seems to be faster than Anti-Grain.
Most but not all of these libraries accept shapes made from quadratic and cubic Bézier splines as well as straight line segments. Those which don't (e.g., K. Kallio's library) take straight-edged polygons only; but it is quite easy to 'flatten' a curve into a series of line segments closer than a desired maximum distance from the actual curve. FreeType does that internally, and its code can be borrowed when necessary.