RealTime RayTracing

Elkészítettem a programom SSE változatát, ahol low-detail scene esetében:
(2 ray/pixel)
(AmdXP 2400+)

320x200 - 20 FPS
640x480 - 05 FPS

Az SSE segítségével négy sugarat követek egyszerre, mivel négy lebegőpontos műveletet tudok egyszerre elvégeztetni.

Az SSE2 utasításkészlet segítségével 8 db
16 bites integer művelet hajtható végre egyszerre. Lehet e 16 biten kellő pontossággal ábrázolni egy ordinátát?

A 16 bites pontosság elégséges a befoglaló dobozok metszésponttesztjének.
Megfelel e háromszög metszésponttesztjéhez?

Melyik lehet a leghatékonyabb algoritmus háromszögek metszésére?

Szerintem a Plucker - koordinátás, ahol a
metszéspontszámítás így néz ki:

for (háromszöglista) {

if (DOT_PRODUCT6(edge0,ray)<0.0f) continue;
if (DOT_PRODUCT6(edge1,ray)<0.0f) continue;
if (DOT_PRODUCT6(edge2,ray)<0.0f) continue;

van metszéspont, határozzuk meg...
}

edge: A háromszög élei Plucker koordinátarendszerben
ray: A sugár egyenese Plucker koord. rendsz

a legmegfelelobb adatszerkezetek kivalasztasahoz ajanlom a kovetkezot:

<a href="http://www.sgi.com/tech/stl/table_of_contents.html">STL</a>

Tetszik ez a megoldas.

A memoriaval azonban jocskan lehet takarekosabban banni, ha dinamikus adatszerkezetekkel dolgozol.

A CELL-t peldaul vector<PHOTON>-ra cserelve, az ures cellak csak minimalis memoriat zabalnak:

vector<PHOTON> PhotonMap[SIZE][SIZE][SIZE];

ez uresen maris csak 128 MB, a tobbi a fotonok mennyisegetol fugg.

(Nem tudom az ures vector mennyit foglal, de ha 8-bytenal tobbet akkor kell irni egy sajatot:))

Ha meg igy is tul nagy a pazarlas a sok ures cella miatt, akkor javaslom a kovetkezot:

class POS
{
int x; //0-SIZE-1
int y; //0-SIZE-1
int z; //0-SIZE-1
}

hash_map<POS, vector<PHOTON>>

Ebben az esetben a memoriafogalas mar tenyleg a fotonok szamaval aranyos, mig a cellak elerese meg mindig O(1).

Photon map rendering

A kamera (ha úgy tetszik szem) koordinátarendszerben** vagyunk, ahol a [0,0,1] irányba nézünk. Virtuális világunk rendelkezik egy 2x2-es befoglalódobozzal (min[-1,-1,-1],max[+1,+1,+1]). Ebbe a dobozba illesztünk egy 3D rácsot - ez lesz a photon-map, amely lefedi az egész világot:

struct PHOTON { // 36 byte

float Color[3];
float Position[3];
float Direction[3;]; // A becsapódás iránya - diffuz esetben szükségtelen (radiosity)
};

struct CELL {

PHOTON photon_array[MAX_PHOTONS_PER_CELL];
/* int num_potons; */
};

CELL PhotonMap[SIZE][SIZE][SIZE];

A memóriaigény: (SIZE^3)*MAX_PHOTONS_PER_CELL*36;
pl:

256^3*16*36 = 9 Gb

Ne feledjük, hogy ezt a memóriamennyiséget minden képkocka számításánál nullázni kell.
Minél nagyobb felbontású a photon-map, annál kevesebb foton esik egy cellába.
Minél kisebb felbontású a photon-map, annál több foton kerül egy cellába - így több fotonnal kell foglalkozni a radiancia becslésekor - a becslés tovább tart.

A photon map előnyei:

