Min Raytracer kan nu rendere med Global Illumination :)

[ZeroHero]

Hejsa,

Saa er jeg kommet saa langt med min raytracer at jeg har implementeret Global Illumination. Jeg anvender teknikken Ambient Occlusion. Jeg har renderet et billede saa I kan se hvordan det ser ud. Jeg syntes helt klart at det giver et mere realistisk rendering men syntes stadig ikke det ser ud som, hvis jeg brugte et kommerciel renderer som eksempelvis Brazil. Der er mange parametre som kan tweakes og aendres ved saa det kan vaere at det blot er et spoergsmaal om min kunsteriske evne der halter lidt. Jeg har noteret mig at Ambient Occlusion giver meget "Noise", muligvis fordi den bruger tilfaeldige rays. Det vil sige at jeg skal bruge mange rays for at faa et forholdvis "rent" billede. Jo, flere rays/samples jeg bruger desto laengere bliver renderings tiden. Jeg syntes ikke rigtigt der er nogle aabenlyse optimerings metoder tilgaengelig. Min raytracer er allerede optimeret med octrees/voxels. Jeg har brugt: "A Fast Voxel Traversal Algorithm for Ray Tracing" af John Amanatides og Andrew Woo for at optimere min raytracer. Naar jeg slaar Ambient Occlusion fra gaar det da ogsaa ret hurtigt. Jeg syntes bare at jeg har laest at Ambient Occlusion burde vaere hurtig, men det kan ogsaa vaere at den er hurtig i forhold til andre Global Illumination algoritmer saa som Photon Mapping.

[thpgames]

Jeg savner lidt textur i modellen. Jeg vil tro at det er light-setting der primært skal justeres (area light &c.), nu er AO er jo heller ikke rigtig GI...
Hvilken renderer er det du bruger ?
Cheers !

[ZeroHero]

Jeg har bevidst ikke tilfoejet tekstur for lettere at kunne se shadingen. Saa vidt jeg har laest mig frem til kan Ambient Occlusion sagtens forsvares at blive sat under kategorien: Global Illumination. Den er ikke saa praecis som saa mange andre algoritmer men det er Global Illumination den repraesentere. Jeg bruger en renderer som jeg selv har skrevet.

[Tabu]

Nu ved jeg ikke meget om kodning.. men bare for at stille min nysgerrighed... er det realtime.. eller pre-renderet?
Fedt projekt i hvert tilfælde.. men realtime Ambient Occlution.. "Coolness factor * 1000"

[ZeroHero]

I foerste omgang har jeg implementeret min raytracer til pre-/offline rendering. Jeg haaber paa at kunne optimere mine algoritmer saa meget at jeg kan opnaa real-time (real tid) rendering. I gaar aftes fik jeg leget lidt med parametrene og nu faar jeg det resultat jeg havde soegt efter. Jeg vil uploade resultaterne senere i dag.

[Gorm]

Øv altså, der er slet ikke nok hardcore nørder på dette forum..

Men lad mig prøve så godt jeg kan, jeg har nemlig lavet en del en GI og photon mapping implementationer i tidernes morgen..

Så du har helt ret, støjen kommer fra den totalt tilfældig sampling a hemispheren. Dvs at du i øjeblikket nok i øjeblikket bruger en uniform fordeling som din fordelingsfunktion (dvs den måde du sampler hemispheren på). En måde at få mindre støj på, med færre rays, og derfor også en meget hurtigere hastighed er at finde en bedre måde at sample hemispheren på. En typisk måde et at inddele din hemisphere i et mindre antal patches, og så skyde en ray ud i en tilfælde retning indenfor det patch. Altså noget lignende nedenstående når du laver din final gathering/ambient occlusion beregning.

Code: Select all

for( float phi =0 ; phi < PI/2 ; phi+=deltaPhi)
{
  for( float theta = 0 ; theta < 2*PI ; theta += deltaTheta)
  {
     float randomPhiDirection = random angle between phi and phi+deltaPhi;
     float randomThetaDirection = random angle between theta and theta+deltaTheta
     Vector n = make normalized vector from spherical vector( randomPhiDirection, randomThetaDirection);
     Shoot ray in direction n
  }
}

