Riempimento di un poligono: prestazioni della regola di carica contro la regola dispari

Question

Per un poligono complesso (es .: autointersezione) la scelta tra le regole di riempimento Avvolgimento o Pari-Dispari fa la differenza nel modo in cui il poligono viene riempito.

Ma per i poligoni non intersecanti c'è qualche differenza di prestazioni tra le regole di riempimento Avvolgimento o Dispari pari. Capisco che sarebbe specifico per l'impianto ma quale degli algoritmi è più efficace per i poligoni non complessi.

Una domanda di follow-up qual è la complessità (ovvero O (cosa?)) di ciascuno di questi algoritmi. Voglio sapere se vale la pena sbarazzarsi di alcuni punti del poligono (principalmente duplicati o quelli che si trovano sulla stessa linea) per migliorare le prestazioni.

PS: se è importante, sto usando xlib

PPS: posso confermare che il problema non è legato all'hardware poiché l'utilizzo di una scheda grafica diversa non modifica le prestazioni

Answer 1

Oggi, la maggior parte delle implementazioni di X utilizza l'hardware 2D della scheda grafica, quindi la differenza tra i due è probabilmente trascurabile.

Poiché si tratta di una domanda relativa alle prestazioni, le probabilità che la mia risposta sia corretta sono circa del 10%, tuttavia (con le prestazioni hai una probabilità del 90% di sbagliarsi senza misurare). Se vuoi essere sicuro, non c'è altro che scrivere un piccolo test delle prestazioni e vedere di persona.

x11perf potrebbe aiutare.

Puoi trovare l'algoritmo per il poligono indipendente dall'hardware qui: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c?rev=HEAD

Esiste una seconda versione che è molto più veloce se sei sicuro che il tuo poligono sia convesso: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c?rev=HEAD

La seconda versione ignora la regola di riempimento (che non si applica ai poligoni convessi). Commenti sull'algoritmo: http: // cvsweb .xfree86.org / CVSweb / XC / programmi / Xserver / mi / mipoly.h? rev = HEAD

L'algoritmo funziona in questo modo: calcola il contorno, quindi crea oggetti span (che sono solo una coordinata x, y e una larghezza) tra i bordi. Se si utilizza la regola EvenOdd, verranno creati più oggetti span in caso di intersezioni. Se non ce ne sono (ad esempio, quando il poligono è convesso), allora non noterai una differenza di runtime perché la regola di riempimento equivale a una variabile booleana nel ciclo principale di miFillPolygon (cioè la maggior parte del codice è uguale per entrambi regole di riempimento).

Cercare di migliorare le prestazioni ottimizzando il contorno del poligono non ti acquisterà molto nel caso comune, tranne se sai che i tuoi poligoni contengono un numero molto alto di punti non necessari (diciamo, puoi sbarazzarti della metà del numero di punti nel caso comune). Ottimizzare un poligono con & Lt; 10 punti probabilmente costeranno più di quanto raggiungano.

Ma ancora: tutto si basa sul sentimento intestinale o sulla conoscenza di un vecchio articolo. Se vuoi sapere se i bug nel driver della tua scheda gfx si rovinano con il risultato, devi sporcarti le mani e scrivere un test che misura quanto tempo impiega ogni caso. Non c'è modo di dire il runtime di alcun algoritmo complesso semplicemente osservandolo a causa di fattori esterni: velocità delle routine di allocazione della memoria, quantità di memoria libera (quando inizia lo scambio), numero di core della CPU che è possibile utilizzare, quanti altri processi ti combatteranno per la CPU, ritaglio del poligono finale sullo schermo, dettagli di implementazione e ottimizzazioni, bug, ecc.