3DICA.TXT v2.11 (C) Ica/2 1996,1997 --------- Sis„llys -------- 0 Yleist„ l”pin„„ 0.1 Kuka on Ica/2? 0.2 Miksi ihmeess„ kirjoitin t„m„n dokumentin? 0.3 Kenelle t„m„ dokumentti on suunnattu? 0.4 What's new? 0.5 Tulossa 0.6 Gr33tZ 0.7 3d-termist”„ yms. 0.8 Frequently Asked Questions 0.9 Thanks for support 1 Vektorit 1.1 Yleist„ 1.2 Vektorin yht„l” 1.3 Vektorin pituus 1.4 Vektorien yhteenlasku 1.5 Skalaaritulo 1.6 Vektoritulo 1.7 Skalaarikolmitulo 1.8 Matriisitulo 1.9 Vektorin ja matriisin tulo 2 3D:n alkeet 2.1 2D- ja 3D-maailman yhteys 2.2 3D-py”ritysten perusyht„l”t 2.3 Sinin ja kosinin taulukoiminen 2.4 Pisteen py”ritt„minen kaikkien akseleiden ymp„ri samanaikaisesti 2.5 Idea enginen toteuttamiseen 3 3D ja matriisit 3.1 Aivan uusi ajattelutapa 3.2 Objektimatriisin liikuttaminen eli transformointi 3.2.1 Siirt„minen eli translaatio 3.2.2 Py”ritt„minen eli rotaatio 3.2.3 Kamera 3.3 Pisteen transformointi objektimatriisilla 3.4 Hierarkiset transformaatiot 3.5 Sekalaista matriiseista 4 Erilaisia polygonifillej„ 4.1 Flat-kolmio 4.1.1 Fixed point 4.2 Gouraud-kolmio 4.3 Texture-kolmio 4.3.1 Perspektiivikorjauksen periaate 5 Sorttaustapoja 5.1 Z-sorttaus 4.2 Z-buffer 5.3 BSP-puu 5.3.1 The main idea 5.3.2 Tarvittavat kaavat 5.3.3 Vinkkej„ 5.4 S-buffer 6 Varjostustapoja 6.1 Flat-sheidaus 6.1.1 Z-Flat 6.1.2 Lambert Flat 6.2 Gouraud-sheidaus 6.2.1 Z-Gouraud 6.2.2 "Oikea" Gouraud 6.3 Phong-sheidaus 6.3.1 Phong Illuminating 6.3.2 Env-mappaus 6.3.3 Voltaire/OTM:n Phong 7 Muuta mukavaa 7.1 Hidden face removal 7.1.1 Backface culling 7.1.2 View cone 7.2 Kamera and how did I do it 7.3 Objektin py”ritysnopeuden suhteuttaminen koneen nopeuteen 0 Yleist„ l”pin„„ ----------------- 0.1 Kuka on Ica/2? Olen oikealta nimelt„ni Ilkka Pelkonen, 18-vuotias c-, (pascal-) ja assembler-ohjelmoija. Koodaamiseni on ollut l„hinn„ hupihommaa (en ole julkaissut mit„„n), joten harva lukija varmaan Arkadian yhteislyseolaisia lukuunottamatta on minusta aiemmin kuullut (edellisten versioiden lukijat sit„kin enemm„n ;) Opiskelin siis mainitussa koulussa ABi-asteella (kirjoitukset ovat jo takana), ja syksyll„ olisi tarkoitus aloittaa uusi el„m„ Otaniemen tietotekniikkaosastolla. Nyt on sitten sekin varmistunut ett„ sis„ll„ ollaan ja kirkkaasti. En malta olla hiukan brassaamatta: pisteit„ 52.45, pisteraja 43.89. Itse olen tyytyv„inen :D Kuulun gruuppiin nimelt„ Hubris, entinen Dozer. Watch out, syksyll„ on tulossa jonkinlainen demoviritelm„ jos ehdimme. Nimikin moisella jo on: Rain. Hubriksen l”yt„„ asm97:lta p”yd„st„ C9, paikoilta 1-3. Tulkaahan moikkaamaan, min„ olen se parimetrinen 486sx-prossu kaulassa roikkuva rillip„„- lipputanko :) Niin muuten, jos olet asiasi osaava graafikko, ilmoittaudu (jos uskallat :) Yhteyden minuun saa parhaiten e-mailaamalla osoitteeseen ilkka.pelkonen@mbnet.fi (mbnettil„iset voivat toki messuta privamailiin ;), eli kommentit t„st„ tekstist„ (ja miksei jostain muustakin =) sinne. Etenkin muita samaan kouluun ja samalle osastolle tulijoita - tai vaikkapa jo siell„ olijoita - kehotetaan ottamaan yhteytt„, mutta kuulen siis eritt„in mielell„ni palautetta t„st„ dokumentistakin. Virheet saa, ei vaan PITŽŽ, ilmoittaa :) Ai niin, kyll„. K„yt„n OS/2 Warpia ja olen siihen eritt„in tyytyv„inen :) 0.2 Miksi ihmeess„ kirjoitin t„m„n dokumentin? Minua ovat jo jonkin aikaa h„irinneet ep„toivoisten yl„astetta p„„tt„m„ss„ olevien tai lukion vasta aloittaneiden nuorten koodaajanalkujen ruinaukset kunnon opastuksesta 3d-koodauksen maailmaan. Syksyll„ '96 kirjoitin mielest„ni sangen tyhjent„v„n selostuksen MBnetin PC-ohjelmointi-alueelle, mutta k„vi ilmi, etteiv„t monet olleet lainkaan ymm„rt„neet mist„ tekstiss„ puhuttiin. Niinp„ p„„tin alkaa kaiken aivan alusta - selostaa per„ti vektoreista l„htien, miten kolmiulotteisen maailman koodaus PC:n (tai miksei jonkin muunkin koneen) ruudulle oikein tapahtuu. Nyttemmin olen jatkanut kirjoittamista l„hinn„ dokumentin saaneen suosion positiivisesti yll„tt„m„n„, ja lis„„kin lienee luvassa riippuen jaksamisestani ja ajan riitt„misest„. T„m„ taitaa olla oikea paikka morjenstaa Kaj Bj”rklundia, jonka kanssa olemme 3d-koodauksen ideanvaihdossa. Olen saanut h„nelt„ apua mm. valonl„hteen k„sittelyyn, hidden face removaliin, gouraudiin ja phong illuminating -shadeen. Herra Bj”rklund on my”s vastuussa osasta t„m„n dokumentin tekstist„ versiosta 2.1 l„htien, tosin allekirjoittaneen editoimana (voi kaauhea minkk„laassja krijootus- ja kieli oppivihreit„ se heppu tekee ;) Moi vaan sullekkin, RoDeX eli Henri Tuhkanen. Siin„ on mies joka osaa optata :O Žij„ll„ on ihan uskomattomia ideoita esim. texturemappauksen optimointiin, ja h„n jakelee auliisti tietouttaan minullekin :) P„„timme RoDeXin kanssa alkaa koodata 3d-engine„, jonka grafiikkapuolesta vastaa h„n ja geometriasta min„. Sas' n„hd„, mit„ siit„ tulee, mutta suunnitelmissa on rellata pd-verssu sitten joskus, mahdollisesti ensi kes„n„. Dokumentista on olemassa my”s helppolukuisempi html-versio mist„ kunnia lankeaa Jonni Lehtirannalle. Ko. versio l”ytyy osoitteesta http://www.nimad.fi/sudet/members/valokas/, joten kaikki heti sinne ;) 3dican virallinen levityspaikka l”ytyy www:st„ Jere Sanisalon kotisivuilta osoitteessa http://www.sicom.fi/~cooldude/. 0.3 Kenelle t„m„ dokumentti on tarkoitettu? T„m„n saa lukea kuka vain joka tuntee olevansa sen tarpeessa :) Kohderyhm„ksi suunnittelin alunperin itse n. 14-17-vuotiaat, joille on jo opetettu trigonometrian ja geometrian perusk„- sitteet, mutta vektorit tai matriisit ovat t„ytt„ hepreaa. Ohjelmointikokemusta oletan olevan ainakin sen verran, ett„ lukija osaa k„ytt„„ taulukoita -- *ja**omaa**j„rke„„n*! Ei ohjelmointia -- edes 3d-ohjelmointia ;) -- opita p„iv„ss„ tai viikossa, eik„ h„t„ilyst„ ole kuin haittaa. Paras tapa on edet„ j„rjestelm„llisesti efekti kerrallaan. Lukemallahan se selvi„„ ett„ onko t„st„ tekstist„ jotain hy”ty„ :) Ja jos on niin paljon ett„ mietit miten voisit korvata vaivann„k”ni, k”yh„ opiskelija ei panisi ollenkaan pahakseen pient„ avustusta esim. kaksikymppisen muodossa (toki enemm„nkin saa l„hett„„, mutta v„hint„„n tuon l„hett„neet saavat hyv„n mielen lis„ksi greetit ensi versioon). HUOM! Žl„ pid„ t„t„ ahneena rahanlyps„misen„, vaan asetu minun asemaani: jos olisit itse n„in kauan kirjoittanut teksti„ josta ei itsellesi ole mit„„n hy”ty„, etk” ottaisi mielell„si vastaan pikku stipendi„ lukijoiden taholta?-) Ja t„m„ on tosiaan siis vain ehdotus, ei miss„„n nimess„ vaatimus -- information wants to be free. Jos raha tuskin riitt„„ ruokaan, ymm„rr„t varmaan s„„st„„ sen kaksikymppisen parempaan tarkoitukseen ;) Mutta osoite on joka tapauksessa Ilkka Pelkonen Kynnysm„entie 10 01860 Perttula, tai tilillekin voi maksaa PSP 800027-30577532, jolloin viitteeksi teksti "3DICA". Kiit„n etuk„teen, jos joku katsoo asiakseen kannustaa minua (tai siis oikeastaan meit„ :) jatkamaan t„m„n dokumentin kehitt„mist„. Mahdollisen rahal„hetyksen mukaan voi muuten liitt„„ lauseen, lausahduksen tms. jonka haluaa julkaistavaksi 3dicassa (tilaahan t„„lt„ l”ytyy ;) Pid„t„n itsell„ni oikeuden olla julkaisematta sairaita, (liian) loukkaavia tai muuten mauttomia juttuja. 0.4 What's new? Uutta versiossa 1.1: Olen johtanut 3d:n konvertoimisen 2d:hen ja 3d-py”ritykset alusta l„htien. Mukaan on tullut my”s muutama uusi osio, jotka l”ytyv„t sis„llysluettelosta (ja luonnollisesti teks- tist„kin :D Lis„ksi huomasin muutamia puutteita ja ep„selvyyksi„, jotka olivat p„„sseet livahtamaan mukaan. N„it„ ei en„„ pit„isi esiinty„. Viel„ valitettiin kuvien ep„selvyydest„ ja siit„, ett„ pseudo- 3d-engine oli "optimoitu" eik„ helposti tajuttava "t„ydellinen" engine. N„it„kin haittoja olen yritt„nyt korjata. Ai niin, muutin my”s nimen v„h„n persoonallisempaan suuntaan :) Uutta versiossa 2.0: - Polygoninpiirron selityst„ on hiukan parannettu, ja klippausrutiineista l”ytynyt bugi korjattu. - Kappalejakoa on muutettu j„rkev„mm„ksi dokumentin kasvamisen my”t„. - Vektorit on selostettu *viel„kin* paremmin :) - Mukana ovat nyt my”s gouraud, texturemappaus, pari fake- phongia, Z-buffer, BSP-puu, ... - Matriisilaskennassa tarvittavia laskutoimituksia on lis„tty matriisitulolla ja vektorin ja matriisin tulolla. - Liitin t„h„n versioon env-mappaukseen sopivan bittikartan mukaan pcx-muodossa. Uutta versiossa 2.1: - Kaj Bj”rklund on tullut mukaan kehitysty”h”n. Flat-poly- gonien, interpolaation ja phong illuminating -efektin selvent„minen sek„ frameskip ovat h„nen k„sialaansa. - Vektorin ja matriisin tulossa oli ajatusvirhe, joka on korjattu. - Matriisipy”ritykset ovat nyt mukana kokonaisuudessaan. - Innostuin S-Bufferista, opettelin sen ja lis„sin saman tien osion my”s t„h„n tutoriaaliin :) - Lukijoiden pyynn”ist„ useita vanhan tekstin kohtia on selvennetty. - Vektoriteht„vien ratkaisut ovat mukana useiden lukijoiden pyynn”st„. Nyt ei niiss„ pit„isi olla ep„selvyyksi„ :I - 3d-sanasto, joka tosin on lapsenkengiss„„n. - Kaj meni ja v„„nsi TP7:lla dokumenttiin nipun esimerkki- ohjelmia, jotka l”ytyv„t paketista 3DI_SRC.ZIP. Mukana 3D Studion .ASC-loaderi (ja esimerkki-ASC), .PCX-loaderi texturemappausta varten (ja esimerkki-PCX), sek„ Lambert Flatin, Z- ja oikean gouraudin, env-mappauksen ja texture- mappauksen esimerkkiohjelmat. T„ss„ vaiheessa viel„ melko dokumentoimatonta mutta silti kohtalaisen selv„„ pascal -koodia. - Voltaire /OTM:n kehitt„m„n Phong-toteutusmuodon idea on selostettu. Oikeaa phongia ei ole viel„k„„n. Uutta versiossa 2.1a (ei p„„ssyt koskaan levitykseen :) - Matriisipy”ritysten esimerkkipseudossa oli moka, korjattu. Kiitos informoinnista, sin„-joka-MBnetiss„-k„yt„t-nime„ Mika&Janne Tolvanen. - Pikkupukkeja korjattu. - Gouraudiin lis„tty optimointivinkki joka v„hent„„ cmp:n ja mahdollisia xchg:it„ hliness„. - Perspektiivikorjauksen periaate selostettu. Kiitos kun selvensit sit„ minulle, Timo Saarinen. - Hidden face removalia tarkennettu. - Tulossa-osio lis„tty. - FAQ lis„tty. - Thanks for support -osio lis„tty. Uutta versiossa 2.11: - 3dican virallisen levityspaikan osoite lis„tty. - Yleist„ l”pin„„ l”pisty lis„„, mm. 3d-enginen mainos ja paikat asm97:lla ilmoitettu. - Jotkut purkit ottivat 3di_src.zipin dizzin koko 3dican dizziksi, joten muutin sen p„„tteen. - Yksi FAQ lis„tty (vau). 0.5 Tulossa Some potential features to be added: - Bugikorjausta, jos korjattavaa l”ytyy - Pascal-esimerkkikoodiin kommentteja & t„ydennyst„ - C-esimerkkikoodia - Oikea phong - 3d-sanaston ja FAQ:n laajentamista - Ehdota itse uusia aiheita! 0.6 Gr33tZ iCA/2 gRe37z th3 f0ll0WiNG d00dz... Friction: Esit„ taas kanaa=) Ventolin qsee. Ducha: Keep up the (v„hemm„n) good work, pal! (kuulin yhden biisisi X) Ripple: Ei kukaan VOI olla noin hyv„. Paitsi min„ :I Firestorm: Milloin se c&c-tappaja valmistuu? Frac(tal): No nyt poistin muistutuksen siit„ 3d-starfieldist„ :D MiGbear: "Nyt on Sukat. Nyt on SUKAT! AAAAAAAA!!!" Oca: Sulkis rulaa, varsinkin kun min„ voitan. Viel„k” k„r„yttelet prossutuulettimia? :) Ozmo: Onko se polttamisen lopettaminen tosiaan niin hauskaa, ett„ se pit„„ tehd„ useampia kertoja kuussa?-) Jucka: Milloin is„si menee seuraavan kerran jenkkeihin? Tarttisin farkkuja ;) RoDeX: Ker„ilisit postimerkkej„, polygonirutiinien ker„ily on jotenkin ..outoa ;) Praetor: Paljonko sivuillasi on ollut k„vij”it„? Pizzaman: V„itell„„n jos elet„„n. Eik„ se el„m„ kirjoituksiin loppunut :I Wrath: Mik„ projekti nyky„„n rullaa? ;) Jokke: Kai se pit„„ sitten sinuakin greetata ;) tonic: tAAt rlz 8-) Et sitten tullutkaan opiskelukaveriksi ;( rAATO/tAAt: Kyh„t„„nk” jotain siisti„ kunhan irvimiselt„si ehdit? ;) RRRulettavaKonna: Olet er„s oudoimmista tyypeist„ joiden kanssa olen m”lissyt... :I KajBj”rkLund: Kiitos RC:n ilmaisesta rekkauksesta! :) HezeRaunio: Sait kai yo-aineista enemm„n kuin preleiss„? :I JukkaPMannInen: Ei t„h„n keksi mit„„n :) WesaWeps„l„Inen: Win95! Win95! Win95! ..on *sielt„* :) JereSaniSalo: Miten raytrace-enginesi toimii? Minullakin alkaa olla se edess„, varjot pit„isi saada skulaamaan... PanuArtimo: Sun Warp-desktoppi on RUMA! :) (MBnet-versio) HenriKronLund: Miten menee? Ei ole messuiltu sitten TZ:n kaatumisen! IlkkaWuorenMaa: Juoksu? Hauskaa? BUHAHA!! Mutta H™LKKŽ... ;) ;) TapioWuorInen: Hubris voitti! 8-) JanneGr”nThal: Kommenttisi ovat joskus *uskomattoman* hauskoja :) Pid„ vain tagilistaani silm„ll„ ;) 0.7 3d-termist”„ yms. Ensinn„kin k„ytt„m„ni koordinaatisto on seuraavanlainen: x-akseli kulkee vasemmalta oikealle, y-akseli ylh„„lt„ alas ja z-akseli osoittaa suoraan ruudun sis„„n. Py”ritysrutiinit toimivat oikean k„den systeemin mukaisesti, eli kun peukalo osoittaa akselin suuntaan, sormet taipuvat positiiviseen py”rityssuuntaan (eli py”ritt„ess„si z-akselin ymp„ri positiiviseen suuntaan, pisteet py”riv„t ruudulla my”t„p„iv„„n). Ja sitten 3d:hen liittyv„„ termist”„. N„m„ ovat vain ensimm„i- sin„ p„„h„n juolahtaneita termej„, seuraaviin versioihin saata- neen huomattavasti kattavampi "sanasto". Mailia vain, niin selvitet„„n muutkin ep„selv„t termit ja saadaan listaankin lis„yst„! Bilineaarinen filtter”inti (suodatus) Tekniikka, jolla l„helle zoomattujen bittikart- tojen piksel”itymist„ voidaan v„hent„„. Esim: Ota pala ruutupaperia, ja t”kk„„ siihen piste. Se ei luultavasti osu ruudun keskelle. Piirr„ pisteen ymp„rille ruutu. Osa ruudusta on nyt toisten paperin ruutujen alueella, eli tietty pinta-alaprosentti osuu yhteens„ nelj„n ruudun alueelle. N„iden prosenttim„„rien mukaan sekoitetaan texeleist„ oikeanv„rinen pikseli, joka laitetaan ruudulle. Face Objektin pinnan polygoni, jonka kulmat ovat verteksej„. Klippaus N„kym„tt”miss„ olevien polygonien tai niiden osien piirt„m„tt„ j„tt„mist„. Matriisi Er„„nlainen lukutaulukko, jonka avulla er„„t monimutkaiset laskutoimitukset ovat helpompia. Matriisimatematiikkaa k„ytet„„n mm. 3d-py”ri- tysten helpottamiseen. Objekti Esine 3d-avaruudessa. Origo Avaruuden keskipiste, koordinaatit (0,0,0). Paletin kvantisointi Tapa, jolla voidaan k„ytt„„ 256-v„risess„ tilas- sa samanaikaisesti sek„ 256-v„rist„ bittikarttaa ett„ varjostusta, montaa eri bittikarttaa joissa on eri paletit, tai vaikkapa 24-bittisi„ kuvia 256-v„risess„ tilassa. Polygoni Monikulmio, huom. EI v„ltt„m„tt„ kolmio. n- kulmainen polygoni voidaan muodostaa n-2 kolmi- osta. Quaternion 4d-avaruus, k„yt„nn”llinen kuulemma py”rityksiss„. S-buffer Segmented buffer, Z-bufferin paranneltu versio jossa pisteiden sijaan tarkastellaan vaakaviivoja (k„ytet„„n my”s nimistyst„ scanline Z-buffer, mik„li olen ymm„rt„nyt oikein). Sorttaus Polygonien piirt„misj„rjestyksen m„„ritt„minen siten, ett„ takimmaiset piirret„„n ensin ja etum- maiset vasta lopuksi. Subpixel Sijainti pikselin sis„ll„ (ks. bilineaarinen filtter”inti). Subtexel Sijainti texelin sis„ll„ (ks. bilineaarinen filtter”inti). Texel Texturemap pixel eli bittikartan pisteen v„ri. Vektori Jana jolla on vakituinen pituus ja suunta, mutta ei paikkaa (voi l„hte„ origosta, mutta my”s huomattavan monesta muusta pisteest„ :) Verteksi Objektin kulmapiste, johon kiinnittyy yksi tai useampia faceja. Verteksinormaali Kulmapisteen normaali, joka saadaan laskemalla ristitulolla jokaisen verteksiin kiinnittyv„n polygonin normaali ja ottamalla niiden keskiarvo (tai laittamalla vektori sojottamaan objektin origosta verteksiin, jos halutaan p„„st„ helpolla gouraudissa -- EI toimi muissa kuin gouraudissa!). Yleens„ verteksinormaalit ovat yksikk”vektoreita, koska siten p„„st„„n eroon jakolaskuista loopeissa (niiss„ tarvitaan usein skalaarituloa joka vaatii parikin vektorin pituudella jakamista. Jos pituus on yksi, ei jakolaskua luonnollisesti tarvita :) Z-buffer Sorttaustapa, jossa pisteet lajitellaan ruudun kokoiseen taulukkoon niiden z-koordinaattien mukaiseen j„rjestykseen. Vain etummaisin pikseli piirret„„n. 0.8 Frequently Asked Questions Perustavanlaatuinen neuvo kaikkiin kysymyksiin: KŽYTŽ JŽRKEŽSI! TIETENKŽŽN koodisi ei toimi, jos ohjelma ei vastaa edes k„ytt„m„si ohjelmointikielen SYNTAKSIA! Q: 3d-py”ritykseni, jotka on otettu suoraan pseudosta, eiv„t toimi. A: Tutki, ovatko kaikki muuttujat oikeaa tyyppi„. Onko sini- ja kosinitaulukko m„„ritelty oikein? Ovatko ne varmasti **256-alkioisia**? Oletko k„ytt„nyt yhdess„ kohdin muuttu- jaa jonka nimi on otettu pseudosta, ja toisessa itse nimet- ty„, muka samana muuttujana? Q: Texturemappausrutiinini sotkee ruudun. En l”yd„ mist„„n mit„„n vikaa. A: Mahdollisesti py”ristysongelma. Fixed: putpixel( x, y, tmap[ u/65536+v/256) ] ) Olet nerokkaasti ajatellut optimoivasi, eli kun v pit„isi jakaa 2^16:lla ja kertoa 2^8:lla, oletkin jakanut 2^8:lla. Tulos on v„„r„. Miksik”? Nyt fixedpointtisi kahdeksaa ylemp„„ bitti„ ei nollata ollenkaan vaan tmap k„sitt„„ ne u-koordinaateiksi joten tulos on p„in ..rsett„. Oikea tapa on seuraava: putpixel( x, y, tmap[ u/65536+(v/65536)*256) ] ) Float: putpixel( x, y, tmap[ word(u+v*256) ] ) u:n ja v:n desimaaliosat sotkeutuvat toisiinsa v„„rist„en tuloksen. Oikea tapa: putpixel( x, y, tmap[ word(u)+word(v)*256) ] ) Q: Flat-polygonirutiinini ei toimi. A: Onko muuttujat m„„ritelty oikein? K„yt„tk” pascalin kokonaislukujakolaskua floateilla tai p„invastoin? Onko fixedpointtisi oikein m„„ritelty? Muistatko jakaa sill„ loppuvaiheessa? Toimiiko verteksinsorttauksesi varmasti? Q: Mit„ ovat 3D-Studion asc-formaatissa face-listauksessa esiintyv„t termit AB, BC ja CA? (no huhhuh :) A: Ne ilmoittavat wireframe-kuviossa, piirret„„nk” viiva vai ei (minusta ainakin eritt„in k„tev„ ominaisuus). 0.9 Thanks for support L„mpim„t kiitokseni n„ille 3dican kehitysty”t„ tukeneille henkil”ille (lainausmerkeiss„ heid„n omat moikkauksensa, niiden per„ss„ minun kommenttini). Suokaa anteeksi omat tekstini, kello on l„hemm„s y”kahta ja juttu 'luistaa' pahan kerran... X) Joonas Pihlajamaa: "Imuroi lamertutti, imuroi lamertutti! BAD KARMA rulettaa!" Ai ai, kyll„h„n Jokke-pojan pit„isi tiet„„ ett„ Ilkka-set„ on jo liian iso k„ytt„m„„n mink„„nlaisia tutteja. Tosin sen takiahan sit„ voisi niit„ vaikka imuroidakin jos ei roskiin jaksa heitt„„ ;) Ja kaikkihan tiet„v„t ett„ Bad Karma on l„hinn„ vitsi. (vitsi (vitsi (vitsi (vitsi (vitsi))))) (eli loppujen lopuksi: kommentti oli vitsi -- siis se edellinen, ei j„lkimm„inen) :] Tommi Pisto Juujuu, osaan min„ koodata, mutta lopeta nyt kuitenkin se kenkieni nuoleminen; lankkaus j„i eilen v„liin ja nahka menee pilalle. ;D -- asiaan... -- 1. Vektorit ----------- Jos t„m„ ei tunnu kiinnostavan, siirry vain suoraan efekteihin; joudut kuitenkin palaamaan t„m„n kappaleen pariin jossain vaiheessa ;) 1.1 Yleist„ y ^ _ B Vektorit ovat janoja joilla on suunta, | /| ja joita voidaan siirrell„ koordinaa- | / tistossa haluttuihin paikkoihin kunhan | A\ niit„ ei k„„nnet„. | Vektori piirret„„n merkitsem„ll„ kuvan -------|--------> mukaisesti poikkiviiva sen alkup„„h„n | x (ei pakollinen) ja nuolen k„rki loppup„„h„n. Vektorit on tapana ilmoittaa yksikk”vektoreiden i, j ja k avulla. i on x-, j y- ja k z-akselin suuntainen vektori. N„iden kaikkien pituus on yksi pituusyksikk”, mist„ nimityskin. Mainittakoon t„ss„ vaiheessa, ett„ kaikki vektoriyht„l”t ovat sovellettavissa sek„ 2d- ett„ 3d-koordinaatistoihin, ainoa ero on 3d-koordinaatistossa ylim„„r„inen termi zk. Vektoreiden kirjaintunnusten p„„lle piirret„„n yleens„ viiva osoittamaan kyseess„ olevien vektorien, mutta DOS-tekstitilan ollessa kyseess„ katson oikeudekseni olla n„in tekem„tt„ :) (My”s i:n, j:n ja k:n p„„ll„ on siis normaalisti viiva. i:n ja j:n p„„ll„ olevia pisteit„ ei t„ll”in tarvitse merkit„.) 1.2 Vektorin yht„l” Nyt laskemme vektorin AB yht„l”n. Jos A-pisteen koordinaatit ovat A(Ax,Ay,Az) ja B-pisteen vastaavasti B(Bx,By,Bz), miss„ x,y ja z ovat alaindeksej„, vektorin AB yht„l” on __ _ _ _ AB = (Bx-Ax)i + (By-Ay)j + (Bz-Az)k _ _ _ = Xi + Yj + Zk. (yht„l” esitet„„n siis normaalisti alemmassa, sievennetyss„ muodossa) T„m„ tarkoittaa siis, ett„ vektorin suunta saadaan kun menn„„n ensin jostain mielivaltaisesta pisteest„ X yksikk”„ x-akselin suuntaan, sitten Y yksikk”„ y-akselin suuntaan ja lopuksi Z yksikk”„ z-akselin suuntaan. Kun t„h„n saatuun pisteeseen piirret„„n viiva pisteest„ josta aloitettiin (ja viivan loppu- p„„h„n se nuoli osoittamaan vektorin suuntaa), saadaan vektori jonka yht„l” on Xi+Yj+Zk. Vektori voidaan siis k„sitt„„ my”s janana pisteest„ (0,0,0) pisteeseen (X,Y,Z). HUOM! LOPPUPISTEEN koordinaatista VŽHENNETŽŽN aina ALKUPISTEEN koordinaatti. 1.3 Vektorin pituus Vektorin AB pituus merkit„„n sen itseisarvona ja lasketaan ynn„„m„ll„ sen termien neli”t yhteen ja ottamalla summasta neli”juuri (sqrt, SQuare RooT; ruotsia. ;) __ |AB| = sqrt( X^2 + Y^2 + Z^2 ). Matikkaa koulussa opiskelleet muistavat, ett„ t„m„ on sama kuin pisteen (X,Y,Z) et„isyys origosta. Yksikk”vektori on vektori, jonka pituus on yksi. Saat vektorista yksikk”vektorin jakamalla i:n, j:n ja k:n kertoimen vektorin pituudella. Jos et usko, voit kokeilla itse ;) _ _ TEHTŽVŽ: Olkoon a = i + j + k. M„„rit„ a:n suuntainen yksikk”- vektori. Ratkaisu: _ |a| = sqrt ( 1^2 + 1^2 + 1^2 ) = sqrt(3), _ a:n suuntainen yksikk”vektori: (1/sqrt(3))i + (1/sqrt(3))j + (1/sqrt(3))k). 1.4 Vektorien yhteenlasku Vektorien yhteenlasku tapahtuu laskemalla termit yhteen. V„hennyslasku vastaavasti, mutta miinusmerkkinen vektori osoittaa vastakkaiseen suuntaan kuin plusmerkkinen. _ _ _ _ _ _ _ Esim. Olkoon a = Axi + Ayj + Azk ja b = Bxi + Byj + Bzk. _ _ _ _ _ T„ll”in a + b = (Ax+Bx)i + (Ay+By)j + (Az+Bz)k _ _ _ _ _ ja a - b = (Ax-Bx)i + (Ay-By)j + (Az-Bz)k. _ __-->/| a+b__-- / __-- / b |----a----> \ / a-b\ / -b >/_ _ _ _ _ _ _ _ _ TEHTŽVŽ: Olkoon a = 2i - 6j ja b = i + 3j. Laske | 2a - b |. Ratkaisu: 2a = 2*2i - 2*6j = 4i - 12j, 2a-b = (4-1)i + (-12-3)j = 3i - 15j, | 2a-b | = sqrt( 3^2 + (-15)^2 ) = sqrt(9+225) = sqrt(234). 1.5 Skalaaritulo Vektorien tulosta k„ytet„„n nimityst„ skalaari- eli pistetulo. Pistetulo luetaan "a piste b" ja se lasketaan kertomalla a:n pituus b:n pituudella ja viel„ vektorien v„lisen kulman kosinilla. Sen voi my”s laskea kertomalla molempien vektorien i:n, j:n ja k:n kertoimet yhteen ja lis„„m„ll„ ne toisiinsa. HUOM! Vektorien v„linen kulma tarkoittaa aina pienemp„„ kulmaa joka j„„ vektorien v„liin niiden alkaessa samasta pisteest„. _ _ _ _ _ _ _ aúb = |a||b|cos(a,b) /| = Ax*Bx + Ay*By + Az*Bz. b /\ / | ----------> a HUOM! Vektorit ovat toisiaan vastaan kohtisuorassa, kun niiden v„linen kulma on 90 astetta eli cos(a,b)=0 eli aúb=0! _ _ _ _ TEHTŽVŽ: M„„rit„ vektorien a+b ja a-b v„linen kulma, kun a = 3i + j ja b = i - 7j. Ratkaisu: a+b = (3+1)i + (1-7)j = 4i - 6j a-b = (3-1)i + (1+7)j = 2i + 8j (a+b)ù(a-b) = |a+b| * |a-b| * cos(a+b,a-b), toisaalta (a+b)ù(a-b) = 4*2 + (-6)*8 = 8-48 = -40. |a+b| = sqrt( 4^2 + (-6)^2 ) = sqrt(16+36) = sqrt(52), |a-b| = sqrt( 2^2 + 8^2 ) = sqrt(4+64) = sqrt(68). Yht„l”st„ sqrt(52) * sqrt(68) * cos(a+b,a-b) = -40 saadaan cos(a+b,a-b) = -40 / sqrt(52*68). T„st„ kulma on 132.3 astetta. 1.6 Vektoritulo Kolmiulotteisessa avaruudessa m„„ritell„„n kahden vektorin a ja b vektori- eli ristitulo a x b (luetaan "a risti b") vektorina, jonka _ - pituus |a x b| ilmoittaa vektorien |\ axb _ a ja b m„„r„„m„n suunnikkaan alan: \ /| |a x b| = |a||b|sin(a,b) (suunnikkaan \ a / \ b alan kaava, k„ytet„„n my”s geomet- \/\ / > riassa) \/ |axb| /| - suunta m„„r„ytyy siten, ett„ a x b \ / on kohtisuorassa vektoreita a ja b b\ / a vastaan. >/ HUOM! Kuviossa siis my”s b ja axb ovat suorassa kulmassa toisiaan vastaan, vaikkei silt„ n„yt„ :) Muuta muistettavaa ristitulosta: - a x a = 0, - a x b = -(b x a) eli vaihdantalaki ei ole voimassa suoraan, - kun r on vakio, (ra) x b = r(a x b) eli vakion siirr„nt„laki on voimassa, - a x (b + c) = a x b + a x c eli osittelulaki on voimassa, - i x j = k (ja vastaavasti k x i = j ja j x k = i). Ristitulon lauseke voidaan kirjoittaa helposti muistettavaan muotoon ottamalla avuksi k„site determinantti (matriiseja, jee!-) Kaksirivinen determinantti m„„ritell„„n nelj„st„ luvusta muodostettuna kaaviona, jonka arvo lasketaan seuraavasti: ³ a b ³ ³ c d ³ = ad - cb (kyseess„h„n on RISTItulo :) Kolmirivinen determinantti taas, jota useimmiten k„ytet„„n, tarkoittaa vektorien a=Axi+Ayj+Azk ja b=Bxi+Byj+Bzk ristituloa: _ _ _ _ _ ³ i j k ³ a x b = ³ Ax Ay Az ³ ³ Bx By Bz ³ ³ Ay Az ³ _ ³ Az Ax ³ _ ³ Ax Ay ³ _ = ³ By Bz ³ i + ³ Bz Bx ³ j + ³ Bx By ³ k _ _ _ = (Ay*Bz-By*Az)i + (Az*Bx-Bz*Ax)j + (Ax*By-Bx*Ay)k Eli siirryt„„n yksi kerrallaan ylimm„ll„ vaakarivill„ i:n, j:n ja k:n kohdalle, ja peitet„„n jokaisen kohdalla vuorollaan kohdalla oleva pystyrivi (siis niin, ett„ kyseess„ oleva kirjain j„„ peittoon). Lopuista alemmista riveist„ muodostetaan kaksirivinen determinantti, lasketaan sen normaalisti ja lopuksi kerrotaan ylimm„n rivin kirjaimella. Piis of keik, isnt it, m„„„n?-) Useampirivisi„kin determinantteja on n„kynyt, ja ne ratkaistaan vastaavasti. Siis esimerkiksi nelirivisest„ determinantista muodostetaan kolmirivisi„ jne. TEHTŽVŽ: M„„rit„ vektorien i - j + 2k ja 2i + 3j - k m„„r„„m„n suunnikkaan ala. Ratkaisu: ³ i j k ³ ³-1 2³ ³ 2 1 ³ ³ 1 -1³ ³ 1 -1 2 ³ = ³ 3 -1³i + ³-1 2 ³j + ³ 2 3³k ³ 2 3 -1 ³ = (-1*(-1)-3*2)i + (2*2-(-1)*1)j + (1*3-2*(-1))k = (1-6)i + (4+1)j + (3+2)k = -5i + 5j + 5k. Ala = vektorin pituus = sqrt( (-5)^2 + 5^2 + 5^2 ) = sqrt(75). 1.7 Skalaarikolmitulo Skalaarikolmitulo merkit„„n (a x b)úc ja sen itseisarvo ilmoittaa vektorien a, b ja c m„„r„„m„n suuntaiss„rmi”n tilavuuden (ks. ristitulossa suunnikas). HUOM! Jos t„m„ tilavuus on nolla, vektorit a, b ja c ovat tietysti samassa tasossa! Skalaarikolmitulo on helppo laskea kolmirivisell„ determinantilla, jolloin ristitulon tapauksessa k„ytetty„ determinanttia muutetaan vain ylimm„n rivin osalta, _ _ _ ³ Cx Cy Cz ³ (a x b)úc = ³ Ax Ay Az ³ ³ Bx By Bz ³ ja lasketaan muuten t„sm„lleen samalla tavalla. Esim. Vektorien i + j - k, 2i - 4j + k ja -4i + 3k skalaarikolmitulo: ³ 1 1 -1 ³ ³-4 1³ ³ 1 2³ ³ 2 -4³ ³ 2 -4 1 ³ = 1 * ³ 0 3³ + 1 * ³ 3 -4³ + -1 * ³-4 0³ ³ -4 0 3 ³ = (-4*3 - 0*1) + (1*(-4) - 3*2) - (2*0 - (-4)*(-4)) = -12 + (-10) + 16 = -6. TEHTŽVŽ: M„„rit„ vakio a siten, ett„ vektorit i - j + 2k, 2i + 3j - k ja ai - 4j + k ovat saman tason suuntaisia. Ratkaisu: ³ 1 -1 2 ³ ³ 3 -1³ ³-1 2 ³ ³ 2 3³ ³ 2 3 -1 ³ = 1*³-4 1³ + (-1)*³ 1 a ³ + 2*³ a -4³ ³ a -4 1 ³ = (3*1-(-4)*(-1)) - (-1*a-1*2) + 2*(2*(-4)-a*3) = (3-4) - (-a-2) + 2*(-8-3a) = -1 + a + 2 - 16 - 6a = -5a - 15 Samassa tasossa -> skalaarikolmitulo = 0, -5a - 15 = 0 <=> -5a = 15 <=> a = -3. 1.8 Matriisitulo Ovat ne sitten hianoja, nuo determinantit eli matriisit. Pelk„ll„ ristitulolla vain ei paljon tee, esimerkiksi matriisien avulla tapahtuvassa 3d-py”rittelyss„ tarvitaan matriisien kertolaskua: ³ a b c ³ ³ k l m ³ ³ ak+bn+cq al+bo+cr am+bp+cs ³ ³ d e f ³ * ³ n o p ³ = ³ dk+en+fq dl+eo+fr dm+ep+fs ³ ³ h i j ³ ³ q r s ³ ³ hk+in+jq hl+io+jr hm+ip+js ³ Matriisituloa voidaan selvitt„„ tulkitsemalla se ensimm„isen matriisin vaaka- ja toisen matriisin pystyrivien muodostamien "vektorien" pistetuloiksi (ks. 1.5): ensin ensimm„isen matriisin ylin vaakarivi ja toisen matriisin ensimm„inen pystyrivi, sitten ensimm„isen matriisin ylin vaakarivi ja toisen keskimm„inen pystyrivi, sitten 1. matriisin ylin vaakarivi ja toisen viimeinen pystyrivi. Edelleen 1. matriisin keskimm„inen vaakarivi ja toisen ensimm„inen, ... Ja tulokset uuteen matriisiin 1. matriisin termien paikoille, esimerkin mukaisesti. 1.9 Vektorin ja matriisin tulo Eip„ t„ss„ muuta kuin esimerkki„ kehiin (4x4-matriisi koska niit„ k„ytet„„n 3d-laskutoimituksissa): ³ a b c 0 ³ (Xi+Yj+Zk) * ³ e f g 0 ³ = (aX+eY+iZ+m)i + (bX+fY+jZ+n)j + ³ i j k 0 ³ (cX+gY+kZ+o)k ³ m n o 1 ³ Eli i:n uusi kerroin saadaan kertomalla 1. pystyrivin eli i-rivin arvot vektorin kertoimilla sek„ alin yhdell„, j:n ja k:n kertoimet vastaavasti. T„t„ kaavaa voidaan k„ytt„„ vektorien lis„ksi my”s pisteen transformoimiseen matriisilla, jolloin kirjaimet (X,Y,Z) ilmoittavat pisteen alkuper„iset koordinaatit, ja kaavan tuloksen i:n, j:n ja k:n kertoimet vastaavasti tuloskoordi- naatit. 2. 3D:n alkeet -------------- 2.1 2D- ja 3D-maailman yhteys Avaruudessa sijaitsevan pisteen koordinaatit ilmoitetaan kolmen koordinaatin - x:n, y:n ja z:n - avulla. Kaksiulotteiselle monitorin pinnalle t„llaista pistett„ ei kuitenkaan voida suoraan piirt„„, joten tarvitaan muunnoskaava, jolla z-koordinaatti voidaan sis„llytt„„ x:„„n ja y:hyn. Mietit„„np„ asiaa. Pisteen voi kertoa vakiolla, jolloin se pysyy origon kautta kulkevalla suoralla: (X, Y, Z) => k(X, Y, Z) = (kX, kY, kZ) Jos m„„rit„mme kamerapisteeksi origon, voimme k„ytt„„ t„t„ kaavaa ja ottaa k:ksi 1/z:n jolloin z-koordinaatista tulee vakio: 1/Z * (X, Y, Z) = (X/Z, Y/Z, 1). T„llaiset pisteet ovat tasolla Z=1. Jos haluamme avaruutemme l„hemm„s / kauemmas oletusarvoisesti, voimme muuttaa kaavaa hiukan: a/Z * (X, Y, Z) = (X*a/Z, Y*a/Z, a) Nyt tason, jolla kaikki pisteet ovat, yht„l” on Z=a, ____________________________________ | ^y _ | | ³ /|z x(10,0,30) | ³ / | | ³ / | -----³-------/---------x(10*a/30,0,a)----- | ³ / ^ | |__³___/___³_________________________| ³ / (0,0,a) ÄÄÄÄÄÄÄÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ> ³ x ³ eli kaikki avaruuden pisteet siirret„„n nelikulmion esitt„m„lle tasolle siten, ett„ ne pysyv„t origon kautta kulkevalla suoralla. Kaava on siis seuraavanlainen: X_SCREEN = X0 * PERSPECTIVE / Z0 Y_SCREEN = Y0 * PERSPECTIVE / Z0 PERSPECTIVE kertoo, kuinka l„helt„ 3d-maailmaa tarkastellaan (mit„ pienempi arvo, sit„ l„hemp„n„ ollaan). Kokeilemalla selvi„„ kuhunkin tilanteeseen sopiva arvo, usein k„ytet„„n 2:n potensseja 8 ja 9; niill„ on nopea laskea, ja ne ovat sopivalla et„isyydell„. T„ll”in z-akselin 0-kohta eli kohta, jossa z-koordinaatin arvo ei vaikuta x:„„n ja y:hyn, on tietysti sama eli 256 tai 512, ja muuteltaessa z:n arvoa reaaliaikaisesti huomataan 3d-efekti. HUOM! Jos z:n arvoksi tulee kesken ohjelman ajon nolla, ei tapahdu mit„„n kivaa. Siisp„ v„ltt„k„„mme t„llaista sattu- essaan niin kovin valitettavaa tapahtumaa mahdollisuuksiemme mukaan! Kolmiulotteisuuden havainnollistamisen esimerkki pseudokoodina (piirt„„ pisteen ruudun keskiosaan. Z:n arvon muuttuessa se h„vi„„ ruudusta): x = 1 y = 1 z = 256 while (gx<320) and (gx>-1) and (gy<200) and (gy>-1) gx = x * 256 / z + 160 ; keskipiste = ruudun keskipiste gy = y * 256 / z + 100 ; (320x200-tila) putpixel(gx,gy,15) z = z - 1 if (z = 0) ; varmistetaan ettei VAIN... :) z = -1 endif endwhile "Viritetty" versio onkin sitten jo 3d-starfield, demoscenen perusefekti puolenkymment„ vuotta sitten. Suositeltava harjoitusteht„v„ muuten! 2.2 3D-py”ritysten perusyht„l”t Huom. en itse k„yt„ n„it„ py”rityksi„ en„„, kun sain k„siini matriisipy”ritysten selostuksen. Vakavampaan 3d-koodaamiseen matriisit ovat ainoa oikea tapa, mutta aluksi n„m„ peruspy”ritykset kelpaavat ihan hyvin. Ensin pit„nee selvitt„„ trigonometristen funktioiden periaate. Jos piirr„mme ympyr„n, jonka keskipiste on xy-tason origossa ja jonka s„de on 1, ympyr„n jokaisen pisteen koordinaatit saadaan seuraavasti t:n saadessa kaikki reaaliarvot (lukion matikkaa ihan ensimm„isilt„ kursseilta): ^ x = cos(t) ____|____ y = sin(t) / | \A(x,y) / | / \ Janan OA pituus on siis 1 ja / | / \ t on kulma jonka jana OA | |/ \t | muodostaa x-akselin kanssa. --|--------O---|----|----> | | | Kun aloitamme uuden kierroksen, \ | / sini ja kosini py”r„ht„v„t my”s \ | / ymp„ri ja rumba jatkuu. \____|____ / | Jos kerromme x:n ja y:n jollain reaaliluvulla, voimme pienent„„ tai suurentaa ympyr„n kokoa tarpeen mukaan. -- ok -- Haluamme py”ritt„„ pistett„ (X1,Y1) ^ y kulman k verran vastap„iv„„n eli | positiiviseen kiertosuuntaan. T„ss„ x(X2,Y2) _x(X1,Y1) tapauksessahan py”ritt„minen tapahtuu \ | __-- z-akselin ymp„ri, koska z-koordinaatti \|__--\ a pysyy koko ajan samana eli sit„ ei ----------|----> x huomioida. | HUOM! K„yt„mme vasemman k„den py”rityssuuntaa, eli kun vasemman k„den peukalo osoittaa akselin, jonka ymp„ri py”- ritet„„n, suuntaan, sormet taipuvat positiiviseen kierto- suuntaan (z-akseli ty”ntyy siis t„ss„ koordinaatistossa kohti- suoraan ruudun sis„„n, y-akseli alas ja x-akseli oikealle). Kulma, jonka jana origosta pisteeseen (X1,Y1) muodostaa x-akselin kanssa, olkoon a. T„ll”in kulma, jonka jana ori- gosta pisteeseen (X2,Y2) muodostaa saman akselin kanssa on k+a. Uudet koordinaatit ovat siis X2 = r * cos(k+a) Y2 = r * sin(k+a), miss„ r on py”rityss„de. Kaavojen (lukion taulukoista) cos(a+b) = cos(a) * cos(b) - sin(a) * sin(b) sin(a+b) = sin(a) * cos(b) + cos(a) * sin(b) avulla muutamme uusien koordinaattien yht„l”n muotoon X2 = r * cos(k) * cos(a) - r * sin(k) * sin(a) Y2 = r * sin(k) * cos(a) + r * cos(k) * sin(a) Toisaalta seuraavan kuvan perusteella voimme p„„tell„ lis„„: ^ | _(X1,Y1) | /| | r / | | / |Y1 |/ a | ---------|---------------> | X1 Kyseess„h„n on suorakulmainen kolmio, jonka kateetit muodostuvat pisteen x- ja y-koordinaateista ja hypotenuusa py”rityss„teest„. Koska (t„m„n verran varmaan kaikki osaa- vat?-) cos(a) = X1 / r sin(a) = Y1 / r, voimme ilmoittaa r*cos(a):n ja r*sin(a):n x:n ja y:n avulla: r * cos(a) = X1 r * sin(a) = Y1. Niinp„ kaavoistamme supistuvat hankalat py”rityss„de ja alkupisteen ja origon muodostaman janan sek„ x-akselin v„li- sen kulman lausekkeet pois: X2 = X1 * cos(k) - Y1 * sin(k) Y2 = X1 * sin(k) + Y1 * cos(k). Omiin silmiins„h„n sit„ ihminen parhaiten uskoo, joten kokeilu laskimella ja ruutupaperilla voi olla paikallaan. Piirr„ siis koordinaatisto, ja siihen piste (5,5). Py”r„yt„ t„t„ pistett„ 45 astetta vastap„iv„„n (piirr„ geokolmion avulla uusi piste, et„isyys origoon s„ilyy tietysti samana). Laske sitten yll„olevien kaavojen avulla sama, ja huomaat, ett„ mittaus- tarkkuuden rajoissa tulokset ovat yht„pit„v„t (0,7). Nyt lis„„mme mukaan z-koordinaatin, ja voimme esitell„ kaikki kaavat siistiss„ paketissa. Z-akselin ymp„ri: X2 = X1 * cos(k) - Y1 * sin(k) Y2 = X1 * sin(k) + Y1 * cos(k) Z2 = Z1, Y-akselin ymp„ri: X2 = X1 * cos(j) - Z1 * sin(j) Y2 = Y1 Z2 = X1 * sin(j) + Z1 * cos(j), X-akselin ymp„ri: X2 = X1 Y2 = Y1 * cos(i) - Z1 * sin(i) Z2 = Y1 * sin(i) + Z1 * cos(i). Kokeillaan j„lleen (ympyr„ ruudulle): X1 = 30 Y1 = 0 Z1 = 256 for (i=0 --> 359) X2 = X1 * cos(i) - Y1 * sin(i) Y2 = X1 * sin(i) + Y1 * cos(i) Z2 = Z1 X2 = X2 * 256 / Z + 160 Y2 = Y1 * 256 / Z + 100 putpixel(X2,Y2,15) endfor Ympyr„n saa toki ruudulle paljon helpomminkin, mutta niuhottajille tiedoksi, ett„ nyt oli tarkoitus havainnollistaa n„it„ kaavoja :) 2.3 Sinien ja kosinien taulukoiminen Trigonometristen funktioiden k„ytt” reaaliajassa on niin hidasta, ett„ kun ne taulukoidaan, koodin nopeus monin- kertaistuu. Valaisen taulukoimisen ideaa esimerkin avulla: (sinus ja cosinus ovat 256-alkioisia signed 16bit-taulukoita) for a=0 to 255 sinus[a] = SCALE * sin( a * pi / 128 ) cosinus[a] = SCALE * cos( a * pi / 128 ) endfor HUOM!!! Monet lukijat ovat l„hett„neet toimimatonta koodiaan, jossa er„s useimmiten lukuisista virheist„ on se, ettei alkoita varata kuin 255. C-kieless„ taulukko pit„„ siis varata n„in: short sinus[256], EI sinus[255]! K„sitt„m„t”nt„ miten ihmiset voivat olla tyhmi„ ;) Sinin ja kosinin arvothan liikkuvat v„lill„ -1..1. Koska kokonaislukumuuttujia on nopeampi k„ytt„„, joudumme turvautumaan fixedpointiin eli kertomaan desimaaliluvun tietyll„ kertoimella, jolla pit„„ sitten kalkulointien j„lkeen my”s jakaa. T„ss„ tapauksessa kerroin on vakio SCALE, joka siis vaikuttaa vain mittaustarkkuuteen. Muista jakaa sill„ sitten jokaisessa py”rityslausekkeessa tai tulee *huikeita* lukuja! Sopiva arvo SCALElle on esim. 256 (optimoidessa on helppo ja nopeaa jakaa 2^8:lla eli shiftata luvun bittej„ oikealle 8:lla (Shift Arithmetic Right)). ^^^^^^^^^^ EI shr vaan sar, koska luku voi olla my”s negatiivinen! Ohjelmointikielet vaativat trigonometrisille funktioille parametreina radiaaniarvoja, joten yll„olevassa esimerkiss„ on konvertoitu asteet radiaaneiksi. Asteiden ja radiaanien yhteysh„n on se, ett„ pii on puoli- ympyr„n asteet eli 180 astetta. Niinp„ asteiden konvertoiminen radiaaneksi tapahtuu normaalisti n„in: kulma_rad = kulma_asteina * pi / 180. Yll„olevassa esimerkiss„ on kuitenkin jaettu 128:lla. Miksik”? No siksi, ett„ n„in saadaan n„pp„r„sti m„„ritelty„, ett„ 128*2 astetta on t„ysympyr„. Seh„n on 256 eli byte/unsigned char/jne! Nyt kun siis byte-tyyppist„ muuttujaa kasvatetaan astemuut- tujana, py”r„ht„v„t trigonometriataulukot ymp„ri juuri oikeas- sa kohdassa eli t„ysiympyr„n kohdalla -> ei tule hyppy„, vaan py”ritys jatkuu tasaisena aloittaen uuden kierroksen! Yll„oleva pit„„ sitten luultavasti lukea moneen kertaan :) Ei tietenk„„n ole v„ltt„m„t”nt„ k„ytt„„ juuri 256-alkioista taulukkoa, vaikka sill„ saavutetaankin tuo rollaustemppu. On t„ysin perusteltua k„ytt„„ joskus suurempialkioisiakin taulu- koita, sill„ siten kappaleita voidaan py”ritt„„ pehme„mmin. Kokonaisuudessaan rollaustemppu ei ole mitenk„„n erityisesti koodia nopeuttava, k„tev„mpi vain. 2.4 Pisteen py”ritt„minen kaikkien akseleiden ymp„ri samanaikaisesti Kaikkien akseleiden ymp„ri py”ritt„minen ei tapahdukaan yht„ helposti kuin yhden akselin ymp„ri. Itse k„ytin ennen matriiseihin siirtymist„ seuraavaa tekniikkaa (omaksuttu Bas van Gaalenilta, tnx vaan sinnekin p„in :) 1) x-koordinaatti y-akselin suhteen 2) y- " x- " " 3) z- " y- " " 4) z- " x- " " 5) y- " z- " " 6) x- " z- " " Nyt sitten m„„ritell„„n kolme byte-tyyppist„ muuttujaa jotka kasvavat tai v„henev„t tasaisesti, ja k„ytet„„n niiden arvoja kulmina. Esimerkiksi i,j ja k ovat kivoja, kun niit„ k„ytet„„n vektoreissakin. Sitten py”ritykset, konvertoinnit ja pikseli ruudulle! Fiilis on hauska, kun ensimm„isen kerran liikkuu pikseli 3d-avaruudessa jonkinlaista ympyr„rataa ;) T„ss„ on pseudokoodinp„tk„, jolla voidaan py”ritt„„ pistett„ 3d-avaruudessa yhden, kahden tai kolmen akselin ymp„ri samanaikaisesti. Kun konvertoit t„m„n k„ytt„m„llesi ohjelmointi- kielelle, on sinulla k„yt”ss„si 3d-rutiini, jolla saat aikaan *melkein* mit„ vain. K„ytt” tapahtuu muuttamalla haluttujen kulmien arvoja (i=x-akselin ymp„ri, j=y, k=z), ajamalla t„m„ rutiini ja piirt„m„ll„ piste ruutuun. 10 minuutin sessio ruudulla liikkuvan pikselin ihailua on muuten ihan normaalia :D - a, b, c ovat apumuuttujia (arvoina ei mit„„n "m„„r„tty„"), - xp, yp, zp ovat pisteen alkukoordinaatit joita *EI* muutella, - orig_x, orig_y ovat ruudun keskipisteen koordinaatit. a = ( cosinus[j] * xp - sinus[j] * zp ) / 256 b = ( -cosinus[k] * yp - sinus[k] * a ) / 256 c = ( cosinus[j] * zp + sinus[j] * xp ) / 256 x = ( cosinus[k] * a - sinus[k] * yp ) / 256 y = ( -cosinus[i] * b + sinus[i] * c ) / 256 z = ( cosinus[i] * c + sinus[i] * b ) / 256 + PERSPECTIVE if (z=0) z=1 endif x = x * PERSPECTIVE / z + orig_x y = y * PERSPECTIVE / z + orig_y Jos muuten ihmetytt„„, ett„ mill„ perusteella a, b ja c esiintyv„t juuri noissa kohdissa kaavoja, voit kokeilla: py”rit„ vain yhden akselin ymp„ri kerrallaan muiden kulmien ollessa nollia. T„ll”in a:n, b:n ja c:n lausekkeesta supistuvat aina sinikertoimiset koordinaatit pois (sin(0) = 0), ja j„ljelle j„„ vain haluttu koordinaatti. Plus- ja miinusmerkkej„ on my”s eri kohdissa kuin yksitt„isiss„ kaavoissa. T„m„ johtuu siit„, ett„ kun lasketaan jokaisen akselin ymp„ri py”ritykset joka kerta vaikkei aina v„ltt„m„tt„ py”ritett„isik„„n kuin vaikkapa yhden akselin ymp„ri, merkkeihin tulee muutoksia laskutoimitusten tiimellyksess„. Esim. Py”ritet„„n pistett„ 90 astetta (eli 256-asteisessa ympyr„ss„ 128/2 = 64 astetta) z-akselin ymp„ri. Mit„ koodi t„ll”in tekee? Rivi kerrallaan: a = ( 256 * xp - 0 * zp ) / 256 = xp b = ( -0 * yp - 256 * xp ) / 256 = -xp c = ( 256 * zp + 0 * xp ) / 256 = zp x = ( 0 * xp - 256 * yp ) / 256 = -yp y = ( -256 * (-xp) + 0 * zp ) / 256 = xp z = ( 256 * zp + 0 * (-xp) ) / 256 = zp. N„in ollaan siis saatu aivan oikea tulos, ett„ x-koordinaatista tulee y-koordinaatin vastaluku ja y-koordinaatista x-koordinaatti z-koordinaatin s„ilyess„ ennallaan. HUOM!! Rutiini py”ritt„„ pisteen (0,0,0) ymp„ri, EI pisteen (x_ruudun_kp,y_ruudun_kp,PERSPECTIVE) tms ymp„ri kuten jotkut ovat luulleet, eli pisteeseen lis„t„„n ruudun keskipisteen koordinaatit vasta py”ritt„misen j„lkeen! 2.5 Idea enginen toteuttamiseen Polygonit ja pisteet olisi tietysti mukava saada jonkinlaiseen taulukkoon, josta ne olisi helppo poimia. Aika fiksu tapa on tehd„ pisteille taulukko, ja asettaa polygonitaulukon arvot osoittamaan t„m„n pistetaulukon indeksej„: signed integer vertex[3,3] = ( (0,0,0), (10,0,0), (0,10,0) ) unsigned integer face[1,3] = ( (0,1,2) ) Nyt voidaan osoittaa vertex- eli pistetaulukkoon n„ps„k„sti vertex[face[0,0],0] etc. Polygoneille voi samaan taulukkoon m„„ritt„„ my”s vaikkapa v„riarvon (ja vertekseille verteksinormaalit env-mappausta, phongia tai gouraudia varten). HUOM! Žl„ k„yt„ py”ritetyille ja alkuper„isille pisteille samaa taulukkoa -- tuloksena on muuten pelkk„„ sotkua ruudun t„ydelt„. Siisp„ alkuper„iset ja py”ritetyt pisteet omiin taulukoihinsa! 3. 3D ja matriisit ------------------ T„t„ kappaletta ei ole v„ltt„m„t”nt„ lukea, ellet sitten satu haluamaan enginest„si nopeampaa ja k„tev„mp„„ ;) 3.1 Aivan uusi ajattelutapa T„h„n asti olemme k„sitelleet objekteja pisterypp„in„, eli olemme aina suorittaneet operaatiot jokaiselle pisteelle erikseen. Milt„ tuntuisi esitt„„ objektia yht„kki„ nelj„n vektorin (suunnat yl”s, sivulle ja eteen sek„ paikkavektori) avulla, suorittaa kaikki operaatiot niille ja vasta lopuksi liitt„„ pisteet mukaan kertomalla se objektimatriisilla? T„ss„ tavassa on monta hyv„„ puolta: se on nopeampi, yksinkertaisempi ymm„rt„„, helpompi toteuttaa ja eksaktimpi. Ai miss„k” mieless„ eksaktimpi? Otetaan esimerkiksi (juujuu, on se suoraan otmmatx.doc:sta :) lentokone, jonka nokka osoittaa z-akselin, oikea siipi x-akselin ja vasen siipi y-akselin suuntaan. Py”rit„ lentokonetta y-akselin ymp„ri niin, ett„ sen nokka osoittaa negatiivisen x-akselin suuntaan. Nyt kun py”rit„t sit„ z-akselin ymp„ri, py”riik” se *oman* z-akselinsa vai *avaruuden* z-akselin ymp„ri? Tarkoitus on tietysti, ett„ se py”rii oman z-akselinsa ymp„ri (miten muuten olisivat toteutettavissa esim. lentosimulaattorit?), mutta "normaaleilla" py”rityksill„ n„in ei k„y. Siisp„ matriiseja. 3D-ohjelmoinnissa k„ytet„„n 4x4-matriiseja, joista tiedot l”ytyv„t seuraavasti: ³ [X-akselin yksikk”suuntavektori] 0 ³ ³ [Y-akselin yksikk”suuntavektori] 0 ³ ³ [Z-akselin yksikk”suuntavektori] 0 ³ ³ [Keskipisteen koordinaatit] 1 ³ Eli ensimm„isen rivin kolme enimm„ist„ saraketta ilmoittavat objektin x-akselin suuntavektorin i:n, j:n ja k:n kertoimien arvot, toisen ja kolmannen rivin vastaavasti y- ja z-akselin, kuvan mukaisesti. Viimeisen pystyrivin arvot ovat aina nuo (0,0,0,1), joten ne voi j„tt„„ poiskin. Alimman rivin kolme ensimm„ist„ saraketta ilmoittavat siis objektin keskipisteen koordinaatit ((0,0,0) jos halutaan sen py”riv„n oman keskipisteens„ ymp„ri -- py”ritysrutiinit py”ritt„v„t *aina* origon ymp„ri -- tai muuten tarpeen mukaan). Viimeisen sarakkeen arvot ovat aina kuviossa esitetyt, ne eiv„t vaihtele. HUOM! Kuten kuvasta n„kyy, vektorit ovat YKSIKK™vektoreita, eli niiden pituus on yksi. Kannattaa ehk„ alustaa objekti- matriisi aina siten, ett„ objekti lep„„ esimerkkimme lentokoneen mukaisesti xz-tasolla, jolloin se on seuraava: ³ 1 0 0 0 ³ ³ 0 1 0 0 ³ ³ 0 0 1 0 ³ ³ 0 0 0 1 ³ T„ll”in siis objektin yksikk”vektorit ovat i, j ja k eli samat kuin avaruuden yksikk”vektorit. Kaikki 3d-operaatiot ovat matriisitekniikalla matriisien kertolaskua tai matriisin ja vektorin kertolaskua. 3.2 Objektimatriisin liikuttaminen eli transformointi 3.2.1 Siirt„minen eli translaatio Objekti siirt„minen tapahtuu yksinkertaisesti siirt„m„ll„ objektimatriisin keskipistett„, eli kertomalla t„llaisella matriisilla: ³ 1 0 0 0 ³ ³ 0 1 0 0 ³ ³ 0 0 1 0 ³ ³ X Y Z 1 ³ miss„ X, Y ja Z ovat kunkin akselin suuntaan liikuttava matka (eri akselien suuntaiset yksikk”vektorit j„tet„„n tietysti ennalleen). HUOM! Siirt„minen kannattaa tehd„ vasta py”ritt„misen j„lkeen, ellet halua objektin py”riv„n *uuden* origon, ei oman keskipisteens„ ymp„ri. 3.2.2 Py”ritt„minen eli rotaatio Objektia py”ritett„ess„ kerrotaan objektimatriisi n„ill„ matriiseilla j„rjestyksess„ X, Y, Z tai tarpeen mukaan. X-akselin ymp„ri: ³ 1 0 0 0 ³ ³ 0 cx sx 0 ³ ³ 0 -sx cx 0 ³ ³ 0 0 0 1 ³ Y-akselin ymp„ri: ³ cy 0 -sy 0 ³ ³ 0 1 0 0 ³ ³ sy 0 cy 0 ³ ³ 0 0 0 1 ³ Z-akselin ymp„ri: ³ cz sz 0 0 ³ ³ -sz cz 0 0 ³ ³ 0 0 1 0 ³ ³ 0 0 0 1 ³ cx, sx, cy, sy, cz ja sz tarkoittavat tietysti ao. akse- lien ymp„ri py”ritett„vien kulmien kosineja ja sinej„ (KUVIA en sent„„n ripannut otmmatx:sta ;) N„it„ ei tietenk„„n tarvitse kertoa joka framelle, vaan voimme hiukan prekalkuloida (alin vaakarivi ja oikeanpuo- leisin pystyrivi pysyv„t samoina, joten k„yt„n aluksi 3x3-matriiseja): ³ 1 0 0 ³ ³ cy 0 -sy ³ ³ cy 0 -sy ³ [X]*[Y] = ³ 0 cx sx ³ * ³ 0 1 0 ³ = ³ sx*sy cx sx*cy ³ ³ 0 -sx cx ³ ³ sy 0 cy ³ ³ cx*sy -sx cx*cy ³ ³ cy 0 -sy ³ ³ cz sz 0 ³ [X]*[Y]*[Z] = ³ sx*sy cx sx*cy ³ * ³ -sz cz 0 ³ ³ cx*sy -sx cx*cy ³ ³ 0 0 1 ³ ³ cy*cz cy*sz -sy 0 ³ ³ sx*sy*cz-cx*sz sx*sy*sz+cx*cz sx*cy 0 ³ = ³ cx*sy*cz+sx*sz cx*sy*sz-sx*cz cx*cy 0 ³ ³ 0 0 0 1 ³ Py”ritetty ja siirretty objektimatriisi saadaan siis kaavasta [O'] = [O]*[X]*[Y]*[Z]*[T]. Puhuin kappaleen alussa lentokone-esimerkist„ ja mainitsin, ett„ matriisit ovat ainoa tapa toteuttaa se. Mitenk” homma toimii? Py”ritet„„n vain p„invastaisessa j„rjestyksess„: [O'] = [O]*[Z]*[Y]. Nyt lentokone-esimerkki toimii oikein. Toisaalta ohjelmoija ei voi tiet„„, mink„ akselien suhteen milloinkin py”ritet„„n, joten voisi olla viisasta py”ritt„„ maailmaa Y-akselin ja konetta Z-akselin ymp„ri, eli yleisemmin *ensin* j„lkimm„isten, sitten edellisten kulmien ymp„ri. 3.2.3 Kamera Kameran saa matriisitekniikalla huomattavasti k„tev„mmin mukaan kuin geometrisissa py”rityksiss„: ei tarvitse tehd„ muuta kuin kertoa py”ritetty ja siirretty objektimatriisi kameramatriisilla! [O'] = [O']*[C]. 3.3 Pisteen transformointi objektimatriisilla Nyt tarvitsee en„„ transformoida kaikki pisteet t„ll„ saadulla matriisilla, ja objektin liikuttaminen on selv„! Transformointi voidaan tehd„ helposti luvun 1.9 esitt„m„ll„ tavalla, tosin pisteen koordinaatteja pidet„„n t„ll”in vektorin i:n, j:n ja k:n kertoimina: X = X0*a + Y0*e + Z0*i + m Y = X0*b + Y0*f + Z0*j + n Z = X0*c + Y0*g + Z0*k + o (m, n, o ovat objektin keskipisteen koordinaatit) T„h„n tarvitaan siis yhdeks„n kertolaskua ja yhdeks„n yhteenlaskua -- ei todellakaan paha, kun verrataan edellisiin 12 kerto- ja 6 yhteenlaskuun, ja t„m„ tapa on my”s huomattavasti selke„mpi. Pseudoa lapsukaisille (py”ritet„„n pistett„ matriisitek- niikalla x-akselin ymp„ri): - xm, om, temp_m, old_om (4,4)-kokoisia liukulukutaulukoita - (xp,yp,zp) alkup. piste, (x,y,z) py”ritetty piste kulma = 0 old_om = om looppaa joka framelle: xm[1,1] = cos(kulma) xm[1,2] = sin(kulma) xm[2,1] = -sin(kulma) xm[2,2] = cos(kulma) om = old_om for a=0 -> 3 for b=0 -> 3 temp_m[a,b] = om[a,0]*xm[0,b] + om[a,1]*xm[1,b] + om[a,2]*xm[2,b] + om[3,1]*xm[3,b] om = temp_m x = xp*om[0,0] + yp*om[1,0] + zp*om[2,0] + om[3,0] y = xp*om[0,1] + yp*om[1,1] + zp*om[2,1] + om[3,1] z = xp*om[0,2] + yp*om[1,2] + zp*om[2,2] + om[3,2] putpixel(x,y,z) < kasvata kulmaa > „l„_en„„_looppaa HUOM! Kaikille pisteille ei tarvitse toistaa matriisien kertolaskua, vaan ne kerrotaan samalla objektimatriisilla eli rivit x=xp*.. etc ovat ainoat jotka toistetaan. Loput laskutoimitukset tehd„„n vain kerran / frame. 3.4 Hierarkiset transformaatiot Juu, *t„m„kin* on otmmatx:sta, enk„ edes keksinyt parempaa suomenkielist„ nime„ tuolle otsikolle (englanninkielinen vastinehan kuuluu "hierarchical transformations" :I Oletko koskaan miettinyt, miten on toteutettu pelit, joissa on (vektoripohjaisia) tyylikk„„sti liikkuvia ihmism„isi„ objekteja (Tomb Raider, Quake, mechailut, ...)? Homma hoituu hierarkisilla transformaatioilla. Otetaan esimerkiksi ihmisen k„si. Kun py”rit„t k„tt„ olkap„„st„ asti ymp„ri, my”s ranne, k„mmen ja sormet py”riv„t. Jos taas py”rit„t k„mment„, k„si ei py”ri ranteesta yl”sp„in mutta sormet py”riv„t. K„den osat ovat siis hierarkisesti riippuvaisia: k„mmen voi antaa komentoja sormille, muttei ranteelle, eli se on hierarkisessa j„rjestyksess„ n„iden v„liss„. Samaan tapaan voidaan jakaa linkitettyyn listaan kaikki ruumiinosat. Hierarkisessa systeemiss„ objekti on siis jaettuna osiin, ja eri osat ovat riippuvaisia toisista osista. Mutta miten t„m„ sitten toteutetaan? Jatketaan k„siesimerkill„. Ranteen matriisi on [R], k„mmenen [K] ja sormien [S1], [S2], [S3], [S4] sek„ [S5], ja ne sijaitsevat linkitetyss„ listassa seuraavasti: [R] ³ ÚÄÄÄÂÄÄ[K]ÄÄÄÂÄÄÄ¿ ³ ³ ³ ³ ³ [S1] [S2] [S3] [S4] [S5] (hieno kuva, vaikka itse sanonkin :) Ranteen transformointi, kuten muistamme, tapahtuu n„in: [R] = [R]*[Xr]*[Yr]*[Zr]*[Tr]. K„mmen pit„„ siis oman liikkeens„ lis„ksi transformoida samalla kaavalla, [K] = [K]*[Xk]*[Yk]*[Zk]*[Tr]*[R], ja sormet kaavalla [S?] = [S?]*[Xs?]*[Ys?]*[Zs?]*[Tr]*[K]. HUOM! Jotta n„it„ kaavoja voi k„ytt„„, pit„„ jonossa edellinen matriisi olla valmiiksi transformoitu, eli laskemisj„rjestys on "nokkimisj„rjestys": linkitetyss„ listassa ylh„„lt„ alas. 3.5 Sekalaista matriiseista 1) Jos k„ytet„„n luvun 3.4 kaavaa objektimatriisin transformointiin, py”ristysvirhe alkaa v„hitellen vaikuttaa tulokseen v„„rist„en objektia. Objektimatriisi kannattaa siis tallentaa ja tarkistaa sen arvo tasaisin v„liajoin, vaikka joka sadannella framella. Liukulukumuuttujilla asialla ei ole merkityst„. 2) On kuulemma olemassa my”s toisenlainen (nopeampi) tapa kertoa kaksi matriisia, mutta en ole saanut siit„ tarkempia tietoja, eli jos joku tiet„„ jotain, saa kertoa :) 3) Minulle on mainostettu my”s hiukan erilaista matriisitek- niikkaa. V„itt„v„t sen olevan nopeampi ja k„tev„mpikin, mutta minun selitt„m„ni tapa on yksinkertaisempi ymm„rt„„. Eli: k„ytet„„n 3x3-matriiseja, ja objektien keskipisteiden koordinaatit s„ilytet„„n erillisess„ taulukossa jolle tehd„„n ikiomat transformointirutiinit. Nyt kameran liikkuminen on vaikeampi saada mukaan, mutta objekti py”rii aina oman keskipisteens„ ymp„ri eik„ tarvitse tallettaa vanhaa objektimatriisia joka framelle erikseen. 4x4-matriiseillakin objekti saadaan py”rim„„n keskipisteen- s„ ymp„ri, jos kerrottaessa objektimatriisi py”ritysmatrii- seilla leikit„„n, ett„ kyseess„ ovatkin 3x3-matriisit. Nyt koko keskipistett„ ei edes oteta huomioon, ja s„„styt„„n monelta vaivalta. Mit„ tekniikkaa k„yt„t, se on oma asiasi ;) 4. Erilaisia polygonifillej„ ---------------------------- Piste py”rii nyt siis ruudulla, mutta alkaa pidemm„n p„„lle n„ytt„„ aika tyls„lt„, joten jotain j„re„mp„„ olisi kiva saada aikaan. T„ss„ astuvat kuvaan polygonit. K„sittelen vain kolmioita, koska niiden piirt„minen on nopeinta ja vaivattominta, ja niist„ voi koostaa vaikka kuinka- monikulmaisen polygonin jos tarvetta esiintyy. J„re„mm„ss„ 3d-grafiikassa kolmioiden hy”ty h„vi„„ init-osan viedess„ tehoja jopa enemm„n kuin loopit viev„t, joten nelikulmioiden k„ytt” my”hemmin on j„rkev„„. 4.1 Flat-kolmio Haluamme piirt„„ seuraavan kolmion: a /| / | <-yl„osa / | b /_______| <- huom \ | \ | \ | <-alaosa \ | \ | \| c Pelk„st„„n t„t„ kuviota katselemalla pit„isi saada aikaan t„ydellinen kolmiofilleri. Jos ongelmia (tai laiskuutta :) kuitenkin ilmenee, idea on seuraava: Interpoloi a.x:„„ niin ett„ se liukuu a.x:st„ b.x:„„n (b.y-a.y) askeleessa. Interpoloi a.x:„„ my”s niin, ett„ se liukuu a.x:st„ c.x:„„n (c.y-a.y) askeleessa. Sitten liiku a.y:st„ b.y:hyn lis„ten joka askelella yhden y-koordinaattiin ja interpoloiden „skeisi„ arvoja sek„ vetelem„ll„ vaakaviivoja liu'utettavien x-arvojen v„liin. N„in olet piirt„nyt kolmion yl„osan. Sitten vain sama homma b.y:st„ c.y:hyn, niin alaosakin piirtyy. Voisi olla fiksua mietti„ ja koodata t„m„ kohta itse, ilman seuraavan pseudop„tk„n apua, jotta idea menisi kunnolla kaaliin ja my”hemm„t interpoloinnit etc selkiytyisiv„t parem- min, joten suosittelen sen yli hypp„„mist„ kunnes olet ymm„r- t„nyt interpoloinnin idean (selitetty alla). ** begin triangle ** - koordinaatit ovat (x1,y1), (x2,y2), (x3,y3), - x, y ovat kolmen alkion taulukoita samaa tyyppi„ kuin koordinaatit, - a on apumuuttuja, - delta_x, delta_y ovat kolmen alkion taulukoita samaa tyyppi„ kuin koordinaatit, - d on kolmen alkion taulukko reaalilukutyyppi„. < j„rjestet„„n x- ja y-taulukkoon pisteet siten, ett„ (x[0],y[0]):ssa on piste, jonka y-koordinaatti on pienin, (x[1],y[1]):ssa toiseksi pienin ja viimeisess„ suurin > delta_x[0] = x[1]-x[0] delta_y[0] = y[1]-y[0] delta_x[1] = x[2]-x[1] delta_y[1] = y[2]-y[1] delta_x[2] = x[0]-x[2] delta_y[2] = y[0]-y[2] for (a=0 -> 2) jos (delta_y[a] ei ole nolla) d[a] = delta_x[a] / delta_y[a] muussa tapauksessa d[a] = 0 endjos endfor for (a=y[0] -> y[1]) horizline( x[0] + (a-y[0]) * d[0], x[0] + (a-y[0]) * d[2], a, color ) endfor for (a=y[1] -> y[2]) horizline( x[1] + (a-y[1]) * d[1], x[0] + (a-y[0]) * d[2], a, color ) endfor ** end triangle ** ** begin horizline ** - a on apumuuttuja for (a=x1 -> x2) putpixel(a, y, color) endfor ** end horizline ** ..„n ti ikspl„neiss”n: Kohta joka luultavasti ihmetytt„„ on koodin ensimm„inen looppi, jossa m„„ritell„„n d:n arvot. Mik„ ihmeen dee? Katsotaanpas... Horizline-loopeissa d:t„ n„yt„„n k„ytt„v„n x-koordinaattien m„„ritt„miseen. Hmm... Kun ollaan viimeist„ kertaa ensimm„i- sess„ silmukassa, eli a = y[1], kutsuttaessa horizline„ ensim- m„inen x-koordinaatti n„kyy saavan arvon x[0] + (y[1]-y[0]) * d[0]) = x[0] + (y[1]-y[0]) * (x[1]-x[0]) / (y[1]-y[0]). Lausekkeesta supistuvat (y[1]-y[0]:t pois, ja j„ljelle j„„ x[0] + x[1] - x[0] = x[1], eli kun y-koordinaatti on y[1], x-koordinaatti on vastaavasti x[1], mik„ lienee melko j„rkev„„. Ahaa! d on siis jonkinlainen kerroin, jonka avulla x- ja y-koordinaatti suhteutetaan toisiinsa! Very, VERY smart, I'd say! T„m„ on nyt sitten sit„ interpolointia: x- ja y-koordinaatit suhteutetaan toisiinsa siten, ett„ kun y:t„ lis„t„„n yhdell„, x:„„ lis„t„„n sellaisella luvulla, ett„ y:n saavuttaessa loppu- arvonsa my”s x saavuttaa omansa, eli suomeksi: lineaarinen interpolaatio on yhden arvon liu'uttamista tasaisesti toiseen. Esim. Interpoloikaamme arvo 0 arvoon 4 seitsem„ss„ askeleessa. Askel Arvo 0 0.00 1 0.57 2 1.14 3 1.71 4 2.29 5 2.86 6 3.43 7 4.00 Kuten varmasti huomasitkin, arvo kasvaa 4/7:lla joka askeleel- la, eli arvo on funktio f(X) = X0 + X*(4/7). Yleinen funktio lineaariseen interpolointiin on siis f(X) = A + X*((B-A)/steps), miss„ liu'utaan A:sta B:hen steps m„„r„ss„ askeleita, ja f'(X) (f(X):n derivaatta) eli f(X):n kasvunopeus on (B-A)/steps. Eli jos meill„ on looppi for (y=10 -> 20) x=f(y) piste(x,y) endfor eli for (y=10 -> 20) x=a+x((b-a)/steps) piste(x,y) endfor, se voidaan esitt„„ my”s muodossa x=a for (y=10 -> 20) piste(x,y) x=x+f' endfor eli x=a for (y=10 -> 20) piste(x,y) x=x+(b-a)/steps endfor. N„in olemme n„pp„r„sti optimoineet yhden addin, yhden kertolaskun, yhden jakolaskun ja yhden miinuslaskun yhteen ainoaan pluslaskuun (koska (b-a)/steps on vakio, sen voi laskea etuk„teen l. prekalkuloida). Yll„oleva pseudokoodi ei ota huomioon sit„, ett„ polygoni saattaa olla osittain tai kokonaan reunojen ulkopuolella. Horizline ei my”sk„„n osaa aavistaakaan, ett„ sille saattaa tulla ensimm„isen„ x-arvona suurempi kuin j„lkimm„inen, jolloin loopista tulee *hyvin* pitk„. Tarttis varmaan tehr„ jotain, ja se jotain olisi sitten niin kuin klippaukset ja parit xchg:t. Klippaukset on helppo tyrk„t„ horizline-rutiiniin (huomattavaa on my”s, ett„ mik„li klippauk- set ovat gouraud- tai texture-filleriss„, on muistettava p„i- vitt„„ u:ta ja v:t„ tai gouraudin v„riarvoja oikeissa paikoissa): ** begin horizline ** - a on apumuuttuja - max_x on ruudun leveys jos y>max_y tai y<0 ei_sitten_piirret„k„„n endjos jos x1 suurempi kuin x2 eXCHanGe(x1,x2) endjos jos x1 pienempi kuin nolla x1 = 0 jos taas x1 suurempi kuin max_x ulostaudu_rutiinista endjos jos x2 pienempi kuin nolla ulostaudu_rutiinista muussa tapauksessa jos x2 suurempi kuin max_x x2 = max_x endjos for (a=x1 -> x2) putpixel(a, y, color) endfor ** end horizline ** Wauziwau. Siin„ siis kaikessa yksinkertaisuudessaan kolmionpiirt„misen idea, mutta optimoitavaa tuostakin toki l”ytyy. Hauskoja hetki„ vain optimisaation parissa, sill„ t„m„h„n on se kaikkein eniten aikaa viev„ osa koko 3d-enginess„. Optimointivinkki: Hline-rutiinissa ei tarvitse verrata x:n arvoja toisiinsa vaan x1 on aina pienempi kuin x2, jos kolmiorutiinissa tutkitaan 4.1.1 Fixed point T„m„ oli jotenkin luonnollisinta laittaa interpoloinnin j„lkeen, vai mit„ mielt„ olette?-) Aina ei ole j„rkev„„ k„ytt„„ liukulukuja. T„ll”in, esimerkiksi tarvittaessa jakolaskuja, kannattaa joskus ottaa fixed point, jossa esim. 32-bittist„ lukua k„sitell„„n niin, ett„ 16 ylint„ bitti„ ovat luvun kokonaislukuosa ja alimmat 16 bitti„ desimaaliosa. Mitenk” t„m„ onnistuu? Helppoa: ensin siirret„„n 32-bittiseen muuttujaan jaettava, sitten kerrotaan se 2^16:lla eli siirret„„n jaettava luvun 16 ylimm„ksi bitiksi, ja lopuksi jaetaan jakajalla. Tuloksesta saadaan 2^16 kertaa liian suuri, mutta sikapaljon tarkempi kuin normaalilla kokonaislukujen jakolaskulla, juuri niiden 16 desimaalibitin ansiosta. Nyt sitten operoidaan t„ll„ luvulla, ja muistetaan kertoa kaikki muutkin samassa yhteydess„ tarvittavat luvut 2^16:lla, ja kun ollaan valmiita ja tulos pit„isi esitt„„ (esim. polygonirutiinissamme pikseli ruutuun), muistetaan viel„ jakaakin, yll„tys yll„tys, 2^16:lla (tuosta 2^16:sta pit„„ kyll„ tehd„ makro -- shift-f1 ;) Fixed pointtia k„ytt„v„ pseudokoodiesimerkki l”ytyy alta, kappaleesta 4.2 (eli IHAN alta :) 4.2 Gouraud-kolmio Gouraud-kolmion ja flat-kolmion piirt„misen idea on pitk„lti sama. Gouraud-rutiinille ilmoitetaan vain kolme arvoa enemm„n (jokaisen kulman v„riarvo), ja rutiini interpoloi sitten niiden v„lill„ piirt„en kauniin varjostetun kolmion. Flat-kolmio k„ytti yksinkertaista interpolaatiota, gouraudiin tarvitaan kolminkertainen (interpoloidaan x:n ja y:n, v„riarvon ja y:n sek„ v„riarvon ja x:n v„lill„). Piirrett„ess„ gouraud-kolmio flat-kolmioon lis„t„„n vain kaksi uutta osiota. Horizline-rutiini muuttuu monimutkaisem- maksi v„rin ja x:n v„lisen interpolaation my”t„, mutta itse p„„rutiini s„ilyy suurin piirtein samanlaisena. Gouraud-kolmiosta en esit„ t„sm„llist„ pseudoversiota, vaan jokainen saa itse kehitell„ sen vinkkien pohjalta. N„yt„n kuitenkin t„rkeimm„t kohdat. Ensimm„inen outer loop uusitusta p„„rutiinista: - c[0] on (x[0],y[0]):n v„riarvo - dc:t lasketaan d:n tapaan mutta interpoloimalla c:n ja y:n eik„ x:n ja y:n v„lill„ for (a=y[0] -> y[1]) gouraud_horizline( x[0] + (a-y[0]) * d[0], x[0] + (a-y[0]) * d[2], c[0] + (a-y[0]) * dc[0], c[0] + (a-y[0]) * dc[2], a ) endfor Gouraud-horizline fixedpointilla ja ilman klippauksia: - dc on 32-bittist„ kokonaislukutyyppi„ < vertailu: onko x1 suurempi kuin x2? Jos on, vaihda sek„ x1 ja x2 ett„ c1 ja c2 > dc = ((c2-c1)*65536)/(x2-x1) for (a=x1 -> x2) putpixel(a,y,c1+((a-x1)*dc)/65536) endfor Sulkuja tarvitaan noin paljon jotta laskutoimitukset tulisivat varmasti oikeassa j„rjestyksess„ (jotkut k„„nt„j„t aloittavat lausekkeen purkamisen oikealta). T„h„nkin voisi ottaa derivaatan k„sitteen, eli c1+((a-x1)*dc):n derivaatta eli kasvunopeus on dc. N„in p„„semme eroon kaikista kertolaskuista, ja saamme gouraudin interpolaatiosan hilpe„sti yhteen addiin: c1=c1*65536 ; HUOM! for (a=x1 -> x2) putpixel(a,y,c1/65536) ; HUOM! c1=c1+dc endfor Itse asiassa onkin muuten ep„selvemp„„ mietti„k„„n koko c1+((a-x1)*dc)-k„sitett„, sill„ tuo on varsin selv„, tuttu jo edellisest„ interpolointi-esimerkist„, jossa interpoloitiin arvo 0 arvoksi 4 seitsem„ss„ askeleessa. Tuo looppi siis liu'uttaa arvon c1 arvoksi c2 (x2-x1) askeleessa. Voiko t„t„ en„„ helpommaksi tehd„? ;) Nyt lienee pikainen sana optimoinnista paikallaan, jotta kaikki p„„sev„t hieman sen makuun :) Assya osaat tietysti, mill„ sin„ muuten luulet nopeaa vektorigrafiikkaa koodaavasi?-) Kuten huomaatte, tuossa yll„olevassa esimerkiss„ joudutaan jakamaan 65536:lla, ja jakolasku on tunnetusti varsin hidas operaatio jos sit„ tehd„„n paljon (tosin esim. djgpp optaa 2:n potensseilla jakamiset sareiksi). Nopeinta j„lke„ saa aikaan k„ytt„m„ll„ hyv„ksi iki-ihanaa carry-lippua: Meill„ on kaksi 16-pittist„ muuttujaa, rekisteri„ if you wish. (Vaihtoehtoisesti voi olla yksi 8-bittinen ja toinen 16-bittinen, jos haluamme s„„st„„ rekistereit„ ja tyyty„ 8 bitin desimaali- osaan.) < dx = c1:n desimaaliosa, eli 32-bittisen fixedpoint-luvun 16 alinta bitti„, bx = c1:n kokonaislukuosa, yli ylimm„t piltit. > loopissa: add dx,[adderin_desimaali_osuus] adc bx,[adderin_kokonaisluku_osuus] Ai miksik” noin? Kun ylempi k„sky py”r„ytt„„ dx:n ymp„ri, carry -lippu menee p„„lle, ja dx:n arvoksi j„„ yhteenlaskun alimmat 16 bitti„. adc-k„skyss„ lis„t„„n bx:„„n kokonaislukuosa ja yksi ylim„„r„ist„, jos desimaaliosuus ylitti luvun 2^16-1 eli 0.999... (eli jos siis carry-lippu on p„„ll„). N„in bx:ss„ on sitten pelkk„ kokonaislukuosuus, joten emme joudu edes shiftaamaan. Toinen vaihtoehto olisi .8-fixedpointilla toteutus: < ax=16-bittinen fixedpoint-luku (=alkuper„inen c1*256) > loopissa: mov [ruutu+ruutupos],ah ;ah = kokonaislukuosa. add ax,[fixed_inkkaaaja] N„in 256:lla jakaminen k„y ihan ilmaiseksi (ah:ssa on ax:n 8 ylint„ bitti„). T„t„ ideaa voi laajennella hyvin, hyvin paljon, esimerkiksi niin, ett„ yhdess„ rekisteriss„ interpoloidaan useampaa arvoa etc. Optimointivinkki: gouraudissa v„rideltat ja texturessa (u,v) -koordinaattien deltat s„ilyv„t vakioina, joten niit„ ei tarvitse laskea kuin kerran / poly. Toki kannattaa mietti„, mist„ sen deltan ottaa ;) Optimointivinkki #2: Hline-rutiinissa ei tarvitse verrata x:n arvoja toisiinsa vaan x1 on aina pienempi kuin x2, jos kolmiorutiinissa tutkitaan kulmakertoimia (eli d:n arvoja) y1:st„ y2:een (d[0]), y1:st„ y3:een (d[2]) ja y2:sta y3:een (d[1]) sek„ annetaan hlinen ensimm„iseksi parametriksi seuraavat arvot: interpoloitaessa y1:st„ y2:een suurempikulma- kertoiminen, y2:sta y3:een pienempikulmakertoiminen tekij„. 4.3 Texture-kolmio K„sittelyss„ 'klassinen' texturemappaus ilman perspektiivi- korjausta. Perspektiivikorjaamaton mappaus toimii aika mukavasti objekteilla joissa ei ole isoja polygoneja. T„ll”in texturen v„„ristymist„ ei huomaa, eli klassisen mappauksen k„ytt” lienee t„ss„ tapauksessa perusteltua. Perspektiivi- korjausta tarvitaan kuitenkin useimmissa 3d-systeemeiss„. Anyway, asiaan: Ja j„lleen interpolointi-ideaa kehitell„„n: nyt on vuorossa texturemappaus. Ja j„lleen kerran idea on sama, vain kaksi interpoloitavaa lis„„ eli yhteens„ viisinkertainen inter- polaatio. Texturemappauksessa interpoloidaan x:n ja y:n, u:n ja y:n, v:n ja y:n, u:n ja x:n sek„ v:n ja x:n v„lill„ (u ja v ovat pisteit„ bittikartta-avaruudessa). Tilanne on "helpoin" (lainausmerkit varmaan ymm„rr„tte :I hahmottaa seuraavanlaisesta kuviosta: (x1,y1) (u1,v1)_________________(u2,v2) /\ | /(au2,av2) / / \ | / / (ax1,y)/------\(ax2,y) |/ / / \ |(au1,av1)/ /____ \ | / (x3,y3) -----_____\ | / (x2,y2) | / | / (u3,v3) Vasemmanpuoleinen kuvio on siis ruudulle piirtyv„ kolmio, johon on piirretty yksitt„inen "scanline" eli yhden outer loopin tulos, yksi horizlinen kutsu. Oikeanpuoleinen kuvio vastaa kolmiota bittikartta-avaruudessa, ja sama scanline on merkitty siihenkin toiselta kantilta katsottuna. Texturemappausrutiinissa ei siis tarvitse kuin inter- poloida, interpoloida ja viel„ kerran interpoloida; helppo homma gouraud-rutiinin ymm„rt„neelle (itse v„„nsin gouraudin j„lkeen texturemappauksen -- tosin ilman pers- pektiivikorjausta -- yhdess„ p„iv„ss„)! Ai ett„ koodia kaipaisitte? No way: a) koodi on niin samanlaista kuin gouraudissa ja flat -kolmiossa, ett„ sit„ olisi tyls„ kirjoittaa t„h„n uudelleen ja b) pit„„h„n sit„ jotain itsekin tehd„ ;) Mutta kuten sanottu, e-mail toimii jos olet keskim„„r„ist„ typer„mpi yksil” ;) 4.3.1 Perspektiivikorjauksen periaate Aloitetaan esimerkill„: 3d-starfieldin toiminta. Otetaan piste (1,1,3000), josta haluamme liikkua tasaisesti pisteeseen (1,1,1). T„m„ onnistuu tietysti interpoloimalla z-koordinaattia lineaarisesti: nyt piirtyy 3d-avaruuteen kaunis suora viiva, joka 2d-n„yt”lle transformoitaessa muuttuukin yll„tt„en k„yr„ksi. Mit„s jos haluamme liikkua t„m„n v„lin siten, ett„ se n„ytt„„ *ruudulla* suoralta viivalta? Pit„„ tietysti k„ytt„„ 2d-koordinaattien lineaarista interpolointia. 3d->2d -transformointikaavathan ovat seuraavat: x_2d = x/z, y_2d = y/z. Esimerkkitapauksessamme x ja y ovat molemmat ykk”si„, eli kaavamme sievenev„t muotoon x_2d = 1/z, y_2d = 1/z. N„in olemme saaneet selville, ett„ jos haluamme 3d-k„yr„n n„ytt„v„n ruudulla suoralta, pit„„ interpoloida z:n k„„nteis- arvoa eik„ z:aa itse„„n. My”skin huomaamme, ett„ jos z pysyy vakiona, 'perspektiivin korjaamista' ei tarvita. Mitenk” t„m„ texturemappaukseen liittyy -- texture-kolmiohan l„nt„t„„n jo 2d:hen transformoitujen koordinaattien varaan? Kyll„, *3d-maailman* koordinaatit on transformoitu n„yt”lle, mutta miten on *texture-avaruuden* eli k„yt„nn”ss„ bittikar- tan kanssa? Kyll„, se on 2d-taso jota ei tunnu j„rkev„lt„ en„„ uudelleen v„„nt„„ (tai siis suoristaa :) 2d:hen, mutta kokeile itse klassista texturemappausta ja tule sen j„lkeen sanomaan ett„ texture-kolmiosi liittyv„t toisiinsa saumatto- masti -- ja kerro minulle tekniikka jolla teit sen ;) Tarttis tehr„ jotain j„lleen kerran. Mitenk„s olis jos teht„iski se n„in: u_2d = u/z, v_2d = v/z. Ei, homma ei todellakaan ole t„ll„ selv„. Nyt lineaarinen interpolointi n„ytt„„ ruudullakin lineaariselta, mutta eiv„th„n nuo ole ne koordinaatit joita kaipasimme esitt„m„„n bittikartta-avaruuden koordinaatteja; (u,v) olisi sopivampi koordinaattipari. Hey! Nyt keksin! Interpoloidaan my”s 1/z:aa (z_2d) lineaarisesti, ja toimitetaan jokaiselle pikselille seuraava opereiss”ni (operatsioone jos on italialaisia lukijoita): u_bitmap = u_2d / z_2d, v_bitmap = v_2d / z_2d eli u_bitmap = (u/z) / (1/z), v_bitmap = (v/z) / (1/z) eli u_bitmap = u, v_bitmap = v! Tuloksena ovat siis juuri haluamamme koordinaatit ja viel„ oikein interpoloituina! K„tev„ systeemi, etten sanoisi. Mutta hidas. Ah niin sikamaisen hidas. Vaatimattomat kaksi jakolaskua per PIKSELI X) Ei auta itku markkinoilla jos *h„t„* yll„tt„„, mutta kyll„ se keinot keksii vaikka ylei- nen vessa olisikin varattu. Suomeksi, optimointikeinoja l”ytyy. 1) Ei toimiteta t„t„ hankalaa operaatiota joka pikselille, vaan otetaan mallia Quakesta ja k„ytet„„n sit„ vain joka 8. tai 16. pikseli sek„ interpoloidaan lineaarisesti eli k„ytet„„n klassista, perspektiivikorjaamatonta tekniik- kaa niiden v„lill„. Eroa ei k„yt„nn”ss„ voi havaita muussa kuin nopeudessa ;) 2) Toinen jakolasku saadaan pois (tosin tilalle kaksi kertolaskua, mutta joka tapauksessa paaljon nopeampaa) n„in (hlinen loopissa): z = 1/z_2d ; z = 1/(1/z) = z u_bitmap = u_2d*z v_bitmap = v_2d*z. T„m„h„n ei vaikuta perspektiivikorjaukseen h„iritsev„sti, koska z_2d se kuitenkin on jota interpoloidaan. 5. Sorttaustapoja ----------------- Ilman mink„„nlaista sorttausta ruudulle tulee aikamoista sotkua piirrett„ess„ isompia m„„ri„ polygoneja; polygonit piirret„„n aina samassa j„rjestyksess„, joten engine piirt„„ joissain kulmissa p„„llimm„iset polygonit ensin ja kauimmaiset vasta viimeiseksi. T„ss„h„n tulee ik„vi„ "l„pin„kyvyys"-efektej„, eli jonkinlaista polygonien lajittelua kaivattaisiin. 5.1 Z-sorttaus Z-sorttauksen idea on, ett„ lajitellaan polygonit niiden z-koordinaattien keskiarvon mukaan. T„h„n on helppo k„ytt„„ quicksorttia, kuten seuraavassa pseudokoodissa: funktio quicksort(left, right) - q on apumuuttuja jos left pienempi kuin right q = partition(left,right) quicksort(left,q) quicksort(q+1,right) endjos endf funktio partition(left, right) - x, a, b apumuuttujia - crd on py”ritettyjen pisteiden taulukko - face on polygonitaulukko x = crd[face[left,0],2] + crd[face[left,1],2] + crd[face[left,2],2] a = left-1 b = right+1 toista ikuisesti: v„henn„ b:st„ yksi niin kauan kuin (crd[face[b,0],2] + crd[face[b,1],2] + crd[face[b,2],2]) on pienempi kuin x lis„„ a:ta yhdell„ niin kauan kuin (crd[face[a,0],2] + crd[face[a,1],2] + crd[face[a,2],2]) on suurempi kuin x jos a pienempi kuin b vaihda(face[a],face[b]) muussa tapauksessa lopeta funktio ja palauta arvona b endjos endtoista endf Sitten vain piirret„„n polygonit j„rjestyksess„. Z-sortti ei ole todellakaan t„ydellinen sorttaustapa, mutta kelpaa perussortiksi ihan hyvin. Kun pidemm„lle p„„st„„n, kannattaa opetella vaikka t„ss„kin selitetty BSP-puu, joka on jo huomattavasti kehittyneempi algoritmi -- ja toisaalta my”s huomattavan paljon vaikeatajuisempi ja vaikeampi toteuttaa. 5.2 Z-buffer (Kappaleen kirjoitti uusiksi Tapio Vuorinen, ja h„nen tekstins„ muokkasi luettavaksi Ica/2.) Z-bufferointi on helpoin (mutta ei todellakaan nopein!) tapa tehd„ p„„llekk„in menevi„ objekteja. Toisin kuin esim. BSP, Z-buffer ei vaadi polygonien pilkkomista osiin niiden leika- tessa. BSP on kyll„kin aivan omaa luokkaansa muuttumattomien objektien tms. tekoon. Kuten nimikin kertoo, p„„osassa on puskuri (taulukko), johon talletetaan objektin pisteiden Z- ja v„riarvoja. Taulukon koon t„ytyy olla sama kuin ruudun pikselim„„r„n, esim. MCGA -tilassa 64000 v„hint„„n 16-bittist„ alkiota (hirve„ sana) sek„ jokaiselle alkiolle lis„tavu v„riarvoa varten. Muistia kuluu siis rmodessa 192000 tavua ja pmodessa 256000 tavua. Z-buffer on siis t„m„n n„k”inen C:ll„: typedef struct { short z; unsigned char color; } zbuftype; zbuftype zbuf[64000]; Ennen kuin piirr„mme ruudulle mit„„n, t„ytyy meid„n asettaa Z-buffer-taulukkomme t„yteen sen suurinta mahdollista arvoa (16-bittisill„ muuttujilla 32767). Sitten polygoneja piirt„- ess„mme interpoloimme X:n (ja esim. gouraudissa v„rin) lis„ksi my”s Z:aa. Vaakaviivanpiirtorutiinissa tarkistamme jokaisella pikselill„ onko interpoloimamme Z *pienempi* kuin Z-bufferissa t„ll„ kohdalla oleva Z-arvo. Jos on, asetamme interpoloimamme Z-arvon bufferiin. Jos taas ei, siirrymme suoraan seuraavaan pikseliin. T„m„ tarkistus hidastaa rutiinia j„rjett”m„sti, mutta onneksi Z:aa voi interpoloida aivan samoin kuten X:n tai v„rin: vain yksi ADD per pikseli. Lopuksi, kun kaikkien n„kyvien polygonien kaikki pisteet on k„ytetty Z-bufferin kautta, piirret„„n Z-bufferissa olevat pisteet ruudulle. Jos k„yt„t fixed-point -tekniikkaa, muista, ett„ Z-bufferiin kannattaa tallettaa vain kokonaislukuosa; muuten muistintarve kasvaa nopeasti kaksinkertaiseksi (esim. C: short -> long), koska tarvitaan arvoalueeltaan suurempia muuttujia. *Lyhyt* pseudo-p„tk„ h-linest„: z = z1 for x=x1 -> x2 if (z < zbuffer[y*320+x]) zbuffer[y*320+x] = z endif < interpoloidaan z:aa > z = z + kz endfor Optimoinnit voi sitten jokainen tehd„ itse (eli l„hinn„ siir- tymisen S-bufferiin ;). 5.3 BSP-puu BSP-puu on saanut mainetta eritt„in vaikeana mutta erinomaisena sorttaustapana. Molemmat m„„ritelm„t ovat oikeita: vaikka valmiilla rutiineilla voi saada eritt„in nopeaa j„lke„, omien BSP-puuta k„ytt„vien rutiinien koodaus on todella ty”l„s operaatio. Varsinkin jos kaikki dokumentaatio on englanniksi eik„ tarvittava matikka ole hallussa ;) EN selosta BSP-puuhun tarvittavan linkitetyn listan k„ytt”„, sen voi jokainen osaamaton lukea esim. Mikrobitin numerosta 11/95. Linkitetyn listan erikoistapaus, bin„„ripuu, tarkoittaa, ett„ jokaisesta puun haarakohdasta l„htee kaksi uutta haaraa: 1 / \ 2 3 / \ / \ 4 5 6 7 Etcetc. T„m„n toteuttaminen on yksinkertaista, enk„ usko lukijallekaan j„„v„n vaikeuksia. 5.3.1 The main idea BSP-puuta on yht„ helppo soveltaa 2d-maailmaan kuin 3d-avaruuteenkin (tosin en n„e mit„„n j„rke„ 2d-maailman sorttauksessa). 2d-maailma on helpompi piirt„„ ;) joten selostan p„„periaatteen sen avulla. T„ss„ on kuusi viivaa: 1 | ------------- | 2 | ---___ 3 | / ---___ / \ ---___ / \ 4 / 6 \ / \ / ________--------- -------- 5 X (kamerapiste) N„m„ pit„isi piirt„„ oikeassa j„rjestyksess„ k„ytt„en BSP-puuta. Ensin tehd„„n puun alustus: Aloitamme viivasta 1. Tutkimme, mill„ puolella sit„ ovat loput viivat, ja teemme bin„„ripuun jonka toiselle haaralle menev„t viivan 1 "oikealla" puolella olevat viivat ja toiselle "vasemmalla" olevat viivat. Jos jokin viiva on osittain oikealla, osittain vasemmalla, se katkaistaan leikkauskohdasta ja siit„ muodostetaan kaksi viivaa joista molemmat ovat luonnollisesti jommalla kummalla puolella viivaa 1. Sitten otetaan viiva 2 ja tutkitaan viivojen 3, 4, 5 ja 6 osalta sama, ja jatketaan t„t„ kunnes kaikki viivat on j„rjestetty somaan pikku puuhun. Kun sitten pit„isi piirt„„ n„m„ viivat, tehd„„n seuraavasti: Tutkitaan, mill„ puolella ollaan viivaa 1. Jos ollaan vasemmalla, tutkitaan onko oikealla puolella viivoja, ja jos on, menn„„n alas oikeaa haaraa. Kun oikea haara on k„yty l„pi, piirret„„n viiva 1 ja siirryt„„n vasempaan haaraan. Jos alunperin oltiin oikealla, tehd„„n p„invastoin eli ensin vasenta, sitten oikeaa haaraa. MUISTA piirt„„ viiva 1 mainitussa kohdassa! Esimerkkitapauksessamme tehd„„n seuraavat viivojen jako-operaatiot: 1 | 2a ------------- | 2b ---___ 3a | / ---___ / 6a \ -- ___ \ 4 3b / \ / 6b \ / 5b 5c ___ ____--- ---- -------- 5a X (kamerapiste) Bin„„ripuu taas n„ytt„„ t„lt„: _____1______ 2a 2b / \ 3a 3b / / \ 4 5a 6a / \ \ 5c 5b 6b Kuvassa n„kyv„n kamerapisteen suhteen piirrettyn„ viivojenpiirtoj„rjestys lasketaan siis n„in: 1) Olemme ykk”sen oikealla puolella. 2a piirret„„n siis ensin, sitten 1, sitten menn„„n alas oikeaa haaraa. 2) Olemme my”s 2b:n oikealla puolella, eli ensin menn„„n alas vasenta haaraa. 3) 3a:n suhteen olemme vasemmalla. Siisp„ 3a piirret„„n ensin ja sitten menn„„n alas vasenta haaraa (oikealla puolella ei ole viivoja). 4) Viivan 4 suhteen olemme 5b:n puolella eli oikealla. Piirtoj„rjestys on siis 5c, 4, 5b. 5) Palaamme takaisin 2b:hen ja piirr„mme sen, mink„ j„lkeen marssimme kohti sen oikeaa puolta ja 3b:t„. 6) Olemme 3b:n vasemmalla puolella eli piirr„mme 6a:n ja 3b:n ja menemme 5a:han. 7) 5a:n suhteen olemme vasemmalla, siisp„ piirr„mme ensin 6b:n ja vihon viimeisen„ 5a:n. Eli j„rjestys on 2a,1,3a,5c,4,5b,2b,6a,3b,6b,5a. N„ytt„„pi kohtuullisen j„rkev„lt„. Kannattaa kokeilla itse paperilla, ei tuosta v„ltt„m„tt„ muuten tolkkua saa. Itse piirsin 18:n viivan "maailman" vain hahmottaakseni BSP-puun paremmin. Puusta tulikin sitten A4:n kokoinen ;) 5.3.2 Kaavat Hieno homma tuo BSP-puu, mutta miten se toteutetaan? Itsekin kysyin asiaa ennen kuin itse asiassa edes mietin toteutustapoja, mutta keksin itsekin ihan hyv„n konstin. Lukion analyyttisen geometrian kurssilla opetetaan mm. miten muodostetaan tason ja avaruussuoran yht„l” pelkist„ avaruuspisteist„. Koska en voi olettaa lukijalla olevan t„t„ tietom„„r„„, selostan asian itse. Tason yht„l” on seuraava: Nx * (X-ax) + Ny * (Y-ay) + Nz * (Z-az) = 0, miss„ N on tason normaalivektori (Nx etc ovat siis sen i:n, j:n ja k:n kerroin), X, Y ja Z samat kuin esim. 2d-suoran yht„l”ss„ eli niiden arvot vaihtelevat ihan sikana, ja (ax,ay,az) on tason yksi piste. T„ll„ perusteella pit„isi siis muodostaa kolmion k„rkien kautta kulkeva taso. T„h„n taas tarvitaan normaalivektoria, joka lasketaan tekem„ll„ ensiksi kolmion pisteist„ kaksi vektoria ja ottamalla sitten niiden ristitulon. Nyt sijoitetaan X:n, Y:n ja Z:n paikalle tutkittavan pisteen koordinaatit. Jos tulokseksi saadaan nolla, piste on tasolla. Jos taas tulos on negatiivinen, se on tason toisella puolella, jos se on positiivinen, se on toisella. T„t„ sovelletaan kohdassa 4.3.1 selostettuun systeemiin, ja toimitaan tulosten mukaisesti. Jos kaikki tietyn kolmion kulmat eiv„t ole samalla puolella tutkittavaa tasoa, ne leikkaavat toisensa. T„ll”in pit„„ laskea leikkauspisteet ja muodostaa niiden avulla kolme uutta kolmiota, joista jokainen on jommalla kummalla puolella tasoa. T„h„n tarvitaan avaruussuoran yht„l”„, joka on t„llainen: X = X1 + (X2-X1)t Y = Y1 + (Y2-Y1)t Z = Z1 + (Z2-Z1)t T„m„ suora kulkee siis pisteiden (X1,Y1,Z1) ja (X2,Y2,Z2) kautta, t-kertoimen saadessa kaikki reaalilukuarvot. Kun suoran X, Y ja Z sijoitetaan tason X:n, Y:n ja Z:n paikalle, ratkaistaan t ja sijoitetaan se taas suoran X:„„n, Y:hyn ja Z:aan, olemme saaneet suoran ja tason leikkauspisteen koordinaatit: Nx*(X1+(X2-X1)t-ax) + Ny*(Y1+(Y2-Y1)t-ay) + Nz*(Z1+(Z2-Z1)t-az) = 0 T„st„ ratkaistaan siis t: Nx*(X2-X1)t + Ny*(Y2-Y1)t + Nz*(Z2-Z1)t = Nx*(X1-ax) + Ny*(Y1-ay) + Nz*(Z1-az) < = > t * ( Nx*(X2-X1) + Ny*(Y2-Y1) + Nz*(Z2-Z1) ) = Nx*(X1-ax) + Ny*(Y1-ay) + Nz*(Z1-az) < = > Nx*(X1-ax) + Ny*(Y1-ay) + Nz*(Z1-az) t = ------------------------------------ Nx*(X2-X1) + Ny*(Y2-Y1) + Nz*(Z2-Z1) Onneksi t„t„ ei tarvitse k„ytt„„ kuin inittiosassa ;) 5.3.3 Vinkkej„ 1) Tason yht„l”n laskeminen on sen verran hidasta, ett„ kannattaa laskea normaalit vain ihan ohjelman alussa ja py”ritell„ sitten niit„ pisteiden mukana. 2) Helpoin tapa ei tosiaankaan ole nopein. Kannattaa ehk„ inittiosassa tutkia, montako polygonisplitti„ eri vaihtoehdot eli eri polygonien valinta ykk”spolygoniksi aiheuttavat, ja ottaa sitten k„ytt””n se jossa niit„ tulee v„hiten -- nopeutta tulee roimasti lis„„ kun polygonien m„„r„ pienenee puoleen, mik„ tapahtuu varsin helposti. 3) K„rsiv„llisyytt„. BSP-puurutiinien koodaus on todella hidasta hommaa, ne kun vaativat jo sen verran monimutkaisempaa matikkaa kuin joku rupunen z-sort :) 4) Jos BSP-rutiinisi ovat hitaammat kuin Z-buffer, on jossain pahasti vikaa ;) 5) BSP-puu ei ole itsetarkoitus eik„ se sovellu kaikkeen 3d:hen. Esimerkiksi raytrace-enginess„ on pakko k„ytt„„ Z- tai S-bufferia koska objektit voivat leikata toisensa, mit„ BSP-puu ei salli. Henkil”kohtaisesti suosittelenkin S-bufferia. 5.4 S-buffer S-buffer eli segmented buffer on Hot Wax Softwaren Paul Nettlen kehitt„m„ Z-bufferin paranneltu -- ja *huomattavasti* nopeampi (mies itse kehuu, ett„ S-buffer p„ihitt„„ nopeudessa jopa hardware-Z-bufferin :O -- versio, jossa ei pidet„ kirjaa pisteist„ vaan vaakaviivoista. T„ll„ tavalla s„„stet„„n huomattavasti laskutoimituksia; suurimmassa osassa horizline- kutsuista ei tarvitse vertailla kuin p„„tykoordinaatteja. S-bufferissa on siis 3d-taulukko (tai linkitetty lista, jota Nettle itse suosittelee jostain k„sitt„m„tt”m„st„ syyst„), johon sijoitetaan jokaisen hline-kutsun tiedot, vertaillaan niit„ toisiinsa, toimitaan asianmukaisesti ja lopulta piirre- t„„n n„kyviss„ olevat viivat (tai osat). Itse k„yt„n seuraavanlaista taulukkoa (texturemappaukseen tarkoitettu, pmode): typedef struct { short xb,xe,zb,ze; // x_begin, x_end, ... byte ub,ue,vb,ve; long kz,ku,kv; // kz = (ze-zb)*65536/(xe-xb) jne unsigned char used; // jos 0 -> ei k„yt”ss„ } sbuf_t; sbuftype sbuf[200][100]; // 200 rivi„ 320x200-tilassa, // max. 100 segmentti„ / rivi HUOM! Segmentit ovat taulukossa x-koordinaattien suuruus- j„rjestyksess„ vasemmalta oikealle. T„llainen taulukko vie siis muistia rmodessa 200*100*25=500000, pmodessa alignoinnista johtuen 200*100*28=560000 tavua, ja mit„ monimutkaisempi maailma on kyseess„, sit„ suuremmaksi pit„„ maksimisegmenttim„„r„„ kasvattaa. S-buffer-polygonirutiinille pit„„ "normaalista" rutiinista poiketen (samoin kuin Z-bufferissa) ilmoittaa my”s pisteiden z-koordinaatit (x:ien ja y:iden pit„„ silti olla jo 2d-n„yt”lle transformoituja). Outer loopissa interpoloidaan sitten muiden lis„ksi my”s z-koordinaatteja, ja ilmoitetaan ne S-buffer- hlinellekin. S-buffer-hline ei varsinaisesti piirr„ mit„„n, vaan lis„„ vain uuden rivin S-bufferiin, ja vasta kun S-buffer on valmis, piirret„„n koko roska kerralla n„yt”lle. P„tk„ polyrutiinista: for y=y1 -> y2 sbuf_hline(xb,xe,y,zb,ze,col) xb=xb+dx1 yb=yb+dx2 zb=zb+dz1 ze=ze+dz2 endif HUOM! Jos polyrutiinille ilmoitettavat koordinaatit ovat pisteen 3d-koordinaatit, pit„„ muistaa transformoida x ja y 2d-koordinaateiksi ennen looppia! Sbuf_hline: Klippaa ja tee muut normaalit initialisoinnit (klippaus vasta dz:n, du:n ja dv:n laskemisen j„lkeen, of coz) for i=0 -> 99 if not sbuf[y][i].used lis„„ hline suoraan bufferiin ja merkitse se varatuksi poistu Tee muut vertailut endfor Ai mik„ "tee muut vertailut"? Nooh: samalla rivill„ olevat horizlinet voivat sijaita monin eri tavoin toistensa suhteen, joten niit„ pit„„ vertailla toisiinsa ja toimia tulosten mukaisesti. L”yd„n itse Nettlest„ poiketen vain kuusi tapaa, miten viivat voivat sijaita toistensa suhteen (vanha viiva = v, uusi = u): (1) vvvvvvvv uuuuuuuu (2) vvvvvvvv uuuuuuuu (3) vvvvvvvv uuuuuuuuuuu (4) vvvvvvvv uuuuuuuuuuu (5) vvvvvvvv uuuuuuuuuuu (6) vvvvvvvvvvv uuuuuuuu N„ill„ tavoilla voidaan esitt„„ kaikki viivojen erilaiset sijainnit, mukaanlukien my”s erikoistapaukset (kuten yhden pikselin mittaiset viivat ja t„sm„lleen samoissa (x,y) -koordinaateissa olevat viivat). Kohdan 1 viiva lis„t„„n vain suoraan puskuriin *ennen* oikealla puolella olevaa viivaa ja keskeytet„„n hlinen ajo (kaikki viivat ovat sen jommalla kummalla puolella, koska vasemman- puoleiset viivat on jo tarkistettu -- neh„n ovat S-bufferissa j„rjestyksess„ vasen -> oikea). Kohdan 2 tapauksessa hyp„t„„n tutkimaan seuraavaa vanhaa viivaa, jos sellainen l”ytyy. Jos ei, lis„t„„n viiva puskurin viimeiseksi. Kohdassa 3 viiva katkaistaan vanhan viivan xe:n kohdalta (muista interpoloida z:aa, u:ta ja v:t„ oikein), vertaillaan vasemmanpuoleisen p„tk„n ja vanhan viivan z-koordinaatteja, lis„t„„n vasemmanpuoleinen p„tk„ tai sen osa tarvittaessa puskuriin, ja jatketaan oikeanpuoleisen p„tk„n ja seuraavan vanhan viivan kanssa, jos sellainen l”ytyy. Jos ei, p„tk„ lis„t„„n puskurin viimeiseksi. 4. kohdan viiva katkaistaan vanhan viivan xb:n kohdalta, lis„t„„n vasemmanpuoleinen p„tk„ puskuriin ennen vanhaa viivaa, ja toimitaan oikeanpuoleisen p„tk„n kanssa samoin kuin yll„ vasemmanpuoleisen kanssa. 5. kohdassa katkaistaan viiva sek„ oikealta ett„ vasemmalta puolelta ja toimitaan muuten kuin 3. ja 4. kohdassa. 6. kohdassa menetell„„n suoraan kuten kohdan 3 vasemmanpuo- leisen p„tk„n kanssa. Kun kaikki polygonit on piirretty, k„yd„„n S-buffer l„pi ylh„„lt„ alas, vasemmalta oikealle, ja piirret„„n viivojen- p„tk„t normaalin hlinen tapaan. Piece of cake ;) ... [ep„m„„r„ist„ ruikutusta ja vikin„„] ... No hyv„ on, kun pyysitte niin kauniisti: t„ss„ S-bufferin hallintaan tyhjennys- ja piirt„misrutiinit. K„ytt„v„t muuten ylemp„n„ esitelty„ sbuf-taulukkoa. - tmap on 256x256-kokoinen bittikartta funktio flip_sbuf integer i,j,k ; apumuuttujia integer du,dv ; hline„ varten for i=0 -> 199 j = 0 while sbuf[i][j].used<>0 sek„ j<100 du = 0 dv = 0 for k=sbuf[i][j].xb -> sbuf[i][j].xe putpixel(k,i,tmap[sbuf[i][j].ub+du/65536+ (sbuf[i][j].vb+dv/65536)*256]) du = du + sbuf[i][j].ku dv = dv + sbuf[i][j].kv endfor j = j + 1 endwhile endfor endf funktio clear_sbuf() integer i,j for i=0 -> 199 j = 0 while sbuf[i][j].used<>0 sek„ j<200 sbuf[i][j].used=0 j = j + 1 endwhile endfor endf 6. Varjostustapoja ------------------ Nyt on sitten se polygonikin ruudulla, mutta n„ytt„„ sekin aika tyls„lt„ kun v„rit pysyv„t koko ajan samoina; realismi olisi kiva juttu. 6.1 Flat-sheidaus 6.1.1 Z-flat Z-flat on melko s„„litt„v„n n„k”inen sheidaus, joka saadaan aikaan nimens„ mukaisesti antamalla polygonille v„riarvo sen kulmien z-koordinaattien keskiarvon perusteella: v„ri = max_col - (kulma1.z + kulma2.z + kulma3.z) / a, miss„ a on jokin sopiva luku jolla jakamalla keskiarvo saadaan suurimman mahdollisen v„rinumeron (max_col) ja nollan v„limaastoon. Koska kyseess„ on koordinaatisto jossa z-akseli sojottaa siihen suuntaan johon luultavasti t„ll„kin hetkell„ katsot ;) niin z-arvo on kauempana suurempi eli saatu arvo pit„„ v„hent„„ suurimmasta mahdollisesta v„rinumerosta. 6.1.2 Lambert Flat Lambert Flat onkin jo huomattavasti paremman n„k”inen, siin„ kun on ihka oikea valonl„hdekin. Samalla saadaan viimeinkin jotain k„ytt”„ niille vektoreille, joita alussa yritettiin niin kovasti opiskella ;) Lambert flatkin tosin v„lkkyy ik„v„sti. Idea on seuraavanlainen: annetaan valonl„hteelle i-, j- ja k-arvot, eli vektorin kertoimet, jotka osoittavat valonl„hteen suunnan (itse valonl„hde on „„rett”m„n kaukana). Jokaiselle framelle lasketaan sitten jokaista polygonia vastaavan tason normaalivektori (ristituloa ja vektorin yht„l”n laskemista), ja selvitet„„n pistetulon avulla t„m„n vektorin ja valovektorin v„lisen kulman kosini (mit„ pienempi kulma, sit„ kirkkaampi v„riarvo). Sopivalla kertoimella saadaan t„m„ v„riarvo haluttujen v„rirajojen sis„„n, esimerkiksi itsell„ni RGB-tilassa v„lille 0..63 kertoimella 63. Lopuksi tarkistetaan onko v„riarvo nega- tiivinen. Jos on, muutetaan se nollaksi, eik„ polygonia n„y. Pseudoa ”ken: - LSi, LSj, LSk valonl„hdevektorin kertoimet (Light Source) - Ni, Nj, Nk tason normaalivektorin kertoimet - a apumuuttuja funktio LambertFlat < lasketaan tason normaalivektorin kertoimet (ensin muodos- tetaan kaksi vektoria kolmesta pisteest„ ja sitten niiden ristitulo) > a = sqrt(Ni*Ni + Nj*Nj + Nz*Nz) * _ __ sqrt(LSi*LSi + LSj*LSj + LSk*LSk) // a = |N| * |LS| jos a ei ole nolla (nollalla ei viitsi jakaa) color = max_col * (LSi*Ni + LSj*Nj + LSk*Nk) / a jos color pienempi kuin nolla color = 0 endjos muussa tapauksessa color = 0 endjos palauta color endf T„m„h„n on aika hidas tapa (tulee kaksi neli”juurta, lukuisia mulleja ja div jokaiselle polygonille), joten nopeutus olisi tarpeellinen. Jos molempien vektorien pituus on yksi, l„htee suurin osa mulleista, div ja molemmat sqrt:t litomaan. (miten vektorin pituudeksi varmistetaan yksi, ks. luku 1.3) Jos valonl„hdevektoria liikutellaan, pit„„ sen pituudeksi varmistaa t„m„ yksi joka framella, tosin jos liev„ ep„tark- kuus ei haittaa, voidaan laskea se vain n. joka nelj„nnell„ framella tai tarpeen mukaan. Jos taas se pysyy paikallaan, voidaan sen pituus laskea ennen py”rittely„ ja se pysyy koko ajan samana. Normaalivektorien tilanne on v„h„n kinkkisempi; tuo pituus on aika hidasta laskea, ja divvej„kin tulisi enemm„n kuin Suomen perustuslaki sallii. Ei, kyll„ on oltava nopeampi konsti. Ja onkin! Mit„s sanot t„st„: lasketaan jokainen normaalivektori taulukkoon init-vaiheessa, varmistetaan sen pituudeksi yksi (tai oikeastaan mieluummin max_col niin ei tarvita sit„ yht„ mullia joka polylle ja fixedpointkin tulee samalla suoraan) ja py”ritell„„n sitten niit„kin ihan kuin ne olisivat koordinaatteja! Nopeutus on huomattava. Siis init-osassa: - laske normaalivektorin i:n, j:n ja k:n kertoimet, - laske vektorin pituus, - kerro i:n, j:n ja k:n kertoimet max_col:lla, - jaa ne vektorin pituudella. Nyt funktio sieventyy muotoon funktio LambertFlat color = LSi*Ni + LSj*Nj + LSk*Nk jos color pienempi kuin nolla (ei muuten ole jos k„ytet„„n hidden face removalia) color = 0 endjos palauta color endf 6.2 Gouraud-sheidaus "Mit„s me jollain Flatilla, Gouraudia kehiin!" huutaa kansa. "Gou-raud, Gou-raud!!" kiljuvat kohta jo pikkulapsetkin. "Mik„s siin„", tuumi Caesar, "Kansa on huvinsa ansainnut." "Avatkaa portit!", h„n komensi. "Gouraud esiin!" Ja rauta- porttien viel„ naristessa rynt„si areenalle Gouraud, petojen sukua. (anteeksi, kello on paljon :D Lukija pohtii varmaan mit„ selitt„mist„ gouraudissa viel„ on, gouraud-kolmio kun on jo k„sitelty. Homma ei vain toimi niin kauan kuin ei tiedet„ mit„ v„riarvoja millekin objektin pisteelle annetaan. 6.2.1 Z-Gouraud Z-gouraud toimii samalla periaatteella kuin Z-flat, eli v„riarvo otetaan pisteen z-koordinaatista. Se on aika tyls„n n„k”inen, mutta hienompi joka tapauksessa kuin Z-flat, jonka pesee mik„ shade tahansa ;) Eli otetaan pisteen Z-koordinaatti, jaetaan se sopivalla kertoimella (sopiva riippuu objektista) ja v„hennet„„n maksimiv„riarvosta; no problem. 6.2.2 "Oikea" Gouraud T„m„ taas skulaa samoin kuin Lambert Flat, sill„ erotuksella ett„ ei oteta polygonin ja valovektorin v„list„ kulmaa vaan jokaiselle pisteelle siihen kiinnittyvien polygonien ja valovektorin v„listen kulmien keskiarvo. Ei mik„„n minuutin nakki, joten pseudo lienee paikallaan. Luulin, ett„ t„m„ on (c) Kaj Bj”rklund, mist„ miehen itsens„ kommentti: "hehee, tuo calcnor on suoraan ripattu jostain sorsasta :)" No juuh, crediitit calcnor-funktiosta kuuluvat siis Jeroen Bouwensille. Eip„ siin„ sin„ns„ ole mit„„n erikoista, olin v„„nt„nyt t„sm„lleen samanlaisen funktion kuin tuo calcnor on ennen kuin Kaj heitti minulle koko roskan, siis CalcNormals -funktion, jossa oli tuo calcnorkin. funktio CalcNormals < lasketaan yhden tason normaalivektori ristitulolla > funktio calcnor(X1,Y1,Z1,X2,Y2,Z2,X3,Y3,Z3,NX,NY,NZ) int RelX1,RelY1,RelZ1,RelX2,RelY2,RelZ2 RelX1=X2-X1 RelY1=Y2-Y1 RelZ1=Z2-Z1 RelX2=X3-X1 RelY2=Y3-Y1 RelZ2=Z3-Z1 NX=RelY1*RelZ2-RelZ1*RelY2 NY=RelZ1*RelX2-RelX1*RelZ2 NZ=RelX1*RelY2-RelY1*RelX2 endf < face = polygonitaulukko, vertex = pistetaulukko > int i,a,ox,oy,oz float cx,cy,cz,len,cn for i=0 -> pisteiden lukum„„r„-1 cx=0 cy=0 cz=0 cn=0 for a=0 -> polygonien lukum„„r„-1 < jos polygoni koskettaa pistett„ i > if ((face[a][0]=i) tai (face[a][1]=i) tai (face[a][2]=i)) < funktio palauttaa (ox,oy,oz):aan normaalin i:n, j:n ja k:n kertoimet > calcnor(vertex[face[a][0]].x,vertex[face[a][0]].y, vertex[face[a][0]].z,vertex[face[a][1]].x, vertex[face[a][1]].y,vertex[face[a][1]].z, vertex[face[a][2]].x,vertex[face[a][2]].y, vertex[face[a][2]].z,ox,oy,oz) < (cx,cy,cz) tulevat sis„lt„m„„n normaalien keskiarvon, cn:„„ lis„t„„n koska se ilmoittaa montako normaalia on laskettu cx:„„n jne yhteen > cx=cx+ox cy=cy+oy cz=cz+oz cn+=1 endif endfor < jos joku polygoni koskettaa pistett„ > if cn > 0 < lasketaan keskiarvot > cx=cx/cn cy=cy/cn cz=cz/cn < lasketaan normaalivektorin pituus > len=sqrt(cx*cx+cy*cy+cz*cz) if len = 0 len=1 endif < varmistetaan ett„ kaikki normaalivektorit ovat pituudeltaan 1 eli tehd„„n niist„ yksikk”vektoreita > normal[i].x=cx/len normal[i].y=cy/len normal[i].z=cz/len endif endfor endf Ja k„ytt” siis tapahtuu samaan tapaan kuin Lambert flatissa. 6.3 Phong-sheidaus 6.3.1 Phong Illuminating Phong illuminating tarkoittaa sit„, ett„ paletin avulla kikkailemalla (ns. ep„lineaarinen paletti) saadaan gouraud n„ytt„m„„n hienommalta phongilta. Mik„s siin„, hienompi siit„ tulee kuin tavallisesta gouraudista. Phong illuminating saadaan aikaan k„ytt„m„ll„ seuraavaa kaavaa: color = ambient + (cos x) * diffuse + (cos x)^n * specular, miss„ ambient on polyn v„ri kun siihen ei osu ollenkaan valoa eli minimiv„ri, diffuse polyn alkuper„inen v„ri, ja specular polyn v„ri kun siihen tuleva valo on kohtisuorassa pintaa vastaan eli v„rin maksimiarvo. x on valovektorin ja verteksin normaalivektorin v„rinen kulma, ja se saa vaihdella vain v„lill„ -90..90 astetta eli -pi/2..pi/2 radiaania. Miksei v„lill„ 0..360 astetta? Siksi, ett„ ment„ess„ yli 90 asteen valoa ei osu polyyn ollenkaan, jolloin pit„ k„ytt„„ minimiarvoa ambient. Siisp„ tarkistuk- set, ja jos kulma ei ole vaaditulla v„lill„, annetaan sille arvo -90 tai 90 astetta, eli kosinille arvo nolla, eli v„rille arvo ambient. n on objektin hohtavuus eli highlightin ominaisuus, joille- kuille varmaan tuttu rendausohjelmista. Kokeilemalla selvi„„ kuhunkin tilanteeseen sopiva arvo. Pseudoa j„lleen: funktio SetPalette < katkaistaan v„riarvo oikealle v„lille 0..63 > funktio snap(arvo) if arvo > 63 arvo = 63 else if arvo < 0 arvo = 0 endif palauta arvo endf int i float cosi,r,g,b for i=0 -> 255 cosi=i*PI/1024 r=snap(5+cosi*60+cosi*cosi*cosi*cosi*150) g=snap(0+cosi*30+cosi*cosi*cosi*cosi*150) b=snap(-5+cosi*15+cosi*cosi*cosi*cosi*150) muuta_vari(i,r,g,b) endfor endf T„ss„ esimerkiss„ punaisen v„rin (r) minimiarvo on siis viisi, arvo normaalivalaistuksella 60, maksimiarvo 150, hohtavuus nelj„ ja kulma vaihtelee v„lill„ 0..90 astetta (v„rill„ 255 kulma on nolla, v„rill„ nolla se on 90 astetta, eli kirkkain arvo tulee paletin loppuun). 6.3.2 Env-mappaus Monet sekoittavat oikean phongin env-mappaukseen, mutta ne ovat kaksi eri asiaa. Env-mappauksessa k„ytet„„n bittikarttaa (environment map) josta saadaan pikseleille v„riarvot. Sen avulla voi tehd„ erilaisia kuvioita varjostukseen, jolloin pinnat alkavat n„ytt„„ vaikkapa metallisilta. T„m„n dokumen- tinkin mukana tulee yksi bittikartta, joka kelpaa melko hyvin env-mappaukseen. Ai mist„k” niit„ saa? Kaverinkaverin kuvan- k„sittelyohjelmilla tuollaisten tekeminen on helppoa ;) Env-mappaus toimii muuten samoin kuin gouraud, mutta gouraud-kolmion sijasta kutsutaan texture-kolmiota, ja normaalien ja valovektorin v„listen kulmien sijasta k„ytet„„n normaalien i:n ja j:n kertoimia indeksein„ esim. 256x256 -kokoiseen bittikarttaan. T„ll”in tosin ei saada aikaan aitoa liikuteltavaa valonl„hdett„, mutta sekin onnistuu pienen kikkailun avulla -- pseudoesimerkki alla. - LS on valonl„hdevektori - N[0..2] ovat kolmion verteksien normaalivektorit - cx1, cy1 etc ovat koordinaatit env-mappiin - a on apumuuttuja - env-map on 256x256-kokoinen bittikartta (metal.pcx) if ( LS.k <= 0 ) ; k„ytet„„n systeemi„ suoraan cx1 = env_crd( N[0].i - LS.i ) cy1 = env_crd( N[0].j - LS.j ) cx2 = env_crd( N[1].i - LS.i ) cy2 = env_crd( N[1].j - LS.j ) cx3 = env_crd( N[2].i - LS.i ) cy3 = env_crd( N[2].j - LS.j ) else a = N[0].i + LS.i ; yhteenlasku - LS.i vastakkainen kuin yll„ if (a<0) a = a + 1 ; vastakkaiselle puolelle else a = a - 1 cx1 = env_crd( a ) ; konvertointi a = N[0].j + LS.j if (a<0) a = a + 1 else a = a - 1 cy1 = env_crd ( a ) a = N[1].i + LS.i if (a<0) a = a + 1 else a = a - 1 cx2 = env_crd( a ) a = N[1].j + LS.j if (a<0) a = a + 1 else a = a - 1 cy2 = env_crd ( a ) a = N[2].i + LS.i if (a<0) a = a + 1 else a = a - 1 cx3 = env_crd( a ) a = N[2].j + LS.j if (a<0) a = a + 1 else a = a - 1 cy3 = env_crd ( a ) endif texture( x1, y1, x2, y2, x3, y3, cx1, cy1, cx2, cy2, cx3, cy3 ) funktio env_crd ( float arvo ) - a apumuuttuja a = arvo * 127 + 128 palauta a Funktio env_crd konvertoi siis normaalin kertoimen (v„lill„ -1..1) bittikartan koordinaateiksi (0..256, keskell„ kirkkain). Pseudon alussa tutkittiin, onko valonl„hteen k:n kerroin positiivinen vai negatiivinen. T„m„ siksi, koska menetelm„ ei p„de molemmille yht„ hyvin, vaan positiiviset arvot vaativat hiukan s„„t„mist„. Negatiivisilla k:n arvoilla saadaan siis pseudon osoittamalla tavalla laskettua env-mapin koordinaatit: V„hennet„„n normaalien i:n ja j:n kertoimista valovektorin i:n ja j:n kertoimet ennen kuin transformoidaan niit„ bittikartan keskikoordinaatteihin. Ai mihink” k:n kerroin? Ei mihink„„n, mutta koska n„iden vektorien pituuden pit„„ olla yksi, voidaan v„hent„m„ll„ i:n ja j:n arvoja saada k:n kertoimelle painoarvoa: esimerkiksi jos i:n ja j:n kerroin on 0.5, k:n kertoimelle j„„ arvoa 0.7 (vektorin pituus 0.5^2 + 0.5^2 + 0.7^2 = 1). *T„m„*systeemi*ei*tepsi*valonl„hteisiin*joiden*k:n*kerroin*on* *positiivinen*, vaan ne vaativat seuraavan: k:n kerroin on positiivinen ja vektori (-LS.i,-LS.j,-LS.k) on valonl„hdevektoria vastakkainen. Jos huijataan rutiini luule- maan valonl„hdevektorin olevankin toisella puolella, saadaan tarkalleen p„invastainen tulos kuin olisi tarkoitus. Miksi n„in? Siksi, ett„ t„m„n vastakkaissuuntaisen vektorin k:n kerroin on luonnollisesti negatiivinen, ja voimme k„ytt„„ normaalia systeemi„. P„invastaisuus taas h„vi„„, kun siirret„„n keskell„ bittikarttaa olevat arvot laidoille ja laidoilla olevat keskelle -> … vot: tuloksena on haluttu, alkuper„inen valonl„hdevektori! T„ytyy kyll„ rintaa kumistellen kertoa, ett„ t„m„ valonl„hde- systeemi on kokonaan itse keksim„ni :O 6.3.3 Voltaire/OTM:n Phong Phong-sheidauksen idea on l”yt„„ tarkka v„riarvo jokaiselle pikselille. T„m„ onnistuu interpoloimalla polygonirutiinissa verteksinormaaleja, eli etsim„ll„ jokaiselle pikselille oman normaalivektorinsa, ja m„„ritt„m„ll„ t„m„n sek„ valovektorin v„lisen kulman kosini skalaaritulon avulla (ks. 1.5). Koska interpoloidut normaalit eiv„t ole v„ltt„m„tt„ yksikk”vekto- reita, tarvitaan jokaiselle pikselille neli”juuri -- uh-oh, realtimen„ ei taida onnistua ;) T„m„ ainoa oikea phong-sheidaus on upean n„k”inen, mutta sit„ ei ole j„rkev„„ k„ytt„„ kuin still-systeemeiss„ eli esimerkiksi raytrace-enginess„; lis„laskettavaa tulee joka pikselille pistetulon verran: nelj„ kertolaskua, kaksi yhteenlaskua, yksi jakolasku ja neli”juuri -- l„hemm„s 300 pentium-kelloa! Toki t„t„ voi optimoida, mutta kolme kertolaskua ja yksi jakolasku j„„ joka tapauksessa, mik„ on meid„n tarkoituksiimme aivan liikaa. Onneksemme Zach Mortensen on keksinyt realtimeen paremmin sopivan tekniikan: eip„s interpoloidakaan normaaleja, vaan otetaan ennen polygonirutiinin kutsumista jokaisen verteksi- normaalin ja valovektorin v„linen kulma, ja interpoloidaan- kin niit„ (kulmathan muuttuvat lineaarisesti)! Heihei, pis- tetulo, nyt ei tarvita jokaiselle pikselille kuin kosini- taulukkoon vilkaisu, mik„ on miltei yht„ nopeata kuin gouraud-shadettaminen! Kun kosinitaulukon suurimmaksi arvoksi m„„ritell„„n viel„ 255 ja pienimm„ksi nolla, ei saatuja arvoja tarvitse edes fiksailla vaan ne ilmoittavat suoraan pisteen v„riarvon. Yksinkertaista, mutta helppoa :) Tsakhin tekniikassa on vain yksi ongelma: kun kulmat kahdella tai useammalla verteksill„ ovat samat, koko n„iden verteksien v„linen matka on samaa v„ri„ -- lineaarisen interpoloinnin haitta. T„t„k„„n ei juuri huomaa objektien liikkuessa, ja onhan t„m„ joka tapauksessa gouraudia paljon hienompi sheidausmenetelm„, kunhan viel„ k„ytet„„n phong illuminating -menetelm„„ palettia generoidessa ;) 7. Muuta mukavaa ---------------- 7.1 Hidden face removal 7.1.1 Backface culling Backface cullingin idea on yksinkertainen: jos polygoni on v„„rin p„in, sit„ ei tarvitse piirt„„. T„m„ ei tietenk„„n toimi, ellei polygoneja ole m„„ritelty oikein, joten kannat- taa olla tarkkana (esimerkiksi 3DStudiolla tehdyt objektit ovat oikeanlaisia, eli verteksit clockwise-j„rjestyksess„). Onko polygoni v„„rin p„in, on helppo p„„tt„„ t„m„n pseudo- koodin avulla ((c) Bas van Gaalen / Jeroen Bouwens, don't know / remember): funktio visible(x1, y1, x2, y2, x3, y3) - dx1, dy1, dx2, dy2 ovat koordinaattien erotuksia dx1 = x3 - x1 dy1 = y3 - y1 dx2 = x3 - x2 dy2 = y3 - y2 jos ( ( dx1*(dy2-dy1)-(dx2-dx1)*dy1 ) > 0 ) palauta_arvo TRUE muuten palauta_arvo FALSE endf Jos funktio palauttaa arvonaan TRUE, eli kameravektorin ja tason normaalivektorin v„lisen kulman kosini on positiivinen eli -90 < kulma < 90 astetta, polygoni piirret„„n, muuten luonnollisesti ei. 7.1.2 View cone View cone tarkoittaa kartion (cone) muotoista n„kyviss„ olevaa aluetta katsottaessa johonkin suuntaan. Tekniikka on siit„ k„tev„, ett„ jos jokin polygoni tai objekti on m„„ritellyn kartion ulkopuolella, sen voi j„tt„„ saman tien huomiotta. Hienostunein view conen muoto klippaa kartion reunaan osittain n„kyviss„ olevat polygonit, mutta yksin- kertaisemmassa 3d-enginess„ t„llaiset tapaukset voi hoitaa grafiikkaklippauksilla l. polygonirutiinin sis„ll„. K„sittelen t„ss„ vain j„lkimm„ist„ tapaa. Homma hoituu yksinkertaisesti vertaamalla 2dx-, 2dy- ja z-koordinaattia ruudun rajoihin ja toimimalla tulosten mukaan. Z-koordinaatin tapauksessa polygoni j„tet„„n piirt„m„tt„, jos sen yhdenkin pisteen z on pienempi kuin nolla, koska muuten k„ypi piirtorutiineissa hiukan h”p”sti. Pseudoa: if KAIKKIEN verteksien z:t positiiviset sek„ JONKIN verteksin x positiivinen ja pienempi kuin MAX_X sek„ JONKIN verteksin y positiivinen ja pienempi kuin MAX_Y then piirr„. 7.2 Kamera and how did I do it Miksi vaivautua suurellisiin koordinaatistojen muuttamisiin kameran liikkuessa, kun saman saa aikaan py”ritt„m„ll„ koko 3d-avaruutta kamerakulmien verran vastakkaisiin suuntiin? Toki valonl„hteet etc pit„„ muistaa py”ritt„„ samalla, muuten tulee helposti "py”riv„n planeetan syndrooma", jossa planeetta py”rii, ja l„heisen t„hden aiheuttama varjo py”rii saman- aikaisesti. Sellainen n„ytt„„ *melko* naurettavalta ;) Matriisitekniikassahan t„t„ tapaa k„ytet„„nkin, mutta paljon helpommin: kertomalla objektimatriisi kameramatriisilla on kameran paikkaa muutettu. 7.3 Objektin py”ritysnopeuden suhteuttaminen koneen nopeuteen T„ss„ esitell„„n vain yksi tekniikka t„m„n tekemiseksi. Jos se ei jostain t„ysin k„sitt„m„tt”m„st„ syyst„ kelpaa neidille, h„n on vain hyv„ ja lukee Midaksen dokumentit. Otsikon ilmoittamaa tekniikkaa kutsutaan hienosti frameskipiksi, skriinsynkkaukseksi etc, mutta t„ss„ siit„ k„ytet„„n v„hemm„n tyylik„st„ nime„ "harppominen". Harppomisen idea on siis py”ritt„„ opjekteja kaikilla koneilla samaa vauhtia. Perusidea on hyvin yksinkertainen: kun objektit p„ivitet„„n yhden kerran, on piirretty yksi frame. 386:lla framen piirt„miseen menee huomattavasti enemm„n aikaa kuin penttijumilla, mist„ seuraa, ett„ 386:lla objektin tulee harppoa enemm„n kuin pentiumilla eli piirt„„ v„hemm„n frameja aikayksik”ss„. Jos siis oletamme, ett„ objektin py”rimiskulman pit„isi kasvaa 9 astetta per sekunti, toimimme seuraavasti: Frame Kulma 386:lla Kulma penttijumilla -------------------------------------------- 1 0 0 2 3 1 3 6 2 4 9 3 5 - 4 6 - 5 7 - 6 8 - 7 9 - 8 10 - 9 Miksik” n„in? Siksi, ett„ pentium joutaa piirt„m„„n 10 freimi„ per sekunti, kun kolkasikuutonen pystyy vain nelj„„n. N„in opjektisi py”rii kaikilla koneilla samaa vauhtia, tosin penalla huomattavasti sulavammin kuin 386:lla. Pseudon koodaaminen on sitten hauskaa. K„„nt„j„ ei ainakaan valita ;) falku=lueaika; toista floppu=lueaika kulma=kulma+nopeus*(floppu-falku) falku=floppu; kunnes 1=2 Kaikki muuttujat ovat tietysti reaali(tai fixed)-kamaa. Niin, ja lueaika on sitten *tarkka*, eli mik„„n avuton 18.2Hz:n resoluu- tiolla varustettu perustaimeri ei kelpaa. --- KB> (niin ilkka, selvenn„ (lue kirjoita uudestaan) tuo koko p„tk„ :) Muutin vain kieliasua hiukan, korjasin kielioppivirheet ja lis„sin muutaman capitaaliletterin :) --- Didn't get the point? T„m„n kappaleen kirjoitti alunperin Kaj Bj”rklund :) EOF