[CUDA]Rasterizzazione parallela?

[Tommo]

Salve,
sono da un pò con le prese di questo problema, ma non mi viene un'idea decente a pagarla oro :D
Avevo anche pensato di farci un contest ma mi sembrava scorretto :asd:

Comunque, in pratica sto cercando di realizzare un rasterizer con CUDA... tuttavia mi son reso conto che la rasterizzazione è un problema inerentemente non-GPU-parallelo se si utilizza un algoritmo semplice, perchè ogni triangolo può contenere N pixels, da 0 fino anche a tutto quanto lo schermo.
Dato che il tallone d'achille del GPGPU è l'accesso alla memoria, un ipotetico stream che deve accedere a 1900*1200 pixels può bloccare la scheda per qualche secondo :asd:
Ora per renderizzare attorno a quella risoluzione il famoso coniglio da 35.000 poly (in wireframe) ci metto 0,006 microsecondi, non esattamente performante (molto ottimisticamente 170 fps, solo lui)

Quindi dovrei trovare un algoritmo che:
-possa essere spezzato in n < 1.000.000 threads
-abbia un branching predicibile e coerente, cioè che tutti i thread si eseguono più o meno uguale
-acceda ad elementi adiacenti in memoria, in numero costante, e magari il meno possibile.
-faccia uso della cache locale

Avevo in mente qualche organizzazione spaziale a tree + raycasting, ma in sostanza non ho idea di come farlo...
spero che qualche luminare mi illumini :D

[gugoXX]

Non sono affatto un luminare di informatica grafica, ma da che mi ricordi io il ray-tracing e' estremamente parallelizzabile, nel senso che per sua definizione il colore di ciascun pixel e' trattato indipendentemente dagli altri.
Cio' significa che se hai 2 milioni di pixel, allora potrai effettuare un parallelismo pari a 2 milioni.

Tutto sta nello scrivere l'algoritmo del pixel generico in modo efficiente.
Da che mi risulti, oggi siamo ancora lontani dal real-time.

[Tommo]

Il fatto è che come si sta discutendo nel thread poco sopra, il modello differisce anche tanto dall'esecuzione...
per questo ho parlato di "cuda-parallelo" e non "parallelo" :D

Cioè, mentre è vero che la rasterizzazione o il raytracing in sè sarebbero dei problemi super-paralleli, cuda (e la struttura delle gpu in genere) aggiunge dei limiti pesanti che rendono questi problemi decisamente inadatti ad essere mappati:
-accessi coerenti, in numero costante e in potenze di 2 (16,13,64 bits) in memoria
-esecuzione simultanea (ogni if che prende un diverso branch diventa seriale)
è evidente che sono condizioni estranee al parallelismo in sè, ma sono rese necessarie dai limiti tecnici...
e se non si rispettano si cade subito nel worst-case.

anche il raytracing ha dei raggi che devono iterare un intero tree di n strutture, e poi generare m raggi di radiosity... il che rende impossibile prevedere
1) quali path prenderà l'esecuzione di ogni raggio
2) come e quando accederà alla memoria
Portando le performance al livello di qualsiasi CPU.
Infatti so bene che il raytracing non gira in tempo reale, e non mi piace nemmeno come tecnica... non per niente io voglio usare la rasterizzazione :D