3D software rendering med C++

Tags:    c++
Skrevet af Bruger #1474 @ 11.08.2008

Vektor Klasse

3D grafik er baseret på vektor matematik. Hvis du aldrig har arbejdet med dette emne før så fortvivl ikke. Vi vil lave en ganske almindelig vektor klasse, som kan de mest basale funktioner med nogle enkle tilføjelser. I første omgang behøver du ikke at kunne forstå, hvad disse funktioner rent faktisk gør. Først når vi skal til at simulere realistisk lyskilder, vil du få brug for at forstå det.

En geometrisk vektor repræsenterer en retning, men den kan også opfattes som blot et punkt i et 3-dimensionel rum. Når der tænkes på et punkt bliver vektoren ofte kaldt for en vertex. En vektor skal derfor bestå af mindst tre komponenter, der hver repræsenterer henholdsvis akserne X, Y og Z. I mange sammenhænge vil disse tre komponenter være nok til at dække de fleste behov, men da vi i forbindelse med 3D ofte gerne vil arbejde med 4x4 matricer vil vi få brug for homogene koordinater. Homogene koordinater har tilføjet en fjerde komponent som kaldes enten for W eller H (Homogeneous). Den fjerde komponent repræsenterer ikke en akse på samme måde som de tre første gør. Den homogene komponent er egenligt bare en skalér der har effekt for de resterende komponenter. Det vil vi komme ind på senere.

Siden vi gerne vil opnå en nøjagtig placering af vores vektor, bliver vi nødt til at bruge decimal tal til at reprænsenter vores fire komponenter. Computeren kan tilbyde to typer decimal tal, hvoraf den ene er mere nøjagtig end den anden. Vi snakker selvfølgelig om float typerne: double og single. Float typen: double, er mere præcis end float typen single, men den er også lidt langsommere. Man kan sagtens bruge dem begge, men da vi er mest interesseret i præcision fremfor hastighed, vil vi nok få mest gavn af float typen: double.

Som tidligere nævnt skal vores vektor klasse kunne de mest grundlæggende ting som f.eks. at lægge to vektor sammen, men den bliver også nødt til at havde en mere fremtrædende funktion. Da de mest almindelige 3D modeller er bygget op af trekanter, skal den kunne finde en skæringspunkt i en trekant. En trekant har selvfølgelig tre kanter, derfor må den også bestå af tre punkter. Som nævnt tidligere kan disse punkter opfattes som tre vertex'er eller tre vektorer. Derfor vil det være meget naturligt at placere en sådan funktion i netop vores vektor klasse.

Der findes mange algoritmer der kan finde en skæringspunkt i en trekant. Nogle er bedere end andre, alt afhængig af hvilke informationer man ønsker omkring skæringspunktet. I vores tilfælde har vi behov for en hel del information. Først skal vi vide om vores skæringsvektor rent faktisk har en skæringspunkt i en given trekant eller ej. Hvis den har en skæringspunkt, skal vi vide, hvor henne på trekantens flade punktet befinder sig. Vi skal også vide, hvor punktet befinder sig i henhold til eventuelle tekstur (texture) koordinater. Vi vil også gerne vide om vores skæringsvektor skærer forsiden eller bagsiden af trekanten.



Som du kan se på illustrationen ovenover, har vi en en blå skærings vektor og en trekant der består af vektorne V1, V2 og V3. I dette tilfælde skærer vores vektor trekantens flade, men det er let at forestille sig en situation, hvor en vektoren ikke ville skære trekanten. Samtidig kan du se at vektoren går igennem trekanten fra den nærliggende flade, som vi kunne kalde forsiden, og går ud gennem trekantens bagside. Hvorfor er det vigtigt at vide? Det vil blive vigtig for os, når vi kommer til at skulle beregne lysets fald. Desuden er det ikke sikkert du overhovedet ønsker at rendere bagsiden. Der kan opnåes visuelle effekter ved ikke at rendere den.