deltaPhi og deltaTheta afhænger af bla hvor mange patches du vil inddele din hemisphere i. Som en start kan du nok sige at:

Code: Select all

const float deltaPhi = (PI/2) / (sqrt(Number of rays to shoot out));
const float deltaTheta = (2PI) / ((sqrt(Number of rays to shoot  out));

Dette er bare from-the-top-of-my-head så det er muligt at jeg har byttet rundt på theta og phi, m.m. Grunden til at man tager en tilfældig ray indenfor hvert patch, er at du ellers vil kunne se en grid-lignende aliasing.

Andre optimeringer er ting som aldrig bruge new og delete mens din algoritme kører; lægge dit octree i en flad array af strukturer istedet for pointere, osv. Med ting som raytracing, hvor hukommelsen bliver vandret så enormt meget og tilfældigt, giver det langt mere end man skulle tro at undgå pointere. Ved at imitere træer ved smart indexering i en flad array er du sikker på dine datastrukturer er så cache venlige som muligt.

Du kan måske også med fordel implementere Irradiance Caching og endo Irradiance Gradients (søg på Google) for din algoritme. Den basale ide er at måle ændringen i belysning og så kun beregne en ny værdi, hvis det ikke giver mening at interpolere imellem cachede naboværdier. Det svære er så at finde ud af hvornår det giver mening

Håber nogle af disse ideer hjælper

PS. Hvis du har brug det fandt jeg lige en god formel om spheriske coordinater på Wikipedia

[ZeroHero]

Vil det sige jeg er en "hardcore Noerd"? Mange tak for dine tips om optimereing. Jeg bruger faktisk pointers i stedet for indexering. Haaber jeg vil kunne lave det om til indexering i loebet af weekenden. Jeg er ikke helt med paa at indele hemispheren i patches. Jeg havde en lille forestilling om at jeg muligvis kunne lave en fast antal samples/rays for en sphere og gruppere/indexering dem, saaledes at jeg vil finde den sample/ray der ligger taettest paa normalen og dermed kunne finde en tilhoerende gruppe smples der til sammen vil udgoer en hemisphere. Problemet er selvfoelgelig at jeg skal igennem alle rays i spheren og finde dot produktet mellem normalen og de forskellige samples/rays for at finde den naermest liggende sample/ray. Jeg er bange for at den process vil tage alt for lang tid. Jeg har ogsaa leget med idéen om at lave finde en roterings matrix ved at antage normalen som en retnings vektor. Dermed ville jeg kunne multiplicere min matrix med min hemisphere. Men igen saa jeg ved ikke om dette vil tage laengere tid end bare at finde nogle tilfaeldige samples/rays.

[Gorm]

Du kan jo forudberegne din rotations matrix ud fra normalen og en (gættet) orientering (up vector). Så det er bare en matrix multiplication pr ray, hvilket ikke skulle koste dig så meget.

En anden optimering, som jeg tænker du måske heller ikke har lavet, er at istedet for at transformere alle vertices fra et objekt ind i world (ray) space, så kan du transformere din ray ind i objekt space. På den måde kan du fjerne en del matrix multiplikationer fra din indre løkke.
Altså

Code: Select all

Matrix & localToWorldMatrix = this->GetObjectWorldMatrix();
for( int i = 0 ; i < numTriangles ; i++ )
{
  Vertex localVertex0;
  Vertex localVertex1;
  Vertex localVertex2;
  GetTriangle(i, localVertex0, localVertex1, localVertex2);
  Vertex worldVertex0 = Matrix::Multiply(localToWorldMatrix, localVertex0);
  Vertex worldVertex1 = Matrix::Multiply(localToWorldMatrix, localVertex1);
  Vertex worldVertex2 = Matrix::Multiply(localToWorldMatrix, localVertex2);
  CalculateIntersection(ray, rayData, worldVertex0, worldVertex1, worldVertex2);
}

kan blive til

Code: Select all

Matrix & localToWorldMatrix = this->GetObjectWorldMatrix();
Matrix & worldToLocalMatrix = localToWorldMatrix.Invert();
Ray localRay = Matrix::Multiply(worldToLocalMatrix, ray);

for( int i = 0 ; i < numTriangles ; i++ )
{
  Vertex localVertex0;
  Vertex localVertex1;
  Vertex localVertex2;
  GetTriangle(i, localVertex0, localVertex1, localVertex2);
  CalculateIntersection(localRay, rayData, localVertex0, localVertex1, localVertex2);
}

Håber det gav mening. Du kan selvfølgelige også flytte erklæringerne i ovenstående ud af den indre løkke, så de ikke bliver allokeret på stacken hver gang i bliver talt op.

[ZeroHero]

Hej Gorm, jeg har implementeret min octree i en lang array og i stedet for pointers til min array bruger jeg index. Det hele bliver renderet som det skal men der er kun en lille hage. Renderingstiden er nu foroeget med dobbelt saa lang tid som foer. Jeg har vaeret i gennem min kode flere gange for at se om jeg har lavet noget dumt men det ser ikke saadan ud. Jeg kan sagtens se at i teorien burde det gaa hurtigere ved at have min octree i en lang array men af en eller anden grund ser det ud som om at mine pointers gaar hurtigere.

Noget andet jeg har taenkt paa, er, at naar jeg finder tilfaeldige rays til min hemisphere, burde jeg finde en maksimum afstand mellem de fundne rays? Hvis nu jeg havde en maksimum afstand maakse jeg ville faa en mere jaevn hemisphere og dermed mindre "noise"?

Jeg vil proeve at implementere noget color-bleeding. Jeg har laest mig frem til at Ambient Occlusion kan udvides med denne "feature" uden nogen "performance" udgift! Undskyld de mange engelske udtryk! Men jeg haaber paa at kunne faa tid til at implementere photon mapping paa et tidspunkt. Naar jeg kommer saa langt kan det maaske vaere jeg kunne faa en hjaelpende haand fra dig. Jeg fryter lidt at denne teknik er langt mere kompleks og svaere at implementere. Har du evt. nogle gode guides og introduktion til at implementere Photon mapping med en ray tracer? Jeg har selv fundet en del pdf filer der omhandler photon mapping men der er ikke meget omkring selve implementeringen.

[ZeroHero]

Her er en lille opdatering.
Foerste billede er en lille skib og den sidste billede er en rendering af den samme model som vist foer men denne gang bruger jeg en Blinn shading og lader lyskilderne kaste skygger. Til alle renderinger bruger jeg en 1024 samples for min hemisphere.

[Gorm]

Hej Gorm, jeg har implementeret min octree i en lang array og i stedet for pointers til min array bruger jeg index. Det hele bliver renderet som det skal men der er kun en lille hage. Renderingstiden er nu foroeget med dobbelt saa lang tid som foer. Jeg har vaeret i gennem min kode flere gange for at se om jeg har lavet noget dumt men det ser ikke saadan ud. Jeg kan sagtens se at i teorien burde det gaa hurtigere ved at have min octree i en lang array men af en eller anden grund ser det ud som om at mine pointers gaar hurtigere.

Interessant. Jeg vil ikke afvise at det kan ske, men du er sikker på at der ikke bliver lavet noget copy-by-value nu, hvor du ikke længere bruger pointere? Der er referencer og const referencer over det hele?

[quote="ZeroHero"
Naar jeg kommer saa langt kan det maaske vaere jeg kunne faa en hjaelpende haand fra dig. Jeg fryter lidt at denne teknik er langt mere kompleks og svaere at implementere. Har du evt. nogle gode guides og introduktion til at implementere Photon mapping med en ray tracer? Jeg har selv fundet en del pdf filer der omhandler photon mapping men der er ikke meget omkring selve implementeringen.[/quote]

Sure thing, bare send mig en besked når den tid er. Jeg kan dog sige at Henrik Wann Jensen's bogRealistic Image Synthesis Using Photon Mapping er ret god.

[ZeroHero]

Jeg skaber min octree som jeg har gjort foer:

class Octree
{
Children[8] = pointers til 8 nye Octree klasser.
}

Dernaest laver jeg en lang array af klassen Octree_Element
Denne klasse indeholder kun det jeg skal bruge under renderingen

Octree_Elements[ X ]

Nu laver jeg mine voxels som indeholder indexs.

unsigned int Voxels[ X * Y * Z ]

Naar jeg "Traverse" gennem mine voxels vil jeg saa faa en index fra arrayen Voxels og dernaest bruge denne index i min array af Octree_Elements.

Er det ikke saadan noget lign. du havde forestillet dig jeg skulle goere? eller er der noget jeg burde goere anderledes?

[Gorm]

Jeg tænkte nu på om det kunne lade sig gøre for dit octree. Lad os for nemhedens skyld tage et binært træ som eksempel:

Code: Select all

struct TreeNode
{
  TreeNodeElements * elements[];
};

Selve træet ser så ud som:

Code: Select all

class Tree
{
   TreeNode nodes[2^depth-1];
};

Root noden har så index 0, dens børn har index 1 og 2, deres børn har index 3 og 4 (for parent med index 1) samt 5 og 6 (for parent med index 2), osv. Hvis du allerede har dit træ, som en array er det endda nogenlunde ligetil at lave din algoritme stack-baseret istedet for at kalde via rekursion. Dette burde også give dig nogle cpu cycles.

Hagen ved ovenstående metode er at den bruger mindst plads hvis dit træ er balanceret. Når du kommer til din photon mapper og skal lave et kd-træ til at søge efter fotoner, er der nogle gode hints her .

Octrees er der dog notorisk ubalancerede, og det som kan give dig mest performance her er typisk at finde ud at hvor dybt det kan betale sig at have et træ. Udover at subdivide indtil din geometry ikke længere passer i en bounding box, så bør du også have en minimumsgrænse, så hvis du har mindre end X stykker geometry (el. polygoner alt efter hvordan du gør det) tilbage så subdivider du ikke mere, også selvom din nuværende node er mange gange større end der er behov for..

Generelt er min påstand at Octrees er gode til realtime ting, da man her typisk vil sige "tegn de X objekter i den her node også selvom de er ude for frustum eller bagved andet geometry". Grunden til dette, er at det typisk er hurtigere at tegne det alligevel, end at teste for om det kan betale sig. For raytracing er jeg dog ikke overbevist om at octrees er dit bedste valg. Her er dine kriterier at holde din træstruktur så balanceret og lav (dvs ikke-dyb) som mulig, så din søgning bliver så hurtig som overhovedet muligt. Hvis du har en statisk scene kan det måske endda betale sig at tage al din geometry, skille det af i enkelte polygoner, smide polygonerne ind i en kæmpe usorteret polygon suppe, og derefter sorterer alle polygoner ind i et bsp træ el. lign.

[ZeroHero]

Jeg kan sagtens foelge dig med at octree'en ikke er saerlig balanceret. Hvis jeg KUN bruger min octree til renderingen vil det gaa ret langsomt, netop fordi den er "dyb" - altsaa er opbygget af mange nodes. Men det er mine uniform voxels som optimerere hele renderingen og dermed reducerere renderings tiden gevaldigt. Jeg valgte octree'en fordi den officielle artikel "A Fast Voxel Traversal Algorithm for Ray Tracing" af John Amanatides og Andrew Woo bruger octree'en som basis trae til deres voxels. Dermed slipper jeg ogsaa for at splitte geometrien op, hvilket vil vaere en langsomlig process naar jeg vil til at bruge animerede og dynamiske scener. Jeg ved ikke om en KD trae ville kunne bruges til mine voxels - jeg tvivler dog da det skal vaere uniformet traestruktur - og det er octree'en jo.