Struttura dati/approccio per raytracing efficiente

Question

Sto scrivendo un 3D raytracer come progetto di apprendimento personale (Enlight) e ho riscontrato un problema interessante relativo ai test di intersezione tra un raggio e una scena di oggetti.

La situazione è:

• Ho un certo numero di primitive che i raggi può intersecarsi con (sfere, scatole, aerei, ecc) e gruppi di essi. Collettivamente chiamerò questi oggetti scena.
• Desidero essere in grado di eseguire il rendering degli oggetti primitivi con trasformazioni arbitrarie affini avvolgendoli in un oggetto Transform (importante, questo consentirà di utilizzare più istanze delle stesse primitive in posizioni diverse nella scena poiché i primitivi sono immutabili)
• oggetti Scene possono essere memorizzati in una gerarchia volume di delimitazione (cioè sto facendo partizionamento spaziale)
• miei test intersezione lavorano con Ray oggetti che rappresentano un segmento raggio parziale (iniziare vettore, direzione vettore normalizzato, inizia distanza , distanza finale)

Il problema è che quando un raggio colpisce il riquadro di delimitazione di un oggetto Transform, sembra che l'unico modo per eseguire un test di intersezione con le primitive trasformate contenute sia trasformare lo Ray nello spazio di coordinate trasformate. Questo è abbastanza facile, ma se il raggio non colpisce alcun oggetto trasformato, devo ricorrere allo Ray originale per continuare la traccia. Poiché Transforms può essere annidato, ciò significa che devo mantenere un'intera pila di Ray s per ogni traccia di intersezione che viene eseguita.

Questo è naturalmente all'interno del ciclo interno dell'intera applicazione e del collo di bottiglia principale delle prestazioni. Verrà chiamato milioni di volte al secondo, quindi mi preme minimizzare la complessità/evitare allocazioni di memoria non necessarie.

Esiste un modo intelligente per evitare di dover allocare nuovo Ray s/mantenere uno stack Ray?

O c'è un modo più intelligente di fare tutto questo?

Answer 1

La maggior parte delle volte in raytracing hai qualche (centomila) oggetti e molti altri raggi. Probabilmente milioni di raggi. Stando così le cose, ha senso vedere quale tipo di calcolo si può spendere sugli oggetti per renderlo più veloce/più facile avere i raggi interagire con loro.

Una cache sarà molto utile come suggerito da boyfarrell. Potrebbe avere senso non solo creare le trasformazioni avanti e indietro sugli oggetti che le sposterebbero verso o dal frame globale, ma anche per mantenere una copia dell'oggetto nel frame globale. Rende più costoso creare oggetti o spostarli (perché la trasformazione cambia e quindi le copie globali della cache memorizzate), ma probabilmente è ok.

Se lanci N raggi e hai oggetti M e N >> M, allora è ragionevole pensare che ogni oggetto abbia raggi multipli. Se assumiamo che ogni raggio colpisce un oggetto, allora ogni oggetto ha raggi N/M che lo colpiscono. Ciò significa trasformare i raggi N/M in ciascun oggetto, colpire i test e eventualmente invertirli. O N/M trasforma per oggetto al minimo. Ma se mettiamo in cache l'oggetto trasformato, possiamo eseguire una singola trasformazione per oggetto per raggiungere il frame globale e quindi non abbiamo bisogno di alcun ulteriore. Almeno per i test d'impatto.

Answer 2

Definisci i tuoi primitivi nella loro forma base (scala dell'unità, centrata su 0,0,0, non ruotata) e quindi spostali nella scena utilizzando solo le trasformazioni. Cache il risultato delle trasformazioni complete avanti e indietro in ciascun oggetto. (Non dimenticare i normali vettori, ne avrai bisogno per i riflessi)

Questo ti darà la possibilità di testare il colpo usando la matematica semplificata (invertirai il raggio trasformandolo nello spazio dell'oggetto e il calcolo colpirà con l'oggetto modulo base) e quindi trasformare il punto d'impatto e il possibile vettore di riflessione nello spazio reale usando l'altra trasformazione.

È necessario calcolare le intersezioni con tutti gli oggetti nella scena e selezionare il colpo più vicino all'origine del raggio (ma non in una distanza negativa). Per accelerare ulteriormente, racchiudi più oggetti in "bounding box" che saranno molto semplici da calcolare e passeranno il raggio del mondo reale agli oggetti chiusi se colpiti (ma tutti gli oggetti useranno ancora le loro matrici precalcolate).