Den nok mest kendte algoritme er Möller & Trumbore's klassiske skæringsalgoritme fra 1997. Den er designet til Raytracing og er blevet testet af mange forskellige programmører gennem tiden. Det eneste negative man kan sige om denne algoritme, er, at den er relativ langsom. Men du vil nok ikke kunne finde mange algoritmer, der kan levere så mange informationer som denne og samtidig være stabil. Denne artikel vil ikke beskrive, hvordan selve algoritmen fungere. Hvis du er interesseret i disse oplysninger, findes der et hav af artikler på nettet som du kan læse. Derimod vil vi fokusere på, hvordan vi kan aflæse de relevante informationer og bruge dem i vores program.

Möller & Trumbore's skærings funktion kalder vi for: Intersect, da er det engelske ord for det samme. Den skal som sagt skrives i vores vektor klasse. Her er funktionens prototype:

Fold kodeboks ind/udKode 


Lad os kaste et hurtigt blik på, hvilke værdier funktionen kan returnere og betydningen af dem.
Funktionen kan returnere værdierne 0, 1 eller 2:
0 = Funktionen har IKKE har fundet en skæringspunkt.
1 = Skæringspunkt er fundet på forsiden af trekanten.
2 = Skæringspunktet er på bagsiden af trekanten.

RayNear og RayFar vil tilsammen udgør en segment. Som tidligere nævnt kan en vektor opfattes som at være en retning eller et punkt. Skæringspunktet kan ikke findes ved blot en retning. Vi skal vide hvor linjen starter og hvor den slutter. Vi kunne antage at startpunktet altid vil ligge i koordinat nul. Altså, hvor X, Y og Z alle tre er lige præcis nul og dermed bruge vektorens koordinater som slutpunktet. Når du engang kommer til at implememtere skygger og specielt reflektioner, vil du finde ud af at samme algoritme kan bruges, men du vil få brug for at ændre startpunktet. Derfor er det bedst at havde en startpunkt og en slutpunkt defineret som to separate vektorer.



V1, V2 og V3 er alle vektorer der tilsammen udgør en trekant. Parameteren: TwoSided, vil afgøre om bagsiden af en trekant skal ignores eller ej. Den sidste parameter: DepthTest, angiver ganske enkelt den tilladte dybde. Som regl har den samme værdi som RayFar vektorens Z komponent men den skal altid havde en positiv værdi. Hvis trekanten er længere væk end, hvad denne parameter tillader kan den ignoreres.

Selve skæringspunktet, hvis der altså er fundet en, vil blive gemt i vektor klassens X, Y og Z komponenter. Dog er det ikke de geometriske koordinater der er tale om.

X og Y komponenterne vil indeholde barycentriske koordinater. Disse kan også opfattes som UVW koordinater, altså trekantens fysiske tekstur (texture) koordinater. Vi vil ikke komme til at bruge W komponenten i denne artikel men den kan omregnes ganske enkelt: ( 1 - U - V ) eller ( 1 - X - Y ).

Z komponenten er afstanden mellem RayNear og RayFar. Den geometriske skæringspunkt kan derfor findes ved at trække RayFar fra RayNear, for denæst at gange resultatet med Z komponenten og til sidst lægge det hele til RayNear vektoren:

Skæringspunkt = RayNear + ( RayFar - RayNear ) * Z

Vi kan bruge funktionen FollowLine til denne udregning.



Vektor klassen vil komme til at se således ud:

Fold kodeboks ind/udKode 



Hvad synes du om denne artikel? Giv din mening til kende ved at stemme via pilene til venstre og/eller lægge en kommentar herunder.

Del også gerne artiklen med dine Facebook venner:  

Kommentarer (26)

User
Bruger #13520 @ 01.09.08 21:15
coolt
User
Bruger #12871 @ 13.09.08 13:32
Wow!
Det er ikke hverdag man falder over en så gennemført tutorial. Du forklarer tingene rigtig godt og detaljeret uden at du forventer at folk er indforstået med hvad det lige er du mener. Jeg har arbejdet med 3D før i 3D's MAX og har tit tænkt på hvordan man kunne programmere sådan noget selv. Så du skal virkelig have mange tak for at vise mig hvordan man evt. kunne gøre det.
Keep up the good work :D
5/5 point
P.S. Lige et lille spørgsmål... Hvor har du alt din viden fra?
User
Bruger #1474 @ 17.09.08 14:12
Mange tak for jeres kommentar.

