algoritmo generale immagine rastering vettore

Question

Qual è l'algoritmo generale di immagine di vettore rasterizzazione? Ho trovato un sacco di algoritmi di rasterizzazione primitivi, come linee, cerchi, curve di Bezier ecc ma per generale, che cosa devo fare? Semplicemente, andare foreach figura vettore di immagine vettoriale, ottenere i suoi pixel e metterli immagine raster in? O qualcos'altro?

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

Answer 1

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

(Un poligono è definito come uno o più curve chiuse a base di segmenti rettilinei e splines parametriche - in pratica normale sono 2 ° ordine (conica alias quadratica) e 3 ° ordine (cubica) curve di Bezier Queste curve chiuse sono. definita in modo che l'interno è sempre sulla sinistra, mentre la curva è attraversato;. forme così ordinari eseguiti in senso antiorario e fori corrono in senso orario)

(i) (proiezione) Convertire il poligono allo stesso sistema di coordinate bitmap di destinazione. La necessità di risoluzione non essere la stessa, e per le immagini anti-alias è spesso maggiore:., Ad esempio, utilizza FreeType 64esimi di pixel

(ii) (fare monotona Y) Se necessario, dividere ogni segmento del poligono in segmenti più piccoli che eseguono continuamente verso l'alto o verso il basso. Questa fase è necessaria solo per segmenti curvi, ed è relativamente facile quando usando curve di Bezier. Il metodo usuale è quello bisect volte fino a ottenere monotonia. Eliminare tutti i segmenti orizzontali.

(iii) (segnare i limiti di esecuzione) Disegna ogni segmento in una bitmap temporanea. Utilizzare l'algoritmo di Bresenham per linee rette; per le curve, bisect fino a quando la linea è zone più (diciamo) di 1/8 di pixel dalla curva reale, quindi utilizzare una linea retta dall'inizio alla fine. Quando disegno, pixel mark in qualche modo per indicare (a) siano essi inizia o estremità delle piste - linee verso il basso sono partenze e linee ascendenti sono fini; (B) la copertura - la frazione di pixel che è all'interno della forma. È qui algoritmi differiscono nei dettagli, e dove avvolgimento regole ( non nullo rispetto pari-dispari ) si distinguono.

(iv) (scansione) traslare gli bitmap temporanea, riga per riga. Per ogni riga, scansione da sinistra a destra. Mantenere uno stato che indica se la posizione corrente è all'interno della forma o meno da (per esempio) aggiungendo il numero memorizzato nella bitmap per un numero memorizzato. In semplice rasterizzazione monocromatico questo numero, scritta nella fase precedente, sarà +1 quando attraversano un bordo nella forma e -1 quando esce dalla forma. corre accumulo di pixel nello stesso stato. Invia le corse al modulo disegno: per esempio, FreeType emette funzionamenti costituiti da una coordinata Y, avviamento e le coordinate X, fine e copertura da 0 a 255. Il modulo di disegno può usare la copertura come valore alfa applicata al colore disegno corrente o come una maschera applicata a una texture.

È possibile che questo è un grande eccesso di semplificazione, ma dà l'idea generale.

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

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

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

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

C'è anche la scan-linea sistema bandiera bordo implementata da Kiia Kallio, che sembra essere molto promettente e sembra essere più veloce di Anti-Grain.

La maggior parte ma non tutte queste librerie accettano forme a base di curve di Bezier quadratiche e cubiche, nonché segmenti di linea retta. Coloro che non poligoni (ad esempio, la biblioteca di K. Kallio) prendere retti fare solo; ma è abbastanza facile 'appiattire' una curva in una serie di segmenti di linea più vicino di un desideratodistanza massima dalla curva reale. FreeType fa quello interno, e il suo codice può essere preso in prestito quando necessario.