Modo discussione | Modo lineare

MarkSkyzoid · 07-09-2011 11:43

Ciao ragazzi!
Come detto in un altro post, sto sviluppando un piccolo motore di rendering via software.
E' da un paio di giorni che sto impazzendo con il rendering dei triangoli...finchè c'era solo wireframe era tutto ok, ma ora che voglio implementare il filling e, più in là, lo shading sta diventando un casino.
Comunque ieri notte, dopo tante bestemmie, sono riuscito a realizzare un piccolo algoritmo che (almeno in alcuni casi sembra funzionare).
Lo posto di seguito:
http://pastebin.com/H80znK4F

Come codice è sicuramente buggato e lento, quindi ottimizzazioni sono bene accolte.
Inoltre se voglio disegnare solo un poligono lo disegna bene, ma se l'oggetto ha più poligoni(per es. nelle primitive ho implementato un cubo), crea degli artefatti visivi poco carini.
Le cause secondo me possono essere queste:

L'algoritmo fa schifo ed è totalmente sbagliato
I vertici devono essere ordinati in ordine antiorario
Manca il clipping(che non ho ancora implementato)

Se c'è bisogno poi posto immagini e video di quello che succede al mio cubo...

Inoltre il clipping in che fase della pipeline è presente?
Per ora la mia pipeline è questa:

Trasformazione dei vertici( object space -> world space -> camera space)
Proiezione dei vertici sul piano di visualizzazione(salvo anche la coordinata z nei vertici 2D, per poi lavorare allo zbuffering)
Scan conversion dei triangoli e disegno

Spero di ricevere tante tante risposte utili Zizi

XD
Grazie per l'aiuto a chiunque risponderà Sorriso

Ciao!

TheCrib · 07-09-2011 13:44

(07-09-2011 11:43)MarkSkyzoid ha scritto: crea degli artefatti visivi poco carini.

Frase chiave, che dice tutto e niente ;)

Cosi' ad occhio, direi che non c'e' una quantizzazione (float -> int) ben definita.. cosa importante per non avere gaps tra poligoni ed avere eventuale precisione sub-pixel.