Jeg har min viden fra forskellige bøger, websites og selvfølgeligt mit universitet. Jeg er netop blevet færdig som: Computer Spil Programmør på et Engelsk universitet. Da jeg altid har arbejdet med real-time rendering, har jeg i et stykke tid gået og fået lyst til at prøve software rendering. Håber at I kan drage nytte af min artikel.
User
Bruger #12364 @ 06.10.08 11:38
Genialt! Det var lige hvad jeg havde brug for!
User
Bruger #14855 @ 21.04.09 19:29
Søren du laver generalt DE BEDSTE artikler!
User
Bruger #11164 @ 07.05.09 01:31
Jeg har et forslag til din vektor klasse. Jeg benytter operator overloading til ting som at addere, subtrahere og skalarproduktet. Jeg synes det gør brugen af vektorer meget mere overskuelig :) Ellers thumbs up.
User
Bruger #1474 @ 07.05.09 12:56
Jeg plejer også at bruge operator overloading i mine vektor klasser men jeg ville skrive C++ koden så den let kunne sammenlignes med Delphi koden (Se den samme artikel for Delphi: http://www.udvikleren.dk/Delphi/Article.aspx/319/ ). Operator overloading er en forholdsvis ny feature i Delphi derfor har jeg ikke inkluderet den i Delphi versionen. I tilfælde af at en C++ programmør er interesseret i at lære Delphi (eller modsat) eller bare er interesseret i at se forskellen mellem de to sprog burde disse artikler være et godt udgangspunkt.


Mange tak for jeres kommentar. Hold jer endelig ikke tilbage hvis I har forslag, kritik eller ros :)


PS: Glem nu ikke rate mine artikler :P
User
Bruger #15008 @ 24.05.09 21:27
Dejligt at kunne læse noget på dansk ;-) Super godt skrevet.
User
Bruger #14855 @ 17.06.09 15:32
Hmm, god artikel, men ringe du har lavet PRÆCIS den samme artikel, bare med C++!
User
Bruger #14855 @ 17.06.09 15:33
Undskyld men Delphi!
User
Bruger #14855 @ 17.06.09 15:33
*Mener
User
Bruger #1474 @ 17.06.09 17:10
Jonas:: Hvorfor ser du det som et negativt ting at have en artikel der viser implementationen i flere sprog? Skal Delphi udviklere ikke havde chancen for at implementere denne artikel? :)

Mange tak for rosen.
Jeg modtager gerne ris såvel som ros :)
User
Bruger #14855 @ 19.06.09 23:29
Mener bare at du har lavet 2 af de samme artikler og fået dobblet point for det, du kunne bare ha' lavet det hvor artikel navnet var: "3D software rendering med C++ og Delphi" :) Men synes det er ret mærkeligt :)
User
Bruger #1474 @ 20.06.09 19:10
Hvorfor skulle jeg blande to sprog sammen når de er delt i to adskilte teknologier på dette forum? I så fald hvilken udviklings teknologi skulle jeg så poste dem under? :) Er det fordi du mener at jeg har fået for mange points for de artikler? :)
User
Bruger #1474 @ 20.06.09 20:00
Hvorfor skulle jeg blande to sprog sammen når de er delt i to adskilte teknologier på dette forum? I så fald hvilken udviklings teknologi skulle jeg så poste dem under? :) Er det fordi du mener at jeg har fået for mange points for de artikler? :)
User
Bruger #14855 @ 21.06.09 21:00
Jep :)
User
Bruger #1474 @ 21.06.09 23:01
Jamen så må du jo snakke med de admins der har ansvar for artikeler her på forummet og tage problemstilling op hos dem. Det kan jeg næsten ikke gøre noget ved. Håber trods alt du kan bruge mine artikler til noget.
User
Bruger #14855 @ 22.06.09 14:39
Det kan jeg da SIKKERT! :) Artiklen er meget god :) Men synes bare det er urætfærdigt at man får Up for begge :)
User
Bruger #14103 @ 01.08.09 17:13
Jonas:

