Copertura - difetto nell'algoritmo - come sbarazzarsi del suo uso?

10

Introduzione

Molti dei motori di rendering della grafica vettoriale di tipo mainline hanno un difetto algoritmico al loro interno. Rendono ogni forma separatamente e gli antialias calcolando la copertura dei pixel e quindi li compongono uno sopra l'altro. Sì, è semplice ma le soluzioni corrette sono ancora più semplici.

Questo porta a un problema di conflazione poiché confonde la copertura con la trasparenza. L'Alpha blending segue una regola che non rappresenta la situazione in modo accurato, ad esempio, prendi un pixel coperto al 50% che è vicino a un pixel che è coperto al 50% e non finisce con una copertura del 100% finisce con una copertura del 75% . Ciò che appare dipende da come l'algoritmo è sintonizzato e da altri dettagli, ma in pratica si tratta di un errore noto. Qualcuno ha persino provato il problema di documentare i diversi errori del motore insieme a scrivere un articolo che mostra come potrebbe essere fatto meglio.

Immagine1:campionetotalmentenonrappresentativo,direnderingdiunaformacompostadatriangoliconerroreingranditonellarigasuperiore. origine SVG

Il problema ha una semplice soluzione ingenua * solo un super campione senza calcolo della copertura e filtrare l'immagine verso il basso. Come bonus, puoi utilizzare algoritmi di ricostruzione delle immagini migliori rispetto al filtro box (leggi A Pixel is Not a Square 3 ). Esistono anche soluzioni che hanno una velocità comparabile come soluzioni attuali e queste soluzioni sono molto più facili da fare nelle pipeline di rasterizzazione hardware (e raramente si vede questo errore su GPU perché è stato creato per evitare solo questo problema).

Anche questo non è un problema senza un costo. Ci sono molte persone che lavorano nella progettazione grafica che trascorrono una quantità non trascurabile di tempo cercando di aggirare questo problema manualmente assicurandosi che qui ci sia sovrapposizione e nessuna sovrapposizione per risolvere il problema che il computer dovrebbe fare per loro. E fallendo in modo spettacolare in molti casi. Ma ai loro clienti non interessa il motivo per cui l'errore è presente, devono risolverlo.

Domanda

Come si diffonde l'errore? Dal momento che stanno facendo tutti lo stesso errore, si potrebbe concludere che usano la stessa fonte per il loro algoritmo. Cosa avrebbe potuto far scegliere ai progettisti questo algoritmo? Perché solo i programmatori 3D hanno riconosciuto questo errore e persino hanno codificato la sua parte nelle API e l'insegnamento mentre i programmatori 2D no?

Come fare in modo che questo errore smetta di propagarsi ulteriormente?

Addendum (ma non me lo chiedo)

* Apparentemente la mia affermazione che il super campionamento funziona senza difetti è straordinaria e richiede prove straordinarie. Ok, quindi il tasto per il super campionamento funzionante è che il super campionamento non esegue l'elaborazione della copertura. In sostanza, il super-campionatore tratta ogni campione come un campione di punti. Dal momento che il campione di punti non assume alcuna ipotesi dell'area sottostante, non sta causando il confronto alfa dove non si verifica.

Affinché funzioni coerentemente, come descritto in una delle risposte. Abbiamo bisogno di fare per elaborare i campioni con campionamento intero per coerenza. Questo ci assicura che ogni punto una volta trasformato nello spazio dello schermo ottiene esattamente la stessa soluzione per le coordinate uguali e che nessun campione è ombreggiato da un bordo di pixel 2 volte. Per fare ciò, un campione potrebbe non innescare un pixel ot è esattamente on se è per esempio il campione in basso a sinistra (così facciamo una regola che i bordi esatti sono elaborati in > vs < =). Tutte le schede grafiche della console tranne una funzionano in questo modo. Garantisce che nessun dato aggiuntivo debba essere memorizzato nella cache e che non è necessario eseguire test aggiuntivi nelle vicinanze. Questa soluzione è stabile, più generale e coerente delle soluzioni basate sulla copertura.

L'algoritmo è esattamente lo stesso dell'originale con un codice leggermente inferiore e un numero leggermente maggiore di campioni. È quindi coerente se non più dell'algoritmo basato sulla copertura. Lo sappiamo perché utilizziamo tali metodi da secoli in quasi tutti gli altri campi di elaborazione del segnale e nelle schede grafiche.

Quindi questo metodo ha uno svantaggio? Bene, è un po 'più lento se si vuole solo fare una supposizione ingenuo. In teoria ha un comportamento asintotico più veloce rispetto al rasterizzatore di copertura, un po 'come un raytracer è ancora solo alla pari in scene tipiche. Inoltre potrebbe rendere più doloroso implementare l'uso degli effetti basati sulla convoluzione.

    
posta joojaa 26.09.2016 - 15:42
fonte

2 risposte

6

Il supercampionamento, una volta eseguito in modo ingenuo, è dispendioso dal punto di vista computazionale, dal momento che se si utilizza ad esempio metà della dimensione dei pixel del display, sono necessari quattro volte la memoria e la larghezza della banda. Wikipedia menziona questo e indica anche il supersampling adattivo come possibile soluzione. Ma questo inizia a rendere l'algoritmo molto più sofisticato, complesso e difficile da implementare.

E immagino che questa sia la ragione per cui stai cercando: se vuoi un algoritmo che non ha bisogno di molta più memoria e tempo di esecuzione, le cose stanno diventando molto più complicate rispetto all'ingenuo approccio alla "trasparenza".

    
risposta data 28.09.2016 - 08:58
fonte
6

Il supersampling non risolverà il problema in generale: lo renderà meno evidente. Con i pixel della metà della dimensione, il problema sarà mezzo evidente ma non andrà via.

Il punto di architettura dietro questi progetti è che vogliamo che il comando "render triangle ABC" abbia un significato definito. Non vogliamo che sia ambiguo se non considerato come parte di una collezione di comandi di disegno - ad esempio, avendo un significato quando "render triangle BCD" è anche nella collezione (con lo stesso o un colore diverso) e un altro significato quando non lo è.

Considerando, per esempio, un migliaio di triangoli, anche trovare tutti i triangoli che condividono un lato o parte di un lato con ABC è computazionalmente pesante (ricordando che deve essere rifatto mille volte). Ci sono anche molti altri problemi pratici: in particolare che tutte le richieste di rendering originali devono essere mantenute in giro, anche se sono state disegnate molto tempo fa, nel caso in cui debbano essere riesaminate a causa di una nuova richiesta aggiuntiva.

La linea di fondo è che una soluzione perfettamente coerente non è praticabile. Rimane la domanda: dovremmo cercare di migliorare la situazione attuale quando possiamo? In generale, la risposta a questa domanda è No. Un'implementazione perfettamente coerente di un modello è sempre migliore, anche se il modello stesso presenta i limiti che hai illustrato. L'alternativa sarebbe un'implementazione che a volte fa meglio e altre volte no, senza che il programmatore possa sapere quale di questi due si terrà in un caso particolare. Inoltre, può saltare da "fa meglio" a "non fa meglio" come risultato di piccole modifiche apportate dal programmatore - o anche come risultato di quelle al di fuori del controllo del programmatore. La prevedibilità, in un contesto di programmazione, è di gran lunga migliore della correttezza occasionale.

    
risposta data 26.09.2016 - 21:09
fonte

Leggi altre domande sui tag