- geometriától független (akár procedurális geometriát is kezelhetünk, CSG)
- minden fényutat kezel (kausztika, indirekt illumináció)
- fényszóró és fényelnyelő közegek megjelenítése (füst, köd, stb)
- nincs zaj (lásd path tracing), a hiba elmosódás formájában jelentkezik

Hátrány:

Ebben a 3D-tömbös esetben a gigantikus memóriaigény. Egy tömb adatai viszont könnyen elérhetőek. Válasszuk a tömb dimenzióit kettő valamely hatványának...

** A sokszögekkel közelített objektumokat transzformálhatjuk ebbe a koordinátarendszerbe, magasabb rendű felületeknél viszont a sugarat transzformáljuk.

a realtime raytracing hamarosan elérhetövé válik, csak a kérdés az megéri e
minöségi ugrás csak a tükrözödésben és az árnyékokban jelentkezne,mivel nem csalással lennének megoldva
de ahhoz hogy realtime lefusson el lehet felejteni a bezier,nurbs felületeket
marad csak a polygonos megoldás ami khm má elég ocska
amugy a RT algoritmust fel lehet gyorsitani a következö képpen:
elöször a vidkártyával lerendereljük a képet és eztvisszaolvassuk procival
igy az elsö sugarütközéseket könnyedén megkapjuk
utána már csak a tükrözödö felületekröl inditjuk a sugarakat
egy játékban a pontok kb 10-30%-a lehet
tükrös, igy nagyon sok idöt megtakaritunk
a másik gyorsitás: azon tul hogy befoglalo gömböt haználunk minden objectre,vagy részeire
felosztjuk a teret kockákra és tároljuk a kockákban levö objecteket
majd a sugarat ugy számoljuk mintha a kocka egységkocka lenne és a sugár pontjait(kockáit) a halado diferenciák modszerével számoljuk

a legnagyobb problémám a felületek és a sugar döféspontjának a meghatározása
ami egy 3szögnél még nem is bonyolult
de mi van ha én beziert vagy nurbs-ot szeretnék használni, ha valaki tud ezekre gyors algoritmusokat ,megköszönném ha leirná

Hogyan lehet Visual C++ 6.0-ban SSE utasításkészletet használni?

Van esetleg újabb fordító, amely alapból tudja?

ezt meg kell nézni

Ez egy ATI,nem raytrace.

wow

érdemes összehasonlítani hova feljődtek a 'csalások'

ATI demók
real-time raytrace
raytrace
szerintem nem a trace a legélethűbb .

Ja es a hashtablahoz persze csak a photonok szamaval aranyos memoria kell, ezert vetettem fel.

Elorebocstom, Globalis illuminacios temaban nem nagyon vagyok otthon, a photon mappingrol hallottam azert valamicsket.
Szoval miert ne lehetne a kd-fa-t hash-tablaval kivaltani?
A kd-fa logaritmikus eleresu. Mig a hashtabla gyakorlatilag ugyanugy konstans eleresu mint a tomb, legfeljebb a konstans egy kicsit nagyobb.

A hashtabla kulcsa termeszetesen az (x,y,z) valamilyen felbontasban lenne.

Mit gondoltok, melyik globális illuminációs algoritmus lenne a legalkalmasabb arra, hogy a közeljövőben valósidőben fusson?

Szerintem a foton-térkép. Felgyorsulna az eljárás, ha a Kd-fa helyett egy háromdimenziós tömbben tárolnánk a becsapódott fotonokat. Ehhez rengeteg (több gigabyte) memóriára lenne szükség.

egyszeres visszaverodesig mentem el, a visszaverodesnel mar nem vizsgaltam az arnyeksugarakat.
floattal dolgoytam.
Assemblys ciklusmaggal es az SSe-vel csak kezdtem volna dolgozni, amikor meguntam.

