Inhoud
Inleiding computer graphics Introductie 11 Leerkern 1 2
3
4
5 6
14
Invoer en opslag van 3D objecten 14 Ray tracing 18 2.1 Basisprincipe van ray tracing 18 2.2 Secundaire stralen 20 2.3 Intersectieberekeningen 23 De 3D polygon rendering pipeline 25 3.1 Modeling transformaties 25 3.2 De 3D viewing transformatie 31 3.3 Projectie 33 3.4 Clipping 35 3.5 De window to viewport transformatie 37 3.6 Scanconversie 38 3.7 Hidden surface removal 39 3.8 Een eenvoudig lichtreflectiemodel 41 3.9 Flat shading en smooth shading 45 Texture mapping 47 4.1 Wat is texture mapping? 47 4.2 Bilineaire texture mapping 49 4.3 Perspectivische texture mapping 50 Samenvatting 53 Literatuur 55
Terugkoppeling
57
– Uitwerking van de opgaven
10
57
Inleiding computer graphics
Inleiding computer graphics
INTRODUCTIE
In deze inleiding nemen we als toepassingsgebied van de lineaire algebra een kijkje in het vakgebied van de computer graphics, in het bijzonder de 3D computer graphics. Computer graphics is het deelgebied van de informatica dat zich bezighoudt met het maken van afbeeldingen op een computerbeeldscherm of een uitvoerapparaat zoals een printer. In de loop der jaren is computer graphics een steeds grotere rol gaan spelen in het gebruik van computers door de ontwikkeling van computer hardware (invoer- en uitvoerapparaten, geheugens, processors, grafische kaarten enzovoort). In het begin van het computertijdperk bestonden er alleen uitvoerapparaten waarop tekst kon worden afgebeeld. Daarna kwamen er penplotters en vector displays waarop lijnafbeeldingen konden worden getoond. Nog weer later kwamen er printers en beeldschermen die in staat waren om rasterafbeeldingen weer te geven, zoals inkjetprinters, kleurenlaserprinters, beeldbuizen (CRT’s), plasmapanels en liquid cristal displays (LCD). Hierbij zijn de afbeeldingen opgebouwd uit afzonderlijke beeldpunten, ook wel pixels genoemd, die ieder een willekeurige kleur kunnen krijgen. Rasterbeeldschermen maken het mogelijk om, zoals ook bij tv en video, ingekleurde vlakken met grijstinten en kleuren weer te geven in plaats van alleen lijnafbeeldingen. Beeldschermen maken gebruik van een zogenaamd refresh proces. Dit houdt in dat de afbeeldingen op het beeldscherm een groot aantal keer per seconde worden ververst door alle beeldpunten opnieuw de juiste kleur te geven. Hierdoor wordt het mogelijk om naast statische beelden ook animaties op de beeldschermen te tonen. Dankzij deze ontwikkelingen vervult computer graphics een belangrijke rol bij het werken met computers op een gebruiksvriendelijke manier. Operating systems van computers en applicatieprogramma’s kregen hierdoor een grafisch georiënteerd gebruikersinterface, waarmee opdrachten worden gegeven door het gebruik van iconen en menu’s. Dit kwam in plaats van de gebruikersinterface waarmee de gebruiker door het intikken van tekst opdrachten geeft aan de computer en waarmee eveneens antwoorden ontvangen worden in de vorm van tekst. Het gebruik van grafieken en diagrammen om gegevens te presenteren werd ook een normale zaak. Het werd daarnaast geleidelijk mogelijk om met een redelijke rekentijd driedimensionale objecten realistisch op beeldschermen af te beelden. Tegenwoordig wordt 3D computer graphics onder andere gebruikt voor het weergeven van 3D objecten in Computer Aided Design (CAD) pakketten, in modeling en animatiepakketten zoals Maya en 3D Studio Max, in virtual reality applicaties en in 3D computer games.
OUN
11
Capita selecta wiskunde
Voorbeelden van het gebruik van 3D computer graphics zien we dagelijks op tv en complete 3D animatiespeelfilms, zoals Toy Story en Finding Nemo, zijn ook geen unicum meer. Op het internet zien we het gebruik van 3D computer graphics onder andere terug in de opkomst van de virtuele wereld Second Life. Figuur 0.1 en 0.2 tonen beelden van een virtual reality applicatie van de campus van de Technische Universiteit Delft. In figuur 0.1 is de situatie te zien in 2007 en in figuur 0.2 de toekomstige situatie in 2008. Figuur 0.3 toont de tram die in 2008 zal gaan rijden. Deze laatste afbeelding heeft een hogere kwaliteit – onder andere te zien aan de bomen en de schaduweffecten – doordat hier geen gebruik is gemaakt van (real time) virtual reality. Bij figuur 0.3 kan in plaats van enkele tientallen milliseconden veel langer gerekend worden.
12
FIGUUR 0.1
Virtual reality demo van de huidige Mekelweg (TU Delft Virtueel)
FIGUUR 0.2
Virtual reality demo van het toekomstige Mekelpark (TU Delft Virtueel)
OUN
Inleiding computer graphics
FIGUUR 0.3
Tram in het toekomstige Mekelpark (TU Delft Virtueel)
In het voorgaande hebben we opgemerkt dat veel van de huidige computerapplicaties gebruik maken van 2D en/of 3D computer graphics. In deze inleiding houden we ons voornamelijk bezig met 3D computer graphics. We geven geen overzicht van toepassingen van 3D graphics, maar gaan in plaats daarvan een antwoord zoeken op de vraag hoe afbeeldingen van 3D modellen kunnen worden berekend en op een beeldscherm worden weergegeven. De eerste stap bestaat uit het invoeren en in het geheugen opslaan van een model van de 3D objecten. Hiermee leggen we de scène vast die we willen presenteren. In paragraaf 1 laten we zien hoe een 3D model opgeslagen kan worden, zodat de data geschikt is om als uitgangspunt te dienen voor het berekenen van afbeeldingen. Na opslag van het model definiëren we een oogpunt (positie van de waarnemer) en plaatsen we lichtbronnen in de scène. Uit deze informatie wordt uiteindelijk een afbeelding berekend. Hierbij kunnen meerdere wegen bewandeld worden waarvan we er twee beschouwen. De eerste manier om een afbeelding van een 3D scène te berekenen is de methode van ray tracing. Het principe van ray tracing is eenvoudig, maar het algoritme vergt veel rekenkracht van de computer. Daarom is veel aandacht besteed aan methoden om ray tracing te versnellen. Het principe van ray tracing komt in paragraaf 2 aan de orde. Hierbij worden de versnellingstechnieken overigens buiten beschouwing gelaten. De tweede methode om een afbeelding van een 3D scène uit te rekenen bestaat uit de zogenaamde 3D polygon rendering pipeline of viewing pipeline. In paragraaf 3 komen de stappen uit de viewing pipeline aan de orde. De volledige viewing pipeline wordt in tegenwoordige computersystemen door de grafische kaart uitgevoerd. Doordat de 3D viewing pipeline enerzijds minder rekenintensief is dan ray tracing en anderzijds in hardware is geïmplementeerd, kunnen afbeeldingen met deze methode veel sneller worden gemaakt dan met ray tracing. De methode van ray tracing levert wel afbeeldingen van hogere kwaliteit dan met 3D viewing pipeline, doordat in ray tracing allerlei optische effecten meegenomen kunnen worden in de berekeningen, zoals in paragraaf 2 zal blijken. Ten slotte wordt in paragraaf 4 uiteengezet hoe we het realisme van objecten kunnen vergroten door hun oppervlak niet in één kleur weer te geven, maar te voorzien van een textuur.
OUN
13
Capita selecta wiskunde
LEERDOELEN
Na bestudering van de deze inleiding wordt van u verwacht dat u – inzicht heeft in de methoden voor het berekenen van afbeeldingen in computer graphics – de relatie tussen computer graphics en lineaire algebra begrijpt. Studeeraanwijzingen Wellicht kunt u in deze inleiding nog niet alle wiskundige redeneringen en formules volgen. Dat is ook nog niet per se noodzakelijk. Probeert u de hoofdlijnen van het betoog te volgen. In het vervolg van de cursus wordt dieper op de wiskunde ingegaan. Daarna kunt u deze inleiding wel volledig volgen.
LEERKERN 1
Invoer en opslag van 3D objecten
In deze inleiding zullen wij, zoals gebruikelijk is in de computer graphics, de componenten van een vector in de driedimensionale ruimte representeren met de letters x, y en z. Dit in tegenstelling tot wat we gewend zijn in de lineaire algebra, waar de componenten van een vector in de n-dimensionale ruimte vaak worden weergegeven als x1, x2, ..., xn. We zullen bovendien zien dat in de 3D computer graphics vaak gebruik wordt gemaakt van een vierdimensionale ruimte. De componenten van een vector worden dan aangeduid met de letters, x, y, z en h. Bij een punt P met coördinaten x, y, z, hoort een plaatsvector p , die we noteren met een kolomvector: ⎛ x⎞ ⎜ ⎟ p = ⎜ y⎟ ⎜z⎟ ⎝ ⎠
In de vierdimensionale ruimte wordt dit: ⎛ x⎞ ⎜ y⎟ p=⎜ ⎟ ⎜z⎟ ⎜⎜ ⎟⎟ ⎝h⎠
In lopende tekst noteren we dat ook wel met p = (x, y, z)T en p = (x, y, z, h)T.
Hiërarchisch modelleren Scène
14
In pakketten waarmee driedimensionale objecten kunnen worden ingevoerd in de computer, zogenaamde modelingprogramma’s, heeft de gebruiker vrijwel altijd de mogelijkheid om 3D objecten als een hiërarchisch model in te voeren. Het complete 3D model, dat kan bestaan uit een enkel object of meerdere objecten, zullen we de scène noemen. De gebruiker heeft bij hiërarchisch modelleren de beschikking over basisvormen (primitieven) die in de scène geplaatst kunnen worden. Meestal kan de gebruiker deze
OUN
Inleiding computer graphics
objecten op de juiste positie zetten, roteren en de juiste afmetingen geven op een grafisch interactieve manier, ofwel door rechtstreeks de 3D objecten te manipuleren. Tot de primitieve objecten kunnen een bol, kubus, piramide, cilinder, kegel en eventueel ook een torus behoren. Met deze bouwstenen kan de gebruiker componenten maken door exemplaren van de primitieve objecten correct ten opzichte van elkaar te positioneren. Iedere component wordt in een eigen 3D modeling coördinatenstelsel gedefinieerd. Exemplaren van de componenten kunnen vervolgens in een nieuw modeling coördinatenstelsel worden gecombineerd tot ingewikkelder componenten. Zo kan het interieur van een klaslokaal worden gemodelleerd door eerst een tafel te modelleren door een kubus inhomogeen te schalen en als tafelblad te gebruiken en vervolgens vier getransleerde cilinders als tafelpoten te gebruiken. Uit deze vijf primitieven (een kubus en vier cilinders) hebben we het object tafel gemaakt. Een aantal exemplaren van het object tafel kunnen we vervolgens plaatsen in het coördinatenstelsel waarin we het complete klaslokaal definiëren. Andere objecten, zoals de muren, kunnen op soortgelijke manier worden toegevoegd in het coördinatenstelsel van het klaslokaal. Als ons complete model moet bestaan uit het volledige interieur van een schoolgebouw met meerdere identieke klaslokalen, dan plaatsen we meerdere exemplaren van het object klaslokaal in het coördinatenstelsel voor het gehele schoolgebouw. Op deze manier bouwen we de gehele scène als een hiërarchie van objecten. Het coördinatenstelsel waarin de gehele scène is gedefinieerd noemen we het wereldcoördinatenstelsel. Objecten die niet kunnen worden ingevoerd door primitieve objecten zoals blokken, bollen en cilinders te combineren, kunnen worden gedefinieerd met surface-modelingtechnieken. Bij surface modeling heeft de gebruiker de mogelijkheid om objectoppervlakken aan te passen door controlepunten in de ruimte te verplaatsen, wat tot gevolg heeft dat het objectoppervlak in de richting van deze punten wordt mee verplaatst. De oppervlakken die op die manier worden ingevoerd, worden intern gerepresenteerd met splineoppervlakken, een wiskundige beschrijvingsmethode voor complex gekromde oppervlakken. Zo kan de carrosserie van een auto worden gemodelleerd of de vorm van een vliegtuigvleugel. De manier waarop de 3D objecten vervolgens in het geheugen van de computer worden opgeslagen, is afhankelijk van de methode die gebruikt wordt om afbeeldingen van de objecten uit te rekenen. Wij nemen twee methoden onder de loep om 3D modellen te visualiseren, namelijk ray tracing en de 3D polygon rendering pipeline. Bij ray tracing is het handig om gekromde objectoppervlakken van primitieve objecten te beschrijven met een impliciete representatie of met een parametrische representatie. Bij de polygon rendering pipeline worden alle gekromde oppervlakken benaderd met een netwerk van platte vlakjes. We bekijken eerst hoe een object opgeslagen kan worden als we er met ray tracing een afbeelding van maken. Ray-tracingafbeeldingen uit de begintijd van de 3D computer graphics bevatten vaak een groot aantal bollen. De reden hiervoor is dat een bol het eenvoudigste object is om te ray tracen. Waarom dat zo is wordt duidelijk in paragraaf 2.
OUN
15
Capita selecta wiskunde
als P(x, y, z) een punt is met de coördinaten x, y, z, dan ligt P op het oppervlak van een bol met middelpunt M = (xM, yM, zM) en straal r, als voldaan is aan de volgende impliciete representatie:
Impliciete representatie
( x − x M )2 + ( y − y M )2 + ( z − z M )2 = r 2 Parametrische representatie
Een parametrische representatie voor diezelfde bol is x = xM + r cosφ cosθ y = yM + r cosφ sinθ z = zM + r sinφ waarbij parameter φ waarden aanneemt uit het interval (–π/2, π/2) en θ uit het interval (–π, π) (zie figuur 1.1).
P( x , y , z )
M ( xM , y M , zM )
φ
θ
FIGUUR 1.1
φ en θ voor parametrische representatie van een bol
OPGAVE 1.1
Beschrijf de mantel van een cilinder met grondvlak in het xz-vlak, hoogte 5, straal van het grondvlak 2, en als middelpunt van het grondvlak het punt (1, 0, 3) met een parametrische representatie. Gekromde oppervlakken van andere objecten zoals een kegel of een torus kunnen op soortgelijke manier met een impliciete of parametrische representatie worden opgeslagen. De opslag van objecten op deze manier kost weinig geheugenruimte, maar is voor slechts een beperkt aantal vormen mogelijk. Het probleem van het beperkte vormdomein kan worden opgelost door gebruik te maken van splines om (delen van) ingewikkeld gekromde oppervlakken te representeren. Representatie van oppervlakken met splines valt buiten het kader van deze inleiding.
Polygoon
16
De representatie van objecten op de bovenbeschreven manier is niet geschikt voor het maken van afbeeldingen met de 3D viewing pipeline. Daarvoor is een benaderende representatie van de oppervlakken van de objecten met polygonen (veelhoeken) geschikter. Een polygoon kan worden opgeslagen als een geordende lijst van n ≥ 3 hoekpunten P1, P2, ..., Pn die in hetzelfde vlak liggen. De zijden van de polygoon zijn dan P1P2, P2P3, ..., Pn–1Pn en PnP1 (zie figuur 1.2).
OUN
Inleiding computer graphics
P5
P1
P1 N
P6
P2
p1 − p 2
P4
P2
P3 FIGUUR 1.2
p3 − p2
P3
Polygoon P1P2 ... Pn met naar buiten gerichte normaalvector N = ( p3 − p2 ) × ( p1 − p2 )
In de polygon rendering pipeline wordt op veel plaatsen gebruik gemaakt van een vlakvergelijking van het vlak waar de polygoon in ligt en van een naar buiten gerichte normaalvector op de polygoon. Daarom worden de coëfficiënten a, b, c en d van de vlakvergelijking ax + by + cz + d = 0 meestal ook opgeslagen.
Vlakvergelijking ax + by + cz + d =0
Normaalvector (a, b, c)T
Om uit de lijst met hoekpunten een naar buiten gerichte normaalvector te kunnen bepalen, worden de hoekpunten altijd van buiten het object af beschouwd en tegen de wijzers van de klok in gedefinieerd (zie figuur 1.2). Laat p1 , p2 , ... pn de plaatsvectoren zijn van de hoekpunten P1, P2, ..., Pn. De naar buiten gerichte normaalvector is dan gelijk aan: N = ( p3 − p2 ) × ( p1 − p2 ) Hierin is het uitwendig product ‘×’ gedefinieerd door: ⎛ x2 y 3 − x3 y 2 ⎞ ⎜ ⎟ x × y = ⎜ x3 y1 − x1 y3 ⎟ ⎜x y −x y ⎟ 2 1⎠ ⎝ 1 2
Er geldt voor de coëfficiënten a, b en c van de vlakvergelijking dat ⎛a⎞ ⎜ ⎟ ⎜b⎟ = N ⎜c⎟ ⎝ ⎠
We hebben hiermee drie van de vier coëfficiënten van de vlakvergelijking gevonden. Door in de vlakvergelijking behalve de gevonden waarden voor a, b en c tevens voor (x, y, z) een van de hoekpunten van het vlak in te vullen, bijvoorbeeld punt P1, kunnen we vervolgens coëfficiënt d berekenen. OPGAVE 1.2
Gegeven zijn de punten A = (2, 3, 1), B = (2, 0, 1) en C = (0, 1, 3). Bepaal een normaalvector van het vlak ABC. Stel een vlakvergelijking op van het vlak waar driehoek ABC in ligt.
OUN
17
Capita selecta wiskunde
In figuur 1.3 is een voorbeeld gegeven van een 3D object, de lijst van coördinaten van hoekpunten en de geordende lijsten van hoekpunten per polygoon (van buiten af gezien tegen de wijzers van de klok in).
hoekpunten
P5
P1 = ( -1, 0 , 1) P2 = ( -1, 0 , - 1) P3 = (1, 0 , - 1) P4 = (1, 0 , 1) P5 = ( 0 , 3 , 0) polygons V1 = P1 P2 P3 P4 V2 = P1 P5 P2
P2
P3
V3 = P2 P5 P3 V4 = P3 P5 P4 V5 = P4 P5 P1
P1
P4
FIGUUR 1.3
Geometrische informatie van een 3D object
OPGAVE 1.3
Waarom wordt de polygoon V1 in figuur 1.3 weergegeven met P1P2P3P4 en niet met P1P4P3P2? Naast de geometrische informatie van de objectoppervlakken in de scène (coördinaten van hoekpunten, lijsten van hoekpunten per polygoon en eventueel de coëfficiënten van vlakvergelijkingen) worden ook materiaaleigenschappen opgeslagen: – kleur van het oppervlak – gladheid van het oppervlak – eventuele textuur (zie paragraaf 4) die op het oppervlak moet worden getoond. 2
Ray tracing
Ray tracing is een methode om afbeeldingen van 3D scènes van hoge kwaliteit te maken. Bij ray tracing worden gekromde objectoppervlakken meestal niet benaderd met polygonen. In plaats daarvan vormt een beschrijving van de objecten met impliciete vergelijkingen of een parameterrepresentatie meestal het uitgangspunt. 2.1
Window
18
BASISPRINCIPE VAN RAY TRACING
Eerst wordt een oogpunt in de scène geplaatst met een of meerdere lichtbronnen. Ook wordt een projectievlak gedefinieerd en in het projectievlak een rechthoekig gebied dat we het window noemen.
OUN
Inleiding computer graphics
Het window wordt verdeeld in beeldpunten, de pixels van een denkbeeldig beeldscherm dat op de plaats van het window komt te staan. Door ieder van de pixels van dit denkbeeldige beeldscherm volgen we een straal de scène in (zie figuur 2.1).
FIGUUR 2.1
Principe van ray tracing
De straal is een rechte lijn door het oogpunt E = (xE, yE, zE) en een pixel P = (xp, yp, zp). De straal kunnen we beschrijven met de vectorvoorstelling: ⎛ x ⎞ ⎛ xE ⎞ ⎛ xP − xE ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ = + y y λ ⎜ yP − yE ⎟ ⎜ ⎟ ⎜ E⎟ ⎜z⎟ ⎜z ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ E⎠ ⎝ zP − zE ⎠
Voor alle objectoppervlakken van de scène berekenen we vervolgens of de straal het objectoppervlak doorsnijdt en zo ja, wat de parameterwaarde voor het snijpunt is. Deze berekeningen leiden ertoe dat we alle parameterwaarden, zeg λ1, λ2, ..., λn, van intersectiepunten van de straal met de oppervlakken van objecten in de scène vinden. De intersectiepunten sorteren we vervolgens op afstand vanaf de waarnemer, door de parameterwaarden te sorteren. Als λi de kleinste parameterwaarde is, dan is het objectoppervlak waarbij deze parameterwaarde hoort, het zichtbare oppervlak in de pixel waar de straal bij hoort. Het zichtbare punt op het objectoppervlak is het punt: ⎛ xE ⎞ ⎛ xP − xE ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ yE ⎟ + λi ⎜ y P − y E ⎟ ⎜z ⎟ ⎜z −z ⎟ E ⎠ ⎝ E⎠ ⎝ P
OUN
19
Capita selecta wiskunde
Voor het zichtbare object zijn materiaaleigenschappen gegeven. Uit deze materiaaleigenschappen, de positie van het zichtbare punt in de scène, de naar buiten gerichte normaalvector op het objectoppervlak in dit punt, en de richtingen vanuit het zichtbare punt naar de lichtbronnen toe wordt met een lichtreflectiemodel (zie paragraaf 3.8) een kleur voor de pixel berekend. Als de straal door een pixel geen enkel objectoppervlak doorsnijdt, dan wordt aan de betreffende pixel de achtergrondkleur toegekend. De rekentijd van het ray-tracingalgoritme wordt bepaald door het aantal beeldpunten (pixels) van de afbeelding, het aantal objectoppervlakken in de scène en de complexiteit van deze oppervlakken. Voor iedere pixel moet namelijk voor ieder objectoppervlak een eventuele intersectie worden vastgesteld en de parameterwaarde voor het intersectiepunt worden berekend. Voor een scène met bijvoorbeeld 1000 oppervlakken waarvan een afbeelding moet worden berekend met een resolutie van 1000 bij 1000 beeldpunten, moet een miljard intersectieberekeningen worden uitgevoerd tussen een straal en een objectoppervlak. Dat is zeker voor complexe objectoppervlakken, zelfs met de rekenkracht van huidige computers een tijdrovende klus en daarom zal in een ray tracer het aantal intersectieberekeningen zoveel mogelijk worden gereduceerd. Bijvoorbeeld door het plaatsen van (groepen van) objecten in bounding volumes met eenvoudige vorm (zoals een bol). Als het bounding volume van een groep objecten niet wordt doorsneden door een straal, dan hoeven voor de individuele objecten uit de groep geen intersectieberekeningen met de straal te worden uitgevoerd, omdat de objectoppervlakken dan niet doorsneden worden. 2.2
SECUNDAIRE STRALEN
Het ray tracing algoritme is eenvoudig uit te breiden tot een methode waarmee afbeeldingen kunnen worden berekend waarin rekening is gehouden met de volgende optische effecten: – slagschaduw – transparantie en breking – weerspiegeling van de omgeving in gladde objectoppervlakken. Vanuit het oogpunt volgden we in paragraaf 2.1 een straal door een pixel van het beeldscherm en berekenden we het snijpunt met het dichtst bij het oog gelegen objectoppervlak. In figuur 2.2, 2.3 en 2.4 is dit een oppervlak van object 2.
Secundaire stralen Primaire stralen
Schaduwstraal
20
De optische effecten worden berekend door vanuit het zichtbare punt van object 2 stralen verder door de ruimte te volgen. De stralen die we verder volgen noemen we secundaire stralen, terwijl we de stralen door de pixels primaire stralen noemen. Om slagschaduw te berekenen volgen we een straal vanuit het zichtbare punt op object 2 richting de lichtbron. We noemen deze straal een schaduwstraal. In figuur 2.2 snijdt deze straal een oppervlak van object 3. Dit betekent dat het punt op object 2 in de slagschaduw ligt van object 3 op object 2 met betrekking tot de betreffende lichtbron. Bij de bepaling van de kleur van de pixel tellen we daarom geen bijdrage van deze lichtbron mee.
OUN
Inleiding computer graphics
FIGUUR 2.2
Gebroken straal
Secundaire stralen voor bepaling van slagschaduw
Om transparantie en brekingseffecten te bepalen volgen we, wanneer object 2 in figuur 2.3 van een transparant materiaal zoals glas is, een straal het transparante materiaal in. De richting is te bepalen uit de brekingsindices van lucht en het materiaal van object 2, met de brekingswet van Snellius. We noemen deze straal een gebroken straal.
FIGUUR 2.3
Secundaire stralen voor bepaling van breking
Van deze secundaire straal bepalen we wederom de snijpunten met alle objectoppervlakken. Het eerste objectoppervlak dat doorsneden wordt, is het oppervlak waar het licht object 2 verlaat. Vanaf dit punt volgen we een secundaire straal verder door de ruimte in een richting, bepaald met de wet van Snellius. Voor deze straal bepalen we vervolgens de snijpunten met objectoppervlakken. Dit proces kan een aantal keer worden herhaald. Hierbij moeten we in de praktijk een grens stellen aan het aantal keer dat vanaf een snijpunt secundaire stralen verder door de ruimte worden gevolgd. Voor iedere secundaire straal berekenen we een bijdrage met het lichtreflectiemodel aan de kleur van de pixel waar de primaire straal bij hoort, en mengen deze bijdrage met de kleur die we hebben bepaald voor de primaire straal. Op deze manier kunnen we objecten in de afbeelding zichtbaar maken die achter transparante materialen liggen.
OUN
21
Capita selecta wiskunde
Gespiegelde straal
Om weerspiegelingen van de omgeving in gladde objectoppervlakken zichtbaar te maken volgen we, wanneer het oppervlak van object 2 in figuur 2.4 van een glimmend materiaal is, een secundaire straal verder door de ruimte. De secundaire straal wordt teruggekaatst via hoek van inval is hoek van terugkaatsing. We noemen deze straal een gespiegelde straal. Voor deze secundaire straal berekenen we wederom de snijpunten met alle objectoppervlakken in de scène. Voor de situatie in figuur 2.4 vinden we dat object 1 doorsneden wordt door de secundaire straal. Aan de kleur voor de pixel dat bij de primaire straal hoort, voegen we nu een bijdrage toe van object 1 door het lichtreflectiemodel (zie paragraaf 3.8) toe te passen. Vanuit het punt op object 1 volgen we eventueel weer een schaduwstraal, een gebroken straal (als object 1 van een transparant materiaal is) en een gereflecteerde straal verder door de ruimte.
FIGUUR 2.4
Secundaire stralen voor bepaling van weerspiegelingen
De berekeningen die moeten worden uitgevoerd voor een secundaire straal zijn dezelfde als die voor een primaire straal. Ook voor een secundaire straal worden de intersectiepunten met objecten in de scène berekend. Bij gebroken stralen en gespiegelde stralen worden de intersectiepunten weer gesorteerd op diepte langs de straal. Secundaire stralen kunnen leiden tot nieuwe secundaire stralen die vanaf het dichtstbijzijnde snijpunt verder door de ruimte gevolgd moeten worden. Dit proces van herhaald volgen van secundaire stralen gaat in theorie door tot in het oneindige. Denk aan het geval dat we een afbeelding willen maken van een ruimte waarin alle wanden perfecte spiegels zijn. In de praktijk stoppen we met het verder volgen van secundaire stralen als een bepaalde diepte is bereikt, ofwel als we een aantal niveaus diep secundaire stralen hebben gevolgd. De bijdrage van secundaire stralen aan de kleur van een pixel wordt naarmate de stralen meer niveaus diep zijn gevolgd, steeds kleiner. Het toevoegen van een aantal niveaus van secundaire stralen heeft gevolgen voor de rekentijd. In plaats van één miljoen stralen bij een afbeelding van 1000 bij 1000 pixels, hebben we te maken met vele miljoenen stralen, want bij een primaire straal horen (maximaal) drie secundaire stralen, waarvan er twee (de gebroken straal en de gespiegelde straal) weer kunnen leiden tot (maximaal) drie secundaire stralen die verder gevolgd moeten worden.
22
OUN
Inleiding computer graphics
2.3
INTERSECTIEBEREKENINGEN
Een cruciaal onderdeel van het ray tracing proces is het uitvoeren van intersectieberekeningen tussen een straal en een objectoppervlak. De complexiteit van de intersectieberekening is sterk afhankelijk van de representatie van het objectoppervlak. Het eenvoudigste object in een ray tracer is een bol. De bol beschrijven we met een impliciete representatie of een parametrische representatie (zie paragraaf 1). Van een bol met middelpunt M en straal r is het zeer eenvoudig te bepalen of de bol wel of niet doorsneden wordt door de straal (lijn in 3D). De bol wordt doorsneden als geldt dat de afstand van het middelpunt van de bol tot de lijn kleiner dan of gelijk is aan de straal van de bol. Is dit het geval, dan kunnen de snijpunten met een eenvoudige berekening worden bepaald. Als we uitgaan van een impliciete representatie van de bol, dus met de vergelijking: (x – xM)2 + (y – yM)2 + (z – zM)2 = r2 en van de vectorvoorstelling ⎛x⎞ ⎛ xE ⎞ ⎛ x P − xE ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ y ⎟ = e + λ ( p − e ) = ⎜ yE ⎟ + λ ⎜ yP − yE ⎟ ⎜z⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ zE ⎠ ⎝ zP − zE ⎠
voor de straal, dan vinden we door substitutie van x, y en z in de vergelijking van de bol de volgende vierkantsvergelijking waaruit λ moet worden bepaald: 2
e + λ( p − e ) − m − r2 = 0
Hierin is m de plaatsvector voor het middelpunt van de bol. OPGAVE 2.1
De waarnemer bevindt zich in de oorsprong van een 3D coördinatenstelsel. Het projectievlak is het vlak z = –10. Een straal gaat voorts door het punt (1, –1, –10). In de scène bevindt zich een bol met straal 5 en het middelpunt in het punt (0, –3, –20). Bereken de intersectiepunten van de bol met de straal. Benaderen van een boloppervlak met platte vlakken is bij ray tracing ongewenst. Niet alleen hebben we dan een benadering van het boloppervlak in plaats van een exacte representatie, de berekeningen die moeten worden uitgevoerd om de bol te ray tracen zijn ook nog eens veel ingewikkelder. We moeten bij een benadering met polygonen namelijk voor iedere polygoon (en dat zijn er veel voor een redelijke benadering van een bol) het snijpunt van een lijn met het vlak waar de polygoon in ligt berekenen, of vaststellen dat de lijn en het vlak evenwijdig zijn. Vervolgens moeten we met behulp van de zijden van de polygoon nog bepalen of het gevonden snijpunt binnen of buiten de polygoon ligt. Voor een enkele polygoon leidt dit al tot meer rekenwerk dan bij de snijpuntberekening van een lijn met een bol. Voor alle polygonen tezamen waarmee het boloppervlak is benaderd, is de rekentijd derhalve een veelvoud van de rekentijd voor de intersectieberekening van een lijn met een bol.
OUN
23
Capita selecta wiskunde
Voor objecten zoals een kubus of een piramide ontkomen we echter niet aan intersectieberekeningen van een straal met een polygoon. Daarom besteden we aan deze intersectieberekening toch enige aandacht. We gaan wederom uit van de vectorvoorstelling van de straal en bepalen voor de polygoon een vlakvergelijking van het vlak waar de polygoon in ligt. Door de x-, y- en z-component van de vectorvoorstelling van de straal in te vullen in de vlakvergelijking, krijgen we een vergelijking in λ waaruit we de parameterwaarde voor het snijpunt kunnen bepalen. Invullen van de gevonden parameterwaarde in de vectorvoorstelling van de lijn levert het snijpunt op. Nu moeten we nog bepalen of het snijpunt met het vlak ook binnen de polygoon ligt. De berekening die daarvoor moet worden uitgevoerd noemen we een punt-in-polygoontest. Deze test kan op verschillende manieren worden uitgevoerd. We laten een methode zien die toepasbaar is voor convexe polygonen. Een punt P ligt in een convex polygoon P1P2... Pn als de som van de hoeken tussen de lijnstukken PP1 en PP2, PP2 en PP3, PP3 en PP4, ..., PPn en PP1 gelijk is aan 360°. Figuur 2.5 laat dit zien voor een convexe vierhoek. In de situatie links is de som van de hoeken 360° omdat de hoekpunten ’rondom’ P liggen. In de situatie rechts liggen de hoekpunten niet ’rondom’ P en is de som van de hoeken niet gelijk aan 360°. P4
P1
P4
P1
α4 P α 1 αα 3 2 P3
P2
P α4 α3 α1 α2
P2
P3
Punt-in-polygoontest: P in P1P2P3P4 ⇔ α1 + α2 + α3 + α4 = 360°
FIGUUR 2.5
De hoek ϕ tussen twee vectoren x en y kan berekend worden met: cosϕ =
( x, y) x⋅ y
In de teller van deze breuk staat het inproduct van de vectoren x en y, in de noemer het product van de lengte van de vectoren. Als bijvoorbeeld x = (1, 3)T en y = (2, 1)T, dan volgt: cosϕ =
1⋅ 2 + 3⋅1 1+ 9 ⋅
4+1
Hieruit volgt weer dat
24
OUN
=
5 = 50
ϕ
= 45°.
1 2
2
Inleiding computer graphics
OPGAVE 2.2
Gegeven is driehoek P1P2P3 met P1 = (–3, 0), P2 = (2, –2) en P3 = (5, 3). Ligt punt P = (3, 2) in deze driehoek? En punt Q = (1, 2)? Het berekenen van de intersectiepunten voor een cilinder is ingewikkelder dan voor een bol. We gaan uit van een impliciete representatie van de cilinder. Behalve de cilindermantel moeten we ook het bovenvlak en het ondervlak van de cilinder representeren (met een vlakvergelijking). Bij de bepaling van de intersectiepunten van de lijn met de cilindermantel moet, indien er intersectiepunten zijn met de onbegrensde cilinder, ook bepaald worden of de intersectiepunten tussen het bovenvlak en het ondervlak liggen. Bij de bepaling van een intersectiepunt met het bovenvlak moet tevens worden vastgesteld of dit intersectiepunt binnen het cirkelvormige gebied ligt dat de bovenkant van de cilinder vormt. Voor het ondervlak moet eenzelfde bepaling plaatsvinden. Voor complexe gekromde oppervlakken, zoals dat van een theepot, een wastafel, een vliegtuigvleugel of een scheepshuid, worden doorgaans representatiemethoden met splineoppervlakken gebruikt. Voor dit soort oppervlakken zijn de intersectieberekeningen veel ingewikkelder dan voor bijvoorbeeld bollen, cilinders of blokken. Er wordt dan vaak gebruik gemaakt van numerieke methoden om de intersectiepunten te benaderen of de complexe gekromde oppervlakken worden benaderd met bijvoorbeeld een netwerk van driehoeken waarvoor vervolgens intersectieberekeningen worden uitgevoerd. 3
De 3D polygon viewing pipeline
Een snel alternatief voor ray tracing is om een verzameling van polygonen als basis te gebruiken en deze af te beelden door middel van de 3D polygon viewing pipeline. We gaan ervan uit dat de oppervlakken van alle objecten uit de scène, zoals in paragraaf 1 besproken, zijn benaderd met platte vlakken (polygonen). Per object of polygoon zijn tevens materiaaleigenschappen opgeslagen, die de kleur en gladheid van het oppervlak bepalen en tevens vaststellen of dit oppervlak is voorzien van een textuur, en zo ja welke. In deze paragraaf zien we hoe vanuit deze interne representatie afbeeldingen kunnen worden berekend van de scène. 3.1
Modeling coördinatenstelsels
Modeling transformaties Wereldcoördinatenstelsel
MODELING TRANSFORMATIES
Ieder object is gedefinieerd in zijn eigen modeling coördinatenstelsel. Exemplaren van deze objecten (primitieven of componenten die uit deze primitieven zijn opgebouwd) worden door middel van transformaties correct gepositioneerd in coördinatenstelsels van grotere componenten, en uiteindelijk in het coördinatenstelsel waarin de gehele scène is gedefinieerd. De transformaties die objecten van het ene modeling coördinatenstelsel in het andere brengen of in het coördinatenstelsel waarin de complete scène is gedefinieerd noemen we modeling transformaties. Het coördinatenstelsel waarin uiteindelijk de gehele scène is gerepresenteerd noemen we het wereldcoördinatenstelsel. De transformaties die op de onderdelen worden uitgevoerd, moeten altijd worden uitgevoerd op punten. Het transformeren van een polygoon gebeurt namelijk door alle hoekpunten van de polygoon te transformeren.
OUN
25
Capita selecta wiskunde
Dit betekent dat we de transformaties kunnen beschrijven door te definiëren hoe een punt (x, y, z) wordt afgebeeld op zijn beeld (x', y', z') onder de betreffende transformatie. Translaties rotaties en schalingen Elementaire transformaties
De soorten modeling transformaties die wij in eerste instantie beschouwen zijn translaties, rotaties en schalingen. Deze elementaire transformaties, zijn translatie over een vector, rotatie om de x-as, y-as of z-as, en schaling met schalingsfactoren in x-, y- en z-richting. Met deze elementaire transformaties kunnen we ingewikkelder transformaties realiseren door een aantal elementaire transformaties achter elkaar uit te voeren. De elementaire transformaties kunnen we definiëren met behulp van vergelijkingen. ⎛ tx ⎞ ⎜ ⎟ – translatie over een vector ⎜ t y ⎟ : ⎜⎜ t ⎟⎟ ⎝ z⎠ ⎛ x ' ⎞ ⎛ x ⎞ ⎛ tx ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ y ' ⎟ = ⎜ y ⎟ + ⎜ ty ⎟ ⎜ z ' ⎟ ⎜ z ⎟ ⎜⎜ ⎟⎟ ⎝ ⎠ ⎝ ⎠ ⎝ tz ⎠
– rotatie over een hoek α om de x-as tegen de wijzers van de klok in: 0 ⎛ x'⎞ ⎛ 1 ⎜ ⎟ ⎜ y α ' 0 cos = ⎜ ⎟ ⎜ ⎜ z ' ⎟ ⎜ 0 sin α ⎝ ⎠ ⎝
0 ⎞⎛ x ⎞ ⎟⎜ ⎟ − sin α ⎟ ⎜ y ⎟ cos α ⎟⎠ ⎜⎝ z ⎟⎠
– rotatie over een hoek α om de y-as tegen de wijzers van de klok in: ⎛ x ' ⎞ ⎛ cos α ⎜ ⎟ ⎜ ⎜ y'⎟ = ⎜ 0 ⎜ z ' ⎟ ⎜ − sin α ⎝ ⎠ ⎝
0 sin α ⎞ ⎛ x ⎞ ⎟⎜ ⎟ 1 0 ⎟⎜ y ⎟ 0 cos α ⎟⎠ ⎜⎝ z ⎟⎠
– rotatie over een hoek α om de z-as tegen de wijzers van de klok in: ⎛ x ' ⎞ ⎛ cos α ⎜ ⎟ ⎜ ⎜ y ' ⎟ = ⎜ sin α ⎜ z' ⎟ ⎜ 0 ⎝ ⎠ ⎝
− sin α cos α 0
0⎞⎛ x ⎞ ⎟⎜ ⎟ 0⎟⎜ y ⎟ 1 ⎟⎠ ⎜⎝ z ⎟⎠
– schaling ten opzichte van de oorsprong met schalingsfactoren sx, sy en sz: ⎛ x ' ⎞ ⎛ sx ⎜ ⎟ ⎜ ⎜ y'⎟ = ⎜ 0 ⎜ z ' ⎟ ⎜⎜ ⎝ ⎠ ⎝0
26
0 sy
0
0 ⎞⎛ x⎞ ⎟⎜ ⎟ 0 ⎟⎜ y⎟ ⎟⎜ ⎟ sz ⎟⎠ ⎝ z ⎠
OUN
Inleiding computer graphics
Positieve rotatierichting
Bij de rotaties is de positieve rotatierichting, gezien vanaf de positieve as richting oorsprong, altijd tegen de wijzers van de klok in. De rotaties en schaling worden geschreven als een matrixvectorvermenigvuldiging, terwijl de translatie wordt geschreven als een vectoroptelling. Het feit dat de translatie als een vectoroptelling wordt geschreven heeft tot gevolg dat we samengestelde transformaties (combinaties van translaties, rotaties en schalingen) niet met een 3 bij 3 matrix kunnen representeren. Combinaties van rotaties en schalingen kunnen zoals het onderstaande voorbeeld laat zien, wel worden gerepresenteerd met een matrix. VOORBEELD
De matrix voor een schaling met schalingsfactoren 1, 2 en 1 gevolgd door een rotatie om de x-as over 90°, kan als volgt met een matrix worden gerepresenteerd. De matrix voor de schaling kunnen we schrijven als:
S1,2 ,1
⎛1 0 0⎞ ⎜ ⎟ = ⎜0 2 0⎟ ⎜0 0 1⎟ ⎝ ⎠
en die voor de rotatie als
Rx,90°
⎛1 0 0 ⎞ ⎜ ⎟ = ⎜ 0 0 −1 ⎟ ⎜0 1 0 ⎟ ⎝ ⎠
De matrix M voor de gevraagde combinatie van elementaire transformaties is dan: ⎛ 1 0 0 ⎞⎛ 1 0 0 ⎞ ⎛ 1 0 0 ⎞ ⎜ ⎟⎜ ⎟ ⎜ ⎟ M = Rx,90° ⋅ S1,2 ,1 = ⎜ 0 0 −1 ⎟⎜ 0 2 0 ⎟ = ⎜ 0 0 −1 ⎟ ⎜ 0 1 0 ⎟⎜ 0 0 1 ⎟ ⎜ 0 2 0 ⎟ ⎝ ⎠⎝ ⎠ ⎝ ⎠
Merk op dat de matrix van de transformatie die het eerst moet worden uitgevoerd achteraan staat.
Homogene coördinaten
Om translaties te kunnen combineren met rotaties en schalingen, en het resultaat dan te representeren met een matrix, maken we in het vervolg gebruik van homogene coördinaten. De homogene coördinaat biedt ons de mogelijkheid om ook de translatie te representeren met een matrix en daarmee combinaties van translaties, rotaties en schalingen. Later zullen we zien dat ook bij de projectiestap de homogene coördinaten nodig zijn. Onze 3D punten breiden we uit met een vierde coördinaat, de homogene coördinaat, waarvoor we de letter h zullen gebruiken. Een punt (x, y, z, h) in homogene coördinaten correspondeert met ⎛x y z⎞ ⎜ , , ⎟ ⎝h h h⎠
OUN
27
Capita selecta wiskunde
in ons 3D coördinatenstelsel. In feite correspondeert ieder punt (λx, λy, λz, λ) in homogene coördinaten met hetzelfde punt (x, y, z) in ons 3D coördinatenstelsel. In homogene coördinaten is (λx, λy, λz, λ) een lijn door de oorsprong en het punt (x, y, z, 1). Een lijn door de oorsprong in homogene coördinaten correspondeert daarom met een punt in het 3D coördinatenstelsel. Als we een punt (x, y, z) moeten transformeren, dan gaan we als volgt te werk. We vervangen het 3D punt door een punt in homogene coördinaten dat op de lijn van punten (λx, λy, λz, λ) ligt. We mogen in principe λ willekeurig kiezen, mits we λ niet gelijk aan 0 nemen. We kiezen λ = 1. Ons punt in homogene coördinaten wordt dan (x, y, z, 1). De 4D plaatsvector van dit punt vermenigvuldigen we met de matrix M die de elementaire of samengestelde transformatie voorstelt. Het beeld heeft weer homogene coördinaat 1: ⎛ x'⎞ ⎛x⎞ ⎜ y'⎟ ⎜ ⎟ ⎜ ⎟ = M⎜y⎟ ⎜ z' ⎟ ⎜z⎟ ⎜⎜ 1 ⎟⎟ ⎜⎜ 1 ⎟⎟ ⎝ ⎠ ⎝ ⎠
Het beeld van (x, y, z) onder de transformatie M is (x', y', z'). De vraag is: ’Hoe ziet de matrix M voor de elementaire transformaties eruit?’ M is geen 3 bij 3 matrix, want dan kunnen we M niet met een 4D vector vermenigvuldigen. Het antwoord op de vraag is dat we de rotatieen schalingsmatrices moeten uitbreiden met een extra rij en een kolom tot een 4 bij 4 matrix, waarbij in de extra rij en kolom nullen staan met uitzondering van het element op de hoofddiagonaal dat gelijk aan 1 moet zijn:
rotatie om x-as: Rx − as
rotatie om y-as: Ry − as
rotatie om z-as: Rz − as
28
OUN
0 ⎛1 ⎜ 0 cos α =⎜ ⎜ 0 sin α ⎜⎜ 0 ⎝0
⎛ cos α ⎜ 0 =⎜ ⎜ − sin α ⎜⎜ ⎝ 0 ⎛ cos α ⎜ sin α =⎜ ⎜ 0 ⎜⎜ ⎝ 0
0
− sin α cos α 0
0 sin α 1 0 0 cos α 0 − sin α cos α 0 0
0 0 0 1 0
0⎞ 0 ⎟⎟ 0⎟ ⎟ 1 ⎟⎠
0⎞ 0 ⎟⎟ 0⎟ ⎟ 1 ⎟⎠ 0⎞ 0 ⎟⎟ 0⎟ ⎟ 1 ⎟⎠
Inleiding computer graphics
schaling: Ss
x , sy , sz
⎛ sx ⎜0 =⎜ ⎜0 ⎜ ⎜0 ⎝
0 sy
0 0
0 0
sz 0
0⎞ 0 ⎟⎟ 0⎟ ⎟ 1 ⎟⎠
Nu rest nog de translatie die in 3D een vectoroptelling was. In homogene coördinaten plaatsen we de translatievector in de laatste kolom van de 4 bij 4 matrix:
translatie: Tt
x ,t y ,t z
⎛1 ⎜0 =⎜ ⎜0 ⎜ ⎜0 ⎝
0 0 tx ⎞ 1 0 t y ⎟⎟ 0 1 tz ⎟ ⎟ 0 0 1 ⎟⎠
Een punt (x, y, z) kunnen we dus transleren door de volgende vermenigvuldiging uit te voeren: ⎛ x'⎞ ⎛ 1 ⎜ y'⎟ ⎜0 ⎜ ⎟=⎜ ⎜ z' ⎟ ⎜0 ⎜⎜ ⎟⎟ ⎜⎜ ⎝ 1 ⎠ ⎝0
0 0 tx ⎞ ⎛ x ⎞ 1 0 t y ⎟⎟ ⎜ y ⎟ ⎜ ⎟ 0 1 tz ⎟ ⎜ z ⎟ ⎟⎜ ⎟ 0 0 1 ⎟⎠ ⎜⎝ 1 ⎟⎠
Uitwerking van de vermenigvuldiging toont aan dat dit overeenkomt met de translatieformules: x' = x + tx y' = y + ty z' = z + tz
Spiegeling in een vlak
Samengestelde transformaties
Uit de elementaire transformaties (translatie, rotatie om x-, y- of z-as en schaling) kunnen we iedere transformatie verkrijgen die we op een object willen uitvoeren om het object op de juiste plaats, in de juiste oriëntatie en op de juiste afmetingen te krijgen. Eén soort transformatie zal hier nog apart enige aandacht krijgen, namelijk de spiegeling in een vlak. Een spiegeling in het xy-vlak kan worden verkregen door de z-coördinaat van punten van het te transformeren object met –1 te vermenigvuldigen. Een spiegeling in het xy-vlak is derhalve niets anders dan een schaling met schalingsfactor –1 in de z-richting. Evenzo kunnen we spiegelen in het xzvlak door een schaling met factor –1 in de y-richting en spiegelen in het yzvlak door een schaling met factor –1 in de x-richting. Andere transformaties die we op objecten willen uitvoeren kunnen we altijd opbouwen uit een aantal elementaire transformaties. We noemen ze samengestelde transformaties. Het volgende voorbeeld illustreert dit.
OUN
29
Capita selecta wiskunde
VOORBEELD
Voor de eenvoud kijken we naar een 2D situatie. We gebruiken voor 2D transformaties 3D homogene coördinaten, zoals we voor 3D transformaties 4D homogene coördinaten hebben gebruikt. We willen een spiegeling in de lijn l: 3x – 4y + 2 = 0 representeren met een 3 bij 3 matrix. Hoe kunnen we deze matrix opbouwen door de transformatiematrices van een aantal elementaire 2D transformaties met elkaar te vermenigvuldigen? In figuur 3.1 zien we de lijn l en een driehoek ABC die in die lijn gespiegeld wordt met als beeld A'B’C’.
α
FIGUUR 3.1
Spiegeling in de lijn l: y =
3
4x
+
1
2
De lijn kan ook geschreven worden als y = 3 4 x + 1 2 en heeft daarom een richtingscoëfficiënt tanα = 3 4 . Door gebruik van de stelling van Pythagoras kunnen we bepalen dat sinα = 3 5 en cosα = 4 5 . We bouwen de transformatie nu op uit de volgende elementaire transformaties: – T0 ,− 1 2
Deze translatie past het assenstelsel aan zodanig dat de lijn door de oorsprong gaat van het nieuwe stelsel. – R–α Deze rotatie past het assenstelsel aan zodanig dat de x-as van het nieuwe stelsel samenvalt met de lijn l. – S1,–1 De spiegeling wordt nu uitgevoerd in de x-as van het nieuwe assenstelsel. – Rα Deze rotatie past het assenstelsel aan zodanig dat de x-as weer zijn oude oriëntatie krijgt. – T0 , 1 2
30
OUN
Inleiding computer graphics
Deze translatie past het assenstelsel aan zodanig dat de x-as weer zijn oude positie krijgt. Er geldt nu voor de spiegeling in de lijn l: Spl = T0 , 1 ⋅ Rα ⋅ S1,−1 ⋅ R−α ⋅ T0 ,− 1 2
2
Alle vijf de transformaties waaruit de spiegeling is opgebouwd zijn eenvoudig te representeren met een 3 bij 3 matrix. Dit geldt ook voor de rotaties aangezien sinα en cosα bekend zijn. Na enig rekenwerk volgt: ⎛ 0.28 0.96 −0.48 ⎞ ⎜ ⎟ Spl = ⎜ 0.96 −0.28 0.64 ⎟ ⎜ 0 0 1 ⎟⎠ ⎝ OPGAVE 3.1
Ga na dat de hierboven gegeven matrix inderdaad de matrix is van de spiegeling in de lijn l. OPGAVE 3.2
Bereken een matrix voor de 2D rotatie om het punt (2, 3) over –90°. OPGAVE 3.3
Gegeven is dat driehoek ABC met A = (2, 2), B = (5, 2) en C = (4, 4) door een transformatie met matrix M wordt afgebeeld op driehoek A'B'C' met A' = (3, 6), B' = (6, 6) en C' = (5, 10). Hierbij wordt X op X' afgebeeld voor X = A, B, C. Bepaal de matrix M. Aanwijzing: zet de drie punten A, B en C (aangevuld met homogene coördinaat 1) in de drie kolommen van een matrix X = (A, B, C). Doe hetzelfde met de drie punten A’, B’ en C’, ofwel X' = (A, B, C). De matrix M is nu de oplossing van X' = MX. We hebben nu gezien hoe we objecten die gedefinieerd zijn in hun eigen modeling coördinatenstelsel, kunnen transformeren naar het wereldcoördinatenstelsel. 3.2
3D viewing transformatie
DE 3D VIEWING TRANSFORMATIE
Na de modeling transformaties is de gehele scène gerepresenteerd in het wereldcoördinatenstelsel met basis x, y, z. We voeren nu een transformatie uit op de gehele scène, de 3D viewing transformatie, die de scène overvoert naar een coördinatenstelsel, waarin de waarnemer kijkt langs de z-as, vanaf de oorsprong in de richting van de negatieve z-as (zie figuur 3.2). Door het uitvoeren van deze transformatie kunnen latere stappen uit de pipeline, waaronder de projectie (zie paragraaf 3.3) en de hidden surface removal (zie paragraaf 3.5), eenvoudiger worden uitgevoerd.
OUN
31
Capita selecta wiskunde
Viewing parameters: COP, VRP, vuv
Projectievlak
De eenheidsvectoren in de x-, y- en z-richting van het viewing coördinatenstelsel zullen we in het vervolg u, v en w noemen. Om de transformatiematrix te bepalen moeten we weten op welke positie (in wereldcoördinaten) de waarnemer zich bevindt, in welke richting de waarnemer kijkt, en welke richting in de 2D afbeelding naar boven toe gericht is. Deze informatie wordt gedefinieerd door de volgende viewing parameters: COP (center of projection; oogpunt), VRP (view reference point; punt waarnaar we kijken) en vuv (view up vector; vector die definieert welke richting de bovenkant wordt in de afbeelding). Het projectievlak wordt het vlak loodrecht op de kijkrichting (van COP naar VRP). We plaatsen het projectievlak zodanig dat VRP in dit vlak ligt.
Wereldcoördinaten en viewing coördinaten
FIGUUR 3.2
Viewing coördinatenstelsel
Een basis u, v, w van ons nieuwe viewing coördinatenstelsel, waarin de waarnemer langs de z-as kijkt, definiëren we als volgt (uitgedrukt in wereldcoördinaten): – w is de vector met lengte 1 gericht van VRP naar COP – u is de vector met lengte 1, loodrecht op w en vuv, gedefinieerd door u = vuv × w – v is de vector met lengte 1, loodrecht op w en u, gedefinieerd door v = w × u. De 3D viewing transformatie kunnen we nu opbouwen uit een translatie T–COP, die de oorsprong van het viewing coördinatenstelsel naar de oorsprong van het wereldcoördinatenstelsel brengt en een samengestelde rotatie R, die de assen van het viewing coördinatenstelsel laat samenvallen met de assen van het wereldcoördinatenstelsel. De rotatiematrix volgt direct uit de basis u, v, w, namelijk: ⎛ ux ⎜ ⎜ vx R=⎜ ⎜ wx ⎜ 0 ⎝
32
uy
uz
vy
vz
wy
wz
0
0
OUN
0⎞ ⎟ 0⎟ 0 ⎟⎟ 1 ⎟⎠
Inleiding computer graphics
Immers, de rotatie met matrix R beeldt u af op de eenheidsvector (1, 0, 0)T in de x-richting in wereldcoördinaten, v op (0, 1, 0)T en w op (0, 0, 1)T. OPGAVE 3.4
Controleer dat u, v en w inderdaad worden afgebeeld op (1, 0, 0)T, (0, 1, 0)T en (0, 0, 1)T. Matrix voor de 3D viewing transformatie
De matrix voor de 3D viewing transformatie is nu gelijk aan R · T–COP. 3.3
Perspectiefprojectie Parallelprojectie
PROJECTIE
Vervolgens moet de scène geprojecteerd worden op het projectievlak, dat loodrecht geplaatst is op de kijkrichting (van COP naar VRP). We nemen aan dat we een perspectiefprojectie willen uitvoeren. We hadden immers het oogpunt COP op eindige afstand geplaatst van de scène en een parallelprojectie kan worden beschouwd als een bijzonder geval van een perspectiefprojectie, namelijk met een oogpunt op oneindige afstand van de scène, zodat alle projectoren evenwijdig lopen. Als het oogpunt op eindige afstand staat van de scène dan komen alle projectoren, waarlangs punten in de scène geprojecteerd worden op het projectievlak, samen in het oogpunt (zie figuur 3.3).
FIGUUR 3.3
Perspectiefprojectie
Ook de perspectiefprojectie representeren we met een matrix. Het projectievlak heeft in viewing coördinaten de vergelijking w = –d, waarbij d de afstand is van COP naar VRP en dus ook de afstand van het oogpunt naar het projectievlak. De projector door een te projecteren punt P = (uP, vP, wP) en COP heeft de vectorvoorstelling: ⎛u⎞ ⎛ uP ⎞ ⎜ ⎟ ⎜ ⎟ = λ v ⎜ ⎟ ⎜ vP ⎟ ⎜w⎟ ⎜ ⎟ ⎝ ⎠ ⎝ wP ⎠
OUN
33
Capita selecta wiskunde
Immers, COP is de oorsprong van het viewing coördinatenstelsel en de lijn gaat dus door de oorsprong van het viewing coördinatenstelsel. Het snijpunt van deze projector met het projectievlak vinden we door de w = –d in te vullen in derde vergelijking w = λwP van de vectorvoorstelling. We vinden
λ=−
d wP
Na invullen van deze waarde van λ in de eerste en de tweede vergelijking van de vectorvoorstelling vinden we de u- en v-coördinaat van het snijpunt van de projector met het projectievlak: u=
− duP − dvP ,v= wP wP
en natuurlijk is w=
− dwP = −d wP
We willen de perspectieftransformatie representeren met een 4 bij 4 matrix in homogene coördinaten. Daarom herschrijven we de vergelijkingen met homogene coördinaat h = − wP d als u ' = uP v ' = vP w ' = wP h=
− wP d
Dit is in vector matrixnotatie te schrijven als ⎛ u' ⎞ ⎛ 1 ⎜ v' ⎟ ⎜0 ⎜ ⎟=⎜ ⎜ w'⎟ ⎜0 ⎜⎜ ⎟⎟ ⎜⎜ ⎝ h ⎠ ⎝0
0 0 1 0 0 1 0 − 1d
0 ⎞ ⎛ uP ⎞ 0 ⎟⎟ ⎜⎜ vP ⎟⎟ 0 ⎟ ⎜ wP ⎟ ⎟⎜ ⎟ 0 ⎟⎠ ⎜⎝ 1 ⎟⎠
De homogene coördinaat h is nu niet 1. Daarom moeten we om het 3D punt te vinden waarop (uP, vP, wP) wordt afgebeeld, delen door de homogene coördinaat, ofwel: u' v ' w ' ⎞ (u, v, w) = ⎛⎜ , , ⎟ ⎝h h h ⎠
34
OUN
Inleiding computer graphics
Matrix voor de perspectiefprojectie
We hebben een matrix voor de perspectiefprojectie gevonden. Deze is gelijk aan: ⎛1 ⎜0 M =⎜ ⎜0 ⎜⎜ ⎝0
0
0
1
0
0
1
0⎞ 0 ⎟⎟ 0⎟ ⎟ 0 ⎟⎠
0 − 1d
Deze matrix kan worden gebruikt voor alle punten uit de scène die moeten worden geprojecteerd. Het resultaat van de vermenigvuldiging van de matrix voor perspectiefprojectie met (up, vp, wp, 1)T, moet nog gedeeld worden door h = − wP d , om de coördinaten van het punt in het projectievlak te vinden. Deze deling moet afzonderlijk worden uitgevoerd voor ieder te projecteren punt, immers wp, en daarmee h, heeft voor ieder te projecteren punt een andere waarde. 3.4
Window
CLIPPING
We hebben in paragraaf 3.2 de viewing parameters COP, VRP en vuv gedefinieerd. Deze parameters bepalen de viewing transformatie volledig. Er is echter nog niet vastgelegd hoe groot het gedeelte van het projectievlak is dat uiteindelijk moet worden afgebeeld op het beeldscherm. Dit gedeelte van het projectievlak noemen we het window (zie figuur 3.4). We leggen het window vast door het definiëren van de linkergrens, rechtergrens, ondergrens en bovengrens van dit window: – windowgrenzen xwmin, xwmax, ywmin en ywmax ywmax
ywmin
xwmin
FIGUUR 3.4
xwmax Window in het projectievlak
Ook definiëren we een vlak dat dicht voor de waarnemer staat en evenwijdig is aan het projectievlak en een vlak dat ver van de waarnemer afstaat en eveneens evenwijdig is aan het projectievlak: Near plane Far plane
View volume
– near plane z = znear – far plane z = zfar Deze extra viewing parameters bepalen het gedeelte van de 3D ruimte dat op het scherm afgebeeld zal worden. We noemen dit volume het view volume. Het view volume heeft de vorm van een afgeknotte piramide (zie figuur 3.5).
OUN
35
Capita selecta wiskunde
FIGUUR 3.5
Clipping
Window, near plane, far plane en view volume
De 3D grafische informatie die zich buiten het view volume uitstrekt, hoeft niet te worden geprojecteerd en wordt daarom verwijderd. Dit proces noemen we clipping. Clipping komt erop neer dat polygonen die geheel buiten het view volume liggen, verwijderd worden en polygonen die gedeeltelijk buiten het view volume vallen, vervangen worden door kleinere polygonen die tegen de randen van het view volume zijn ‘afgeknipt’. Het lijkt handig om de clipping stap na de perspectiefprojectie uit te voeren tegen het window, dus in 2D. Dit is echter niet het geval omdat we dan het deel van de scène dat zich voor het near plane of achter het far plane bevindt, in de afbeelding zouden terugzien. Ook het deel van de grafische informatie dat zich achter de waarnemer bevindt, zou geprojecteerd worden binnen het window en daarom gedeeltelijk zichtbaar worden. Dat laatste is duidelijk niet de bedoeling. De clipping stap moeten we daarom uitvoeren in 3D. Het lijkt nu noodzakelijk om de clipping voor de perspectiefprojectie uit te voeren. Dat doen we echter niet. In plaats daarvan bewaren we na de perspectiefprojectie de oude z-coördinaat, welke belangrijk is bij het clippen. De z-coördinaat zal bovendien verderop in het afbeeldingsproces nog gebruikt worden om te bepalen welke polygonen zichtbaar moeten zijn in de afbeelding. Dat is het geval als meerdere polygonen op hetzelfde gedeelte van het projectievlak worden afgebeeld en zich daarom vanuit de waarnemer gezien achter elkaar bevinden (zie paragraaf 3.7). De perspectiefprojectie met behoud van de oude z-coördinaat vervormt het view volume (de afgeknotte piramide) tot een rechthoekig blok (zie figuur 3.6). Tegen dit rechthoekige blok clippen we de 3D polygonen.
FIGUUR 3.6
36
View volume voor en na perspectiefprojectie
OUN
Inleiding computer graphics
3.5
Draadmodelafbeelding
DE WINDOW TO VIEWPORT TRANSFORMATIE
Indien we afbeeldingen van de 3D scène willen maken waarin alle zijden van alle polygonen worden getoond, dus ook de gedeelten die in werkelijkheid verborgen zijn achter vlakken van het model, dan spreken we van een draadmodelafbeelding. Voor dit type afbeelding hoeven we alleen nog de hoekpunten van alle polygonen te transformeren naar schermcoördinaten en vervolgens alle zijden van alle polygonen als lijnstukken af te beelden op het scherm. Figuur 3.7 toont een voorbeeld van een draadmodelafbeelding van een kubus. We zien van de kubus zowel de vlakken die zich aan de voorkant bevinden, als de vlakken aan de achterkant.
FIGUUR 3.7
Viewport
Draadmodelafbeelding van een kubus
Voor een dergelijke afbeelding moeten we nog definiëren waar de afbeelding op het scherm komt te staan. De rechthoek op het scherm waar we het window op afbeelden noemen we het viewport. Het viewport wordt gedefinieerd door de linkergrens, rechtergrens, ondergrens en bovengrens: - viewportgrenzen xvmin, xvmax, yvmin en yvmax
y vmax
ywmax window to viewport transformatie
ywmin
xwmin
FIGUUR 3.8
Window to viewport transformatie Schermcoördinatenstelsel
window
xwmax
y vmin xvmin
viewport
x vmax
Window to viewport transformatie
De transformatie die het window op het viewport afbeeldt, noemen we de window to viewport transformatie (zie figuur 3.8). Het coördinatenstelsel waarin het viewport is gedefinieerd is het schermcoördinatenstelsel. De bovenstaande figuur laat zien dat door afbeelding van het window op het viewport de afbeelding, indien de verhouding lengte staat tot breedte van window en viewport niet gelijk is, een inhomogene schaling kan ondergaan.
OUN
37
Capita selecta wiskunde
Matrix voor de window to viewport transformatie
Zijn de window- en viewportgrenzen bekend, dan kunnen we een matrix opstellen voor de window to viewport transformatie. We bouwen hiertoe de window to viewport transformatie op uit de volgende transformaties: – een translatie die de linkerbenedenhoek van het window naar de oorsprong brengt – een schaling die de afmetingen van het window laat overgaan in de afmetingen van het viewport – een translatie die het linker benedenhoekpunt van het viewport vanuit de oorsprong naar de juiste plaats in het schermcoördinatenstelsel brengt. OPGAVE 3.5
Een window to viewport transformatie is bepaald door een window met grenzen (xwmin, xwmax, ywmin, ywmax) = (40, 120, –20, 80) en een viewport met grenzen (xvmin, xvmax, yvmin, yvmax) = (0.0, 0.4, 0.2, 0.6). Op welk punt wordt het punt (60, 20) afgebeeld door deze window to viewport transformatie? 3.6
SCANCONVERSIE
We hebben nu de objecten waaruit de scène is opgebouwd vanuit het modeling coördinatenstelsel waarin ze zijn gedefinieerd, getransformeerd naar schermcoördinaten. Voor draadmodelafbeeldingen hoeven alleen nog de zijden van de polygonen als lijnstukken te worden afgebeeld. Pixels
Vectorrepresentatie Rasterrepresentatie
Scanconversie
Beeldschermen zijn opgebouwd uit beeldpunten, die we ook wel pixels (afkorting van picture element) noemen. Een afbeelding kan worden beschouwd als een rechthoek van pixels. Voor iedere pixel moet een kleur worden bepaald. In schermcoördinaten weten we de coördinaten van de eindpunten van de lijnstukken die afgebeeld moeten worden. Een representatie van een lijnstuk door middel van de coördinaten van de eindpunten noemen we een vectorrepresentatie. De vectorrepresentatie moet worden omgezet naar een rasterrepresentatie: een verzameling van pixels die de kleur van het lijnstuk moeten krijgen. De omzetting van grafische primitieven van vectorrepresentatie naar rasterrepresentatie noemen we scanconversie (zie figuur 3.9).
FIGUUR 3.9
38
Scanconversie
OUN
Inleiding computer graphics
Scanconversie moet niet alleen worden uitgevoerd bij het afbeelden van lijnstukken, maar bijvoorbeeld ook bij het afbeelden van polygonen die we met ingekleurd binnengebied willen afbeelden. Uit de representatie van de polygoon als geordende lijst van hoekpunten moeten we bepalen welke pixels zich binnen de polygoon bevinden en deze pixels moeten de kleur van de polygoon krijgen. 3.7
HIDDEN SURFACE REMOVAL
Voor het maken van draadmodelafbeeldingen zijn alle stappen uit de polygoon viewing pipeline nu behandeld. Echter, wanneer we afbeeldingen willen maken waarin de objectoppervlakken ingekleurd worden afgebeeld, dan moeten nog enkele stappen extra worden uitgevoerd. Deze extra stappen worden behandeld in paragraaf 3.7 t/m 3.9. Zij worden niet sequentieel uitgevoerd, maar zijn tezamen met de scanconversie, afhankelijk van welke methode wordt gebruikt, met elkaar verweven.
Hidden surface removal
De eerste stap die extra uitgevoerd moet worden wanneer we afbeeldingen met ingekleurde vlakken willen weergeven, is de zogenaamde hidden surface removal. Deze stap zorgt ervoor dat bij (in schermcoördinaten) overlappende vlakken alleen de vlakken die het dichtst bij de waarnemer zijn, zichtbaar worden in de afbeelding. Als voorbeeld beschouwen we een kubus waar, op een hoek, een kleinere kubus is uitgesneden. Als we dit model afbeelden door alle polygons in willekeurige volgorde te scanconverteren, dan worden veel pixels meerdere keren gekleurd, omdat zij binnen de begrenzing van meerdere polygons van het model liggen. Daardoor zal het uiteindelijke resultaat van de volgorde van de polygons afhangen. De afbeelding van het object waarvan een draadmodel wordt getoond in figuur 3.10a zou er bij afbeelden van de polygons in willekeurige volgorde, uit kunnen zien als in figuur 3.10b. Om de correcte afbeelding, zoals in figuur 3.10c te verkrijgen, moeten we hidden surface removal toepassen. Hidden surface removal is niet zozeer het verwijderen van verborgen vlakken, maar beter is om het te beschrijven als ‘het bepalen en afbeelden van de zichtbare polygons en delen van polygons’. a
FIGUUR 3.10
b
c
Hidden surface removal
OUN
39
Capita selecta wiskunde
Backface removal of backface culling
Een goede start bij het oplossen van het probleem van hidden surface removal bestaat uit het verdelen van de polygons in voorvlakken en achtervlakken. Een voorvlak is een vlak waarvan de naar buiten gerichte normaalvector op het objectoppervlak, naar de waarnemer toe wijst. Een achtervlak is een vlak waarvan de naar buiten gerichte normaalvector op het objectoppervlak, van de waarnemer af wijst. Bepalen of een vlak een voorvlak of een achtervlak is geschiedt door een vector in de kijkrichting te bepalen (VRP – COP) en het inwendig product van deze vector met de naar buiten gerichte normaalvector te berekenen. Als het inwendig product kleiner dan 0 is, dan is het vlak een voorvlak. Als het inwendig product groter dan of gelijk aan 0 is, dan is het vlak een achtervlak. Achtervlakken kunnen nooit geheel of gedeeltelijk zichtbaar worden in de afbeelding. Daarom laten we alle achtervlakken buiten beschouwing bij de verdere berekening van de afbeelding. We noemen dit backface removal of ook wel backface culling. Door de backface removal zullen we gemiddeld de helft van de polygons uitsluiten van verdere berekeningen. Deze reductie van het aantal polygons heeft tot gevolg dat we sneller een afbeelding kunnen uitrekenen. Het probleem van hidden surface removal hebben we echter nog niet opgelost door de backface removal. De vlakken die we overhouden (de voorvlakken) kunnen geheel zichtbaar, geheel onzichtbaar of gedeeltelijk zichtbaar zijn. Toepassen van een hidden-surface–removal-algoritme blijft daarom noodzakelijk. Alleen in het zeer eenvoudige geval dat het model uit slechts één object bestaat, en dit object convex is, is het probleem van hidden surface removal al volledig opgelost door de backface removal.
z-buffer of depth buffer algoritme
Er zijn verschillende (klassen van) hidden-surface–removal-algoritmen waarvan we alleen het belangrijkste algoritme beschouwen. Dit algoritme, het z-buffer of depth buffer algoritme genaamd, is in huidige grafische kaarten van computersystemen geïmplementeerd in hardware. Het is conceptueel eenvoudig en doordat z-buffering geïmplementeerd is in hardware, is het ook nog eens erg snel. Huidige computers kunnen miljoenen polygons per seconde ingekleurd afbeelden, waardoor realtimetoepassingen van 3D computer graphics zoals virtual reality en computer games mogelijk zijn geworden. Het z-buffer (depth buffer) algoritme werkt als volgt: twee buffers worden bijgehouden. De eerste buffer is de kleurbuffer, ter grootte van de te maken afbeelding, waarin de tot op een bepaald moment berekende kleuren van pixels worden bijgehouden. De tweede buffer is de dieptebuffer. Hierin wordt per pixel de diepte bijgehouden van de polygoon dat tot op een bepaald moment het dichtst bij de waarnemer ligt. Polygoon voor polygoon wordt gescanconverteerd en voor iedere pixel binnen de gescanconverteerde polygoon wordt de diepte (z-coördinaat) van de polygoon voor de betreffende pixel (x, y) bepaald uit de vlakvergelijking ax + by + cz + d = 0. Als deze diepte kleiner is dan de diepte die voor de betreffende pixel in de dieptebuffer was opgeslagen, dan wordt de kleur van de polygoon op positie (x, y) in de kleurbuffer opgeslagen en de diepte van de polygoon in de dieptebuffer op positie (x, y). Nadat alle polygons op deze manier gescanconverteerd zijn en verwerkt in de dieptebuffer en de kleurbuffer bevat de kleurbuffer de afbeelding van de 3D scène.
40
OUN
Inleiding computer graphics
OPGAVE 3.6
Bij uitvoering van het z-buffer algoritme moet voor rijen van pixels op het beeldscherm, die we spans noemen, de diepte van de polygoon worden bepaald. De diepteberekening moet op een efficiënte manier gebeuren. Als de diepte z0 voor pixel (x0, y0) al berekend is, dan kan de diepte z'0 voor pixel (x0 + 1, y0) naast pixel (x0, y0) op dezelfde span, worden berekend met de optelling z'0 = z0 + inc. Wat is de vaste waarde inc, uitgedrukt in de coëfficiënten van de vlakvergelijking, die bij iedere volgende pixel op de span bij de voorgaande z-waarde moet worden opgeteld? 3.8
EEN EENVOUDIG LICHTREFLECTIEMODEL
In de beschrijving van het z-buffer algoritme was sprake van het opslaan van de kleur van een polygoon in de kleurbuffer. Bij iedere polygoon is als materiaaleigenschap de kleur opgeslagen en deze kleur zouden we in de kleurbuffer kunnen plaatsen als een polygoon in een pixel zichtbaar blijkt te zijn. Deze methode kan echter leiden tot afbeeldingen waarin een geheel object in één kleur wordt afgebeeld, waardoor we in feite alleen de contour van het object te zien krijgen en geen indruk krijgen van de exacte oriëntatie van de polygonen waaruit het objectoppervlak bestaat, zoals in figuur 3.11b voor een kubus met draadmodel in figuur 3.11a is te zien. a
FIGUUR 3.11
b
c
Lichtreflectiemodel
Veel realistischer afbeeldingen krijgen we door een of meerdere lichtbronnen in de scène te plaatsen en uit de materiaaleigenschappen en de hoek waaronder het licht van de lichtbron op een objectoppervlak valt te berekenen wat de exacte kleur van (een punt op) een objectoppervlak is, zoals in figuur 3.11c is gedaan. In de werkelijke wereld hebben objecten een kleur doordat licht dat op het objectoppervlak valt gedeeltelijk wordt weerkaatst en geabsorbeerd. De kleur die we waarnemen wordt bepaald door de samenstelling (hoeveelheden van verschillende golflengtes) van het licht dat op het object valt, en door de materiaaleigenschappen die bepalen welke percentages van welke golflengtes in welke richtingen worden gereflecteerd. De hoeveelheid door een objectoppervlak naar de waarnemer toe gereflecteerd licht, benaderen we met een eenvoudig empirisch lichtreflectiemodel. Componenten van het lichtreflectiemodel
Het lichtreflectiemodel dat we gebruiken om de kleuren van een objectoppervlak te berekenen bestaat uit een drietal componenten: – de ambient component – de diffuse reflectie component – de spiegelende reflectie component.
OUN
41
Capita selecta wiskunde
Puntlichtbron
Het lichtreflectiemodel gaat uit van een of meer lichtbronnen die zich in de scène bevinden. We gebruiken alleen puntlichtbronnen, dat wil zeggen lichtbronnen waarvan het licht uitzendende oppervlak door de geringe afmeting van de lichtbron of de grote afstand vanaf de scène, kan worden benaderd door een punt. We kunnen kiezen tussen een lichtbron op eindige afstand, waarvoor de richting van waaruit het licht op een object schijnt afhankelijk is van de plaats van het object in de scène en een lichtbron op oneindige afstand, waarbij het voldoende is om een (vaste) lichtrichting te definiëren, zoals bij licht van de zon. Voor iedere lichtbron die in de scène wordt geplaatst is behalve de positie (of lichtrichting bij een lichtbron op oneindige afstand) ook de kleur van het licht dat de lichtbron uitzendt van belang. Omdat de uitvoerapparaten waarop we de afbeeldingen maken, gebruikmaken van een kleurmodel met drie componenten: een rood-, een groen- en een blauwcomponent, zullen we de kleur van de lichtbronnen ook definiëren met een r-, g- en b-component. De kleur van het licht van de i-de lichtbron in de scène is gelijk aan Ii = (ri, gi, bi)T.
Ambient component
De ambient component van het lichtreflectiemodel geeft de bijdrage weer van licht dat niet rechtstreeks van een lichtbron afkomstig is, maar via een of meerdere reflecties op objectoppervlakken uiteindelijk op het zichtbare object valt. Het ambient licht geven we weer met Ia = (ra, ga, ba)T. Een deel van dit ambient licht zal worden gereflecteerd naar het oog van de waarnemer. In ons eenvoudige lichtmodel veronderstellen we de hoeveelheid ambient invallend licht constant in de gehele scène. Het naar de waarnemer gereflecteerde ambient licht kunnen we dan berekenen met de formule:
I amb
⎛k ⎜ a ,r = Ka ⋅ I a = ⎜ 0 ⎜⎜ ⎝ 0
0 ka , g 0
0 ⎞ ⎛ ra ⎞ ⎟ ⎜ ⎟ 0 ⎟ ⋅ ⎜ ga ⎟ ⎟ ka ,b ⎟⎠ ⎜⎝ ba ⎟⎠
Hierin is Ia de constante hoeveelheid ambient invallend licht en representeert de matrix Ka de ambient reflectiecoëfficiënt, een materiaaleigenschap die aangeeft welk percentage van de kleurcomponenten rood, groen en blauw van dat invallende licht gereflecteerd wordt. Ook de reflectiecoëfficiënten Kd en Ks, die we in de andere twee componenten van het lichtmodel aantreffen, zijn matrices. Diffuse reflectiecomponent
42
De diffuse reflectiecomponent van het lichtreflectiemodel is het gevolg van licht dat rechtstreeks vanaf de lichtbron op het oppervlak schijnt. Deze component is afhankelijk van de richting waaruit het licht van de lichtbron komt. We zullen de richting vanaf het oppervlak naar de i-de lichtbron Li noemen. Diffuus gereflecteerd licht is het licht dat rechtstreeks vanaf een lichtbron op het oppervlak valt en waarvan een deel in gelijke hoeveelheden in alle richtingen wordt gereflecteerd, zoals figuur 3.12a laat zien.
OUN
Inleiding computer graphics
a
b V
N
Li
θ
FIGUUR 3.12
Cosinuswet van Lambert
Diffuse reflectie
De lichtrichting Li bepaalt samen met de oriëntatie van het oppervlak de hoeveelheid diffuus gereflecteerd licht. Volgens de cosinuswet van Lambert is de lichtsterkte van het licht dat vanaf een bepaalde richting op een oppervlak valt evenredig met de cosinus van de hoek waaronder het licht invalt. Dit is eenvoudig in te zien, immers naarmate het licht schuiner invalt (grotere hoek met de normaalvector op het oppervlak), wordt dezelfde hoeveelheid licht verspreid over een groter deel van het oppervlak (zie figuur 3.13). De grootte van het oppervlak dat dezelfde hoeveelheid licht ontvangt, is omgekeerd evenredig met de cosinus van de hoek waaronder het licht invalt en dus is de lichtsterkte evenredig met die hoek. a
b
θ b / cos θ
FIGUUR 3.13
Cosinuswet van Lambert
We kunnen de diffuse reflectie van de i-de lichtbron berekenen met de formule
Idif,i = KdIi cosθ = KdIi(N · Li) Hierbij is aangenomen dat N (de normaalvector op het oppervlak) en Li (de vector naar de lichtbron) vectoren zijn met lengte 1 (zie figuur 3.12b). Verder is N · Li het inwendig product van N en Li. De positie of richting van de waarnemer (vector V) speelt in de diffuse reflectiecomponent geen rol. De diffuse reflectiecoëfficiënt, weergegeven met matrix Kd, is een materiaaleigenschap die aangeeft welk percentage van de kleurcomponenten rood, groen en blauw van het invallende licht diffuus gereflecteerd wordt.
OUN
43
Capita selecta wiskunde
Spiegelende reflectiecomponent
Ook de spiegelende reflectiecomponent van het lichtreflectiemodel is het gevolg van licht dat rechtstreeks afkomstig is van de lichtbron. Deze component geeft de hoeveelheid licht weer die volgens hoek van inval is hoek van terugkaatsing wordt gereflecteerd, zoals bij een perfecte spiegel (figuur 3.14a). De hoeveelheid spiegelend gereflecteerd licht dat het oog van de waarnemer bereikt is afhankelijk van de positie van de lichtbron, de oriëntatie van het oppervlak en de positie van de waarnemer. De hoeveelheid spiegelend gereflecteerd licht zal zeer snel afnemen naarmate de richting van perfecte spiegeling meer afwijkt van de richting naar de waarnemer. Dit wordt in het lichtmodel gemodelleerd met de factor cosnφ. Hierbij is n een materiaaleigenschap. Grote waarden van n impliceren dat de spiegelende reflectie snel afneemt wanneer de waarnemer zich verderaf bevindt van de perfecte spiegelende richting. Grote waarden van n geven de indruk van een glad oppervlak, terwijl kleine waarden leiden tot doffe oppervlakken. De spiegelende reflectiecomponent van het lichtmodel zorgt ervoor dat op gladde objectoppervlakken kleine felle weerspiegelingen van de lichtbron ontstaan en op doffe objectoppervlakken de weerspiegeling van de lichtbron over een groter deel van het objectoppervlak wordt uitgesmeerd en veel minder fel is. De weerspiegelingen van de lichtbronnen die het gevolg zijn van de spiegelende reflectiecomponent noemen we highlights. a
b N
V R
FIGUUR 3.14
φ
Li
θ
θ
Spiegelende reflectie
De spiegelende reflectie component wordt berekend met de formule
Ispec,i = KsIi cosnφ = KsIi(Ri · V)n Hierin zijn V (de vector naar de waarnemer) en Ri (de vector in de richting van perfecte spiegelende reflectie) vectoren met lengte 1 (zie figuur 3.14b). Verder is Ks de spiegelende reflectiecoëfficiënt (vergelijk met Ka en Kd) en n de eerder geïntroduceerde materiaaleigenschap die bepaalt hoe glad of dof het materiaal is. De totale hoeveelheid licht die vanaf het zichtbare objectoppervlak het oog van de waarnemer bereikt kan nu worden berekend door de som te nemen van alle componenten van het lichtmodel voor alle lichtbronnen in de scène: Complete lichtreflectiemodel
44
I = I amb + ∑ ( I dif ,i + I spec ,i ) = Ka I a + ∑ [ Kd I i ( N ⋅ Li ) + Ks I i ( R ⋅ V )n ] i
OUN
i
Inleiding computer graphics
OPGAVE 3.7
Een puntvormige lichtbron, gepositioneerd in punt (2, 1, 10), verlicht een bol met middelpunt in (2, 1, 2). Het licht van de lichtbron heeft kleur (r, g, b) = (250, 250, 250). Wat is de diffuse reflectie in punt (5, 1, 6) op het boloppervlak, als de diffuse reflectiecoëfficiënt van het boloppervlak gelijk is aan: 0 ⎞ ⎛ 0.6 0 ⎜ ⎟ ⎜ 0 0.4 0 ⎟ ⎜ 0 0 0.3 ⎟⎠ ⎝ 3.9
FLAT SHADING EN SMOOTH SHADING
De complete scène is opgeslagen als een verzameling polygons. Wanneer we per polygoon het lichtreflectiemodel toepassen, vinden we voor iedere polygoon een kleur. Als een polygoon voor een bepaalde pixel van onze afbeelding de zichtbare polygoon blijkt te zijn, dan kunnen we de met het lichtmodel berekende kleur aan die pixel toekennen. Dat leidt voor de kubus met het draadmodel in figuur 3.11a tot de afbeelding in figuur 3.11c. a
FIGUUR 3.15
Flat shading
Smooth shading
b
c
Shading
Gekromde oppervlakken benaderen we in ons model van de scène met een netwerk van polygonen. Met de hierboven beschreven methode van bepalen van kleuren voor de pixels worden ook de polygonen die een gekromd oppervlak benaderen als platte vlakken afgebeeld. Voor de cilinder met draadmodel in figuur 3.15a leidt dit tot de afbeelding in figuur 3.15b. We noemen het op deze manier afbeelden van objecten met gekromde oppervlakken flat shading. Een afbeelding zoals in figuur 3.15c, waarin over het gekromde oppervlak de kleur geleidelijk verandert, is veel realistischer. De geleidelijk veranderende kleur over het oppervlak geeft een goede indruk van de werkelijke vorm van het oppervlak. Het op deze manier afbeelden van gekromde oppervlakken noemen we smooth shading. In het geval van flat shading gebruiken we bij het toepassen van het lichtmodel de naar buiten gerichte normaalvector op een polygoon.
OUN
45
Capita selecta wiskunde
Voor alle pixels waar punten op de polygoon zichtbaar worden, is deze normaalvector (mede) bepalend voor de kleur van de pixel, zoals we in paragraaf 3.8 hebben gezien. Gouraud shading
Phong shading
Bij smooth shading kunnen we op twee manieren te werk gaan: – Gouraud shading: we rekenen kleuren uit voor de hoekpunten van de polygonen door toepassen van het lichtmodel op de hoekpunten met een benaderde normaalvector, en interpoleren de kleuren over de polygonen. – Phong shading: we benaderen normaalvectoren voor de hoekpunten van de polygonen en interpoleren deze normaalvectoren over de polygonen. Voor punten op de polygonen passen we vervolgens het lichtreflectiemodel toe met gebruik van de geïnterpoleerde normaalvector. Voor zowel Gouraud shading als Phong shading starten we met een berekening van normaalvectoren voor alle polygonen van het polygonnetwerk. Vervolgens rekenen we normaalvectoren uit voor de hoekpunten van de polygonen door het middelen van alle normaalvectoren van de polygonen van het netwerk die het betreffende punt als hoekpunt hebben. Dit zijn de polygonen rondom het hoekpunt. De normaalvectoren van deze polygonen moeten voordat het gemiddelde berekend kan worden eerst allemaal dezelfde lengte hebben, bijvoorbeeld lengte 1. De op deze manier gevonden normaalvectoren voor de hoekpunten zijn goede benaderingen voor de normaalvectoren in de hoekpunten van de polygonen op het werkelijke willekeurig gekromde oppervlak. Afhankelijk van de keuze voor Gouraud shading of Phong shading gaat het algoritme nu verder met het berekenen van kleuren voor de hoekpunten en het interpoleren van deze kleuren over de polygonen (Gouraud shading) of het interpoleren van de normaalvectoren over de polygonen en het toepassen van het lichtreflectiemodel voor zichtbare punten op de polygons (Phong shading). Gouraud shading is veel sneller dan Phong shading. Dit komt doordat bij Phong shading het lichtreflectiemodel voor iedere pixel binnen de geprojecteerde polygoon uitgevoerd moet worden, terwijl dit bij Gouraud shading alleen hoeft te gebeuren voor de hoekpunten van de polygons. Vaak levert de snelle methode (Gouraud shading) echter afbeeldingen op van veel mindere kwaliteit. Dat wordt duidelijk door de situatie te beschouwen waarin een highlight (weerspiegeling van een lichtbron) volledig binnen een polygoon van het polygoonnetwerk valt. Als we Gouraud shading gebruiken, dan rekenen we met het lichtreflectiemodel eerst kleuren uit voor de hoekpunten. Omdat alle hoekpunten buiten de highlight vallen, krijgt geen enkele van de hoekpunten een hoge intensiteit. Daardoor wordt bij interpolatie van intensiteiten voor punten binnen de polygoon ook geen hoge intensiteit gevonden. De highlight wordt daarom volledig weggelaten. Grotere highlights worden met Gouraud shading wel afgebeeld, maar deze laten maar enigszins de vorm van de polygonen zien. Bij het gebruik van Phong shading zal de highlight niet worden gemist omdat hierbij het lichtreflectiemodel voor iedere pixel binnen de geprojecteerde polygoon wordt toegepast. De highlights zullen in dit geval ook de correcte vorm hebben. Denk aan een puntvormige lichtbron boven een biljart met gladde biljartballen; op de biljartballen worden met Phong shading kleine felle cirkelvormige highlights zichtbaar.
46
OUN
Inleiding computer graphics
Textuur
4
Texture mapping
4.1
WAT IS TEXTURE MAPPING?
In het voorgaande zijn we er steeds van uitgegaan dat voor de objecten in de scène materiaaleigenschappen waren gedefinieerd die de kleur en gladheid van het objectoppervlak bepaalden. Echter, de gesteldheid van veel objectoppervlakken is niet te definiëren door het opgeven van een kleur en een gladheid. Denk aan voorwerpen zoals een beschilderde vaas, een boomstam, een bakstenen muur of een houten tafelblad. Deze soorten objecten hebben een oppervlak met een textuur. In engere zin heeft textuur te maken met de structuur van een oppervlak zoals bij de schors van een boom. In de computer graphics gebruiken we het woord textuur ook voor oppervlakken met een volledig vlakke structuur, maar met verschillende kleuren op het oppervlak zoals bij een beschilderde vaas. In de volgende beschrijving van texture mapping hebben we geen methoden in gedachte die tot doel hebben de complexe structuur van bijvoorbeeld een harig of hobbelig oppervlak weer te geven. Er zijn in de computer graphics echter technieken bekend om de structuur van dergelijke oppervlakken, zoals de schil van een sinaasappel, eenvoudiger te definiëren dan door de exacte geometrie van de hobbels in het oppervlak vast te leggen. Een methode die kan worden gebruikt voor dit soort oppervlakken is de methode van bump mapping, die we hier niet verder zullen beschrijven. Hier definiëren we de textuur van een object als een rasterafbeelding (tweedimensionale matrix van kleuren). De texturen die we willen afbeelden op objectoppervlakken zijn derhalve willekeurige plaatjes. Texture mapping kan worden toegepast ter verhoging van het realisme van objectoppervlakken in afbeeldingen of juist om de complexiteit van een scène te reduceren. Een aantal situaties waarin we gebruik kunnen maken van texture mapping zijn, als: – een objectoppervlak is voorzien van een structuur, zoals bij een bakstenen muur, een houten tafelblad of de schil van een sinaasappel – een objectoppervlak is beschilderd, zoals bij een theepot, een vaas of een schilderij – met het oog op reductie van het aantal polygonen in een model wordt ervoor gekozen om details op een oppervlak, zoals ramen en deuren in muren, te representeren door afbeeldingen van deze details op de polygonen aan te brengen – met het oog op reductie van het aantal polygonen in een model wordt ervoor gekozen om objecten nabij of boven de horizon, zoals heuvels, gebouwen in de verte en wolken, te representeren door een afbeelding van deze objecten op een achter de scène geplaatst vlak. Texture mapping kunnen we zowel op 2D polygonen toepassen als op de oppervlakken van 3D objecten. In de beschrijving die volgt gaan we ervan uit dat een polygoon in schermcoördinaten is gegeven en een textuur als een rasterafbeelding in zogenaamde textuurcoördinaten. We beschouwen hoe we een volledige vierkante textuur kunnen afbeelden op een willekeurige vierhoek in de schermruimte (zie figuur 4.1).
OUN
47
Capita selecta wiskunde
a
b P3 '
P4 (0,1)
P3 (1,1)
polygon
y
P4 '
v mapping
v
P2 (1,0)
P1 (0,0)
P1 '
u textuur ruimte
FIGUUR 4.1
P2 ' u scherm ruimte
x
Texture mapping
Het is duidelijk dat de textuur vervormd moet worden om deze te laten passen op de polygoon. Deze vervorming kan op verschillende manieren plaatsvinden. In figuur 4.2 zien we twee afbeeldingen van een polygoon waarop een textuur van witte en zwarte vierkanten is afgebeeld met verschillend resultaat. Op het polygoon a is de methode van bilineaire interpolatie toegepast, terwijl de textuur op polygoon b is gemapt met een perspectivische mapping. a
FIGUUR 4.2
Bilineaire texture mapping
48
b
Bilineaire en perspectivische texture mapping
De bilineaire mapping (figuur 4.2a) heeft de eigenschap dat horizontale lijnen en verticale lijnen in de textuur worden afgebeeld op rechte lijnen in de schermruimte. Daardoor is ieder wit of zwart vierkant uit de textuur op het scherm afgebeeld op een vierhoek (met rechte zijden). Rechte lijnen die niet horizontaal of vertikaal zijn in de textuur worden echter niet afgebeeld op rechte lijnen in de schermruimte. Dit is in figuur 4.2a duidelijk te zien als we de witte velden van linksonder naar rechtsboven volgen. In de textuur lagen deze witte vierkanten op een rechte lijn, namelijk een diagonaal van de textuur, terwijl dit in de schermruimte een kromme is geworden.
OUN
Inleiding computer graphics
Perspectivische texture mapping
De perspectivische mapping (figuur 4.2b) heeft de eigenschap dat rechte lijnen in willekeurige richtingen in de textuur worden afgebeeld op rechte lijnen op het scherm. Ook bijvoorbeeld de diagonalen in de textuur zijn nu rechte lijnen. Volg om dit te controleren in figuur 4.2b de witte velden van linksonder naar rechtsboven. In paragraaf 4.2 en 4.3 laten we zien hoe bij de bilineaire mapping en de perspectivische mapping uit een punt (u, v) in de textuur het punt (x, y) op het scherm, waar (u, v) op wordt afgebeeld, berekend kan worden. De textuur definiëren we met textuurcoördinaten van 0 tot 1 in u- en v-richting, zoals in figuur 4.1. We nemen aan dat we de gehele textuur willen afbeelden op een willekeurige vierhoek op het scherm. De onderstaande tabel geeft de correspondentie tussen punten in de textuur en hoekpunten van de polygoon P1'P2'P3'P4' op het scherm waar de textuur op moet worden afgebeeld. Afbeelding van textuurcoördinaten op schermcoördinaten
TABEL 4.1 textuurcoördinaten
schermcoördinaten
punt
u
v
punt
x
y
P1 P2 P3 P4
0 1 1 0
0 0 1 1
P1 ' P2 ' P3 ' P4 '
x1 x2 x3 x3
y1 y2 y3 y3
4.2
BILINEAIRE TEXTURE MAPPING
We beelden de textuur P1P2P3P4 af op de polygoon P1'P2'P3'P4' met een bilineaire mapping. Bij bilineaire texture mapping berekenen we het beeld (x, y) van een punt (u, v) uit de textuur met de formule Formule voor bilineaire texture mapping
⎛ x1 ⎞ ⎛ x2 ⎞ ⎛ x4 ⎞ ⎛ x3 ⎞ ⎛x⎞ ⎜ y ⎟ = (1 − u)(1 − v ) ⎜ y ⎟ + u(1 − v ) ⎜ y ⎟ + (1 − u) v ⎜ y ⎟ + uv ⎜ y ⎟ ⎝ ⎠ ⎝ 1⎠ ⎝ 2⎠ ⎝ 4⎠ ⎝ 3⎠
(0,1)
Q
Q'
u0
(1,1)
P3 '
1 − u0
P4 '
1 − v0
1 − v0
v
(u 0 , v 0 )
R
(0,0)
P u
FIGUUR 4.3
S
(1,0)
R' v0
P1 '
( x0 , y 0 ) S'
u0
P'
1 − u0
v0 P2 '
Bilineaire texture mapping
OUN
49
Capita selecta wiskunde
OPGAVE 4.1
Ga na dat bij de bilineaire mapping volgens bovenstaande formule de hoekpunten van de textuur inderdaad worden afgebeeld op de (juiste) hoekpunten van de polygoon in de schermruimte volgens tabel 4.1. OPGAVE 4.2
Een vierkante textuur ABCD met A = (0, 0), B = (1, 0), C= (0, 1) en D = (0, 1) wordt afgebeeld met een bilineaire mapping op een polygoon A'B'C'D' met A'= (300, 0), B'= 500, 400), C'= (100, 500) en D'= (0, 100), waarbij X op X' wordt afgebeeld voor X = A, B, C, D. Op welk punt wordt het punt (0.75, 0.20) afgebeeld? OPGAVE 4.3
Bewijs dat een horizontale lijn in de textuur bij een bilineaire mapping wordt afgebeeld op een rechte lijn op het scherm. We bepalen nu de positie van het punt (x0, y0), waar een willekeurig punt (u0, v0) op wordt afgebeeld en maken daarbij gebruik van wat in opgave 4.3 is bewezen. Beschouw figuur 4.3. In deze figuur is in textuurcoördinaten P = (u0, 0), Q = (u0, 1), R = (0, v0) en S = (1, v0). Als we de coördinaten van P invullen in de formule voor de bilineaire mapping, dan vinden we dat dit punt wordt afgebeeld op het punt met plaatsvector ⎛x ⎞ ⎛x ⎞ p ' = (1 − u) ⎜ 1 ⎟ + u ⎜ 2 ⎟ ⎝ y1 ⎠ ⎝ y2 ⎠
Het punt P' ligt op het lijnstuk P'1P'2 op een zodanige positie dat P'1P' : P'P'2 = u0 : (1 – u0). Op een soortgelijke manier kunnen we ook de posities bepalen van de punten Q', R' en S', waarop Q, R en S worden afgebeeld. De verhoudingen zijn te zien in figuur 4.3. Omdat horizontale en verticale rechte lijnen in de textuur worden afgebeeld op rechte lijnen op het scherm, is het punt (x0, y0) het snijpunt van de lijnstukken P'Q' en R'Q'. 4.3
PERSPECTIVISCHE TEXTURE MAPPING
We beelden de textuur P1P2P3P4 af op de polygoon P1'P2'P3'P4' met een perspectivische mapping. Een perspectivische mapping kan worden gerepresenteerd door een 3 bij 3 matrix M. Hierbij wordt gebruik gemaakt van homogene coördinaten. We berekenen het beeld (x, y) van een punt (u, v) met een vector-matrixvermenigvuldiging ⎛ x'⎞ ⎛u⎞ ⎜ ⎟ ⎜ ⎟ ⎜ y'⎟ = M ⎜ v⎟ ⎜h⎟ ⎜1⎟ ⎝ ⎠ ⎝ ⎠
gevolgd door een deling door de homogene coördinaat x=
50
y' x' en y = h h
OUN
Inleiding computer graphics
Merk op dat de matrix M en iedere matrix λM voor λ ≠ 0 dezelfde perspectivische mapping voorstellen. Bij gebruik van matrix λM vinden we namelijk eerst uit ⎛ x '' ⎞ ⎛u⎞ ⎜ ⎟ ⎜ ⎟ ⎜ y '' ⎟ = λ M ⎜ v ⎟ ⎜ h '' ⎟ ⎜1⎟ ⎝ ⎠ ⎝ ⎠
dat
x'' = λx', y'' = λy' en h'' = λh De homogene deling leidt vervolgens tot x=
x '' λ x ' x ' = = h '' λ h h
en y=
y '' λ y ' y ' = = h '' λ h h
Dit is hetzelfde resultaat als bij gebruik van de matrix M voor de perspectivische mapping. M en λM stellen dezelfde mapping voor. Een vraag die we nu graag beantwoorden is: ’Hoe kunnen we uit de correspondentie tussen hoekpunten uit de textuur en hoekpunten van de polygoon op het scherm, zoals in tabel 4.1, een matrix bepalen voor de perspectivische mapping van de textuur op de polygoon?’ Laat ⎛ m1 ⎜ M = ⎜ m4 ⎜m ⎝ 7
m2 m5 m8
m3 ⎞ ⎟ m6 ⎟ 1 ⎟⎠
een matrix voor deze perspectivische mapping. De mapping kan nu ook worden opgeschreven als Formules voor perspectivische texture mapping
m1u + m2 v + m3 m7 u + m8 v + 1 m u + m5 v + m6 (b) y = 4 m7 u + m8 v + 1
(a) x =
Uit het feit dat (0, 0) volgens tabel 4.1 wordt afgebeeld op (x1, y1) vinden we nu door invullen in (a) en (b) de volgende twee vergelijkingen: (1) x1 = m3 (2) y1 = m6
OUN
51
Capita selecta wiskunde
Op dezelfde manier levert de correspondentie tussen (1, 0) in de textuur en (x2, y2) op het scherm de vergelijkingen: (3) x2 = m1 + m3 – x2m7 (4) y2 = m4 + m6 – y2m7 en de correspondenties tussen (1, 1) en (x3, y3) en tussen (0, 1) en (x4, y4) de vergelijkingen: (5) (6) (7) (8)
x3 = m1 + m2 + m3 – x3m7 – x3m8 y3 = m4 + m5 + m6 – y3m7 – y3m8 x4 = m2 + m3 – x4m8 y4 = m5 + m6 – y4m8
De punten (x1, y1), (x2, y2), (x3, y3) en (x4, y4) zijn bekend, dus de enige onbekenden in de vergelijkingen (1) t/m (8) zijn de coëfficiënten m1 t/m m8 van de matrix M. We hebben derhalve een stelsel van 8 lineaire vergelijkingen met 8 onbekenden opgesteld. Dat stelsel kunnen we oplossen en dat levert ons de matrix Mvoor de perspectivische mapping. Affiene mapping
In het geval dat m7 = 0 en m8 = 0 is de mapping een affiene mapping. De textuur wordt op de polygoon afgebeeld door een combinatie van translaties, rotaties en schalingen uit te voeren. De formules (a) en (b) die de perspectivische mapping beschrijven, reduceren voor een affiene mapping tot (a’) x = m1u + m2v + m3 (b’) y = m4u + m5v + m6 VOORBEELD
Beschouw figuur 4.4. De matrix M voor de mapping van ABCD op A'B'C'D' is op meerdere manieren te berekenen. D(0,1)
C (1,1)
y
C ' (2,3)
B' (5,3)
D' (2,1)
A' (5,1)
v
A(0,0)
B(1,0)
x
u
FIGUUR 4.4
Affiene mapping van ABCD op A'B'C'D'
Methode 1 De transformatie kan worden opgebouwd uit – een rotatie om de oorsprong over 90° – een schaling t.o.v. de oorsprong met schalingsfactoren 3 en 2 – een translatie over de vector ⎛ 5⎞ ⎜ 1⎟ ⎝ ⎠
52
OUN
Inleiding computer graphics
Er geldt M = T5,1 · S3,2 · R90û.
Methode 2 De transformatie is een affiene mapping, dat wil zeggen: ⎛ m1 ⎜ M = ⎜ m4 ⎜ 0 ⎝
m2 m5 0
m3 ⎞ ⎟ m6 ⎟ 1 ⎟⎠
Uit (a’) en (b’) en de correspondentie tussen de hoekpunten van de textuur en de hoekpunten van de polygoon op het scherm vinden we acht vergelijkingen.
punt in textuur → punt op scherm
vergelijkingen
(0, 0) → (5, 1)
5 = m3 1 = m6 5 = m1 + m3 3 = m4 + m6 2 = m1 + m2 + m3 3 = m4 + m5 + m6 2 = m2 + m3 1 = m5 + m6
(1, 0) → (5, 3) (1, 1) → (2, 3) (0, 1) → (2, 1)
OPGAVE 4.4
Bereken M door het bovenstaande stelsel van 8 vergelijkingen met 6 onbekenden m1 t/m m6 op te lossen. OPGAVE 4.5
Bereken M door de matrixvermenigvuldiging T5,1 · S3,2 · R90û uit te voeren. 5
Samenvatting
Afbeeldingen van 3D objecten die in de computer zijn opgeslagen kunnen met gebruik van verschillende methoden worden gemaakt. Twee van deze methoden zijn behandeld: de methode van ray tracing en de 3D viewing pipeline. Bij ray tracing worden de modellen van de 3D objecten vaak exact opgeslagen, waarbij gekromde oppervlakken zijn beschreven met een impliciete of een parametrische representatie. De afbeelding wordt berekend door vanuit een oogpunt stralen te volgen door de pixels van een denkbeeldig beeldscherm dat tussen de waarnemer en de objecten in staat. Het dichtst bij de waarnemer gelegen snijpunt van de straal met een van de objecten is het punt van het model dat in de betreffende pixel zichtbaar zal zijn. Voor dit punt kan met een lichtreflectiemodel een kleur worden berekend. Met ray tracing kunnen we afbeeldingen maken van hoge kwaliteit door secundaire stralen verder door de ruimte te volgen, zodat slagschaduw, transparantie met breking en weerspiegelingen van de omgeving in gladde oppervlakken zichtbaar worden. Tegenover de hoge kwaliteit van de afbeeldingen staat dat het proces van ray tracing rekenintensief is.
OUN
53
Capita selecta wiskunde
Een alternatief voor ray tracing is het gebruik van de 3D polygon viewing pipeline. Hierbij wordt gebruik gemaakt van een benadering van gekromde objectoppervlakken met platte vlakken, zodat de gehele scène bestaat uit polygonen. De transformatiestappen uit de 3D polygon viewing pipeline zijn in figuur 5.1 schematisch weergegeven.
FIGUUR 5.1
Transformatiestappen uit 3D polygon rendering pipeline
Naast deze transformatiestappen, die de hoekpunten van de polygonen naar 2D schermcoördinaten overbrengen en de grafische informatie die zich uitstrekt buiten het af te beelden deel van de ruimte verwijderen, moet nog een aantal andere bewerkingen worden uitgevoerd. Deze bewerkingen zijn: scanconversie, hidden surface removal, toepassen van een lichtreflectiemodel en shading. In tegenstelling tot de transformatiestappen uit figuur 5.1 worden ze niet sequentieel uitgevoerd, maar zijn ze in een implementatie van een viewing pipeline verweven tot één algoritme. Hierin zorgt de scanconversie voor het bepalen van de pixels die binnen geprojecteerde polygonen liggen, bepaalt de hidden surface removal de polygoon dat per pixel het dichtst bij de waarnemer ligt, en zorgen het lichtreflectiemodel en de shading voor het vinden van de uiteindelijke kleur die aan een pixel toegekend moet worden. Vaak wordt ter verhoging van het realisme van afbeeldingen of juist om de complexiteit van een scène te reduceren, op objectoppervlakken een textuur aangebracht. Bijvoorbeeld beschilderde oppervlakken of ramen en deuren in muren die door een 2D plaatje worden gerepresenteerd in plaats
54
OUN
Inleiding computer graphics
van een 3D model. De textuur wordt opgeslagen als een 2D afbeelding waarbij per textuurpixel een kleur is gegeven. De textuur moet worden aangebracht op vlakken van het 3D model. Hiertoe wordt de kleur van punten binnen de polygonen berekend door met de inverse van de textuurfunctie (van textuur- naar scherm coördinaten) te bepalen welk punt uit de textuur op het betreffende punt van de polygoon wordt afgebeeld. Het textuurpunt bepaalt dan uiteindelijk de kleur die het punt op het objectoppervlak in de afbeelding krijgt. 6
Literatuur
Op het gebied van computer graphics zijn veel boeken beschikbaar, die u kunt gebruiken als leerboek bij een inleidende cursus op universitair niveau. Enkele hiervan zijn (1), (3), (4), (5) en (6). Bent u geïnteresseerd geraakt in de computer graphics en wilt u het vakgebied uitgebreider gaan bestuderen, dan kunt u gebruikmaken van een van deze boeken. Een zeer uitgebreid naslagwerk op het gebied van computer graphics is (2). Hoewel het boek op bepaalde punten wat verouderd is – de laatste editie dateert uit 1996 – is het boek als naslagwerk nog erg nuttig.
Boeken Angel, E., Interactive Computer Graphics: A-Top-Down Approach Using OpenGL, Addison Wesley, 2006, 4e editie. (1) Foley, J.D. e.a., Computer Graphics: Principles and Practice, Addison Wesley, 1996, 2e editie in C. (2) Hearn, D. en M.P. Baker, Computer Graphics with OpenGL, Pearson Prentice Hall, 2004, 3e editie. (3) Hill jr., F.S. en S.M. Kelley, Computer Graphics using OpenGL, Pearson Prentice Hall, 2007, 3e editie. (4) Shirley, P., Fundamentals of Computer Graphics, A K Peters, Ltd, 2005, 2e editie. (5) Slater, M., A. Steed en Y. Chrysanthou, Computer Graphics and Virtual Environments: From Realism to Real-Time, Addison Wesley, 2002. (6) Wilt u op internet aansprekende voorbeelden bekijken van met de computer gegenereerde afbeeldingen of van 3D computeranimaties, dan zijn (7), (8) en (9) een goede start. Voorbeelden van virtuele werelden op het internet zijn te vinden bij (10), (11) of (12). Om de virtuele werelden te kunnen bekijken zijn wel plug-ins nodig. Dit zijn hulpprogramma’s die als aanvulling op de webbrowser moeten worden geïnstalleerd. Link (13) en (14) leiden naar websites van respectievelijk het Miralab van de Universiteit van Genève en het GVU Center van Georgia Tech University. Op beide universiteiten wordt uitgebreid onderzoek gedaan naar onder andere animatie van menselijke bewegingen en gezichtsanimatie. Geïnteresseerden in Second Life kunnen een kijkje nemen op (15). Op (16) en (17), de startpagina’s van de Amerikaanse Computer Graphics organisatie SIGGRAPH en de Europese Computer Graphics organisatie Eurographics is ook veel informatie te vinden. Deze sites bevatten tevens vele links naar andere sites die te maken hebben met computer graphics.
OUN
55
Capita selecta wiskunde
Websites http://www.anitime.nl (7) http://www.pixar.com (8) http://www.animationtrip.com (9) http://www.mediamachines.com (10) http://www.vrmlsite.com (11) http://www.web3d.org (12) http://miralabwww.unige.ch (13) http://www.cc.gatech.edu/gvu/animation (14) http://www.secondlife.com (15) http://www.siggraph.org (16) http://www.eg.org (17)
56
OUN
Inleiding computer graphics
TERUGKOPPELING
Uitwerking van de opgaven 1.1
De cilindermantel wordt gerepresenteerd door punten met coördinaten x, y, z, waarvoor geldt:
x = 1 + 2cosθ y=h z = 3 + 2sinθ met θ in interval (–π, π) en h in interval (0, 5). Het ondervlak is: y = 0 met voorwaarde: (x – 1)2 + (z – 3)2 ≤ 2. Het bovenvlak is: y = 5 met voorwaarde: (x – 1)2 + (z – 3)2 ≤ 2. 1.2
De plaatsvectoren zijn aT = (2, 3, 1), bT = (2, 0, 1) en cT = (0, 1, 3). De normaalvector berekenen we nu als volgt: ⎛ ⎛ 0 ⎞ ⎛ 2 ⎞ ⎞ ⎛ ⎛ 2 ⎞ ⎛ 2 ⎞ ⎞ ⎛ −2 ⎞ ⎛ 0 ⎞ ⎛ −6 ⎞ ⎜⎜ ⎟ ⎜ ⎟⎟ ⎜⎜ ⎟ ⎜ ⎟⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ N = ( c − b) × ( a − b) = ⎜ ⎜ 1 ⎟ − ⎜ 0 ⎟ ⎟ × ⎜ ⎜ 3 ⎟ − ⎜ 0 ⎟ ⎟ = ⎜ 1 ⎟ × ⎜ 3 ⎟ = ⎜ 0 ⎟ ⎜ ⎜ 3 ⎟ ⎜ 1 ⎟ ⎟ ⎜ ⎜ 1 ⎟ ⎜ 1 ⎟ ⎟ ⎜ 2 ⎟ ⎜ 0 ⎟ ⎜ −6 ⎟ ⎝⎝ ⎠ ⎝ ⎠⎠ ⎝⎝ ⎠ ⎝ ⎠⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
Een normaalvector mogen we ‘schalen’. In dit geval delen we door 6, zodat we vinden: ⎛ −1 ⎞ ⎜ ⎟ N =⎜ 0 ⎟ ⎜ −1 ⎟ ⎝ ⎠
De waarde van de elementen van de normaalvector gebruiken we als coëfficiënten van de vlakvergelijking:
ax + by + cz + d = –x + 0 · y – z + d = –x – z + d = 0 De waarde van d kunnen we nu bepalen door één van de punten in te vullen, bijvoorbeeld A = (2, 3, 1): –2 – 1 + d = 0 Dus d = 3, zodat de vergelijking van het vlak gelijk is aan: –x – z + 3 = 0 Door het invullen van de coördinaten van A, B en C kan direct worden geverifieerd dat alle 3 punten in het vlak liggen. 1.3
Als je vanaf de onderkant (negatieve y-as) naar het grondvlak van de piramide kijkt dan is de volgorde P1P2P3P4 tegen de wijzers van de klok in.
OUN
57
Capita selecta wiskunde
2.1
De vectorvoorstelling van de projector is: ⎛x⎞ ⎛ 1 ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ y ⎟ = λ ⎜ −1 ⎟ ⎜z⎟ ⎜ −10 ⎟ ⎝ ⎠ ⎝ ⎠
De impliciete representatie van de bol is:
x2 + (y + 3)2 + (z + 20)2 = 25 De op te lossen vierkantsvergelijking is: 102λ2 – 406λ + 384 = 0. Deze vergelijking heeft de oplossingen: λ2 ≈ 2.43 en λ2 ≈ 1.55. Nu volgt dat de snijpunten (2.43, –2.43, 24.3) en (1.55, –1.55, 15.5) zijn. 2.2
14 ) = 1.0041 680 −6 ) = 2.2794 hoek( P2 PP3 ) = arccos( 85 −14 ) = 2.9997 hoek( P3 PP1 ) = arccos( 200 hoek( P1 PP2 ) = arccos(
hoek( P1 PP2 ) + hoek( P2 PP3 ) + hoek( P3 PP1 ) = 6.2832 P ligt dus in P1 P2 P3 4 ) = 1.3521 340 0 hoek( P2 QP3 ) = arccos( ) = 1.5708 289 −18 hoek( P3QP1 ) = arccos( ) = 2.9229 340 hoek( P1QP2 ) = arccos(
hoek( P1QP2 ) + hoek( P2 QP3 ) + hoek( P3QP1 ) = 5.8458 Q ligt dus niet in P1 P2 P3 3.1
Spl = T0 , 1 ⋅ Rα ⋅ S1,−1 ⋅ R−α ⋅ T0 ,− 1 = 2
⎛1 0 ⎜ ⎜0 1 ⎜0 0 ⎝
3.2
2
0 ⎞⎛ 4 5 − 3 5 0 ⎞⎛ 1 0 0 ⎞⎛ 4 5 ⎟⎜ ⎟⎜ 1 ⎟⎜ 3 4 0 ⎟⎜ 0 −1 0 ⎟⎜ − 3 5 2 ⎟⎜ 5 5 ⎟⎜ 1 ⎟⎜ 0 1 ⎟⎜ ⎠⎝ 0 ⎠⎝ 0 0 1 ⎠⎝ 0
3 4
5 5
0
0 ⎞ ⎛ 1 0 0 ⎞ ⎛ 0.28 0.96 −0.48 ⎞ ⎟⎜ ⎟ ⎜ ⎟ 0 ⎟ ⎜ 0 1 − 1 2 ⎟ = ⎜ 0.96 −0.28 0.64 ⎟ 1 ⎟⎠ ⎜⎝ 0 0 1 ⎟⎠ ⎜⎝ 0 0 1 ⎟⎠
R2 ,3; −90! = T2 ,3 ⋅ R−90! ⋅ T−2 ,−3 =
⎛ 1 0 2 ⎞ ⎛ 0 1 0 ⎞ ⎛ 1 0 −2 ⎞ ⎛ 0 1 −1 ⎞ ⎜ ⎟⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ 0 1 3 ⎟ ⎜ −1 0 0 ⎟ ⎜ 0 1 −3 ⎟ = ⎜ −1 0 5 ⎟ ⎜0 0 1⎟⎜ 0 0 1⎟⎜0 0 1 ⎟ ⎜ 0 0 1 ⎟ ⎝ ⎠⎝ ⎠⎝ ⎠ ⎝ ⎠
58
OUN
Inleiding computer graphics
3.3
⎛2 5 4⎞ ⎛3 6 5 ⎞ ⎜ ⎟ ⎜ ⎟ X = ⎜ 2 2 4 ⎟ , X ' = ⎜ 6 6 10 ⎟ ⎜1 1 1⎟ ⎜1 1 1 ⎟ ⎝ ⎠ ⎝ ⎠
Los op X' = M, ofwel M = X' · X–1. ⎛ 3 6 5 ⎞⎛ 2 5 4⎞ ⎜ ⎟⎜ ⎟ M = ⎜ 6 6 10 ⎟ ⎜ 2 2 4 ⎟ ⎜ 1 1 1 ⎟⎜ 1 1 1⎟ ⎝ ⎠⎝ ⎠
−1
⎛ 3 6 5 ⎞ ⎛ − 13 − 16 2 ⎞ ⎛ 1 0 1 ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ = ⎜ 6 6 10 ⎟ ⋅ ⎜ 1 3 − 1 3 0 ⎟ = ⎜ 0 2 2 ⎟ ⎜1 1 1 ⎟ ⎜ 0 1 −1 ⎟⎠ ⎜⎝ 0 0 1 ⎟⎠ 2 ⎝ ⎠ ⎝
Dit is de matrix van een schaling met factoren 1 en 2 gevolgd door een translatie over de vector (1, 2)T. Controleer met de tekening.
3.4
⎛ ux ⎜ ⎜ vx ⎜w ⎜ x ⎜ 0 ⎝
uy
uz
vy
vz
wy
wz
0
0
0⎞⎛u ⎞ ⎛ 1⎞ x ⎟ 0 ⎟ ⎜⎜ uy ⎟⎟ ⎜ 0 ⎟ =⎜ ⎟ 0 ⎟⎟ ⎜ uz ⎟ ⎜ 0 ⎟ ⎜ ⎟ ⎜⎜ ⎟⎟ ⎜ ⎟ 1 ⎟⎠ ⎝ 1 ⎠ ⎝ 1 ⎠
namelijk: u · u = ⏐u⏐ = 1 v · u = 0, want v ⊥ u w · u = 0, want w ⊥ u Op dezelfde manier is aan te tonen dat v op (0, 1, 0)T wordt afgebeeld en w op (0, 0, 1)T. 3.5
De linkerbenedenhoek van het window heeft coördinaten (40, -20). De linkerbenedenhoek van het viewport heeft coördinaten (0.0, 0.2). De transformatie start dus met een translatie T–40,20 en eindigt met een translatie T0,0.2. Tussendoor moet een schaling worden uitgevoerd. Het verschil in x-waarden in het windom is 80 en in het viewport 0.4; er moet in de x-richting dus geschaald worden met een factor 0.4 80 = 0.005; in de y-richting moet geschaald worden met een factor 0.4 100 = 0.004.
OUN
59
Capita selecta wiskunde
De transformatiematrix wordt dus: T0 ,0.2 ⋅ S0.005,0.004 ⋅ T−40 ,20 =
0 0 ⎞ ⎛ 1 0 −40 ⎞ ⎛ 0.005 0 −0.2 ⎞ ⎛ 1 0 0 ⎞ ⎛ 0.005 ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ 0.004 0 ⎟ ⋅ ⎜ 0 1 20 ⎟ = ⎜ 0 0.004 0.28 ⎟ ⎜ 0 1 0.2 ⎟ ⋅ ⎜ 0 ⎜0 0 1 ⎟ ⎜ 0 0 1 ⎟⎠ ⎜⎝ 0 0 1 ⎟⎠ ⎜⎝ 0 0 1 ⎟⎠ ⎝ ⎠ ⎝
Nu kan berekend worden waar het punt (60, 20) in het window op wordt afgebeeld in het viewport. 0 −0.2 ⎞ ⎛ 60 ⎞ ⎛ 0.10 ⎞ ⎛ 0.005 ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ 0.004 0.28 ⎟ ⋅ ⎜ 20 ⎟ = ⎜ 0.36 ⎟ ⎜ 0 ⎜ 0 0 1 ⎟⎠ ⎜⎝ 1 ⎟⎠ ⎜⎝ 1 ⎟⎠ ⎝
Het punt (60, 20) in het window wordt dus afgebeeld op (0.10, 0.36) in het viewport. 3.6
Door invullen van (x0, y0) in de vlakvergelijking vinden we z0 =
− ax0 − by0 − d c
Door invullen van (x0 + 1, y0) in de vlakvergelijking vinden we z0' =
− a( x0 + 1) − by0 − d a = z0 − c c
De vaste waarde die bij de z-waarde moet worden opgeteld is dus inc = − a c .
3.7
⎛ 2 ⎞ ⎛ 5 ⎞ ⎛ −3 ⎞ ⎛ 5⎞ ⎛ 2⎞ ⎛ 3⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ L = ⎜ 1 ⎟ − ⎜ 1 ⎟ = ⎜ 0 ⎟ en N = ⎜ 1 ⎟ − ⎜ 1 ⎟ = ⎜ 0 ⎟ ⎜ 10 ⎟ ⎜ 6 ⎟ ⎜ 4 ⎟ ⎜6⎟ ⎜2⎟ ⎜4⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
0 ⎞ ⎛ 0.6 0 ⎛ 250 ⎞ ⎜ ⎟ ⎜ ⎟ Kd = ⎜ 0 0.4 0 ⎟ , I l = ⎜ 250 ⎟ ⎜ 0 ⎜ 250 ⎟ 0 0.4 ⎟⎠ ⎝ ⎝ ⎠
I dif
60
⎛ 150 ⎞ ⎛ 42 ⎞ ( N ⋅ L) ⎜ ⎟ −9 + 16 ⎜ ⎟ = Kd I l = ⎜ 100 ⎟ ⋅ = ⎜ 28 ⎟ 25 N L ⎜ 75 ⎟ ⎜ 21 ⎟ ⎝ ⎠ ⎝ ⎠
OUN
Inleiding computer graphics
4.1
Als (u, v) = (0, 0), dan ⎛ x1 ⎞ ⎛ x2 ⎞ ⎛ x4 ⎞ ⎛ x3 ⎞ ⎛ x1 ⎞ ⎛x⎞ ⎜ y ⎟ = (1 − 0)(1 − 0) ⎜ y ⎟ + 0 ⎜ y ⎟ + 0 ⎜ y ⎟ + 0 ⎜ y ⎟ = ⎜ y ⎟ ⎝ ⎠ ⎝ 1⎠ ⎝ 2⎠ ⎝ 4⎠ ⎝ 3⎠ ⎝ 1⎠
Dezelfde methode geldt ook voor de andere drie hoekpunten. 4.2
⎛ x ⎞ 4 ⎛ 300 ⎞ 12 ⎛ 500 ⎞ 1 ⎛ 0 ⎞ 3 ⎛ 100 ⎞ ⎛ 375 ⎞ ⎜y⎟ = ⎜ ⎟+ ⎜ ⎟+ ⎜ ⎟+ ⎜ ⎟=⎜ ⎟ ⎝ ⎠ 20 ⎝ 0 ⎠ 20 ⎝ 400 ⎠ 20 ⎝ 100 ⎠ 20 ⎝ 500 ⎠ ⎝ 320 ⎠
(0.75, 0.20) wordt afgebeeld op (375, 320) 4.3
De horizontale lijn RS is in textuur: ⎛u⎞ ⎛ 0 ⎞ ⎛ 1⎞ ⎜v⎟ = ⎜v ⎟ + λ ⎜0⎟ ⎝ ⎠ ⎝ 0⎠ ⎝ ⎠
u = λ met 0 ≤ λ ≤ 1 v = v0 voor vaste v0 met 0 ≤ v0 ≤ 1 (u, v) wordt afgebeeld op (x, y) door middel van ⎛ x1 ⎞ ⎛ x2 ⎞ ⎛ x4 ⎞ ⎛ x3 ⎞ ⎛x⎞ ⎜ y ⎟ = (1 − λ )(1 − v0 ) ⎜ y ⎟ + λ (1 − v0 ) ⎜ y ⎟ + (1 − λ ) v0 ⎜ y ⎟ + λ v0 ⎜ y ⎟ ⎝ ⎠ ⎝ 1⎠ ⎝ 2⎠ ⎝ 4⎠ ⎝ 3⎠ ⎛ (1 − v0 ) x1 + v0 x4 ⎞ ⎛ (1 − v0 ) x2 + v0 x3 ⎞ = (1 − λ ) ⎜ ⎟ + λ ⎜ (1 − v ) y + v y ⎟ = (1 − λ )r ' + λ s ' v y v y − + (1 ) 0 1 0 4⎠ 0 2 0 3⎠ ⎝ ⎝
met r' en s' de plaatsvectoren van R' en S' zoals in figuur 4.3. ⎛x⎞ ⎜ y ⎟ = (1 − λ )r ' + λ s ' is de rechte lijn tussen R' en S'. ⎝ ⎠
De horizontale lijn RS wordt dus afgebeeld op rechte lijn R'S'. 4.4
m3 = 5 m6 = 1 m1 = 5 – m3 = 0 m4 = 3 – m6 = 2 m2 = 2 – m1 – m3 = 2 – 0 – 5 = –3 m5 = 3 – m4 – m6 = 3 – 2 – 1 = 0
Nu volgt dus: ⎛ 0 −3 5 ⎞ ⎜ ⎟ M = ⎜ 2 0 1⎟ ⎜ 0 0 1⎟ ⎝ ⎠
OUN
61
Capita selecta wiskunde
4.5
R900
⎛ 0 −1 0 ⎞ ⎛3 0 0⎞ ⎛ 1 0 5⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ = ⎜ 1 0 0 ⎟ , S3,2 = ⎜ 0 2 0 ⎟ , T5,1 = ⎜ 0 1 1 ⎟ ⎜0 0 1⎟ ⎜0 0 1⎟ ⎜0 0 1⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
Nu volgt: ⎛ 1 0 5 ⎞ ⎛ 3 0 0 ⎞ ⎛ 0 −1 0 ⎞ ⎛ 0 −3 5 ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ M = T5,1 ⋅ S3,2 ⋅ R90! = ⎜ 0 1 1 ⎟ ⋅ ⎜ 0 2 0 ⎟ ⋅ ⎜ 1 0 0 ⎟ = ⎜ 2 0 1 ⎟ ⎜0 0 1⎟ ⎜0 0 1⎟ ⎜0 0 1⎟ ⎜ 0 0 1⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
62
OUN