De der UP, er det ikke bare nogle tal, og så ikke mere i det?:)
Altså jeg laver altid Forumindlæg uden point..:)
User
Bruger #13937 @ 15.09.09 17:39
Hey. Virkelig gennemført beskrivelse, og tror bestemt at jeg skal ha undersøgt mere på emnet.

Anyway. Har et par spørgsmål:

Den første kodestump på s. 4, som starter således: "//Den officelle TGA fil header!". Skal den gemmes som TGA.h? For hvis det er tilfældet så prøver den jo på at include sig selv :S

Og kan det her på udvikleren lade sig gøre at hente de filer som bliver brugt/lavet i artiklerne? For det ville da være en fordel hvis man sidder ligesom mig og roder rundt i hvordan det hele skal sidde sammen så man har en virkende bund at starte på, og at man ved fejl evt. ved fejl ved at det ikke er koden, men noget setup :)

Og til sidst. Dette burdet ikke have noget problem med at compile på en ubuntu-installation?

mvh. martin :)
User
Bruger #1474 @ 15.09.09 20:21
Hej Martin,

Stukturen som jeg har kaldt for: FILEHEADER, er den officielle TGA fil header. Den skal ligge øverst i header filen TGA.h således den kan genkendes af TGA klassen. Du kan godt lægge den i en separat header fil, hvis du har lyst til det, men så skal den selvfølgelig inkluderes i TGA header filen inden TGA klassen defineres. Jeg vil nok anbefale at lægge den inden i selve TGA klassen da denne TGA fil format kun benyttes af TGA klassen! Med andre ord så er alt koden i den refererede tekst boks implementeringen af hele TGA klassen og kan skrives i en header fil eller en header med tilhørende cpp fil.

Angående kilde kode, du kan sende mig en udvikler post her på forummet med din mail adresse. Så vil jeg sende projektet til dig i en zip fil.

Alle andre er selvfølgelig også velkommen til at sende mig deres mail adresse.

Projektet skulle være platforms uafhængig. Der bliver ikke brugt nogle operative kommandoer eller API'er af nogen form, så ja, hvis din kompiler ellers kan kompile ganske almindelige console applikationer, så burde du også kunne kompilere dette projekt. Lad mig vide hvis du støder ind i nogle problemer.

Søren Klit Lambæk
User
Bruger #1927 @ 19.02.10 12:08
Rigtig god artikel.

Du har dog glemt at fortælle at man skal huske at ændre RenderImage til at bruge den nye ShadePixel()

Fold kodeboks ind/udKode 




Og Phong laver compile errors

Da du her
Fold kodeboks ind/udKode 


parser V1, V2 og V3 til InterpolateVertexColors funktionen. Den ta'r vectors, men V1, V2 og V3 er vertexes.
User
Bruger #1927 @ 19.02.10 12:10
Eller... Nu bliver jeg forvirret.

Fold kodeboks ind/udKode 
User
Bruger #1927 @ 19.02.10 12:12
Nej, okay. er omvendt. Funktionen forventer vertexes, men V1, V2 og V3 er vectors.

Hvordan den være?
User
Bruger #1927 @ 19.02.10 12:13
Denne side er da håbløst bugged.

Fold kodeboks ind/udKode 
User
Bruger #1474 @ 22.02.10 10:21
Hej Morten, jeg er ikke helt med paa hvad du mener. Baade InterpolateNormals() og InterpolateColors() tager vertexer (Vertices). Kan du ikke give mig noget mere sammenhaengene kode saa jeg kan se mere detaljeret hvad du goer. Tak :)
Du skal være logget ind for at skrive en kommentar.
t