Ugy kepzeltem, hogy az assembly kodresz SSE-vel egy 'szamolo masina'-kent mukodott volna, ami egy tombben kapott volna ray tracelesi alapmuveleteket, ezeket batchban vegrehajtotta volna (mindenfele feleteteles vizsgalat nelkul, csak),
majd a foprogram ezzel dolgozott volna.

Foglalkoztam a temaval, sot irtam is real time ray tracert par eve. Ez mar egy 600MB-os PIII-on is majdnem real time volt, egyszeru scene eseten.
A mai procikkal a dolog mukodik.
Olyan komplex scene-k eseten, amilyeneket a jatekokban hasznalnak manapsag, es amiket a mai gyorsitokartyak vigan elbirnak, nem mukdone a real time ray tracing procibol.

A gond az, hogy a real-time ray tracing a kuszobon van, mar megoldhato, de a legnagyobb gond vele az, hogy nem jelent minosegi ugrast.

Ugyanis a visszaverodest tudja az environment mapping. A user semmit nem lat abbol, hogy ez nem igazi ray-tracing.
Elore leszamolt texturakkal trukkozve, nem mozgo objektumok eseten pedig meg a ray-tracinget messze felulmulo shadinget lehet 'behazudni' a rendszerbe, amit a user megintcsak nem lat.
Ha minosegi ugrast szeretnenk, ahhoz nem eleg a real-time ray tracing, ahhoz real-time radiosity, real time global illumination kellene. Ez gyonyoruen nezne ki, de ehhez megnagyobb szamitasi teljesitmeny kell.
Az a baj, hogy a radiosityra is vannak hagyomanyos poligonos megoldasok, amelyek megint nem a sugarkoveteses modszer fele viszik a merleg nyelvet...

En egyebkent befoglalo gombhierarchiaval dolgoztam. Az optimalizalasnal minden negyedik pontot szamoltam rendesen, a kozbulso pontoknal egy csomo vektort atlagoltam, igy a szamitas sokat gyorsult. Akkoriban eleg aktivan ment a egy real-time ray-tracing levelezesi lista, manapsag a forgalma 0.

Tanulsag: a real-time ray-tracing nem jelent minosegi ugrast, a real-time global illumination meg meg nem nagyon megy. Ha hosszu tavon gondolkodunk, en az utobbira tennem a fo hangsulyt.

Nem emlékszem pontosan, valamikor régen, még sok évvel ezelőtt egy számtech kiállításon volt egy masina, amivel 320x200-as felbontásban valós időben raytrace-eltek. Csak annyi volt a trükkje, hogy minden egyes pixelt külön proci számolt ki

A 3D gyorsítók újabb és újabb generációi az egyre nagyobb felbontáson és az egyre nagyobb számú poligonon kívül semmi átütő újdonságot nem tudnak felmutatni.
A vetett árnyékok, a tükröződés vagy a fénytörés megvalósítása nehézkes és erősen korlátozott, illetve csalásokkal (pl environment mapping) valósítható meg.
Egy sugárkövető algoritmus ezeket mind "alapból " tudja. Ez a módszer viszont rendkívül számítás/időigényes. Hogyan lehetséges valósidőben megoldani?

* Kompromisszumok *

- Moderált felbontás
- Egyszerű geometria
- Egy visszaverődésig/törésig követünk
- Indirekt megvilágítás hanyagolása
- Egyszeres pontosságú (float) számábrázolás
- stb

* Optimalizálás *

- A modern CPU-k segítségével egy bizonyos műveletet egyszerre több adaton is végrehajthatunk.
(3DNow!, SSE, SSE2 )

- "Inner-loop" -ok alacsony szintű (assembly) megoldása.

- stb

Magam is kisérletezek ilyen program írásával több-kevesebb sikerrel. Most éppen a sulinetes AthlonXP-re várok, amely elvileg tudja az SSE utasításkészletet. Ez fontos, mivel a műveleteket négyesével csoportosítottam a programomban - ezek az SSE segítségével egy utasítással elvégezhetőek. Jelentős sebességnövekedésre számítok.