Algoritmo generale per rastering immagine vettoriale

Question

Qual è l'algoritmo generale di rasterizzazione dell'immagine vettoriale? Ho trovato molti algoritmi per rasterizzare le primitive come linee, cerchi, curve di Bezier ecc. Ma per il generale, cosa dovrei fare? Semplicemente, vai a prendere la figura del vettore nella foto vettoriale, prendi i suoi pixel e li metti in un'immagine raster? O qualcos'altro?

E un'altra domanda, come posso migliorare il tempo di elaborazione utilizzando la concorrenza? Posso, ad esempio, separare le figure vettoriali e contemporaneamente ottenere i loro pixel. Ma forse ci sono altri metodi per farlo?

Answer 1

L'algoritmo di rasterizzazione generale è questo, per ogni poligono nell'immagine.

(Un poligono è definito come una o più curve chiuse costituite da segmenti di linea retta e spline parametriche - nella pratica normale queste sono spline di Bézier di secondo ordine (alias quadratico) e di terzo ordine (cubiche). sono definiti in modo che l'interno sia sempre a sinistra, mentre la curva è attraversata, quindi le forme ordinarie girano in senso antiorario e i fori girano in senso orario.)

(i) (proiezione) Converti il ​​poligono nello stesso sistema di coordinate di la bitmap di destinazione. La risoluzione non deve essere la stessa, e per le immagini anti-alias è spesso maggiore: ad esempio, FreeType utilizza il 64 ° pixel.

(ii) (rendere monotona in Y) Se necessario, dividere ciascun segmento del poligono in segmenti più piccoli che scorrono continuamente verso l'alto o verso il basso. Questo passaggio è necessario solo per i segmenti curvi ed è relativamente facile quando si utilizzano le spline di Bézier. Il metodo usuale è bisettare ripetutamente fino a quando non si raggiunge la monotonicità. Scarta tutti i segmenti orizzontali.

(iii) (segna i limiti della corsa) Disegna ciascun segmento in una bitmap temporanea. Usa l'algoritmo di Bresenham per le linee rette; per le curve, bisecare fino a che la linea non è più lontana (ad esempio) di 1/8 di un pixel dalla curva reale, quindi utilizzare una linea retta dall'inizio alla fine. Quando si disegna, contrassegnare i pixel in qualche modo per indicare (a) se sono iniziati o finali di esecuzioni - le linee verso il basso iniziano, e le linee verso l'alto sono le estremità; (b) la copertura - la frazione del pixel che si trova all'interno della forma. È qui che gli algoritmi si differenziano nei dettagli e dove si distinguono le regole di avvolgimento (non-zero rispetto a even-odd).

(iv) (scansione) Attraversare la bitmap temporanea, riga per riga. Per ogni riga, scansiona da sinistra a destra. Mantenere uno stato che indica se la posizione corrente si trova all'interno della forma o meno (ad esempio) aggiungendo il numero memorizzato nella bitmap a un numero memorizzato. Nella semplice rasterizzazione monocromatica, questo numero, scritto nella fase precedente, sarà +1 quando si attraversa un bordo nella forma e -1 quando si esce dalla forma. Accumula esecuzioni di pixel nello stesso stato. Invia le esecuzioni al tuo modulo di disegno: ad esempio, FreeType emette esecuzioni costituite da una coordinata Y, coordinate X di inizio e fine e copertura da 0 a 255. Il modulo di disegno può utilizzare la copertura come valore alfa applicato al colore del disegno corrente o come maschera applicata a una trama.

Quanto sopra è una grande semplificazione eccessiva ma dà l'idea generale.

maggior parte dei programmi open-source utilizzano codice rasterizzazione derivato da uno dei seguenti progetti:

FreeType - un rasterizer carattere che contiene i moduli rasterizer sia mono e anti-aliasing che sono relativamente facili da usare stand-alone - che è, per qualsiasi forma, non solo per i caratteri. Ho usato questo sistema con successo in diversi progetti C++ portatili commerciali.

Il sistema di FreeType è stato ispirato da Raphael Levien Libart.

Anti-Grain è un'altra libreria popolare e influente C++.

C'è anche lo scan-line edge flag system implementato da Kiia Kallio, che sembra promettente e sembra essere più veloce di Anti-Grain.

La maggior parte, ma non tutte, queste librerie accettano forme create da spline di Bézier quadratiche e cubiche e segmenti di retta. Quelli che non lo fanno (ad es. La biblioteca di K. Kallio) prendono solo poligoni a bordi retti; ma è abbastanza facile "appiattire" una curva in una serie di segmenti di linea più vicini di una distanza massima desiderata dalla curva attuale. FreeType lo fa internamente e il suo codice può essere preso in prestito quando necessario.