Algoritmo general para la imagen vectorial de barrido

Question

¿Cuál es el algoritmo general de rasterización de la imagen vectorial? He encontrado muchos algoritmos de primitivas de rasterización, como líneas, círculos, curvas de Bezier, etc. Pero, en general, ¿qué debo hacer? Simplemente, ve foreach vector figure en la imagen vectorial, toma sus píxeles y colócalos en una imagen rasterizada. ¿O algo mas?

Y otra pregunta, ¿cómo puedo mejorar el tiempo de procesamiento utilizando concurrencia? Puedo, por ejemplo, separar figuras de vectores y al mismo tiempo obtener sus píxeles. Pero tal vez hay otros métodos para hacer esto?

Answer 1

El algoritmo general de rasterización es esto, para cada polígono en la imagen.

(Un polígono se define como una o más curvas cerradas hechas de segmentos de línea recta y splines paramétricos; en la práctica normal son splines Bézier de segundo orden (alias cónico cuadrático) y de 3er orden (cúbico). se definen para que el interior esté siempre a la izquierda, a medida que se recorre la curva, por lo que las formas normales se ejecutan en sentido antihorario y los agujeros se ejecutan en el sentido de las agujas del reloj.)

(i) (proyección) Convierta el polígono en el mismo sistema de coordenadas el mapa de bits de destino La resolución no tiene que ser la misma, y ​​para las imágenes antialias es a menudo mayor: por ejemplo, FreeType usa 64 de píxeles.

(ii) (haga monótono en Y) Donde sea necesario, divida cada segmento del polígono en segmentos más pequeños que se extiendan continuamente hacia arriba o hacia abajo. Esta etapa solo se necesita para segmentos curvos, y es relativamente fácil cuando se utilizan las splines de Bézier. El método habitual es bisectar repetidamente hasta que se logre la monotonicidad. Descartar todos los segmentos horizontales.

(iii) (marque los límites de ejecución) Dibuje cada segmento en un mapa de bits temporal. Use el algoritmo de Bresenham para líneas rectas; para las curvas, biseque hasta que la línea no sea más que (digamos) 1/8 de un píxel de la curva real, luego use una línea recta de principio a fin. Al dibujar, marque los píxeles de alguna manera para indicar (a) si se trata de inicios o finales de ejecuciones: las líneas descendentes son inicios y las líneas ascendentes son extremos; (b) la cobertura: la fracción del píxel que está dentro de la forma. Aquí es donde los algoritmos difieren en los detalles, y donde las reglas de devanado (non-zero versus even-odd) se distinguen.

(iv) (escanear) Recorre el mapa de bits temporal, fila por fila. Para cada fila, escanee de izquierda a derecha. Mantenga un estado que indique si la posición actual está dentro de la forma o no (por ejemplo) agregando el número almacenado en el mapa de bits a un número almacenado. En la rasterización monocromática simple, este número, escrito en la etapa anterior, será +1 al cruzar un borde en la forma y -1 al salir de la forma. Acumula ejecuciones de píxeles en el mismo estado. Envíe las ejecuciones a su módulo de dibujo: por ejemplo, FreeType emite ejecuciones que consisten en una coordenada Y, coordenadas X de inicio y final y cobertura de 0 a 255. El módulo de dibujo puede usar la cobertura como un valor alfa aplicado al color de dibujo actual o como una máscara aplicada a una textura.

Lo anterior es una gran simplificación excesiva, pero da la idea general.

mayoría de los programas de código abierto utilizan código de rasterización derivado de uno de los siguientes proyectos:

FreeType - una impresora de trama de fuente que contiene tanto mono y anti-aliasing módulos Rasterizer que son relativamente fáciles de usar autónomo - que es, para cualquier forma, no solo para fuentes. Utilicé este sistema con éxito en varios proyectos comerciales de C++ portátiles.

El sistema de FreeType se inspiró en el Libart de Raph Levien.

Anti-Grain es otro popular e influyente biblioteca de C++.

También está el scan-line edge flag system implementado por Kiia Kallio, que parece prometedor y parece ser más rápido que Anti-Grain.

La mayoría, pero no todas estas bibliotecas aceptar formas hechas a partir de curvas de Bezier cuadráticas y cúbicas, así como segmentos de línea recta. Los que no lo hacen (por ejemplo, la biblioteca de K. Kallio) solo toman polígonos de bordes rectos; pero es bastante fácil "aplanar" una curva en una serie de segmentos de línea más cercanos que una distancia máxima deseada de la curva real. FreeType lo hace internamente, y su código puede tomarse prestado cuando sea necesario.