Algoritmo General para entramada vector de la imagen

Question

¿Cuál es el algoritmo general de rasterizar vector de la imagen?He encontrado una gran cantidad de algoritmos de rasterizar primitivas, tales como líneas, círculos, curvas Bezier, etc.Pero por lo general, ¿qué debo hacer?Simplemente, ir foreach vector de la figura en la imagen de vector, obtener sus píxeles y ponerlos en imagen de trama?O algo más?

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

Answer 1

El general de trazado del algoritmo es este, para cada polígono en la imagen.

(Un polígono se define como una o más curvas cerradas hecha de segmentos de línea recta y splines paramétricos - en la práctica normal de estos son de 2º orden (conic alias cuadrática) y 3er orden (metro cúbico) de las tiras de Bézier.Estas curvas cerradas se definen de forma que el interior siempre está a la izquierda, la curva se recorre;tan ordinario formas de ejecución en sentido anti-horario y los agujeros de ejecución de las agujas del reloj.)

(i) (proyección) Convertir el polígono para el mismo sistema de coordenadas como el mapa de bits de destino.La resolución no necesita ser el mismo, y para suavizar la apariencia de las imágenes es a menudo mayor de:por ejemplo, FreeType utiliza 64ths de píxeles.

(ii) (hacer monótono en Y) Donde sea necesario, dividir cada segmento del polígono en segmentos más pequeños que se ejecutan continuamente hacia arriba o hacia abajo.Esta etapa es necesaria sólo para los segmentos curvos, y es relativamente fácil cuando el uso de splines de Bézier.El método habitual es bisecar repetidamente hasta que la monotonía se logra.Deseche todos los segmentos horizontales.

(iii) (marca de la ejecución de los límites) Dibujar cada segmento en un mapa de bits temporal.Utilizar el algoritmo de Bresenham para las líneas rectas;para las curvas, bisecar hasta que la línea no es más que (dicen) de 1/8 de un píxel de la curva, a continuación, utilizar una línea recta desde el inicio hasta el final.Cuando el dibujo, la marca de píxeles de alguna manera para indicar (a) si se inicia o termina de carreras - las líneas hacia abajo se empieza, y arriba son las líneas de los extremos;(b) la cobertura de la fracción del píxel que dentro de la forma.Esto es donde los algoritmos difieren en los detalles, y donde liquidación reglas (no-cero frente a par-impar) son distinguidos.

(iv) (scan) Atravesar el temporal de mapa de bits, fila por fila.Para cada fila, el barrido de izquierda a derecha.Mantener un estado que indica si la posición actual está dentro de la forma o no (por ejemplo) sumar el número almacenado en el mapa de bits a un número almacenado.En blanco y negro simple, la rasterización de este número, escrito en la etapa anterior, será de +1 al cruzar un borde en la forma y -1 cuando se sale de la forma.Se acumulan las carreras de píxeles en el mismo estado.Enviar las pistas a su módulo de dibujo:por ejemplo, FreeType emite ejecuta consta de una coordenada de inicio y de finalización de las coordenadas X, y de la cobertura de 0 a 255.El módulo de dibujo puede utilizar la cobertura como un valor alfa aplicado al dibujo actual color, o como una máscara aplicada a una textura.

La de arriba es una gran sobre-simplificación, pero da una idea general.

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

FreeType - una fuente trama que contiene mono y anti-aliasing trama módulos que son relativamente fáciles de usar stand-alone, es decir, de cualquier forma, no sólo para las fuentes.He utilizado este sistema con éxito en varios comerciales portátil de proyectos de C++.

FreeType del sistema fue inspirado por Raph Levien del Libart.

Anti-Grano es otro de los populares e influyentes de la biblioteca de C++.

También existe la exploración de la línea de borde de la bandera de sistema implementado por Kiia Kallio, que parece prometedor y parece ser más rápido que los de Grano.

La mayoría, pero no todas, de estas bibliotecas aceptar formas que ha hecho desde cuadrática y cúbica de Bézier estrías así como segmentos de línea recta.Los que no lo hacen (por ejemplo, K.Kallio biblioteca) tomar rectos polígonos sólo;pero es muy fácil 'aplanar' una curva en una serie de segmentos de línea más cerca de lo que desee distancia máxima de la curva real.FreeType hace que internamente, y su código puede ser prestado cuando sea necesario.