[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
Avevo anche pensato di farci un contest ma mi sembrava scorretto

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
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

[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"

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