La PolyScan che ho menzionato nell'altro thread, si impegna molto a suon di floor() e ceil() per fare una conversione consistente.. ma c'e' piu' di un modo (e magari all'inizio puoi evitare di pensare al sub-pixel).

Conviene magari consultare anche un libro.. per la rasterizzazione a me ha aiutato molto Advanced Animation and Rendering Techniques.
Ma sicuramente c'e' qualcosa di piu' aggiornato (magari Prof. Zambetta sapra' consigliare testi piu' aggiornati 8)

Riguardo al clipping.. consiglio clipping in coordinate omogenee.. e poi eventuale test addizionale per scan-line, quando rasterizzi il poligono.. questo perche' da coordinate omogenee al frame buffer (window space) potrebbero esserci delle imprecisioni.. e se si sgarra di un pixel e' un casino.

In ogni caso il clipping e' una questione aperta.. dal punto di vista di perfomance ci sono tante considerazioni che si possono fare... non a caso anche le prime GPU avevano dei comportamenti strani al riguardo.

Buona rasterizzazione !

P.S. Il background della mia pagina di Twitter e' un pezzo di una routine per il calcolo di una slope per un mio vecchio poly rasterizer 8P

MarkSkyzoid · 07-09-2011 14:45

Grazie della risposta Davide Smile

Forse il problema giace, come hai detto tu, nel passaggio da float a int.
Anzitutto premetto che allegro gestisce le coordinate dello schermo come interi. Il problema potrebbe essere nel fatto che nella proiezione dei punti converto i float in int, quindi le coordinate di un Vertex2f sono int e non float come il nome della struttura suggerisce.
Ora faccio una prova su questo e vi dico Sorriso

v71 · 07-09-2011 15:02

Codice:

void DrawTriangle( const CVec3f &v1, const CVec3f &v2, 

                         const CVec3f &v3)

{

    float y1 = v1.y;

    float y2 = v2.y;

    float y3 = v3.y;

    float x1 = v1.x;

    float x2 = v2.x;

    float x3 = v3.x;

    // Bounding box del trianglolo

    int minx = (int)min(x1, x2, x3);

    int maxx = (int)max(x1, x2, x3);

    int miny = (int)min(y1, y2, y3);

    int maxy = (int)max(y1, y2, y3);

    // indirizzo di partenza 

    (unsigned char*&)Buffer += miny * stride;

    // Itera per tutto il bounding box

    // del triangolo verificando che 

    // il punto corrente sia al di

    //  là del semispazio definito

    // dall'intersezione dei lati

    // del triangolo 

    int x,y;

    for( y = miny; y < maxy; y++)

    {

        for( x = minx; x < maxx; x++)

        {

            // se la condizione e' vera il punto si  trova all'interno

            // del triangolo

            if((x1 - x2) * (y - y1) - (y1 - y2) * (x - x1) > 0 &&

            << (x2 - x3) * (y - y2) - (y2 - y3) * (x - x2) > 0 &&

            << (x3 - x1) * (y - y3) - (y3 - y1) * (x - x3) > 0)

            {

                // scrivo un byte 'bianco'

                Buffer[x] = 255; 

            }

        }

        // avanza di una scanline verticale

        ( unsigned char*&)Buffer += stride;

    }

}

Questa funzione fa parte di un mio vecchio rasterizzatore di triangoli.
Prima di essere scarnificato, ci tengo a sottolineare che la funzione
NON e' ottimizzata per la velocità ma per la comprensione della
teoria della rasterizzazione per semispazi.
La teoria e' semplice , se un punto si trova al di la' di ogni semispazio
definito dai lati del triangolo allora il punto e' all'interno del triangolo
e viene scritto nel buffer lineare che deve essere allocato in precedenza
lo stride e' la lunghezza orizzontale del buffer ad esempio un buffer di 800x600 ha uno stride di 800
CVec3f puo' essere sostitutio da qualunque struct o classe che abbia come membri x,y,z le funzioni min e max trovano rispettivamente il minimo ed il massimo fra 3 vertici.

TheCrib · 07-09-2011 15:13

In pratica, dovresti gestire tu la conversione ad int e stabilire una policy.

Ad esempio rasterizzare una span con la x1 non-inclusiva (come fai ora), in modo da evitare overdraw dell'edge in caso di altri poligoni in una mesh.

Un problema che gia' vedo e' che quando x0 >= x1 fai il loop al contrario includendo il pixel a destra (x0, in quel caso).. e questo crea inconsistenze.

In questo caso ti consiglio di semplificare con tipo:

Codice:

int xl, xr;

if (x0 < x1) {  xl = x0;  xr = x1; } else

             {  xl = x1;  xr = x0; }

for(int x = xl; x < xr; ++x)

    putpixel(buf, x, y, makecol(0, 255, 0));

..cosi' gia' hai la consistenza di dire "non includo l'ultimo pixel a destra", ed hai un solo loop.

Altra cosa anche per:

Codice:

for(int y = verArray[1].y; y <= verArray[2].y; ++y)

..forse dovrebbe essere < ?

Sono questo tipo di ragionamenti che complicano il tutto.. ma servono per evitare artefatti vari.

(07-09-2011 14:45)MarkSkyzoid ha scritto: Il problema potrebbe essere nel fatto che nella proiezione dei punti converto i float in int, quindi le coordinate di un Vertex2f sono int e non float come il nome della struttura suggerisce.

Quello va solo ad influire nell'eventuale mancanza di precisione sub-pixel, ma non dovrebbe dare nessun problema di artefatti.. e' una cosa a parte.

(07-09-2011 15:02)v71 ha scritto:

Codice:

if((x1 - x2) * (y - y1) - (y1 - y2) * (x - x1) > 0 && << (x2 - x3) * (y - y2) - (y2 - y3) * (x - x2) > 0 && << (x3 - x1) * (y - y3) - (y3 - y1) * (x - x3) > 0)

<< sono un errore immagino ?

Questa tecnica sembrerebbe lenta 8) ..ma e' tutto sommato piu' vicino a quello che fanno le GPU.
Rasterizzare poligoni grandi con la CPU e' piu' veloce con scanlines tra i bordi del poligono.. ma in pratica in hardware e per poligoni piccoli (come spesso sono, o ridotte da una fase di tiling in hardware) e' piu' efficente lavorare con le equazioni della linea.
Sfrutta la forza bruta ed e' piu' facile da parallelizzare.

