Datamaskingrafikk og WebGL: Del 7

Viser innlegg med etiketten Del 7. Vis alle innlegg

Modul 3.3: Transformasjoner og matrisestack

Hierarkisk modellering og scenegraf

Innledning

I dette notatet ser vi på hvordan man kan lage modeller/objekter bygd opp av andre (mindre) objekter, som igjen er bygd opp av andre objekter, som igjen er bygd opp av andre objekter osv. i en hierarkisk struktur.

Modellen har en "rot" i form av en transformasjon som påvirker hele modellen. Rota kan ha et eller flere barneobjekter som har sin egen transformasjon kombinert med transformasjonen til rota. Tilsvarende gjelder for barn av disse, som har sin transformasjon. Barneobjektenes transformasjon er en kombinasjon av egen transformasjon og forelderens transformasjon. Tilsvarende vil gjelde for ev. barn av disse (barnebarn) igjen osv. Dette betyr at barneobjektene posisjoneres og orienteres i forhold til foreldreobjektet ved at hvert objekt har sin transformasjon som er relativ til sin forelder. Vi kaller dette hierarkisk modellering [56].

Fordelen med å organisere objekter på denne måten er bl.a. at dersom man transformerer et objekt blir alle barn- og barnebarn osv. transformert tilsvarende.

