2IV10 – Instructie 3: Transformaties en viewing 1. Gegeven een vierkant met ribbe 1, waarvan de linkeronderhoek in de oorsprong ligt.
s α C
B
1 A O
1
a. Geef een transformatiematrix waarmee dit vierkant wordt getransformeerd naar een vierkant met ribbe s, geroteerd over een hoek α, waarvan de rechteronderhoek samenvalt met de rechterbovenhoek van het oorspronkelijke vierkant. Eerst transleren we de rechteronderhoek naar de oorsprong (T(-1,0)), vervolgens schalen we (S(s,s)) en roteren we (R(-α)). Om consistent met het plaatje te blijven, moet over een negatieve hoek worden geroteerd. Tot besluit transleren we de rechteronderhoek (die nu in de oorsprong staat) naar de rechterboven hoek met T(1,1). Dit alles in globale coördinaten. De samengestelde matrix M volgt dus uit: M = T(1,1)R(-α)S(s,s)T(-1,0). b. We beschouwen een iets algemenere variant. Geef een recept voor een transformatiematrix voor een geroteerd en geschaald eenheidsvierkant OABC, waarbij het nieuwe hoekpunt O’, A’, B’ of C’ samenvalt met een van de oorspronkelijke hoekpunten O, A, B of C. Definieer P(x) als P(O) =(0,0), P(A)=(1,0), P(B)=(1,1) en P(C)=(0,1), en noem het nieuwe hoekpunt Q’ en het oude hoekpunt Q. Bij het antwoord op a komen twee translaties voor. De translatie T(-1,0) bepaalt om welk punt gedraaid wordt, de translatie T(1,1) bepaalt waar dit punt uiteindelijk terecht komt. Als we dit algemeen maken, dan komen we uit op M=T(P(Q)) R(-α)S(s,s)T(-P(Q’)). 2. We bekijken 3D rotaties. a. Geef 3x3 rotatiematrices voor een rotatie Rx(α ) om de x-as en een rotatie Rz(α) om de z-as.
0 0 1 cos α − sin α 0 Rx (α) = 0 cos α − sin α , en Rz (α) = sin α cos α 0 0 sin α cos α 0 0 1
1
b. Bereken (expliciet) de samengestelde rotatiematrix voor een rotatie over 90 graden (π/2 radialen) om de x-as gevolgd door een rotatie over 90 graden om de z-as. 0 − 1 0 1 0 0 0 0 1 Rz (90) Rx (90) = 1 0 0 0 0 − 1 = 1 0 0 0 0 1 0 1 0 0 1 0 c. Wat is het effect van deze twee opvolgende rotaties? Licht uw antwoord toe. De x-as wordt afgebeeld op de y-as, de y-as op de z-as, en de z-as op de x-as. Met andere woorden, de assen worden gepermuteerd. Ook kun je het effect interpreteren als een rotatie om de vector (1,1,1) over een hoek van 2π/3. d. Krijgen we hetzelfde effect als we de volgorde van roteren omdraaien? Nee. Matrix-vermenigvuldiging is niet commutatief. Als we het uitrekenen, dan krijgen we 1 0 0 0 − 1 0 0 − 1 0 Rx (90) Rz (90) = 0 0 − 1 1 0 0 = 0 0 − 1 0 1 0 0 0 1 1 0 0 en inderdaad, het effect is dramatisch anders. De x-as wordt afgebeeld op de z-as, de y-as op de negatieve x-as, en de z-as op de negatieve y-as. 3. We beschouwen een vervormde kubus. In de oorspronkelijke toestand wordt deze gegeven door 0 <= x,y,z <= 1. Na de vervorming geldt dat: - het ondervlak (in het XOY-vlak) op zijn plaats blijft; - het bovenvlak horizontaal blijft, maar wel verschuift: het punt (0,0,1) wordt verplaatst naar (a, b, c) ; - alle ribben recht en alle vlakken vlak blijven. a. Geef een transformatiematrix voor deze vervorming. De oorsprong blijft op zijn plaats. Er vindt dus geen translatie plaats. Verder, ook de x-as (1, 0, 0) en y-as (0, 1, 0) veranderen niet na transformatie. Echter, voor de z-as (0, 0, 1) geldt dat de nieuwe richting (a, b, c) is. Met behulp hiervan kunnen we nu de transformatie-matrix in een keer opschrijven: 1 0 a 0 0 1 b 0 M = 0 0 c 0 0 0 0 1 Controleer dat als we de punten (0, 0, 0, 1), (1, 0, 0, 1), (0, 1, 0, 1) en (0, 0, 1, 0) vermenigvuldigen met M (x’= Mx, x’ en x kolomvectoren) we inderdaad het gewenste resultaat krijgen. 4. Gegeven een digitale landkaart. Gewenst is om een stukje van deze kaart in een viewport op het scherm af te beelden. In het midden van de viewport moet het punt C (in kaartcoördinaten) worden afgebeeld, de breedte van het af te beelden stuk is w (in kaartcoördinaten). Uiteraard mag er geen vervorming optreden. De viewport wordt
2
opgegeven in pixels. Voor de pixelcoördinaten geldt dat de oorsprong (het punt (0,0)) linksboven ligt en het punt (Nx-1, Ny-1) rechtsonder. De linkerbovenhoek van de viewport heeft coördinaten (Xmi, Ymi), de rechteronderhoek (Xma, Yma). a. Geef een transformatie om punt Q in kaartcoördinaten om te zetten in een punt Q’ in pixelcoördinaten. We bepalen eerst de hoogte h van het window, door te eisen dat de aspect-ratio van window en viewport hetzelfde zijn: h Yma − Ymi Yma − Ymi = dus h = w . w Xma − Xmi Xma − Xmi Hiermee kunnen we de linkeronderhoek P van het window bepalen: P = C – (w/2, h/2). Het punt P verschuiven we naar de oorsprong (T(-P)). Vervolgens schalen we de breedte naar 1 (S(1/w,1/w)) en deze schalen we naar de breedte van de viewport (S(Xma-Xmi, Xma-Xmi)). We gebruiken voor de x en y dezelfde schaalfactor, om geen vervorming te introduceren. Om de y-as de goede kant op te laten staan, spiegelen we om de horizontale as (S(1, -1)). Tot besluit transleren we de oorsprong naar de linkeronderhoek van de viewport (T(Xmi, Yma)). Bij elkaar geeft dit, met de schalingen gecombineerd: M = T(Xmi, Yma)S((Xma-Xmi)/w, -(Xma-Xmi)/w)T(-P).
b. Een gebruiker wijst een punt R’ (pixelcoördinaten) aan. Geef een transformatie om het bijbehorende punt R in kaartcoördinaten te bepalen. Deze transformatie is de inverse van M. R’=MR, dus R= M-1 R’. We kunnen de inverse bepalen door een algemene routine op de matrix M los te laten, maar ook kunnen we hem afleiden uit de formule. Er moet gelden dat MM-1 = I. Dit bereiken we door M rechts te vermenigvuldigen met een reeks transformaties die de transformaties van M van rechts naar links opheffen. We vinden zo: M-1 = T(P)S(w/(Xma-Xmi), -w/(Xma-Xmi))T(-Xmi, -Yma).
5. Gegeven een 3D scene, die wordt bekeken met een virtuele camera. De camera heeft positie P, staat gericht in de richting W, en lijnen in de richting van een vector V komen verticaal in beeld. Aangenomen mag worden dat V en W eenheidsvectoren zijn en loodrecht op elkaar staan. Bij de volgende vragen wordt gevraagd om het effect van de camerabeweging op P, V en W. a. Geef recepten om de camera voor- en achteruit, omhoog en omlaag, en naar links en rechts te bewegen. We definieren een extra hulpvector U=W×V. We hebben nu een compleet assenstelsel voor onze virtuele camera: U staat naar rechts, V omhoog, en W loodrecht het scherm in. Hiermee kunnen we de gewenste operaties uitvoeren. Dit zou ook kunnen met algemene transformatie-routines, maar hier is het net zo handig om het rechtstreeks te doen. Als de verplaatsing a is, dan krijgen we Voor- en achteruit: Omhoog en omlaag: Rechts/links:
P’ = P ± aW; P’ = P ± aV; P’ = P ± aU;
3
De vectoren V en W veranderen niet, het gaat hier om translaties. b. Geef recepten voor het roteren van de camera: pitch (links/rechts), yaw (naar onder/boven), roll (rotatie om middelpunt beeld). Hier veranderen de vectoren V en W, en blijft P hetzelfde. Ook dit zou weer met algemene transformatie-routines kunnen worden gedaan, maar rechtstreeks is handiger. Twee orthonormale 3D vectoren X en Y kunnen we roteren via: procedure RotVecs(X, Y: T3Dvector; var X’, Y’: T3Dvector; α: real); begin X’ = cos α X + sin α Y ; Y’ = –sin α X + cos α Y end; Hiermee kunnen we de gevraagde rotaties opschrijven als: pitch: yaw: roll:
RotVecs(U, W, U’, W’, α); // rotatie om V RotVecs(V, W, V’, W’, α); // rotatie om U RotVecs(U, V, U’, V’, α); // rotatie om W
c. Stel dat de camera gecentreerd is om een punt C. Geef weer recepten voor rotatie, waarbij de camera op dit punt gecentreerd blijft. Het antwoord voor b geeft de gevraagde nieuwe oriëntatie van de vectoren. De nieuwe positie van P kunnen we bepalen door gebruik te maken van de betekenis van de vectoren. De vector W staat in de richting van P naar C, en na het draaien van de camera willen we dat W’ in de richting van P’ naar C staat. De vector W’ weten we al, en die kunnen we gebruiken om P’ te bepalen: P’ = C – W’ |P – C| .
Ofwel, de nieuwe positie van de camera vinden we door vanuit C in de richting van –W’ te gaan over dezelfde afstand |P – C| als in de oorspronkelijke situatie.
Voor de liefhebber: 6. We gaan uit van opgave 3, waarbij we keken naar het afbeelden van een digitale kaart. Stel dat een gebruiker de kaart heeft gecentreerd op een punt C (bijvoorbeeld Eindhoven) met een breedte w (10 km). Vervolgens geeft hij op dat hij de kaart wil centreren op een punt C’ (Amsterdam) met een breedte w’ (20 km). Gewenst is een animatie C(t), w(t), zodat een vloeiende overgang wordt getoond. a. Wat zou je als eisen formuleren? We zouden bijvoorbeeld willen dat (a) de animatie continu is (geen schoksgewijze bewegingen), dat (b) de ‘hoeveelheid’ beweging op het scherm constant is en dat (c) de animatie efficiënt is – van C naar C’ in de kortste tijd. b. Hoe zou je zo’n animatie kunnen definieren? 4
We zouden eerst kunnen uitzoomen, vervolgens de camera transleren, en daarna weer inzoomen. Om bij het uitzoomen een constante verandering te krijgen, veranderen we w steeds met een constante factor: w(t+∆t) = f w(t), met f>1, totdat w(t) = wMAX. Als we deze differentievergelijking omzetten naar een differentiaalvergelijking (dw/dt=fw) en die oplossen, dan krijgen we w(t)=exp(ft). Voor wMAX gebruiken we α|C-C’|, zodat de maximale uitzoomfactor afhankelijk is van de afstand tussen C en C’. Lineair veranderen van w (w(t+∆t) = w(t) + ∆w) geeft geen constante verandering: Bij w=10km heeft een verandering van 1km veel meer effect dan bij w=100km. De translatie kan wel lineair gebeuren: C(t+∆t ) = C(t) + s(C-C’). Bij het inzoomen gebruiken we een factor 1/f. Tot besluit stellen we de factoren α, s en f experimenteel in, zodat op het oog een prettige animatie ontstaat. Deze oplossing kan worden verbeterd. Bij de overgang van zoomen naar translatie treedt een schok(je) op, en het is ook niet de meest efficiënte route. Mooier is om tegelijkertijd de camera te verplaatsen en in- of uit te zoomen, onze virtuele camera moet een soort boog over de kaart heen beschrijven. Het is niet eenvoudig om te bepalen hoe dit te doen. Voor een complete uitwerking, zie: Wijk, J.J. van, Wim A.A. Nuij. Smooth and Efficient Zooming and Panning. In: T. Munzner, S. North (eds.), Proceedings IEEE Symposium on Information Visualization (InfoVis'2003), IEEE Computer Society Press, October 2003, p. 1522. (http://www.win.tue.nl/~vanwijk/zoompan.pdf).
5