MarkSkyzoid · 07-09-2011 15:34

Grazie ad entrambi Smile

Davide ho sfruttato quello che mi hai detto è molte cose le ho risolte...
ma guarda questo video di un quadrato renderizzato che faccio ruotare:

il quadrato è composto da due triangoli e da alcune angolazioni se ne vede solo uno...
è un problema di clipping?

TheCrib · 07-09-2011 16:07

(07-09-2011 15:34)MarkSkyzoid ha scritto: il quadrato è composto da due triangoli e da alcune angolazioni se ne vede solo uno...
è un problema di clipping?

Non di clipping, perche' il clipping non c'e'.. forse intendi di backface-culling (?), ma la tua routine non dovrebbe essere affetta dall'ordine (infatti per ogni scanline verifichi se parte da destra o da sinistra).

Potrebbe essere qualcosa anteriore.. verifica che effettivamente ci sono 2 chiamate alla routine di rasterizzazione.. e printeffa() i valori dei vertici per verificare che siano credibili.

Magari c'e' un bug nella rasterizzazione.. e li' potrebbe convenirti andarci di debugger 8)

v71 · 07-09-2011 17:30

Si, TheCrib e' un errore, non capisco perche' quando inserisco il tag per il codice a volte mi sballa qualcosa, uso il google chrome potrebbe essere questo ?
E comunque hai ragione e' quello che fanno le gpu, l'algoritmo per le gpu sfrutta il tiling dei quadrati e poi e' tutto in parallelo.
Riguardo il tuo problema , non e' il clipping, prova a controllare se nella tua trasformata prospettica il denominatore non diventa zero.
Se poi stai effetuando un backface culling, assicurati di calcolare bene il vettore normale alla superficie e verifica che il dot fra l'osservatore e la normale sia giusto.

MarkSkyzoid · 07-09-2011 17:43

Non diventa zero ho messo questo check

Codice:

if(Polygon::aVertices[vNum]->z == 0)

            Polygon::aVertices[vNum]->z = 0.1f;

Non riesco proprio a capire dove sia il problema...

v71 · 07-09-2011 17:56

Potrebbe essere in 2 punti, nel calcolo delle normali, oppure nell'algoritmo di scanline, ma sembra strano perche' scompare del tutto.
Secondo me il loop della scanline si inverte , sembra che non venga eseguito, controlla il loop per le linee verticali

MarkSkyzoid · 07-09-2011 18:10

Il calcolo delle normali non lo faccio, in quanto per ora non ne ho bisogno...
Ora mi faccio qualche ora di debug sulle scanline...però da quanto ho visto prima viene eseguito...

theGiallo · 07-09-2011 18:13

ricorda il problema della precisione che si ha col raytracing. da qualche parte fai dei confronti con lo zero? scusa ma non ho tempo di guardare il codice Smile

p.s.: perchè codare un renderer a rasterizzazione, quando c'è la GPU, e non a raytracing?

MarkSkyzoid · 07-09-2011 18:36

Per capire come funziona il rendering senza avere la pappa pronta Smile

TheCrib · 07-09-2011 18:41

(07-09-2011 18:36)MarkSkyzoid ha scritto: Per capire come funziona il rendering senza avere la pappa pronta

YEAHHH !!!
E sono cose che torneranno molto utili ...direttamente ed indirettamente.

theGiallo · 07-09-2011 18:46

ah, ok, allora ha senso. lo ho fatto anche io a pezzi nel corso di grafica che ho fatto a Valencia.
Con questo libro.

Modo discussione \| Modo lineare [Software Rendering] Scan Conversion dei triangoli e Clipping
Autore	Messaggio