En slik hierarkisk struktur kalles gjerne en scenegraf [56]. Flere høynivås 3D-APIer har innebygd støtte for dette, bl.a. Three.js (https://threejs.org). Der er scene-objektet rota i scenen, og man knytter toppnivå-objekter til dette. Deretter kan man knytte nye objekter til toppnivå-objektene, som igjen kan ha sine barneobjekter osv.

Dette kan f.eks. visualiseres som vist under.

Figuren illustrerer hvordan en scenegraf kan se ut. Her er scene-objektet rota, mens huset, lyktestolpen, treet og benken er barn av dette. Huset består av tak, huskropp osv. Huskroppen består av vinduer, dør osv. Døra har sin modellmatrise som sørger for å orientere og posisjonere den korrekt i forhold til huskroppen. Huskroppen har på samme måte sin modellmatrise som sørger for å orientere og posisjonere den korrekt i forhold til "hus-rota" osv.

Hver node i treet kan ha sin egen transformasjon og et eller flere barneobjekter. Legg merke til at transformasjoner (modellmatrisene) arves nedover i hierarkiet. Flytter, skalerer eller roterer du en forelder påvirkes alle barne-objekter.

Eksempel: Et tre med grener og kvister/blader

Her demonstreres hierarkisk modellering ved å implementere et enkelt hierarkisk strukturert 2D-tre. Treets ulike deler er animert slik at det svaier i vinden. WebGL har ingen støtte for scenegraf, så her må man implementere alt av transformasjoner selv.

Merk: Scenegrafen til treet vil ut som vist i figuren under; rota øverst, under denne kommer stammen, under denne kommer greinene og deretter kvistene.

Scenegraf for treet. — Scenegraf for treet

Treet består av en stamme, to grener og fire kvister - til sammen sju deler som er koplet sammen hierarkisk. Hver del er et 2D-rektangel med sin egen farge, sin egen størrelse og sin egen transformasjon. I kodeeksemplet er animeres treet ved at greiner og kvistere "vaier i vinden" ved å rotere både stammen, greinene og kvistene. Poenget er å demonstrere at rotasjoner i f.eks. stammen forplanter seg til greiner og kvister. På samme måte vil rotasjon av greinene forplante seg til kvistene osv.

WebGL Tre med grener og kvister. — WebGL Tre med grener og kvister

Figuren består av flere deler som «henger» sammen. Vi ønsker å oppnå to ting:

Det skal være mulig å bevege på en enkelt del uavhengig av de andre delene.
Når man roterer eller flytter på en del skal alle delene under (i hierarkiet) henge med.

Det første punktet innebærer at en kvist skal kunne "svaie" (rotere) uavhengig av grena den sitter på, og at grena skal kunne svaie uavhengig av stammen. Dersom dette skal være mulig må de ulike delene tegnes med sin egen modelltransformasjon.

De ulike delene tegnes vha. et og samme rektangel. Det betyr at samme rektangel tegnes sju ganger. For hver gang settes en ny transformasjon. Alternativet er å definere alle verteksene i forhold til stammen. Dette gjør det imidlertid veldig vanskelig å bevege enkeltdeler som f.eks. en gren eller en kvist.

Det andre punktet betyr at dersom man roterer stammen, skal hele krona følge med. Roterer man en gren, skal kvistene på den grena følge med - men ikke kvistene på nabogrena.

Treets ulike deler

Alle delene vokser langs sin egen lokale +y-akse. Forelder og barn er koplet sammen i et slags ledd. Siden hvert del i utgangspunktet er et rektangel sentrert om origo vil koplingspunktet for barn og forelder være henholdsvis nederst og øverst i rektanglet (i lokale koordinater). Barne-rektanglet må dermed flyttes opp, tilsvarende egen halvlengde, deretter roteres om Z, for så å flytte opp enda en gang tilsvarende forelderens halvlengde.

Treets ulike deler er definert slik:

Treets ulike Javascript-objekter har samme struktur, dvs. de inneholder verdiene: halvLengde, halvBredde og en fargeverdi.

Akkumulert modellmatrise

Treet bygges ved å akkumulere modellmatrisa for de ulike delene. Vi bruker stammens modellmatrise som en del av grenenes modellmatrise. På samme måte brukes grenas modellmatrise som en del av kvistenes modellmatrise. Modellmatrisa til hver del beregnes altså med utgangspunkt i «foreldrerektanglets» modellmatrise.

Hierarkiet i treet ser slik ut. T er en translasjon, R en rotasjon om z-aksen og S en skalering. vind_0, vind_1 og vind_2 er vindutslaget på hvert nivå:

rot (med ev. transformasjon)
 |
 +-- stamme         R(vind_0)   * T(0, 4.0)                     S(0.50, 4.0)
      |
      +-- gren V    T(0, 4.0)   * R(+35 + vind_1) * T(0, 2.5)   S(0.35, 2.5)
      |    +-- kvist  T(0, 2.5) * R(+30 + vind_2) * T(0, 1.5)   S(0.20, 1.5)
      |    +-- kvist  T(0, 2.5) * R(-30 + vind_2) * T(0, 1.5)   S(0.20, 1.5)
      |
      +-- gren H    T(0, 4.0)   * R(-35 + vind_1) * T(0, 2.5)   S(0.35, 2.5)
           +-- kvist  T(0, 2.5) * R(+30 + vind_2) * T(0, 1.5)   S(0.20, 1.5)
           +-- kvist  T(0, 2.5) * R(-30 + vind_2) * T(0, 1.5)   S(0.20, 1.5)

Legg merke til at treet forgreiner seg på to nivåer: stammen har to grener, og hver gren har to kvister. Dette er årsaken til at det er fornuftig å bruke en matrisestack for å holde på transformasjonene til de ulike delene. Matrisestacken omtales i neste avsnitt, men inntil videre kan du bare tenke på det som en liste som inneholder matriser. Til sammen er det sju rektangler, tegnet med det samme verteksbuffer. Her er det viktig å få med seg at skalering ikke er en del av matrisene som legges på matrisestacken. Skalering gjøres, men på en kopi av matrisen som hentes fra toppen av matrisestacken, før aktuell del tegnes. Mer om dette under.

Oppskriften for et ledd: T * R * T

Hvert ledd i treet over består av tre transformasjoner. Grunnen er at rotasjonen i utgangspunktet alltid skjer om origo. Skal en gren rotere om festepunktet sitt (nedre del av rektanglet), må festepunktet først flyttes til origo. Oppskriften blir derfor:

T — Flytt delen opp tilsvarende halvparten av høyden til forelderen. Dette tilsvarer punktet der delen skal koples til forelderen, altså leddet som kopler delene sammen.
R — Roter delen om z-aksen.
T — Flytt delen opp slik at bunnen av delen ligger i origo (y=0), dvs. halvparten av delens høyde.

Legg merke til at de to siste R*T tilsvarer det vi tidligere kalte en Orbit. Produktet av disse tre matrisene er det som legges på matrisestacken.

For at delen skal tegnes korrekt kombineres forrige matrise med en skalering med gitte størrelser for aktuell del. Det betyr at det er følgende matrise, M_del, som brukes til å tegne treets ulike deler.

M_del = M_parent * T(til leddet) * R(leddvinkel) * T(halve lengda) * S(størrelse)

Metodene translate(), rotate() og scale() i cuon-matrix ganger på fra høyre (i likninga over). Det betyr at den transformasjonen som kalles sist i koden, er den som påvirker verteksene først. Derfor er kommentarene i createAndPushPartMatrix() lenger ned nummerert nedover (3, 2, 1): leser du dem nedenfra og opp, får du rekkefølgen verteksene faktisk transformeres.

Legg merke til at forelderen til stammen er rota. Rota er i seg selv ingen del/figur/objekt, den inneholder kun en transformasjon. Rota har dermed ingen høyde så det øverste T'en i TRT-rekkefølgen over har derfor ingen effekt. Stammen vil kun flyttes opp tilsvarende sin egen halvhøyde. Alle de andre delene følger oppskriften.

Bruk av matrisestack

For å kunne ta vare på de ulike matrisene for de ulike delene i hierarkiet kan man bruke en matrisestack. Dette gjør det enkelt å ta vare på og akkumulere transformasjonsmatrisene. I kodeeksemplet er stacken lagt i en egen klasse, Stack, som ser slik ut:

Legg merke til at matrixStack er deklarert som et array. Javascript-array har allerede metoder for push() og pop(), og disse brukes i pushMatrix() og popMatrix().

Legg spesielt merke til at både pushMatrix() og peekMatrix() lager en kopi med new Matrix4(...).

peekMatrix() returnerer en kopi av toppmatrisa. Man kan derfor kalle translate(), rotate() og scale() på denne kopien, uten at matrisa som ligger på stacken endres.
pushMatrix() legger en kopi på stacken. Endrer du matrisa du sendte inn etterpå, påvirker det ikke stacken.

Legg til sist merke til at peekMatrix() kun leser toppen (uten å fjerne den), mens popMatrix() fjerner toppen (uten å returnere den). Trenger du begge, kaller du peekMatrix() først og popMatrix() etterpå.

Bruk av stacken

Vi bruker stacken for å ta vare på matrisen for hver enkelt del. Dette kan oppsummeres slik:

Hent en kopi av forelderens matrise med M_parent = peekMatrix().
Bruk kopien som utgangspunkt for den nye delens matrise: M_part = M_parent * T * R * T.
pushMatrix(M_part) — før skaleringa legges på.
Lag en matrisa som også inneholder skalering: M_{part_scale} = M_parent * T * R * T * S, der S er skaleringsmatrisa.
Tegn rektanglet vha. denne matrisen.
Tegn eventuelle barn (gå til punkt 1). De vil da bruke matrisa du nettopp pushet som sin forelder (uten skalering).
popMatrix() når delene som er knyttet til denne er ferdig tegnet.

Punkt 1 til 3 er samlet i én hjelpefunksjon:

Husk at alle delene tegnes med det samme kvadratet, og hver del må derfor skaleres til sin egen størrelse. Men skaleringa skal ikke arves nedover i treet — ellers ville grenene arve stammens skalering, kvistene arve grenenes osv. Ved å pushe før skaleringa vil stacken kun inneholde leddtransformasjonene, altså rotasjon og translasjon. Hvorfor det er viktig omtales i neste avsnitt.

Bruk av matrisestack gjør det enklere å ha kontroll på matrisene som skal brukes på de ulike delene: Når venstre gren med sine to kvister er "ferdig", må vi tilbake til stammens matrise for å kunne tegne høyre gren. Når den ene kvisten er "ferdig", må vi tilbake til greinas matrise for å kunne tegne neste kvist osv.

Legg merke til at antall pushMatrix() alltid er lik antall popMatrix(). Glemmer man en popMatrix(), får de neste "søsknene" feil forelder, og figuren tegnes galt.

Skalering arves ikke

Punkt 4 i lista over er implementert i en egen funksjon. Den henter en kopi av matrisa på toppen av stacken og legger til en skalering på kopien. Deretter tegnes delen vha. drawRectangle() med denne matrisa.

Variabelnavnet modelMatrixCopy er valgt for å minne om at vi jobber på en kopi.

MERK: Skaleringa hører til geometrien, ikke leddet. Stacken skal holde på delens koordinatramme dvs. hvor festepunktet er og delens posisjon i forhold til sin forelder. Dette er en såkalt "stiv transformasjon" som kun inneholder rotasjon og translasjon. En stiv transformasjon (rigid transformation) er en transformasjon som bevarer form, størrelse og avstander mellom alle punkter i objektet. Objektet endrer verken form eller størrelse, bare posisjon og/eller orientering. Verdiene 0.50 x 4.0, 0.35 x 2.5 og 0.20 x 1.5 er bare en tilpasning av ett felles enhetsrektangel til sju ulike deler. Hadde hver del hatt sin egen geometri i riktig størrelse, ville disse skaleringene ikke vært nødvendig.

Arver man skaleringa, skjer det to ting samtidig:

Avstandene multipliseres, og det akkumulerer. Grenas translate(0, 4.0, 0) blir tolket i stammens skalerte ramme, altså 4.0 × 4.0 = 16 enheter. Kvistene arver så både stammens og grenas skalering.
Rotasjonene blir skjeve. Skaleringa er ikke-uniform (0.50 i x og 4.0 i y), og den havner til venstre for barnets rotasjon i matriseproduktet. Da er barnets rotasjon ikke lenger en rotasjon, men en såkalt skjærtransformasjon (se https://en.wikipedia.org/wiki/Shear_mapping). Rektanglet blir et parallellogram, og leddvinklene blir feil.

Det som kan arves, er en uniform skalering i rota. Skalerer du hele treet med S(2, 2) i rot-matrisa, dobles alt og alle vinkler bevares.

Tegne hele treet

drawTree() legger rot-matrisa på stacken, tegner stammen, og løper deretter gjennom de to grenene og de fire kvistene. De to for-løkkene representerer forgreiningene i scenegrafen. Til slutt poppes rot-matrisa, og stacken er tom igjen:

Legg merke til modelMatrix.translate(0, -7, 0) i rota: Denne gjør at hele treet flyttes 7 enheter nedover, siden matrisa til alle delene beregnes ut fra rot-matrisa.

Hele treet tegnes vha. to for-løkker. Den indre tegner kvistene som er koplet til en gren, mens den ytre tegner grenene som er knyttet til stammen. Her er to grener, hver med to kvister. Du kan enkelt utvide både antall grener og kvister ved å legge inn flere verdier i Javascript-arrayene som for-løkkene gjennomløper.

Vindanimasjon

Ved å animere treets ulike deler ser vi effekten av hierarkisk modellering og bruk av matrisestack. Vinden er implementert av tre sinuskurver med ulik frekvens og fase, én for hvert nivå i treet:

Merk at elapsed er den samme forløpte tida som brukes ellers i animasjonsløkka, slik at animasjonene er uavhengig av frame rate.

Er stacken i balanse?

Etter at hele treet er tegnet skal stacken være tom. I koden er det lagt til en sjekk på om et eller flere kall på popMatrix() er glemt:

I dette eksemplet blir stacken maksimalt fire nivåer dyp — rot, stamme, gren og kvist. Merk at drawPart() ikke pusher noe; den bare leser toppen med peekMatrix().

Variabelen stackVarUbalansert gjør at advarselen skrives én gang istedenfor for hver frame, dersom stacken er i ubalanse.

En rekursiv løsning

I koden vist over skjer det samme når vi legger greiner til stammen og kvister til greinene. Man kan da alternativt gjøre dette vha én rekursiv funksjon. Dette krever enkelte justeringer i koden. Den første er å knytte et barn-attributt til treets ulike deler, slik:

Deretter må drawTree() justeres litt i tillegg til at vi lager en ny reksursiv funksjon, drawTreePartRecursive(), som tegner alle treets deler rekursivt.

Dette vil gi resultatet vist under:

Kodeeksempler

Komplett kode ligger i modul3/cameraclass/vindtre og modul3/cameraclass/vindtre_rekursivt. Stackklassen ligger i base/helpers/Stack.js.