ˇ ´ UCEN ´I TECHNICKE ´ V BRNE ˇ VYSOKE BRNO UNIVERSITY OF TECHNOLOGY
ˇ ´ICH TECHNOLOGI´I FAKULTA INFORMACN ˇ ´ITACOV ˇ ´ ´ ´I USTAV POC E´ GRAFIKY A MULTIMEDI FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF COMPUTER GRAPHICS AND MULTIMEDIA
ˇ ´IM OPENGL GRAFICKE´ INTRO 64KB S POUZIT
´ DIPLOMOVA´ PRACE MASTER’S THESIS
´ AUTOR PRACE AUTHOR
BRNO 2012
ˇ MILET ´S Bc. TOMA
ˇ ´I TECHNICKE ´ V BRNE ˇ VYSOKE´ UCEN BRNO UNIVERSITY OF TECHNOLOGY
ˇ ´ICH TECHNOLOGI´I FAKULTA INFORMACN ˇ ´ITACOV ˇ ´ ´ GRAFIKY A MULTIMEDI ´ ´I USTAV POC E FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF COMPUTER GRAPHICS AND MULTIMEDIA
ˇ ´IM OPENGL GRAFICKE´ INTRO 64KB S POUZIT GRAPHICS INTRO 64KB USING OPENGL
´ DIPLOMOVA´ PRACE MASTER’S THESIS
´ AUTOR PRACE
ˇ MILET ´S Bc. TOMA
AUTHOR
´ VEDOUC´I PRACE SUPERVISOR
BRNO 2012
doc. Ing. ADAM HEROUT, Ph.D.
Abstrakt Diplomov´ a pr´ ace se zab´ yv´ a tvorbou intra s omezenou velikost´ı. Pr´ace popisuje metody pro omezen´ı velikosti v´ ysledn´e aplikace. Hlavn´ı ˇc´ast pr´ace popisuje metody pro generov´an´ı a animaci grafick´eho obsahu. Zab´ yv´a se tvorbou textur a geometrie. Dalˇs´ı ˇc´ast´ı jsou fyzik´aln´ı simulace ˇc´ asticov´ ych a elastick´ ych syst´em˚ u.
Abstract This thesis deals with the creation of the intro with limited size. This work describes methods for reducing the size of the final application. The main part describes methods for generating graphic content and methods for its animation. It deals with creation of textures and geometry. Another part is aimed on the physical simulation of particle and elastic systems.
Kl´ıˇ cov´ a slova grafick´e intro, OpenGL, 64kB, omezen´a velikost, parametry pˇrekladaˇce, exe packer, generov´an´ı ˇsumu, Perlin˚ uv ˇsum, vyˇsˇs´ı dimenze, Voron´eho diagram, barven´ y pˇrechod, textura, bump mapping, triplan´ arn´ı texturov´an´ı, skybox, Marching cubes, Marching tetrahedra, ˇc´asticov´e syst´emy, elastick´e syst´emy, Eulerova numerick´a metoda, Runge Kutta metoda, kolize, voda, ter´en, pohyb kamery, Catmull-Rom, hudba
Keywords graphics intro, OpenGL, 64kB, limited size, compiler arguments, exe packer, noise generation, Perlin noise, higher dimension, Voronoi diagram, color gradient, texture, bump mapping, Tri-Planar texturing, skybox, Marching cubes, Marching tetragedrons, particle system, elastic system, Euler numerical method, Runge Kutta method, collision, water, terrain, camera motion, Catmull-Rom, music
Citace Tom´aˇs Milet: Grafick´e intro 64kB s pouˇzit´ım OpenGL, diplomov´a pr´ace, Brno, FIT VUT v Brnˇe, 2012
Grafick´ e intro 64kB s pouˇ zit´ım OpenGL Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem tuto bakal´ aˇrskou pr´aci vypracoval samostatnˇe pod veden´ım doc. Ing. Adama Herouta Ph.D. Uvedl jsem vˇsechny liter´arn´ı prameny a publikace, ze kter´ ych jsem ˇcerpal. ....................... Tom´aˇs Milet 21. kvˇetna 2012
Podˇ ekov´ an´ı R´ad bych podˇekoval doc. Ing. Adamovi Heroutovi Ph.D. za jeho veden´ı a rady v pr˚ ubˇehu pr´ace. D´ ale bych podˇekoval sv´e matce za korekci nˇekter´ ych gramatick´ ych chyb. Nakonec bych podˇekoval Dormonovi za jeho extraordin´arn´ı n´apady.
c Tom´
aˇs Milet, 2012. Tato pr´ ace vznikla jako ˇskoln´ı d´ılo na Vysok´em uˇcen´ı technick´em v Brnˇe, Fakultˇe informaˇcn´ıch technologi´ı. Pr´ ace je chr´ anˇena autorsk´ym z´ akonem a jej´ı uˇzit´ı bez udˇelen´ı opr´ avnˇen´ı autorem je nez´ akonn´e, s v´yjimkou z´ akonem definovan´ych pˇr´ıpad˚ u.
Obsah ´ 1 Uvod 1.1 OpenGL . . . . 1.2 Intro . . . . . . 1.3 Velikost 64KB . 1.4 Pˇr´ıbˇeh . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
2 2 2 3 3
2 Techniky pro omezen´ı velikosti 2.1 Nastaven´ı pˇrekladaˇce . . . . . . . . . . 2.2 Exe packer . . . . . . . . . . . . . . . 2.3 Program´ atorsk´ y styl a konstrukce . . . ˇ 2.4 Sablony, generov´ an´ı grafick´eho obsahu 2.5 Dalˇs´ı techniky, obfuskace . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
4 4 5 5 7 7
3 Generov´ an´ı grafick´ eho obsahu ˇ 3.1 Sum . . . . . . . . . . . . . . . . . . 3.2 Generov´ an´ı ˇsumu p˚ ulen´ım intervalu . 3.3 V´ıce dimenz´ı . . . . . . . . . . . . . 3.4 Voron´eho diagram . . . . . . . . . . 3.5 Generov´ an´ı textur . . . . . . . . . . 3.6 Generov´ an´ı geometrie . . . . . . . . 3.7 Bump mapping . . . . . . . . . . . . 3.8 Texturov´ an´ı . . . . . . . . . . . . . . 3.9 Skybox . . . . . . . . . . . . . . . . . ˇ asticov´e syst´emy . . . . . . . . . . 3.10 C´ 3.11 Elastick´e syst´emy . . . . . . . . . . . 3.12 Kolize . . . . . . . . . . . . . . . . . 3.13 Voda . . . . . . . . . . . . . . . . . . 3.14 Ter´en . . . . . . . . . . . . . . . . . 3.15 Pohyb kamery . . . . . . . . . . . . . 3.16 Texty . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
8 8 9 11 11 14 17 22 23 23 26 27 31 32 33 34 35
. . . .
36 36 37 39 41
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
4 Implementace 4.1 Hudba . . . . . . . . . . . 4.2 Sc´eny intra . . . . . . . . 4.3 GLSL . . . . . . . . . . . 4.4 Rozdˇelen´ı projektu a FPS
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
5 Z´ avˇ er
. . . . . . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
45 1
Kapitola 1
´ Uvod C´ılem t´eto pr´ ace je vytvoˇren´ı grafick´eho intra s omezenou velikost´ı. Pr´ace pojedn´av´ a o technik´ ach minimalizace velikosti spustiteln´eho souboru pomoc´ı nastaven´ı pˇrekladu, komprimov´ an´ı v´ ysledn´eho souboru, vhodn´eho program´atorsk´eho stylu a generov´an´ı obsahu podle ˇsablon. Zab´ yv´ a se generov´an´ım grafick´eho obsahu jako jsou textury a geometrie. V pr´aci je pops´ an zp˚ usob generov´an´ı v´ıcerozmˇern´eho ˇsumu. D´ale se zab´ yv´a vytvoˇren´ım v´ıcerozmˇern´ ych Voron´eho diagram˚ u. Dalˇs´ı ˇc´ast pr´ace se zab´ yv´a tvorbou textur pomoc´ı ˇsumu, Voron´eho diagram˚ u, barevn´ ych pˇrechod˚ u a transformaˇcn´ıch operac´ı. N´asleduje sekce o generov´ an´ı geometrie intra. V t´eto ˇc´asti je pops´an pˇrevod objemov´e reprezentace tˇelesa na povrchovou reprezentaci. Spadaj´ı sem algoritmy Marching cubes a Marching tetrahedra. D´ale sem patˇr´ı vyhlazen´ı povrchu a optimalizace ukl´ad´an´ı dat produkovan´ ych tˇemito algoritmy. Pot´e se pr´ ace zab´ yv´ a bump mappingem, texturov´an´ım, tvorbou skyboxu, ˇc´asticov´ ymi a elastick´ ymi syst´emy, vodou, ter´enem a pohybem kamery.
1.1
OpenGL
OpenGL je v pr´ aci vyuˇzito pro vykreslov´an´ı veˇsker´e grafiky. OpenGL ( Open Graphics ” Library“) je n´ızko´ urovˇ nov´ a grafick´a knihovna. Za vytvoˇren´ım knihovny stoj´ı spoleˇcnost Silicon Graphics, Inc., jeˇz ji uvedla v roce 1992. Knihovna od poˇc´atku vyˇsla v nˇekolika verz´ıch, pˇriˇcemˇz verze jsou zpˇetnˇe kompatibiln´ı. Obsahuje stovky funkc´ı umoˇzn ˇuj´ıc´ıch specifikaci a manipulaci s grafick´ ymi daty. V dˇr´ıvˇejˇs´ıch dob´ach byla kresl´ıc´ı pipeline fixn´ı a nebylo tedy moˇzn´e ji jakkoliv upravit. Od verze OpenGL 2.0 je k dispozici jazyk GLSL, kter´ ym lze kreslic´ı pipeline naprogramovat a zmˇenit jej´ı chov´an´ı.
1.2
Intro
Grafick´e intro b´ yv´ a kr´ atk´e video vytvoˇren´e programem. Video vytvoˇren´e aplikac´ı neb´ yv´ a nijak interaktivn´ı. D˚ uleˇzitou charakteristikou programu je jeho mal´a velikost. Existuje nˇekolik kategori´ı velikost´ı od 1KB pˇres 64KB aˇz po neomezenou velikost. Program obvykle nepotˇrebuje ke sv´emu bˇehu ˇz´ adn´ a extern´ı data, jako jsou obr´azky textur a soubory s modely ˇci hudbou. Kl´ıˇcov´ ym prvkem intra je kontrast mezi malou velikost´ı programu a mnoˇzstv´ım a silou u ´ˇcinku prezentovan´ ych grafick´ ych a zvukov´ ych informac´ı. Tento kontrast vˇetˇsinou poukazuje na schopnosti dan´eho program´atora nebo skupiny, kteˇr´ı intro vytvoˇrili. U vˇetˇs´ıch skupin vznikaj´ı i r˚ uzn´e podp˚ urn´e n´astroje napˇr´ıklad pro komponov´an´ı a pˇrehr´av´an´ı hudby. Zdrojov´e k´ ody program˚ u b´ yvaj´ı vˇetˇsinou tajn´e a autoˇri si je bedlivˇe stˇreˇz´ı. Intra se objevuj´ı 2
nejˇcastˇeji jako programy vytvoˇren´e pro z´abavu ˇci soutˇeˇz. Vyskytuj´ı se ale i jako komerˇcn´ı prezentace. Obsah intra m˚ uˇze b´ yt kr´ atk´ y pˇr´ıbˇeh, pˇredveden´ı myˇslenky, prezentace schopnost´ı autor˚ u, uk´ az´ an´ı sv´ ych umˇeleck´ ych schopnost´ı, propagace k filmu, reklama nebo jin´e vˇeci. Pokud se jedn´ a o intro vytvoˇren´e pro z´abavu (nejˇcastˇejˇs´ı pˇr´ıpad) nen´ı obsah intra nikterak sv´az´an a n´ aplˇ n je zcela v rukou autora a z´aleˇz´ı jen na nˇem, co bude jeho intro zobrazoˇ vat. Cast´e jsou abstraktn´ı sc´eny, kter´e nemaj´ı mnoho spoleˇcn´eho s realitou, poskytuj´ı vˇsak vydatn´ y grafick´ y z´ aˇzitek. Abstraktn´ı intra se nejˇcastˇeji objevuj´ı u velmi mal´ ych velikost´ı program˚ u. Nev´ yhodou tˇechto typ˚ u inter b´ yv´a, ˇze aˇc jsou grafick´e efekty sebelepˇs´ı ˇcasem, s v´ yvojem grafick´eho hardwaru, stejnˇe zastar´avaj´ı. Proto b´ yv´a d˚ uleˇzit´ ym prvkem intra pˇr´ıbˇeh. Siln´ y pˇr´ıbˇeh m˚ uˇze hodnotu intra znaˇcnˇe zv´ yˇsit. Nicm´enˇe to plat´ı i naopak. Grafick´ a intra jsou fenom´enem. Internet jich obsahuje tis´ıce a komunita kolem inter je velmi ˇziv´ a. Poˇr´ adaj´ı se r˚ uzn´e soutˇeˇze s ocenˇen´ımi. Do budoucna lze oˇcek´avat, ˇze tvorba inter bude pokraˇcovat. S pˇrib´ yvaj´ıc´ım v´ ykonem zobrazovac´ıho hardwaru porostou kvalita vizu´aln´ıch efekt˚ u a moˇznosti inter, avˇsak vˇzdy bude nejv´ıce z´aleˇzet na schopnostech autora.
1.3
Velikost 64KB
Velikost 64KB se m˚ uˇze zd´ at pro aplikaci zobrazuj´ıc´ı grafiku velmi m´alo, kdyˇz i velmi jednoduch´e programy mohou po kompilaci zab´ırat velikost nˇekolika megabajt˚ u. Toto se ˇcasto t´ yk´ a vysoko´ urovˇ nov´ ych jazyk˚ u a vysoko´ urovˇ nov´ ych programovac´ıch prostˇredk˚ u. Tyto vysoko´ urovˇ nov´e n´ astroje poskytuj´ı program´atorsk´ y komfort, ale obvykle nedbaj´ı na v´ yslednou velikost aplikace a ani na jej´ı rychlost. V podstatˇe je mezi k´odem program´atora a v´ ysledn´ ymi instrukcemi procesoru nˇekolik mezivrstev. V samotn´ ych aplikac´ıch se tak vyskytuj´ı spousty nevyuˇzit´eho k´ odu a statick´ ych dat. Kdyˇz se ˇrekne poˇc´ıtaˇcov´a grafika, vˇetˇsinˇe uˇzivatel˚ u se vybav´ı poˇc´ıtaˇcov´e hry a ty bˇeˇznˇe zab´ıraj´ı gigabajty dat, coˇz je i sto tis´ıckr´at v´ıce neˇz obvykl´ a velikost inter. Toto je jedna z nejd˚ uleˇzitˇejˇs´ıch (ne-li nejd˚ uleˇzitˇejˇs´ı) charakteristik intra. Z´akladem mal´e velikosti inter je tedy odstranˇen´ı vˇsech nevyuˇzit´ ych ˇc´ast´ı. Toho lze dos´ahnou vhodn´ ym (n´ızko´ urovˇ nov´ ym) programovac´ım jazykem jako je jazyk C nebo assembler. D´ ale vhodn´ ym nastaven´ım pˇrekladaˇce a vhodn´ ym program´atorsk´ ym stylem. Dalˇs´ı velkou u ´sporu m´ısta lze dos´ ahnout generov´an´ım grafick´eho obsahu. M´ısto, aby se data jako textury a modely ukl´ adaly do konstantn´ıch dat, uloˇz´ı se jen zp˚ usob jejich vytvoˇren´ı. Posledn´ı moˇznost´ı je v´ yslednou aplikaci zkomprimovat.
1.4
Pˇ r´ıbˇ eh
Od zaˇc´ atku jsem chtˇel intro, kter´e zobrazuje pˇr´ırodu. Nechtˇel jsem intro, kter´e je pˇr´ıliˇs abstraktn´ı a mechanick´e. Intro, ve kter´em se vyskytuj´ı nere´aln´e mechanick´e objekty. Proto jsem zvolil m´ırn´ y motiv - pˇr´ırodu. V intru jsou nakonec ˇctyˇri sc´eny. Prvn´ı z nich je vysokohorsk´a sc´ena se zasnˇeˇzen´ ymi vrcholky ˇst´ıt˚ u. Hory jsou sn´ım´any z ptaˇc´ıho pohledu a jsou nasv´ıceny rann´ım sluncem. N´ asleduje pˇr´ımoˇrsk´a sc´ena. V n´ı je m´ırn´a pahorkatina a moˇrsk´ a hladina. Sc´ena je osv´ıcena zapadaj´ıc´ım sluncem. Ve sc´enˇe se kamera ponoˇr´ı do str´anˇe. N´asleduje sc´ena s tunelem, kter´ y smˇeˇruje dol˚ u, do kopce. Tunel je zarostl´ y a vyskytuje se v nˇem pavuˇcina. Na konci je voda. Posledn´ı sc´ena je v jeskyni. Jeskynˇe je z ˇc´asti zatopena. Do jeskynˇe pronik´ a voda v podobˇe nˇekolika vodop´ad˚ u. Jsou zde zavˇeˇseny tˇri barevn´e koberce, pod kter´ ymi jsou rozh´ azeny bedny. Sc´ena ke konci intra vybouchne.
3
Kapitola 2
Techniky pro omezen´ı velikosti Jak jiˇz bylo v u ´vodu ˇreˇceno, velikost aplikace je u inter d˚ uleˇzit´a. Technik pro zmenˇsen´ı v´ ysledn´e aplikace je nˇekolik. Je to nastaven´ı pˇrekladaˇce tak, aby odstranil vˇsechna nepouˇz´ıvan´a data, a aby sv˚ uj pˇreklad optimalizoval na v´ yslednou velikost. Dalˇs´ım zp˚ usobem je v´ yslednou aplikaci zkomprimovat speci´aln´ımi bal´ıc´ımi programy - takzvan´ ymi Exe packery. Ty aplikaci zkomprimuj´ı a vloˇz´ı na zaˇc´atek algoritmus rozbalen´ı a spuˇstˇen´ı. Dalˇs´ı u ´sporu m´ısta lze dos´ ahnou zvolen´ ym jazykem a vhodn´ ymi konstrukcemi v nˇem. Velmi d˚ uleˇzitou ˇc´ast tak´e tvoˇr´ı generov´ an´ı grafick´eho obsahu, protoˇze nem˚ uˇzeme m´ıt uloˇzena prakticky ˇz´adn´a data. Mezi ostatn´ı metody zmenˇsov´an´ı velikosti programu patˇr´ı obfuskace k´odu, kter´ y je uloˇzen ve statick´ ych datech a volba platformy, na kter´e m´a aplikace bˇeˇzet (rozd´ıl ve velikostech aplikace lze pozorovat u tˇriceti dvou bitov´ ych a ˇsedes´ati ˇctyˇr bitov´ ych verz´ıch syst´emu).
2.1
Nastaven´ı pˇ rekladaˇ ce
Pro pˇreklad t´eto pr´ ace byl pouˇzit program GCC. Ten umoˇzn ˇuje nˇekolik nastaven´ı pro zmenˇsen´ı velikosti. V´ yznamn´e parametry jsou: Parametr -s Kompil´ ator pˇri vyuˇzit´ı tohoto parametru zahod´ı veˇsker´ y nevyuˇz´ıvan´ y k´ od programu. Pokud se v programu vyskytne k´od nebo data na kter´e nen´ı odkazov´ano, nemaj´ı v´ yznam pro bˇeh aplikace. Parametr tak´e zajist´ı odstranˇen´ı vˇsech statick´ ych u ´daj˚ u pro ladˇen´ı programu. Tyto u ´daje jsou napˇr´ıklad n´azvy funkc´ı a procedur. Proto je vhodn´e tento parametr nepouˇz´ıvat pˇri ladˇen´ı. Tento parametr m˚ uˇze v´ yslednou velikost zmenˇsit i na tˇricet procent p˚ uvodn´ı velikosti. Parametr -Os Tento parametr donut´ı kompil´ator optimalizovat k´od pˇreuspoˇr´ad´an´ım a hled´ an´ım v´ yhodnˇejˇs´ıch konstrukc´ı. Pˇr´ıkladem m˚ uˇze b´ yt spojen´ı dvou po sobˇe jdouc´ıch cykl˚ u se stejn´ ym poˇctem opakov´an´ı. D´ıky tomuto parametru m˚ uˇze kompil´ator obˇe smyˇcky spojit dohromady. Nesm´ı vˇsak doj´ıt ke zmˇenˇe v´ yznamu. Vyuˇzit´ım tohoto parametru se aplikace m˚ uˇze zmenˇsit aˇz o nˇekolik stovek bajt˚ u. Parametr -nostdlib Tento parametr odstran´ı veˇsker´e standardn´ı knihovny z aplikace a zanech´ a jenom nutn´e minimum. Parametr se obvykle neobejde bez dalˇs´ıho parametru: -Wl,-emain, kter´ ym se specifikuje vstupn´ı bod aplikace. Nesm´ıme zapomenout, ˇze aplikov´ an´ım tohoto parametru se n´am znepˇr´ıstupn´ı vˇetˇsina bˇeˇznˇe pouˇz´ıvan´ ych funkc´ı jako je napˇr´ıklad alokace pamˇeti. Proto je nutn´e tyto chybˇej´ıc´ı funkce dopsat a to
4
obvykle v inline assembleru. Pˇr´ıkladem funkce, kterou je nutn´e dopsat v inline assembleru je funkce exit, bez kter´e se program neukonˇc´ı korektnˇe. Vyuˇzit´ım parametru je moˇzn´e aplikaci zmenˇsit i o 5KB, nicm´enˇe toto zmenˇsen´ı sebou pˇrin´aˇs´ı ˇradu nepˇr´ıjemnost´ı v podobˇe nutn´eho dops´an´ı z´akladn´ıch funkc´ı.
2.2
Exe packer
Exe packer je aplikace na komprimov´an´ı zkompilovan´ ych program˚ u. V´ ysledkem jeho aplikov´an´ı je komprimovan´ y spustiteln´ y soubor. Tˇechto komprimaˇcn´ı program˚ u existuje nˇekolik. Liˇs´ı se sv´ ymi algoritmy pro kompresi. Nˇekter´e pracuj´ı jen v nˇekter´ ych operaˇcn´ıch ´ syst´emech a nˇekter´e jsou multiplatformn´ı. Uzce zamˇeˇren´e poskytuj´ı vˇetˇsinou vˇetˇs´ı komprimaˇcn´ı pomˇer. Mezi v´ yznamnˇejˇs´ı komprimaˇcn´ı programy patˇr´ı UPX [12] ve verzi 3.08. Tento program je multiplatformn´ı a jsou k dispozici jeho zdrojov´e k´ody. T´ım, ˇze je multiplatformn´ı jej lze s v´ yhodou pouˇz´ıt pro multiplatformn´ı intra. T´ımto komprimaˇcn´ım programem lze mimo spustiteln´e aplikace komprimovat i dynamicky linkovan´e knihovny. Poskytuje menˇs´ı komprimaˇcn´ı pomˇer. Vytv´ aˇren´ y program m˚ uˇze zkomprimovat i na tˇricet procent jeho p˚ uvodn´ı velikosti. Dalˇs´ı komprimaˇcn´ı program se jmenuje kkrunchy [6]. Tento exe packer vyvinula nˇemeck´ a skupina Farbrausch. Program bˇeˇz´ı v operaˇcn´ım syst´emu Windows 7 a poskytuje jeden z nejlepˇs´ıch komprimaˇcn´ıch pomˇer˚ u. Proto b´ yv´a ˇcasto vyuˇz´ıv´am pˇri tvorbˇe inter. Nastaven´ım parametru pˇri spuˇstˇen´ı programu lze zvolit poˇzadovanou v´ yslednou velikost.
2.3
Program´ atorsk´ y styl a konstrukce
Vhodn´ ym program´ atorsk´ ym stylem lze uˇsetˇrit tak´e nˇejak´e m´ısto. Existuje nˇekolik v´ yhodn´ ych konstrukc´ı, kter´e jsou v t´eto pr´aci pouˇz´ıv´any: • Vyuˇz´ıv´ an´ı funkc´ı. Vhodn´e je ˇcasto vyuˇz´ıvat funkce na ˇc´asti programu, kter´e se opakuj´ı. Toto patˇr´ı k dobr´emu program´atorsk´emu stylu jako zp˚ usob dekompozice probl´emu. Nicm´enˇe, dobr´ ym n´ avrhem a hled´an´ım m´ıst programu, kter´e lze slouˇcit do funkce lze dos´ ahnout zmenˇsen´ı k´ odu i o stovky bajt˚ u. D˚ uleˇzit´e je db´at na to, aby se velikost aplikace zmenˇsila. Nevhodn´ ym pouˇzit´ım funkc´ı m˚ uˇze velikost naopak nar˚ ust. Pokud m´ ame jen nˇekolik ˇr´ adk˚ u k´ odu, kter´e pouˇz´ıv´ame na mnoha m´ıstech (napˇr´ıklad sˇc´ıt´ an´ı dvou dvojrozmˇern´ ych vektor˚ u), nemus´ı m´ıt vytv´aˇren´ı funkce pro tyto ˇr´adky z pohledu velikosti smysl. Vol´ an´ı funkce pro seˇcten´ı dvou vektor˚ u m˚ uˇze samo o sobˇe zab´ırat v´ıce m´ısta. Proto je v´ yhodnˇejˇs´ı dan´e ˇr´adky k´odu neobalovat funkc´ı. Dobr´e z pohledu velikosti tak ˇcitelnosti m˚ uˇze b´ yt vyuˇzit´ı preprocesoru ˇci inline funkc´ı, kter´e se na m´ıstˇe vol´ an´ı rozbal´ı. • Vyuˇzit´ı rekurze. Program´ atorskou konstrukc´ı, kter´a zmenˇsuje v´ yslednou velikost je tak´e rekurze. Rekurze je sice pomalejˇs´ı na vyˇc´ıslen´ı, ale jej´ı vhodn´e pouˇzit´ı m˚ uˇze pomoci aplikace zmenˇsit. Rekurze je zvl´aˇstˇe vhodn´a pro proch´azen´ı seznam˚ u, z´asobn´ık˚ u, front a strom˚ u, kde se oproti ˇreˇsen´ı bez rekurze znaˇcnˇe zmenˇsuje v´ ysledn´a velikost algoritm˚ u. • Vyuˇzit´ı pˇr´ıkazu goto. Pˇr´ıkaz goto (nepodm´ınˇen´ y skok) uˇz vˇetˇsinou k dobr´emu programovac´ımu stylu nepatˇr´ı. B´ yv´a doporuˇceno tento pˇr´ıkaz nevyuˇz´ıvat, kv˚ uli zanesen´ı
5
nepˇrehlednosti do k´ odu. Nicm´enˇe, pokud potˇrebujeme uˇsetˇrit i des´ıtky bajt˚ u, m˚ uˇze b´ yt pouˇzit´ı tohoto pˇr´ıkazu pˇr´ınosn´e. V´ yhodn´e je pouˇz´ıt jej na vyskoˇcen´ı ze zanoˇren´e smyˇcky. Dalˇs´ı vyuˇzit´ı m˚ uˇze b´ yt pro uvolˇ nov´an´ı pamˇeti. Uvaˇzme pˇr´ıpad, kdy si funkce v pr˚ ubˇehu v´ ypoˇctu alokuje na nˇekolika m´ıstech pamˇet’. Z´aroveˇ n se funkce vˇetv´ı a m˚ uˇze skonˇcit na r˚ uzn´ ych m´ıstech. Pˇred ukonˇcen´ım funkce je z´ahodn´e veˇskerou pomocnou alokovanou pamˇet’ uvolnit. Vzhledem k tomu, ˇze m´ame v´ıcero ukonˇcovac´ıch m´ıst, je nutn´e uvolnˇen´ı doˇcasnˇe alokovan´e pamˇeti prov´est na kaˇzd´em z nich, pˇriˇcemˇz kaˇzd´e uvolnˇen´ı se m´ırnˇe liˇs´ı. Toto lze vyˇreˇsit vytvoˇren´ım uvolˇ novac´ı funkce. Funkce bude m´ıt tolik parametr˚ u, kolik je promˇenn´ ych k uvolnˇen´ı. Nav´ıc uvolˇ novac´ı funkce bude kontrolovat, zda je promˇenn´ a naplnˇen´a (promˇenn´a nemusela b´ yt v dan´em ukonˇcovac´ım m´ıstˇe p˚ uvodn´ı funkce alokovan´a). Nev´ yhodou tohoto ˇreˇsen´ı je, ˇze neuˇsetˇr´ı moc m´ısta (pokud v˚ ubec nˇejak´e). Dalˇs´ı nev´ yhodou je, ˇze uvolˇ novac´ı funkce se vyuˇz´ıv´a jen pro tuto funkci. V´ yhodnˇejˇs´ı je na konec funkce uv´est uvolnˇen´ı promˇenn´ ych v opaˇcn´em poˇrad´ı nˇeˇz jak jsou alokov´ any a za nˇe vloˇzit jedin´ y ukonˇcovac´ı bod funkce. V m´ıstech, kde p˚ uvodn´ı funkce konˇcila se uvede pˇr´ıkaz goto na pˇr´ısluˇsn´e m´ısto do uvolˇ novac´ı sekvence. Situace je zn´ azornˇena na obr´azku 2.1.
Alokace A
Alokace A Větvení goto A
Větvení Uvolnění A Konec
Alokace B
Alokace B
Větvení goto B
Větvení Uvolnění A Uvolnění B Konec
Alokace C Větvení goto C
Alokace C
C: Uvolnění C B: Uvolnění B A: Uvolnění A Konec
Větvení Uvolnění A Uvolnění B Uvolnění C Konec
Obr´ azek 2.1: Vyuˇzit´ı pˇr´ıkazu goto • Vyt´ yk´ an´ı k´ odu. Vyt´ yk´ an´ım lze tak´e uˇsetˇrit nˇekolik bajt˚ u. Vytknout lze (mimo jin´e) tak´e prolog a epilog ˇc´ asti k´odu. Pouˇzit´ı vyt´ yk´an´ı epilogu m˚ uˇzeme vidˇet u pˇr´ıkladu vyuˇzit´ı goto zn´ azornˇen´eho na 2.1. O vyt´ yk´an´ı k´odu se snaˇz´ı i kompilaˇcn´ı program (pˇri vyuˇzit´ı parametru -s), nicm´enˇe program´ator m´a veˇsker´e informace, tak tuto ˇcinnost dˇel´ a efektivnˇeji. • Rozbalen´ı smyˇcek. U smyˇcek jejichˇz tˇelo je dostateˇcnˇe mal´e a poˇcet opakov´an´ı n´ızk´ y, m˚ uˇze v´est rozbalen´ı k uspoˇren´ı m´ısta. • Obecn´e abstraktn´ı datov´e typy. Vytvoˇren´ım obecn´ ych abstraktn´ıch datov´ ych typ˚ u, jako je napˇr´ıklad seznam, m˚ uˇzeme program tak´e zmenˇsit. V pˇr´ıpadˇe, kdy seznam potˇrebujeme na v´ıcero m´ıstech, m˚ uˇze b´ yt vytvoˇren´ı obecn´eho seznamu dobr´ ym krokem. 6
Obecn´ a implementace abstraktn´ıho datov´eho typu obvykle zabere v´ıce m´ısta neˇz implementace konkr´etn´ı, avˇsak, pokud je tento typ vyuˇz´ıv´an na v´ıcero m´ıstech programu, m˚ uˇze b´ yt jeho pouˇzit´ı v´ yhodn´e. Zmenˇsen´ı velikosti totiˇz spoˇc´ıv´a ve sd´ılen´ı obsluˇzn´ ych funkc´ı. ˇ asti nˇekter´ • Vyuˇz´ıv´ an´ı bitov´ ych a jin´ ych operac´ı. C´ ych algoritm˚ u lze efektivnˇe zmenˇsit pomoc´ı s´erie oper´ ator˚ u. V´ ysledkem je u ´spora m´ısta za cenu pˇrehlednosti. Pˇr´ıkladem necht’ je inicializace matice M na jednotkovou matici: for(int i=0;i<16;++i) M[i] = i%4 == i/4; • Inline assembler. Assembler se ˇcasto vyuˇz´ıv´a u mal´ ych inter, protoˇze poskytuje velkou u ´sporu m´ısta. Jeho nev´ yhodou je vˇsak ztr´ata pˇrehlednosti a do jist´e m´ıry i pˇrenositelnosti k´ odu. • Jin´e. Mezi dalˇs´ı techniky m˚ uˇzeme zaˇradit ˇspatn´e program´atorsk´e n´avyky. V pˇr´ıpadˇe, ˇze se snaˇz´ıme uˇsetˇrit kaˇzd´ y bajt, se m˚ uˇzeme rozhodnout neuvolˇ novat n´ami alokovanou pamˇet’ a doufat, ˇze potˇrebnou dealokaci provede operaˇcn´ı syst´em. Dalˇs´ı moˇznost´ı je vytvoˇren´ı v´ıcero zkompilovan´ ych verz´ı aplikace, a t´ım odstranit nutnost zpracov´ an´ı argument˚ u po spuˇstˇen´ı (ve kter´ ych m˚ uˇze b´ yt napˇr´ıklad ˇs´ıˇrka a v´ yˇska okna). Pˇri implementaci algoritm˚ u pro intro se ˇcasto setk´ame se situac´ı, kdy se mus´ıme rozhodnout, mezi velikost´ı, rychlost´ı, znovupouˇzitelnost´ı a ˇcitelnost´ı. Vˇsechny tyto vlastnosti jdou proti sobˇe aˇz na ˇcitelnost, kterou lze t´emˇeˇr vˇzdy zajistit. Z´aleˇz´ı jen na situaci a schopnostech program´ atora pˇredpov´ıdat, kter´ a z implementac´ı dan´eho algoritmu je vhodnˇejˇs´ı. Pˇr´ıpadnˇe lze naprogramovat v´ıcero variant, mezi kter´ ymi se v pˇr´ıpadˇe potˇreby pˇrepne preprocesorem.
2.4
ˇ Sablony, generov´ an´ı grafick´ eho obsahu
Bez generov´ an´ı grafick´eho obsahu by se intra neobeˇsla. Generov´an´ı a ˇsablony jsou z´akladem vˇsech inter. D´ıky generov´ an´ı obsahu podle ˇsablon lze uˇsetˇrit nejv´ıce m´ısta. Lze uˇsetˇrit des´ıtky i stovky megabajt˚ u. Nam´ısto, aby se v aplikaci ukl´adaly textury a modely, uloˇz´ı se jen zp˚ usob, jak je vytvoˇrit. Napˇr´ıklad nebudeme ukl´ad´a body kruˇznice, uloˇz´ıme si jen polomˇer a stˇred a algoritmus na vygenerov´an´ı bod˚ u kruˇznice. Tento zp˚ usob uloˇzen´ı m´ a nˇekolik v´ yhod. Prvn´ı z nich je velikost, kter´a je o mnoho menˇs´ı. Dalˇs´ı v´ yhodou je parametrizov´an´ı generov´ an´ı. M˚ uˇzeme si zvolit kvalitu (poˇcet bod˚ u na kruˇznici), stˇred i polomˇer. Neuloˇzili jsme si tedy jen jednu kruˇznici, ale vˇsechny moˇzn´e kruˇznice ve vˇsech moˇzn´ ych kvalit´ach a to s konstantn´ı velikost´ı dat. V´ ysledn´e intro lze tedy dobˇre parametrizovat a jen mal´ ymi zmˇenami parametr˚ u markantnˇe mˇenit grafick´ y obsah. Generov´an´ı grafick´eho obsahu je vˇenov´ ana cel´ a kapitola 3.
2.5
Dalˇ s´ı techniky, obfuskace
Mezi dalˇs´ı techniky minimalizace velikosti patˇr´ı obfuskace [10]. Obfuskace je vyuˇzit´ı syntaxe jazyka tak, ˇze se pouˇzij´ı co nejkratˇs´ı textov´e konstrukce pro dan´ y program. Obvykle to zahrnuje odstranˇen´ı koment´ aˇr˚ u, zkr´acen´ı identifik´ator˚ u a zruˇsen´ı form´atov´an´ı. Toto lze pouˇz´ıt jen ve speci´ aln´ıch pˇr´ıpadech, kdy je program uloˇzen nezkompilovan´ y ve statick´ ych datech. T´ yk´ a se to program˚ u v jazyce GLSL. U rozs´ahlejˇs´ıch program˚ u v GLSL (shaderech) lze dos´ ahnou u ´spory aˇz stovek bajt˚ u. Nev´ yhodou obfuskace je absolutn´ı ztr´ata ˇcitelnosti. 7
Kapitola 3
Generov´ an´ı grafick´ eho obsahu Jak jiˇz bylo ˇreˇceno v pˇredch´ azej´ıc´ı kapitole, generov´an´ı grafick´eho obsahuje je pro intra kl´ıˇcov´e. Generuj´ı se textury, generuj´ı se modely, generuje se geometrie. Generuje se rozm´ıstˇen´ı model˚ u ve sc´enˇe. Generov´an´ı grafick´ ych objekt˚ u sebou pˇrin´aˇs´ı v´ yhody mal´e velikosti a parametrizov´ an´ı generov´ an´ı. M˚ uˇzeme si tedy napˇr´ıklad uloˇzit jednu ˇsablonu stromu a vhodn´ ym mˇenˇen´ım parametr˚ u generovat pokaˇzd´e jin´ y strom. Nev´ yhodou generov´an´ı je delˇs´ı nahr´ avac´ı ˇcas. Vytvoˇren´ı kvalitn´ı textury m˚ uˇze b´ yt ˇcasovˇe velmi n´aroˇcn´e, z tohoto d˚ uvodu m´ıvaj´ı intra delˇs´ı inicializaˇcn´ı ˇcasy.
3.1
ˇ Sum
ˇ Sum je n´ ahodn´ y sign´ al. Se ˇsumem se ˇcasto setk´av´ame v elektronice. Zde se jedn´a o neˇz´adan´ y jev, kter´ y zkresluje v´ ysledky. Setk´av´ame se s n´ım tak´e u digit´aln´ıch fotografii, kde se napˇr´ıklad projevuje jako zmˇena hodnoty dan´eho pixelu. V informatice se vˇsak ˇsum vyuˇz´ıv´ a (napˇr´ıklad jako zdroj n´ ahodn´ ych ˇc´ısel). N´ahodn´a ˇc´ısla (skuteˇcnˇe n´ahodn´a ˇc´ısla) se vyuˇz´ıvaj´ı v kryptografii. Bˇeˇznˇe vˇetˇsinou nem´ame k dispozici gener´atory skuteˇcnˇe n´ahodn´ ych ˇc´ısel (je k tomu obvykle potˇreba specializovan´ y hardware), proto se pouˇz´ıvaj´ı kongruentn´ı gener´atory produkuj´ıc´ı pseudon´ ahodn´ a ˇc´ısla. Seznam hodnot vygenerovan´ ych t´ımto gener´atorem je pak povaˇzov´ an za ˇsum. V poˇc´ıtaˇcov´e grafice se setk´av´ame s r˚ uzn´ ymi druhy gener´ator˚ u ˇsumu zaloˇzen´ ych na r˚ uzn´ ych druz´ıch gener´ator˚ u pseudon´ahodn´ ych ˇc´ısel. Na gener´atory ˇc´ısel je kladena ˇrada poˇzadavk˚ u z pohledu statistiky. Tyto poˇzadavky je nutn´e dodrˇzet v pˇr´ıpadech, kdy hraj´ı d˚ uleˇzitou roli (napˇr´ıklad v simulac´ıch). V poˇc´ıtaˇcov´e grafice si vˇsak ˇcasto vystaˇc´ıme i s jednoduch´ ymi implementacemi. U inter hraje nejd˚ uleˇzitˇejˇs´ı roli velikost a rychlost.
3.1.1
Gener´ atory pseudon´ ahodn´ ych ˇ c´ısel
Existuje v´ıcero druh˚ u gener´ ator˚ u. Nˇekter´e v podobˇe kongruentn´ıho gener´atoru, jin´e v podobˇe funkce, kter´ a m´ a vstupn´ı parametry a vˇzdy pro stejn´e nastaven´ı parametr˚ u produkuje stejn´ y pseudon´ ahodn´ y v´ ystup. Tyto gener´atory produkuj´ı celoˇc´ıseln´ y v´ ystup s urˇcit´ ym rozsahem. Je vhodn´e gener´atory upravit tak, aby vracely ˇc´ısla s plovouc´ı ˇr´adovou ˇc´arkou v rozsahu h0, 1i. S t´ımto rozsahem se pak pozdˇeji l´epe pracuje. • Kongruentn´ı gener´ ator. U kongruentn´ıho gener´atoru se vyskytuje inicializaˇcn´ı hodnota (takzvan´e sem´ınko). Gener´ator na z´akladˇe tohoto sem´ınka vygeneruje novou hodnotu a tu do sem´ınka uloˇz´ı. Line´arn´ı kongruentn´ı gener´ator m´a tvar xn+1 = (a · xn + b)%m, kde a, b, c jsou vhodnˇe zvolen´e konstanty. Sem´ınko je pak x0 . 8
• Gener´ ator zaloˇzen´ y na funkci. Tento typ gener´atoru vrac´ı stejn´a ˇc´ısla na z´akladˇe stejn´ ych celoˇc´ıseln´ ych vstup˚ u. Nalezen´ı takov´e funkce m˚ uˇze b´ yt obt´ıˇzn´e. Z´akladem je operace zbytku po celoˇc´ıseln´em dˇelen´ı (%), kter´a se pˇri generov´an´ı n´ahodn´ ych ˇc´ısel ˇcasto pouˇz´ıv´ a. Tvar t´eto funkce, kterou jsem v pr´aci pouˇzil je f (x) = (x5 + x4 + x3 + ˇ ıslo N je hodnota 2n , n > 0. Tento z´apis lze pomoc´ı Hornerova sch´ematu x2 +x1 )%N . C´ zefektivnit: f (x) = (x(x(x(x(x + 1) + 1) + 1) + 1))%N . Pro vyˇc´ıslen´ı jedn´e hodnoty potˇrebujeme jen ˇctyˇri n´ asoben´ı, ˇctyˇri sˇc´ıt´an´ı a jednu operaci modulo. Experiment´alnˇe jsem si ovˇeˇril, ˇze pro N = 224 funkce vrac´ı pro vstup x ∈ h0, N − 1i pokaˇzd´e jinou hodnotu. Tento poznatek bychom mohli vyuˇz´ıt pro konstrukci inverzn´ı funkce.
3.1.2
Perlin˚ uv ˇ sum
Perlin˚ uv ˇsum posan´ y v [13] a v [3] je ˇsum zaloˇzen´ y na ˇsumov´e funkci. V poˇc´ıtaˇcov´e grafice se hojnˇe vyuˇz´ıv´ a. Perlin˚ uv ˇsum vrac´ı pro stejn´e souˇradnice stejnou hodnotu v rozsahu h−1, 1i. V´ ysledn´ a hodnota ˇsumu na dan´ ych souˇradnic´ıch je z´ısk´ana jako souˇcet ˇsumov´ ych funkc´ı o r˚ uzn´ ych frekvenc´ıch a amplitud´ach. Frekvence se obvykle vol´ı jako n´asobek z´akladn´ı frekvence f0 mocninou dvˇe. Amplituda jednotliv´ ych frekvenc´ı je urˇcena poˇc´ateˇcn´ı amplitudou a perzistenc´ı. Pokud bychom zvolili poˇc´ateˇcn´ı amplitudu A = 1, perzistenci P = 1/2, tak pro frekvenci f0 · 2n je amplituda a = A · P n . Perlin˚ uv ˇsum budeme pouˇz´ıvat pro generov´ an´ı skybox˚ u.
3.2
Generov´ an´ı ˇ sumu p˚ ulen´ım intervalu
Kdybychom vygenerovali s´erii hodnot pomoc´ı gener´atoru n´ahodn´ ych ˇc´ısel, z´ıskali bychom ˇsum, kter´ y nen´ı pro grafiku pˇr´ıliˇs vhodn´ y. M˚ uˇzeme jej vidˇet v lev´e ˇc´asti obr´azku 3.1. Tento ˇsum m´ a hodnoty v sousedn´ıch bodech pˇr´ıliˇs odliˇsn´e. Pro dalˇs´ı generov´an´ı (napˇr´ıklad textur) je tedy vhodn´e ˇsum generovat jinak. D˚ uleˇzit´e je, aby rozd´ıly v sousedn´ıch bodech byly mal´e. Jedn´ım ze zp˚ usob˚ u jak to zajistit, je generovat hodnoty s ohledem na jiˇz vygenerovan´e hodnoty. Dalˇs´ı vlastnost´ı, kterou chceme zaruˇcit je, aby ˇsum na sebe navazoval. Toto lze zajistit algoritmem p˚ ulen´ı intervalu, jehoˇz v´ ysledek je v prav´e ˇc´asti obr´azku 3.1. Jak je z tohoto obr´ azku patrn´e, ˇsum produkovan´ y t´ımto algoritmem je vhodnˇejˇs´ı pro dalˇs´ı generov´ an´ı (napˇr´ıklad mrak˚ u). Generov´ an´ı ˇsumu pomoc´ı p˚ ulen´ı intervalu je dopodrobna pops´ano v bakal´aˇrsk´e pr´ aci [11]. Z´ akladem je gener´ ator ˇc´ısel (v podobˇe kongruentn´ıho gener´atoru). Pˇredpokl´adejme, ˇze chceme vygenerovat jednorozmˇern´ y ˇsum reprezentovan´ y polem o N prvc´ıch s indexy 0, 1, . . . , N − 1. M´ ame k dispozici z´akladn´ı rozsah gener´atoru d a faktor vyhlazov´an´ı m. Algoritmus pracuje n´ asledovnˇe (jeho vizualizace je v lev´e ˇc´asti obr´azku 3.2 a v´ ystup v prav´e ˇc´ asti obr´ azku 3.2): 1. Nejprve se vygeneruje n´ ahodn´a hodnota s rozsahem gener´atoru h−d, di a uloˇz´ı se do prvku s indexem 0. 2. Nastav´ı se nov´ y rozsah d := d/m. 3. Urˇc´ı se index S vhodn´eho stˇredu. Je to nejvˇetˇs´ı moˇzn´e ˇc´ıslo 2n takov´e, ˇze je menˇs´ı neˇz poˇcet prvk˚ u pole (N ). 4. Prvek s indexem S m´ a hodnotu souˇctu v´aˇzen´eho pr˚ umˇeru a novˇe vygenerovan´e hodnoty s upraven´ ym rozsahem. V´aˇzen´ y pr˚ umˇer je poˇc´ıt´an z hodnot nejbliˇzˇs´ıch, jiˇz vygenerovan´ ych prvk˚ u zleva a zprava od S, pˇriˇcemˇz hodnota v´ahy je urˇcen´a vzd´alenost´ı 9
Obr´azek 3.1: Vlevo: ˇsum jako prost´a sekvence n´ahodn´ ych ˇc´ısel. Vpravo: ˇsum vygenerovan´ y algoritmem p˚ ulen´ı intervalu. ˇ ım je prvek od S vzd´alenˇejˇs´ı, t´ım m´a jeho hodnota menˇs´ı v´ahu. jejich index˚ u od S. C´ Souˇcet vah je roven 1. Pokud ˇz´adn´ y vygenerovan´ y prvek zprava neexistuje, pouˇzije se prvek s indexem 0 a vzd´ alenost je spoˇc´ıt´ana jako vzd´alenost k posledn´ımu prvku pole plus jedna. T´ımto je zajiˇstˇeno opakov´an´ı. 5. Krokem 4 n´ am vznikla dvˇe pole: jedno s indexy 0, . . . , S a druh´e s indexy S, . . . , N −1. Na tato pole se aplikuje tento algoritmus znovu od kroku 2. Pole vˇsak mus´ı m´ıt v´ıce neˇz dva prvky.
Pořadí generování:
1 2
3 4
5
Obr´azek 3.2: Vlevo: kroky algoritmu p˚ ulen´ı intervalu. Vpravo: v´ ysledek algoritmu p˚ ulen´ı intervalu. V´ yˇse popsan´ y postup je urˇcen pro jednorozmˇern´ y ˇsum. V´ıce rozmˇern´a varianta je obdobn´a. V´ ypoˇcet hodnoty stˇredn´ıho bodu se napˇr´ıklad pro dvojrozmˇern´ y ˇsum nepoˇc´ıt´a ze dvou ale ze ˇctyˇr okoln´ıch bod˚ u. Podrobnˇe je obecn´ y algoritmu pops´an v bakal´aˇrsk´e pr´ aci [11].
10
3.3
V´ıce dimenz´ı
Jelikoˇz se v t´eto pr´ aci ˇcasto pracuje s v´ıcerozmˇern´ ymi daty (pˇr´ıkladem m˚ uˇze b´ yt v´ yˇse zm´ınˇen´ y v´ıcerozmˇern´ y ˇsum), pˇredvedeme si zde i postup, jak s tˇemito daty jednotnˇe pracovat. V´ıcerozmˇern´ a data budeme reprezentovat jednorozmˇern´ ym seznamem (polem) prvk˚ u. Zp˚ usob uspoˇr´ ad´ an´ı prvk˚ u v´ıcerozmˇern´ ych dat do jednorozmˇern´eho seznamu je uk´az´an na obr´azku 3.3, kde je pˇredvedeno uspoˇr´ad´an´ı trojrozmˇern´ ych dat. Index do d rozmˇern´eho pole I = (i1 , i2 , . . . , id ) se skl´ ad´ a z d sloˇzek (ˇc´ısel) in , z nichˇz kaˇzd´e indexuje jinou dimenzi (sloˇzka i1 nejniˇzˇs´ı a sloˇzka id nejvyˇsˇs´ı). Rozmˇery (v´ yˇska, ˇs´ıˇrka, ...) dat oznaˇcme r = (r1 , r2 , . . . , rd ). Pˇrepoˇcet na index J do jednorozmˇern´eho pole je d´an vztahem: ! d k−1 X Y J = i1 + i2 · r1 + i3 · r1 r2 + . . . = ik rh (3.1) k=1
h=1
Vztah 3.1 m˚ uˇzeme zefektivnit a pˇrev´est na rekurentn´ı vztah: J1 = id Jn = Jn−1 · rd−n+1 + id−n+1 J
= Jd
60 61 62 63 44 45 46 47 56 57 58 59 28 29 30 31 40 41 42 43 12 13 14 53 54 55 5215 24 25 26 27 36 37 38 39 8 9 10 4811 49 50 51 20 21 22 23 32 33 34 35 4 5 6 7 16 17 18 19 0 1 2 3 x z
y
Obr´ azek 3.3: Uspoˇr´ad´an´ı 3D dat
3.4
Voron´ eho diagram
Voron´eho diagram popsan´ y v [1] je zp˚ usob dekompozice metrick´eho prostoru. Dekompozice je urˇcena vzd´ alenostmi k dan´e diskr´etn´ı mnoˇzinˇe objekt˚ u v prostoru, napˇr´ıklad diskr´etn´ı mnoˇzinou bod˚ u. V lev´e ˇc´ asti obr´ azku 3.4 m˚ uˇzeme vidˇet pˇr´ıklad rozdˇelen´ı dvourozmˇern´eho prostoru. Pro rozdˇelen´ı byla pouˇzita mnoˇzina n´ahodn´ ych bod˚ u (reprezentov´any ˇcern´ ymi teˇckami). Jednotliv´e barevn´e oblasti patˇr´ı k dan´emu ˇcern´emu bodu, kter´ y se v nich nach´ az´ı. Vˇsechny body z jedn´e barevn´e oblasti maj´ı spoleˇcnou vlastnost: vzd´alenost k ˇcern´emu bodu leˇz´ıc´ı v t´eto oblasti je menˇs´ı neˇz vzd´alenost ke vˇsem ostatn´ım ˇcern´ ym bod˚ u. Matematicky si m˚ uˇzeme, pro naˇse potˇreby, Voron´eho diagramy popsat n´asledovnˇe: mˇejme metrick´ y prostor (M, ρ) dimenze d, kter´ y reprezentuje vˇsechny body Voron´eho diagramu. Zobrazen´ı ρ : M × M → R je v naˇsem pˇr´ıpadˇe Eulerova vzd´alenost. D´ale mˇejme mnoˇzinu
11
index˚ u K a body Pk ∈ M, k ∈ K. Oblast (nebo buˇ nka) Voron´eho diagramu, kter´a je asociov´ana k bodu Pk oznaˇcme mnoˇzinou Rk . Pak jsou body v jedn´e mnoˇzinˇe d´any vztahem Rk = {x ∈ M |∀i ∈ K \ {k} : ρ(x, Pk ) ≤ ρ(x, Pi )}. Poˇcet bunˇek diagramu je |K|. Vyuˇzit´ı Voron´eho diagramu m˚ uˇze b´ yt napˇr´ıklad v textur´ach nebo pˇri generov´an´ı geometrie. Voron´eho diagramy dˇel´ı prostor na buˇ nky, proto poskytuj´ı dobr´ y z´aklad k bunˇeˇcn´ ym textur´am. Pˇr´ıkladem m˚ uˇze b´ yt textura dlaˇzby nebo textura vysuˇsen´e p˚ udy. Aby se s diagramem dobˇre pracovalo je vhodn´e jej pˇrev´est na normalizovan´e vzd´alenostn´ı. Vzd´alenostn´ı pole m˚ uˇzeme vidˇet v prav´e ˇc´asti obr´azku 3.4. Kaˇzd´ y prvek pole (pixel textury) si m´ısto pˇr´ısluˇsnosti do dan´e oblasti nese informaci o normalizovan´e vzd´alenosti ke stˇredu oblasti do kter´e patˇr´ı. Pro v´ ypoˇcet vzd´alenosti pouˇzijeme Euler˚ uv v´ ypoˇcet vzd´alenosti pro dimenzi prostoru d: v u d uX ρ(x, y) = t (xk − yk )2 (3.2) k=1
Obr´ azek 3.4: Vlevo: Voron´eho diagram, Vpravo: vzd´alenostn´ı pole.
3.4.1
Navazov´ an´ı
Navazov´ an´ı Voron´eho diagramu a tedy i vzd´alenostn´ıho pole, kter´e je pops´ano v [14] je d˚ uleˇzit´ a vlastnost. Aby se dala textura vytvoˇren´a na z´akladˇe vzd´alenostn´ıho pole pouˇz´ıt opakovanˇe vedle sebe, je nutn´e zajistit navazov´an´ı. Navazov´an´ı lze u vzd´alenostn´ıho pole zajistit u ´pravou v´ ypoˇctu vzd´ alenosti. Oznaˇcme d dimenz´ı prostoru. Bod v prostoru x = (x1 , x2 , . . . , xd ). Rozmˇery pole (v´ yˇska, ˇs´ıˇrka, ...) oznaˇcme r = (r1 , r2 , . . . , rd ). Pˇredpokl´adejme, ˇze vˇsechny body vzd´ alenostn´ıho pole maj´ı nez´aporn´e souˇradnice. Upraven´ y v´ ypoˇcet vzd´ alenosti 3.2, kter´ y respektuje navazov´an´ı, je: v u d uX 0 min(|xk − yk |, rk − |xk − yk |)2 (3.3) ρ (x, y) = t k=1
12
Funkce min vrac´ı minimum ze dvou hodnot. Jak je z upraven´eho vypoˇctu patrn´e, absolutn´ı velikost d´ılˇc´ıho rozd´ılu |xk − yk | nem˚ uˇze b´ yt vˇetˇs´ı neˇz rk /2. V pˇr´ıpadˇe, kdy je |xk − yk | > rk /2 se pouˇzije pro v´ ypoˇcet bod, kter´ y leˇz´ı v sousedn´ım poli. Sousedn´ı pole je totoˇzn´e, jen je posunut´e o rk . N´ azornˇe je to vidˇet na obr´azku 3.5.
posunuté pole
původní pole
A'
A
a'
a
X
B
b
Obr´azek 3.5: V´ ypoˇcet vzd´ alenosti. Poˇc´ıt´ame vzd´alenost k bodu X. Vzd´alenost ke stˇredu buˇ nky A v neopakuj´ıc´ım poli je a = |XA|. Buˇ nka, kter´a je nejbl´ıˇze k bodu X v neopakuj´ıc´ım poli je B (se vzd´ alenost´ı b = |XB|, b < a). V opakuj´ıc´ım poli je nejbl´ıˇze bodu X stˇred buˇ nky A0 , kter´ y je totoˇzn´ y s A jen leˇz´ı v posunut´em poli. Vypoˇc´ıtan´a vzd´alenost je tedy a0 = |XA0 |.
3.4.2
Optimalizace
V´ ypoˇcet vzd´ alenostn´ıho pole je ˇcasovˇe pomˇernˇe n´aroˇcn´a z´aleˇzitost. Pro pole ˇs´ıˇrky w a v´ yˇsky h a poˇctu bunˇek b je potˇreba prov´est w · h · b v´ ypoˇct˚ u vzd´alenost´ı abychom zjistili nejmenˇs´ı vzd´alenost bod˚ u ke stˇredu bunˇek. To znamen´a, z kaˇzd´eho bodu pole spoˇc´ıtat vzd´alenost ke vˇsem stˇred˚ um bunˇek a vybrat tu nejmenˇs´ı. Kdybychom pro vˇsechny body vˇedˇeli, ke kter´e buˇ nce patˇr´ı bylo by potˇreba jen w · h v´ ypoˇct˚ u vzd´alenost´ı. Optimalizac´ı v´ ypoˇct˚ u se budeme snaˇzit tomuto poˇctu v´ ypoˇct˚ u vzd´alenost´ı pˇribl´ıˇzit. Zp˚ usob, jak toho dos´ ahnout je rozm´ıstit stˇredy bunˇek do bin´arn´ıho stromu a poˇc´ıtat vzd´alenosti jen k ˇc´ asti stromu. Bin´arn´ı strom m´a v kaˇzd´em uzlu dvojic´ı bod˚ u. Tato dvojice bod˚ u dˇel´ı prostor na dvˇe ˇc´ asti podle vzd´alenosti k nim. Vytvoˇrit strom je snadn´e. Nejprve se vytvoˇr´ı koˇrenov´ y uzel z prvn´ıch dvou stˇred˚ u bunˇek. Pot´e se do stromu postupnˇe pˇrid´avaj´ı dalˇs´ı stˇredy. Pokud je novˇe vkl´ adan´ y stˇred bl´ıˇze k prvn´ımu bodu uzlu, vloˇz´ı se do lev´eho podstromu. Pokud je bl´ıˇze druh´emu bodu uzlu, vloˇz´ı se do prav´eho podstromu. Pokud podstrom neexistuje, vytvoˇr´ı se nov´ y uzel z dvojice, kterou tvoˇr´ı novˇe vkl´adan´ y stˇred a prvn´ı nebo druh´ y bod rodiˇcovsk´eho uzlu. Postupn´a tvorba stromu je zn´azornˇena v lev´e ˇc´asti obr´ azku 3.6. V´ ysledn´ y bin´ arn´ı strom je pak v prav´e ˇc´asti obr´azku 3.6. B
B
B
B D
C
C A
A
A
AB
D E
C
AE
BC
A
CD
Obr´ azek 3.6: Vlevo: Postupn´e vkl´ad´an´ı bod˚ u do stromu. Vpravo: V´ ysledn´ y strom Kdyˇz m´ ame vytvoˇren´ y strom pro vˇsechny stˇredy bunˇek, je jeˇstˇe potˇreba spoˇc´ıtat k obˇema bod˚ um kaˇzd´eho uzlu stromu vzd´alenosti k nejvzd´alenˇejˇs´ım potomk˚ um a ty do dan´eho
13
uzlu uloˇzit. Vzd´ alenosti jednotliv´ ych bod˚ u uzl˚ u jsou zn´azornˇeny kruˇznicemi v lev´e ˇc´asti obr´azku 3.7. Nalezen´ı nejkratˇs´ı vzd´ alenosti pro kaˇzd´ y bod pole pak spoˇc´ıv´a ve zvolen´ı polomˇeru kolem zkouman´eho bodu. V prvn´ım kroku zvol´ıme pomˇer jako vzd´alenost ke stˇredu n´ahodn´e buˇ nky, prav´ a ˇc´ ast obr´ azku 3.7. V dalˇs´ıch kroc´ıch budeme volit polomˇer ze vzd´alenosti ke stˇredu posledn´ı nejbl´ıˇze nalezen´e buˇ nky. Pokud se kruˇznice kolem aktu´alnˇe zkouman´eho bodu nepˇrekr´ yv´ a s danou kruˇznic´ı v aktu´aln´ım uzlu, nen´ı tˇreba prohled´avat jeho podstrom. Pokud ano, prohled´ a se podstrom uzlu. Pokud je vzd´alenost k bodu uzlu menˇs´ı neˇz aktu´aln´ı polomˇer kolem zkouman´eho bodu, zmenˇs´ıme polomˇer na tuto vzd´alenost. T´ım se n´ am neust´ale zmenˇsuje polomˇer kolem zkouman´eho bodu, neˇz nalezneme hledanou vzd´alenost.
B
B
D
D E
C
E
C
A
A
Obr´azek 3.7: Vlevo: Kruˇznice kolem uzl˚ u. Vpravo: Kruˇznice kolem zkouman´eho bodu s polomˇerem k n´ ahodnˇe vybran´e buˇ nce D.
3.5
Generov´ an´ı textur
Textura slouˇz´ı pro detailn´ı popis struktury povrchu. Vyskytuj´ı se nejˇcastˇeji ve formˇe dvojrozmˇern´ ych obr´ azk˚ u. M˚ uˇzeme se ale setkat i s jednorozmˇern´ ymi, trojrozmˇern´ ymi nebo dokonce ˇctyˇrrozmˇern´ ymi texturami. Trojrozmˇern´e textury slouˇz´ı pro popis objemu a ˇctyˇrrozmˇern´e pro popis objemu mˇen´ıc´ıho se v ˇcase (napˇr´ıklad plameny ohnˇe, kouˇr). Textury si d´ıky jejich velikosti nem˚ uˇzeme do programu uloˇzit, a tak je mus´ıme generovat. Vytvoˇren´ı textury b´ yv´ a obvykle ˇcasovˇe n´ aroˇcn´e, nebot’ obsahuj´ı velk´e mnoˇzstv´ı dat. Z´akladem pro vytvoˇren´ı textur v t´eto prac´ı je ˇsum, kter´ y je popsan´ y v ˇc´asti 3.1 a vzd´alenostn´ıho pole vytvoˇren´e z Voron´eho diagramu, kter´ y je popsan´ y v ˇc´asti 3.4. Tyto dvˇe metody n´am produkuj´ı d rozmˇern´e pole. Vˇsechny hodnoty tˇechto pol´ı jsou v rozsahu h0, 1i. Pˇr´ıklad ˇsumu m˚ uˇzeme vidˇet v prav´e ˇc´ asti obr´ azku 3.1 a pˇr´ıklad vzd´alenostn´ıho pole v prav´e ˇc´asti obr´azku 3.4. Nejd˚ uleˇzitˇejˇs´ım vstupem algoritmu pro vytvoˇren´ı ˇsumu je faktor vyhlazen´ı, kter´ y n´ am urˇcuje pomˇer n´ızk´ ych frekvenc´ı a vysok´ ych frekvenc´ı ve v´ ysledn´em ˇsumu. U Voron´eho diagramu je nejd˚ uleˇzitˇejˇs´ım vstupem rozm´ıstˇen´ı a poˇcet stˇred˚ u bunˇek. Nicm´enˇe tyto moˇznosti n´am neposkytuj´ı dostateˇcnou variabilitu textur. Proto je vhodn´e pole hodnot produkovan´e
14
tˇemito postupy jeˇstˇe d´ ale upravit. Upravit takov´e pole m˚ uˇzeme prost´ ym obarven´ım pomoc´ı barevn´eho pˇrechodu, glob´ aln´ı transformac´ı jako je napˇr´ıklad vyhlazen´ı, lok´aln´ı transformac´ı a sloˇzen´ım nˇekolika vstup˚ u. Jednotliv´e u ´pravn´e operace si pop´ıˇseme v dalˇs´ıch ˇc´astech pr´ace.
3.5.1
Barevn´ e pˇ rechody
Pˇr´ıklad barevn´eho pˇrechodu je zobrazen na obr´azku 3.8. Barevn´ y pˇrechod (nebo t´eˇz gradient) jsou v podstatˇe tˇri funkce R(x), G(x), B(x) (ˇctyˇri v pˇr´ıpadˇe pˇr´ıtomnosti alfa kan´alu). Tyto funkce jsou definovan´e na intervalu h0, 1i. Jejich vstup je hodnota celkov´e intenzity barvy a v´ ystupem intenzita ˇcerven´e respektive zelen´e respektive modr´e barvy. Intenzity jsou takt´eˇz v rozsahu h0, 1i. Barevn´e pˇrechody m˚ uˇzeme v´ yhodnˇe pouˇz´ıt na obarven´ı obr´ azk˚ u v odst´ınech ˇsed´e. Zn´azornˇen´e to m˚ uˇzeme vidˇet na obr´azku 3.9. Pro uloˇzen´ı barevn´eho pˇrechodu staˇc´ı uloˇzit jen kontroln´ı barvy a hodnoty mezi nimi interpolovat. Napˇr´ıklad u barevn´eho pˇrechodu na Obr´azek 3.8 staˇc´ı uloˇzit pouze barvy: tmavˇe modr´ a, svˇetle modr´ a, ˇzlut´ a, svˇetle zelen´a, tmavˇe zelen´a, ˇsed´a a b´ıl´a (v poˇrad´ı zleva doprava). T´ımto m˚ uˇzeme zredukovat pamˇet’ovou n´aroˇcnost. Dalˇs´ı moˇznost´ı je vytvoˇrit algoritmus na generov´ an´ı barevn´ ych pˇrechod˚ u. Mus´ıme vˇsak zv´aˇzit, jestli potˇrebujeme tolik r˚ uzn´ ych barevn´ ych pˇrechod˚ u, ˇze se n´ am je oplat´ı generovat.
Obr´ azek 3.8: Barevn´ y pˇrechod, kter´ y je moˇzn´e vyuˇz´ıt na obarven´ı v´ yˇskov´e mapy.
Obr´azek 3.9: Vlevo: vstupn´ı obr´ azek v odst´ınech ˇsed´e. Vpravo: obarven´ y obr´azek z leva barevn´ ym pˇrechodem z obr´ azku 3.8
15
3.5.2
Glob´ aln´ı transformace
Glob´aln´ı transformac´ı budeme v textu rozumˇet operaci, kter´a transformuje vstupn´ı d rozmˇern´e pole hodnot na v´ ystupn´ı d rozmˇern´e pole hodnot. Pro v´ ypoˇcet jednoho prvku v´ ystupn´ıho pole s indexem I budeme potˇrebovat hodnoty okol´ı vstupn´ıho pole kolem indexu I. Jedn´ a se tedy o d rozmˇernou konvoluci s d rozmˇern´ ym konvoluˇcn´ım j´adrem. Pokud si vytvoˇr´ıme obecnou konvoluci, m˚ uˇzeme ji pouˇz´ıt pro ˇradu transformac´ı. Pˇr´ıkladem tˇechto transformac´ı je vyhlazen´ı a detekce hran. Konvoluˇcn´ı j´adro pro vyhlazen´ı obsahuje hodnoty, kter´e jsou vˇsechny stejn´e a jejichˇz souˇcet je roven jedn´e.
3.5.3
Lok´ aln´ı transformace
Lok´aln´ı transformac´ı budeme v textu rozumˇet (podobnˇe jako glob´aln´ı transformace) operaci, kter´ a transformuje vstupn´ı pole na v´ ystupn´ı pole hodnot. Pole maj´ı rozmˇer d. Pro v´ ypoˇcet jednoho prvku v´ ystupn´ıho pole s indexem I budeme potˇrebovat nˇekolik hodnot ze vstupn´ıho pole. V´ ybˇer tˇechto hodnot z´avis´ı na transformaci. Moˇznosti lok´aln´ı transformace jsou velk´e. Vˇse z´ avis´ı na transformaˇcn´ı funkci. D˚ uleˇzit´e je, aby n´am transformace zachov´ avala opakov´ an´ı. Kdykoliv si transformace zaˇz´ad´a hodnotu pole na souˇradnic´ıch, kter´e leˇz´ı mimo rozsah pole, budeme muset souˇradnice pˇrepoˇc´ıtat. Souˇradnice bodu pole je I = (i1 , i2 , . . . , id ) a velikost pole (v´ yˇska, ˇs´ıˇrka, ...) je r = (r1 , r2 , . . . , rd ). Pokud je sloˇzka souˇradnic in < 0 ∨ in ≥ rn (hodnoty pole indexujeme od nuly), je potˇreba ji pˇrepoˇc´ıtat podle vztahu: i0n = ((in %rn ) + rn )%rn . V lev´e ˇc´ asti obr´ azku 3.10 m˚ uˇzeme vidˇet velmi jednoduchou transformaci. K v´ ypoˇctu v´ ystupn´ı hodnoty na souˇradnic´ıch I = (i1 , i2 ) jsou zapotˇreb´ı dvˇe hodnoty vstupn´ıho pole. Prvn´ı hodnota vstupn´ıho pole, oznaˇcme ji a , je na totoˇzn´ ych souˇradnic´ıch. Druh´a hodnota, oznaˇcme ji b, je na souˇradnic´ıch (i1 + r · cos(2πa), i2 + r · sin(2πa)). Hodnota r ud´ av´ a polomˇer. Hodnota b je v´ ysledn´ a hodnota v´ ystupn´ıho pole na souˇradnic´ıch I. M˚ uˇzeme vidˇet, ˇze hodnota a ud´ av´ a normalizovan´ yu ´hel. Spolu s polomˇerem r vytv´aˇr´ı vektor. Kdyˇz tento vektor pˇriˇcteme k p˚ uvodn´ım souˇradnic´ım, m´ame souˇradnice bodu, jehoˇz hodnota je pouˇzita pro v´ ystup – tedy hodnotu b. Na dalˇs´ıch obr´azc´ıch je postup transformace obdobn´ y. V prav´e ˇc´asti obr´ azku 3.10 je v´ yˇse popsan´ y postup opakov´an nˇekolikr´at. M´ısto abychom pouˇzili dva body ze vstupn´ıho pole, pouˇzijeme jich nˇekolik. Posledn´ı bod ud´av´a hodnotu v´ ystupu. Dalˇs´ı pˇr´ıklady lok´ aln´ıch transformac´ı m˚ uˇzeme vidˇet na obr´azku 3.12
3.5.4
Skl´ ad´ an´ı operac´ı
Nyn´ı, kdyˇz m´ ame z´ aklad vˇsech textur v podobˇe distanˇcn´ıho pole a ˇsumu, lok´aln´ı a glob´aln´ı transformace a barevn´e pˇrechody, m˚ uˇzeme se pustit do vytv´aˇren´ı textur. Vytvoˇren´ı jedn´e textury si m˚ uˇzeme pˇredstavit jako strom. Uzly stromu pˇredstavuj´ı operaci. Operace uloˇzena v uzlu bere sv´e vstupy ze sv´ ych potomk˚ u a v´ ystup pos´ıl´a rodiˇci. V listech tohoto stromu se nach´az´ı bud’ distanˇcn´ı pole nebo ˇsum. V uzlech stromu je lok´aln´ı nebo glob´aln´ı transformace nebo jedna z n´ asleduj´ıc´ıch operac´ı: • Souˇcet hodnot vstup˚ u. • Rozd´ıl hodnot vstup˚ u. • N´ asoben´ı hodnot vstup˚ u. • Souˇcet hodnot vstup˚ u s ohledem na alfa kan´al.
16
Obr´ azek 3.10: Lok´aln´ı transformace • Kompozice vstup˚ u do v´ıcekan´alov´e textury. Pˇr´ıklad textury sloˇzen´e pomoc´ı nˇekolika operac´ı m˚ uˇzeme vidˇet na obr´azku 3.11
Obr´ azek 3.11: Sestaven´a textura
3.6
Generov´ an´ı geometrie
Pro generov´ an´ı geometrie m˚ uˇzeme pouˇz´ıt nˇekolik postup˚ u. V pr´aci budeme pouˇz´ıvat algoritmus, kter´ y pˇrev´ ad´ı objemovou reprezentaci tˇelesa na povrchovou. Pro vygenerov´ an´ı objemov´e reprezentace m˚ uˇzeme pouˇz´ıt ˇsum nebo vzd´alenostn´ı pole. M˚ uˇzeme pouˇz´ıt tak´e
17
Obr´ azek 3.12: Pˇr´ıklady lok´ aln´ıch transformac´ı aplikovan´ ych na vzd´alenostn´ı pole. transformace (lok´ aln´ı, glob´ aln´ı), kter´e n´am objemovou reprezentaci uprav´ı. Pro pˇrevod objemov´e reprezentace budeme pouˇz´ıvat algoritmus Marching tetrahedra.
3.6.1
Pˇ revod do povrchov´ e reprezentace
V dneˇsn´ı poˇc´ıtaˇcov´e grafice se nejˇcastˇeji setk´ame s povrchovou reprezentac´ı tˇeles. D˚ uvod je ten, ˇze souˇcasn´ y hardware je pro to optimalizovan´ y. Obˇcas je vˇsak vhodn´e specifikovat objekty objemem nebo pomoc´ı implicitn´ıch ploch. Pˇr´ıkladem je trojrozmˇern´ y ˇsum, reprezentuj´ıc´ı hustotu objektu v dan´em m´ıstˇe prostoru. Proto potˇrebujeme takto reprezentovan´e objekty pˇrev´est do povrchov´e reprezentace. Existuje nˇekolik algoritm˚ u pro pˇrevod. Jedn´ım z nejzn´ amˇejˇs´ıch je Marching cubes. Dalˇs´ı pouˇz´ıvan´ y algoritmus je Marching tetrahedra.
3.6.2
Marching cubes
Marching cubes algoritmus pops´an v [9] je v ˇceˇstinˇe algoritmus pochoduj´ıc´ıch krychl´ı. Krychle stejn´e velikosti jsou pravidelnˇe rozm´ıstˇeny v prostoru, kde se nach´az´ı objekt, kter´ y chceme pˇrev´est. Abychom mohli algoritmus pouˇz´ıt, mus´ıme m´ıt k dispozici funkci: f : R3 → {0, 1}. Funkce zjist´ı, zda bod na dan´ ych souˇradnic´ıch leˇz´ı uvnitˇr objektu (funkce vrac´ı 1) nebo vnˇe (funkce vrac´ı 0). Pro jednu krychli vyhodnot´ıme tuto funkci pro vˇsechny jej´ı rohy. Z´ısk´ ame jednu z 28 moˇzn´ ych ohodnocen´ı roh˚ u. Existuje patn´act unik´atn´ıch ohodnocen´ı (konfigurac´ı), kter´e m˚ uˇzeme transformacemi pˇrev´est na vˇsechny ostatn´ı. Na hran´ ach krychle se vyskytuje vrchol geometrie (troj´ uheln´ıku) v pˇr´ıpadˇe, kdy ohodnocen´ı roh˚ u krychle, kter´e hrana sd´ıl´ı, nen´ı stejn´e (na jednom rohu je 0 a na druh´em 1). Vznikne tak nˇekolik hran, na kter´ ych leˇz´ı vrcholy troj´ uheln´ık˚ u. Vhodn´ ym propojen´ım vrchol˚ u vznikne troj´ uheln´ıkov´ a s´ıt’ pro jednu konfiguraci krychle. Patn´act troj´ uheln´ıkov´ ych s´ıt´ı pro patn´ act unik´ atn´ıch konfigurac´ı m˚ uˇzeme vidˇet na obr´azku 3.13. Spojen´ım vˇsech
18
Obr´ azek 3.13: Unik´atn´ı konfigurace, obr´azek pˇrevzat z [2] troj´ uheln´ıkov´ ych s´ıt´ı ze vˇsech krychl´ı rozm´ıstˇen´ ych v prostoru vznikne v´ ysledn´a s´ıt’. Marching cubes algoritmus m´a jednu nev´ yhodu. Nˇekter´e konfigurace krychl´ı spolu nejsou kompatibiln´ı podle [9]. Pokud bychom nekompatibiln´ı stavy neˇreˇsili, ve v´ ysledn´e troju ´heln´ıkov´e s´ıti by vznikly d´ıry. Obsluˇzn´ y k´od by n´am zbyteˇcnˇe zvˇetˇsil aplikaci, a tak nen´ı algoritmus Marching cubes v t´eto podobˇe v pr´aci pouˇzit.
3.6.3
Marching tetrahedra
Marching tetrahedra algoritmus (kr´aˇcej´ıc´ı ˇctyˇrstˇen) uˇz netrp´ı probl´emem nekompatibiln´ıch konfigurac´ı jako Marching cubes. Nicm´enˇe produkuje vˇetˇs´ı mnoˇzstv´ı geometrie. Stejnˇe jako u pˇredch´ azej´ıc´ıho algoritmu potˇrebujeme funkci, kter´a rozhodne, zda dan´ y bod leˇz´ı uvnitˇr ˇ nebo vnˇe objektu. Ctyˇrstˇen m´ a ˇctyˇri rohy, proto je celkov´ y poˇcet konfigurac´ı roven 24 . Maxim´ aln´ı poˇcet troj´ uheln´ık˚ u v jedn´e konfiguraci je 2. Vzhledem k tˇemto mal´ ym ˇc´ısl˚ um si m˚ uˇzeme jednotliv´e konfigurace vhodnˇe uloˇzit do konstantn´ıch dat programu. Probl´em tohoto algoritmu spoˇc´ıv´a v rozm´ıstˇen´ı ˇctyˇrstˇen˚ u v prostoru s objektem. Pokud bychom pouˇzili ˇctyˇrstˇen, kter´ y m´a vˇsechny hrany stejnˇe dlouh´e, rozm´ıstˇen´ı v prostoru by nebylo u ´plnˇe snadn´e (tak jako u krychle u pˇredeˇsl´eho algoritmu). Algoritmus na rozm´ıstˇen´ı ˇctyˇrstˇenu by n´ am zbyteˇcnˇe obsadil m´ısto v programu. Proto rozm´ıst´ıme ˇsest ˇctyˇrstˇen˚ u do krychle. Tuto krychli budeme pravidelnˇe rozm´ıst’ovat do prostoru stejnˇe jako u algoritmu Marching cubes. Rozm´ıstˇen´ı ˇctyˇrstˇen˚ u v krychli m˚ uˇzeme vidˇet na obr´azku 3.14. Pro vrcholy krychle spoˇcteme, zda leˇz´ı uvnitˇr ˇci vnˇe objektu. Pot´e pro vˇsech ˇsest ˇctyˇrstˇen˚ u vybereme z tabulky spr´ avnou troj´ uheln´ıkovou s´ıt’.
3.6.4
Vyhlazen´ı
uheln´ık˚ u pˇr´ımo doPokud bychom u algoritm˚ u uveden´ ych v´ yˇse um´ıst’ovali vrcholy troj´ prostˇred hrany na kter´e leˇz´ı, v´ ysledn´a troj´ uheln´ıkov´a s´ıt’ by byla hranat´a. Hranatou troju ´heln´ıkovou s´ıt’ m˚ uˇzeme vidˇet v lev´e ˇc´asti obr´azku 3.15. Vhodn´ ym posunut´ım vrchol˚ u na
19
Obr´ azek 3.14: Rozm´ıstˇen´ı ˇctyˇrstˇen˚ u do krychle hran´ach m˚ uˇzeme dos´ ahnout vyhlazen´ı (prav´a ˇc´ast obr´azku 3.15. Body na hran´ach m˚ uˇzeme posunou podle toho, jak daleko jsou konce hrany od pˇredpokl´adan´eho povrchu. Pokud pouˇzijeme objemovou reprezentaci (napˇr´ıklad ˇsum), hodnota v prostoru n´ am urˇcuje hustotu. Hodnotu hustoty budeme br´at v rozsahu h0, 1i. Kdyˇz hodnota hustoty na dan´ ych souˇradnic´ıch pˇrekroˇc´ı hodnotu prahu T , nach´az´ı se v m´ıstech souˇradnic tˇeleso. Hustotu v bodech na souˇradnic´ıch Sa , Sb na konc´ıch hrany oznaˇcme Ha , Hb . Z´aroveˇ n plat´ı podm´ınka, ˇze pr´ avˇe jeden bod konce hrany leˇz´ı v tˇelese:(Ha ≥ T ∧ Hb < T ) ∨ (Ha < T ∧ Hb ≥ T ). Souˇradnice vrcholu na hranˇe jsou d´any vztahem: (1 − t) · Sa + t · Sb . Parametr a t je vypoˇc´ıt´ an podle vztahu: t = HTb−H −Ha .
Obr´ azek 3.15: Marching tetrahedra. Vlevo: bez vyhlazen´ı. Vpravo: s vyhlazen´ım.
3.6.5
Zmenˇ sen´ı poˇ ctu vrchol˚ u
V´ yˇse uveden´e algoritmy produkuj´ı mnoho geometrie. Pokud budeme data ukl´adat do spoleˇcn´eho pole, nebudeme m´ıt informaci o tom, kter´ y vrchol je sd´ılen v´ıcero troj´ uheln´ıky. Dan´ y bod na hranˇe jedn´e krychle je vygenerov´an i jinou sousedn´ı krychl´ı a je uloˇzen do spoleˇcn´eho pole nˇekolikr´ at. Nav´ıc toto zp˚ usobuje probl´em pˇri v´ ypoˇctu norm´al. Proto je vhodn´e vrcholy, kter´e jsou duplicitn´ı uloˇzit do pole jen jednou. Toto lze zajistit jednoduˇse. Budeme vrcholy do spoleˇcn´eho pole vkl´adat postupnˇe. Vˇzdy porovn´ame souˇradnice pr´ avˇe vkl´adan´eho vrcholu se vˇsemi vrcholy, kter´e jsou jiˇz uloˇzeny.
20
Toto ˇreˇsen´ı m´ a nev´ yhodu a tou je rychlost. Pro velk´e mnoˇzstv´ı vrchol˚ u je potˇreba prov´est velk´e mnoˇzstv´ı porovn´ an´ı. Proto budeme vrcholy ukl´adat do stromu. Pokud budeme cht´ıt zjistit, zda byl jiˇz dan´ y bod uloˇzen, staˇc´ı prohledat jen malou ˇc´ast stromu. Toto algoritmus urychl´ı.
3.6.6
Norm´ aly
Norm´aly se v poˇc´ıtaˇcov´e grafice pouˇz´ıvaj´ı pro st´ınov´an´ı objekt˚ u a pr´aci se svˇetlem. M˚ uˇzeme si ukl´adat norm´ alu ke kaˇzd´e ploˇsce. Norm´ala je v tomto pˇr´ıpadˇe stejn´a pro vˇsechny body ploˇsky (polygonu). T´ımto dos´ ahneme jednolit´eho st´ınov´an´ı. Jednolit´e st´ınov´an´ı m˚ uˇzeme pouˇz´ıt pro ploch´e objekty jako jsou stˇeny, podlaha nebo napˇr´ıklad bedny. Dalˇs´ı moˇznost´ı je ukl´adat si norm´ alu ke kaˇzd´emu vrcholu polygonu. Pot´e budeme osvˇetlen´ı poˇc´ıtat pro vˇsechny vrcholy polygonu a uvnitˇr osvˇetlen´ı interpolovat. Vizu´alnˇe lepˇs´ı v´ ysledky ale dostaneme, pokud budeme interpolovat norm´aly. Pro kaˇzd´ y bod polygonu tak budeme m´ıt k dispozici interpolovanou norm´ alu, kterou pouˇzijeme pro v´ ypoˇcet osvˇetlen´ı. D´ıky interpolaci norm´aly nepotˇrebujeme tolik polygon˚ u (troj´ uheln´ık˚ u) pro reprezentaci hladk´eho objektu. V´ ypoˇcet norm´ aly pro vrchol, kter´ y je sd´ılen k troj´ uheln´ıky s norm´alami a obsahy ni , si , i ∈ {1, . . . , k} je d´ an vztahem: ! k X n = nor ni · s i (3.4) i=1
Funkce nor normalizuje vstupn´ı vektor. M˚ uˇzeme se obej´ıt bez v´ ypoˇctu obsahu troj´ uheln´ık˚ u a vztah 3.4 zjednoduˇsit na: ! k X ni (3.5) n = nor i=1
Probl´em nastane, pokud jsou v objektu velmi u ´zk´e troj´ uheln´ıky. U velmi u ´zk´ ych troju ´heln´ık˚ u je hlavn´ı ˇc´ ast vyhlazen´ı norm´al zastoupena v mal´e oblasti. Povrch objektu je sice vyst´ınov´ an plynule, ale z vˇetˇs´ı vzd´alenosti se jiˇz tak nejev´ı. V lev´e ˇc´asti obr´azku 3.16 m˚ uˇzeme pozorovat hranice troj´ uheln´ık˚ u, kter´e soused´ı s velmi u ´zk´ ymi troj´ uheln´ıky. Algoritmus marching tetrahedra bohuˇzel produkuje tyto u ´zk´e troj´ uheln´ıky pokud je zapnuto vyhlazov´an´ı. Bud’ budeme m´ıt stejnˇe velk´e troj´ uheln´ıky a vizu´alnˇe hladkou interpolaci norm´ al, ˇ ale hranat´ y objekt nebo hladk´ y objekt a viditeln´e hrany troj´ uheln´ık˚ u. Reˇsen´ı m˚ uˇzeme vidˇet v algoritmu, kter´ y by pro dan´ y vrchol nepoˇc´ıtal norm´aly jen z troj´ uheln´ık˚ u, kter´e tento vrchol sd´ıl´ı, ale z vˇetˇs´ıho okol´ı. Implementov´an´ım tohoto ˇreˇsen´ı bychom ale zbyteˇcnˇe zabrali m´ısto v aplikaci. Elegantn´ı ˇreˇsen´ı spoˇc´ıv´ a v pouˇzit´ı gradientu (smˇeru r˚ ustu) trojrozmˇern´eho ˇsumu, kter´ y jsme pouˇzili pro vygenerov´ an´ı geometrie, postup je bl´ıˇze pops´an v [5]. Norm´aly reprezentovan´e pomoc´ı gradientu m˚ uˇzeme vidˇet v prav´e ˇc´asti obr´azku 3.16. Gradient trojrozmˇern´eho ˇsumu si m˚ uˇzeme uloˇzit do trojrozmˇern´e textury a vyuˇz´ıt jej tak´e pro poˇc´ıt´an´ı koliz´ı. V´ ypoˇcet gradientu v bodˇe o souˇradnic´ıch I = (i1 , i2 , i3 ) z´ısk´ame pomoc´ı vztahu: g = (h(I + x) − h(I − x), h(I + y) − h(I − y), h(I + z) − h(I − z))
(3.6)
Ve vztahu 3.6 reprezentuje x respektive y respektive z trojici (1, 0, 0) respektive (0, 1, 0) respektive (0, 0, 1). Funkce h(I) vrac´ı hodnotu ˇsumu na souˇradnic´ıch I. V´ ypoˇcet norm´aly z gradientu je jednoduch´ y staˇc´ı gradient znormalizovat.
21
Obr´azek 3.16: Zobrazen´ı norm´ al. Vlevo: norm´aly pro vrcholy troj´ uheln´ık˚ u. Vpravo: norm´ aly reprezentovan´e gradientem.
3.7
Bump mapping
Bump mapping je metoda pro zv´ yˇsen´ı detailu povrchu. V sekci norm´aly 3.6.6 jsme si popsali interpolaci norm´ aly v bodˇe troj´ uheln´ıku. T´ımto pˇr´ıstupem z´ısk´ame hladk´ y povrch. Zv´ yˇsen´ı u ´rovnˇe detailu bychom mohli dos´ ahnout zvˇetˇsen´ım poˇctu polygon˚ u. Pokud bychom ale chtˇeli m´ıt vyˇsˇs´ı detaily uvnitˇr troj´ uheln´ıku, bez pˇrid´an´ı dalˇs´ıch troj´ uheln´ık˚ u, m˚ uˇzeme zvolit bump mapping. Bump mapping ovlivˇ nuje norm´alu v bodˇe troj´ uheln´ıku a t´ım i v´ ysledn´e st´ınov´an´ı. Pro ovlivˇ nov´ an´ı norm´ aly se pouˇz´ıv´a bump mapa. Bump mapa je textura, kter´ a m´ısto barvy nese informaci o norm´ale. Pokud bump mapu naneseme na troj´ uheln´ık a budeme pomoc´ı n´ı ovlivˇ novat interpolovanou norm´alu, z´ısk´ame vizu´alnˇe detailnˇejˇs´ı st´ınov´ an´ı. V´ ysledek bump mappingu je zn´azornˇen na obr´azku 3.17. Bump mapa je tˇr´ıkan´ alov´ a textura. M´ısto barev (r, g, b) obsahuje sloˇzky norm´aly (u, v, w). Bump mapu budeme vytv´ aˇret z textury tˇesnˇe pˇred obarven´ım. Texturu v odst´ınech ˇsed´e budeme br´ at jako v´ yˇskovou mapu a norm´ala v dan´em bodˇe je na n´ı kolm´a.
Obr´azek 3.17: Vlevo: St´ınov´ an´ı s vyhlazen´ım norm´al. Uprostˇred: st´ınov´an´ı s aplikovan´ ym ’ bump mappingem. Vpravo: troj´ uheln´ıkov´a s´ıt .
22
3.8
Texturov´ an´ı
Postup vytvoˇren´ı textur jsme si popsali v sekci 3.5. Nyn´ı nast´av´a ot´azka, jak texturu nan´est na povrch. Pokud pouˇzijeme trojrozmˇernou texturu je nanesen´ı jednoduch´e. Souˇradnice vrchol˚ u polygon˚ u jsou z´ aroveˇ n i souˇradnice do textury (texturovac´ı koordin´aty). Texturovac´ı koordin´ aty pro trojrozmˇernou texturu m˚ uˇzeme snadno transformovat pomoc´ı transformaˇcn´ı matice. Texturu m˚ uˇzeme roztahovat, ot´aˇcet a posouvat. Nav´ıc m˚ uˇzeme objekt, na kter´ y je nanesena trojrozmˇern´ a textura r˚ uznˇe deformovat, vytv´aˇret do nˇej d´ıry nebo pˇrid´avat polygony. Nemus´ıme se pˇritom starat o pˇrepoˇcet koordin´at. Nev´ yhoda trojrozmˇern´e textury spoˇc´ıv´a v jej´ı velikosti. Povrch objektu prob´ıh´a jen zlomkem celkov´eho objemu textury. Z velikosti plyne i doba na vygenerov´an´ı takov´e textury. Dalˇs´ı nev´ yhoda spoˇc´ıv´a v nesnadn´e konstrukci bump mapy. Povrch objektu m˚ uˇze bodem textury proch´azet r˚ uznˇe natoˇcen, proto bychom potˇrebovali pro kaˇzd´e natoˇcen´ı jinou bump mapu. U dvojrozmˇern´ ych textur je v´ ypoˇcet bump mapy jednoduˇs´ı. Dvojrozmˇern´e textury maj´ı pouze dvˇe sloˇzky texturovac´ıch koordin´ at, proto je nutn´e je vhodnˇe rozm´ıstit po povrchu objektu. Rozm´ıstˇen´ı texturovac´ıch koordin´ at ale nen´ı jednoduch´e. Obvykle b´ yvaj´ı rozm´ıst’ov´any ruˇcnˇe pomoc´ı grafika. Algoritmus pro rozm´ıstˇen´ı koordin´at na netrivi´aln´ı objekt by byl pˇr´ıliˇs sloˇzit´ y a zab´ıral by m´ısto. Proto budeme textury na trojrozmˇern´e objekty nan´aˇset jinak.
3.8.1
Triplan´ arn´ı texturov´ an´ı
Triplan´ arn´ı mapov´ an´ı textur popsan´e v [5] pouˇz´ıv´a pro obarven´ı objektu tˇri r˚ uzn´e textury. Textury jsou nan´ aˇsen´e pod´el tˇr´ı souˇradn´ ych osy (x, y, z). Pokud je norm´ala povrchu v dan´em bodˇe (x, y, z) napˇr´ıklad (1, 0, 0), pouˇzije se textura pro osu x. Souˇradnice pro tuto texturu budou pot´e (y, z). Pˇriˇcemˇz sloˇzka y pˇredstavuje u sloˇzku texturovac´ı koordin´aty (smˇer v ose x v textuˇre). Pro norm´ alu (0, 1, 0) se pouˇzije textura pro osu y. Texturovac´ı koordin´ aty budou v takov´em pˇr´ıpadˇe (u, v) = (x, z). Pokud norm´ala povrchu nen´ı rovnobˇeˇzn´a s jednou ze souˇradn´ ych os, pouˇzije se v´ıcero textur, kter´e se mezi sebou sm´ıchaj´ı. Uvaˇzujme bod povrchu objektu P = (x, y, z) s norm´alou N = (a, b, c) a tˇri textury Tx , Ty , Tz pro tˇri souˇradn´e osy. D´ ale uvaˇzujme funkci f : T × R2 → h0, 1i3 . Funkce f vrac´ı pro texturu T a souˇradnice reprezentovan´e dvojic´ı barvu. V´ ypoˇcet barvy je pak d´an n´asleduj´ıc´ım vztahem: C=
|a| |b| |c| · f (Tx , (y, z)) + · f (Ty , (x, z)) + · f (Tz , (x, y)) S S S
(3.7)
Ve vztahu 3.7 je S = |a| + |b| + |c| normalizace vah. Sloˇzky a, b, c norm´aly ud´avaj´ı v´ahy pro v´aˇzen´ y pr˚ umˇer. Triplan´ arn´ı texturov´ an´ı m˚ uˇzeme modifikovat. M´ısto abychom poˇz´ıvali tˇri textury pro tˇri souˇradn´e osy, m˚ uˇzeme pouˇz´ıt ˇsest a rozliˇsovat smˇer osy. Pro otexturov´an´ı jeskynˇe a pˇr´ıvodn´ıho tunelu ale zvol´ıme jin´ y postup. Pouˇzijeme tak´e tˇri textury, ale ne v souˇradn´ ych os´ach. Jednu texturu pouˇzijeme na stropy (kladn´a osa y). Dalˇs´ı na zem (z´aporn´a osa y). Posledn´ı textura je mapov´ ana na stˇeny. Vztah pro v´ ypoˇcet v´ ysledn´e barvy pro takto rozm´ıstˇen´e textury je obdobn´ y vztahu 3.7.
3.9
Skybox
Skybox je vzd´ alen´e okol´ı od sc´eny, kter´e nereprezentujeme pomoc´ı polygon˚ u, ale jen pomoc´ı obr´azk˚ u. Skybox m˚ uˇzeme pouˇz´ıt pro reprezentaci mrak˚ u, vzd´alen´ ych kraj˚ u nebo tˇreba hvˇezd ve vesm´ıru. Obvykle b´ yv´ a skybox ve formˇe krychle. Na vˇsechny stˇeny krychle je 23
nanesen jin´ y obr´ azek. Obr´ azky na sebe navazuj´ı a tvoˇr´ı tak dojem okol´ı. Pˇr´ıklad rozvinut´eho krychlov´eho skyboxu m˚ uˇzeme vidˇet na obr´azku: 3.18. Skybox m˚ uˇzeme vytvoˇrit fotoapar´ atem a programem na skl´ad´an´ı fotografi´ı. Staˇc´ı vyfotit okol´ı ve vˇsech smˇerech a fotografie n´ aslednˇe sloˇzit dohromady. V naˇsem pˇr´ıpadˇe si ale mus´ıme skybox vygenerovat. V pr´aci budeme pouˇz´ıvat dvˇe metody generov´an´ı skyboxu.
Obr´ azek 3.18: Skybox zobrazuj´ıc´ı dopoledn´ı oblohu Prvn´ı je obdobn´ a tvorbˇe skyboxu pomoc´ı fotoapar´atu. Z jednoho vybran´eho m´ısta si sc´enu vykresl´ıme do ˇsesti smˇer˚ u a v´ ysledky si uloˇz´ıme. Zorn´ y uhel kamery nastav´ıme na 90 stupˇ n˚ u a ˇs´ıˇrku a v´ yˇsku vykreslen´e oblasti zvol´ıme totoˇznou. T´ımto dok´aˇzeme vytvoˇrit jednoduch´e skyboxy. V pr´ aci budeme takto vytvoˇren´ y skybox pouˇz´ıvat pro odraz na hladinˇe vody. Na sloˇzitˇejˇs´ı skybox (napˇr´ıklad oblohy) tato metoda ale nestaˇc´ı. Druh´ a metoda vykresluje stˇeny skyboxu z´aroveˇ n. Metodu budeme vyuˇz´ıvat pro oblohy. Ze stˇredu krychle se pro zvolen´ y pixel a zvolenou stˇenu krychle urˇc´ı paprsek. Pro velikost obr´ azk˚ u na stˇen´ ach krychle (w, h) potˇrebujeme 6 · w · h paprsk˚ u. Paprsek m˚ uˇzeme reprezentovat pouze normalizovan´ ym vektorem u. Tento vektor si m˚ uˇzeme pˇredstavit jako jistou tˇr´ısloˇzkovou souˇradnici. Pokud budeme cht´ıt vykreslit do skyboxu jist´ y element, ˇ pˇred´ame mu tento vektor a element n´am vr´at´ı barvu (r, g, b, a). C´ıslo a je pr˚ uhlednost v intervalu h0, 1i a pouˇz´ıv´ a se pro m´ıch´an´ı novˇe pˇr´ıchoz´ı barvy c = (r, g, b) s pˇredch´azej´ıc´ı cp = (rp , gp , bp ). M´ıch´ an´ı je ˇr´ızeno vztahem: cp = a · c + (1 − a) · cp Algoritmus generov´ an´ı skyboxu obohy je n´asleduj´ıc´ı: 24
(3.8)
1. Nastav´ıme vˇsechny barvy obr´azk˚ u na nulu cp = (0, 0, 0). 2. Pro vˇsechny stˇeny krychle skyboxu a vˇsechny jejich pixely urˇc´ıme normalizovan´ y vektor u. 3. Pro vˇsechny elementy ei , i ∈ 1, . . . , n, kter´e chceme vykreslit z´ısk´ame barvu ci . 4. V´ ysledn´ a barva pro vektor u (a tedy i pro konkr´etn´ı pixel) je cpn . cp1 = a1 · c1 + (1 − a1 ) · cp cpi = ai · ci + (1 − ai ) · cpi−1 Oblohu si budeme reprezentovat pomoc´ı tˇri z´akladn´ı element˚ u: • Barevn´ y pˇrechod oblohy. Barevn´ y pˇrechod oblohy ud´av´a barvu pozad´ı. Ud´av´a barvu atmosf´ery pˇri v´ ychodu slunce, z´apadu slunce nebo v pr˚ ubˇehu odpoledne. Barevn´ y pˇrechod je urˇcen barvou horizontu, poˇc´ateˇcn´ı, koncovou a z´akladn´ı barvou, vektorem ke slunci a exponentem. Poˇc´ateˇcn´ı barva oblohy je barva bl´ızko slunce, koncov´a barva oblohy je barva na opaˇcn´em konci oblohy od slunce. Z´akladn´ı barva je barva mezi poˇc´ ateˇcn´ı a koncovou. Barva horizontu obarvuje oblohu bl´ızko nad zem´ı. Rozm´ıstˇen´ı barev je dobˇre patrn´e na obr´azku 3.19 Exponent ud´av´a rychlost zmˇeny barvy horizontu do barvy oblohy. počáteční barva
koncová barva
základní barva
Slunce
barva horizontu
Obr´ azek 3.19: Rozm´ıstˇen´ı barev oblohy. • Slunce. Slunce je urˇceno vektorem pozice, velikost´ı, barvou, exponentem a velikost´ı okoln´ı z´ aˇre. Velikost slunce je ve steradi´anech. Exponent ud´av´a, jak ostr´a je hranice slunce. Velikost okoln´ı z´ aˇre ud´av´a, do jak´e vzd´alenost od slunce se ˇs´ıˇr´ı barva slunce obr´ azek: 3.20. • Mraky. Mraky jsou reprezentovan´e nekoneˇcnou rovinou, kter´a je um´ıstˇena nad sc´enou, obr´ azek: 3.21. Smˇerov´ y vektor u pro dan´ y pixel skyboxu protne tuto rovinu v jist´ ych souˇradnic´ıch I(x, y). Souˇradnice I pouˇzijeme jako vstup funkce Perlinova ˇsumu popsan´eho v podsekci 3.1.2. Parametry mrak˚ u jsou tedy: Amplituda, frekvence, perzistence a poˇcet sˇc´ıt´ an´ı. Tyto parametry jsou pˇred´any funkci Perlinova ˇsumu. Dalˇs´ı parametry jsou hustota, kryt´ı a barva mrak˚ u. Pro vˇernˇejˇs´ı reprezentaci mrak˚ u budeme obvykle potˇrebovat v´ıcero vrstev mrak˚ u. Probl´em teto metody spoˇc´ıv´a v aliasing efektu na horizontu. Pr˚ useˇc´ık smˇerov´eho vektoru s rovinou mrak˚ u je pro pixely na horizontu velmi daleko. Jednotliv´e souˇradnice pro Perlin˚ uv ˇsum pro pixely, kter´e leˇz´ı vedle sebe v t´eto oblasti jsou velmi odliˇsn´e. T´ım n´am vznik´a probl´em, ˇze barva 25
hranice Slunce plná barva Slunce okolní záře
Obr´ azek 3.20: Hranice slunce a okoln´ı z´aˇre. ˇ sen´ı by mohlo spoˇc´ıvat mrak˚ u na horizontu se prudce stˇr´ıd´a v sousedn´ıch pixelech. Reˇ v pouˇzit´ı jin´eho neˇz Perlinova ˇsumu. Naˇs´ım ˇreˇsen´ım ale bude zvyˇsov´an´ı pr˚ uhlednosti mrak˚ u smˇerem k horizontu. Mraky se tak rozplynou v barvˇe horizontu, obr´azek: 3.22. rovina s Perlinovým šumem
skybox
Obr´ azek 3.21: Vykreslov´an´ı mrak˚ u.
Obr´azek 3.22: Vlevo: mrak bez opravy aliasing efektu. Vpravo: mrak s rostouc´ı pr˚ uhlednost´ı k horizontu.
3.10
ˇ asticov´ C´ e syst´ emy
ˇ asticov´e syst´emy se v poˇc´ıtaˇcov´e grafice pouˇz´ıvaj´ı k nejr˚ C´ uznˇejˇs´ım u ´ˇcel˚ um. Pomoc´ı ˇc´asticov´ ych syst´em˚ u reprezentujeme fyzik´aln´ı jevy, kter´e by se jinou cestou ˇspatnˇe vizualizovaly nebo simulovaly. Jedn´ım z pˇr´ıklad˚ u m˚ uˇze b´ yt simulace snˇeˇzen´ı. Dalˇs´ı pˇr´ıklady jsou p´ısek, ˇ ohˇ nostroj nebo voda. C´ asticov´ y syst´em je sloˇzen s velk´eho mnoˇzstv´ı samostatn´ ych ˇc´astic. ˇ astice maj´ı svoji pozici a Kaˇzd´a ˇc´ astice se chov´ a samostatnˇe podle urˇcit´ ych pravidel. C´
26
Obr´ azek 3.23: Skybox zobrazuj´ıc´ı z´apad slunce rychlost. Tyto parametry slouˇz´ı k popisu pohybu. Rovnice pro popis pohybu jsou 3.10, 3.12 a 3.13 a bl´ıˇze si je pop´ıˇseme v sekci 3.11 o elastick´ ych syst´emech. ˇ astice budeme vykreslovat jako ploˇsky s nanesenou texturou. Budeme rozliˇsovat dva C´ druhy. Jedny ˇc´ astice se neust´ ale nat´aˇcej´ı ke kameˇre. Tento druh ˇc´astic budeme pouˇz´ıvat pro vykreslen´ı vodop´ adu, bublinek ve vodˇe a list˚ u li´anov´e rostliny. Druh´ y druh si udrˇzuje svoji orientaci. V intru jej budeme pouˇz´ıvat pro vykreslen´ı chom´aˇce rostlin. Mimo pozice a rychlosti m´ a u sebe ˇc´ astice tak´e ˇcas. Pokud ˇcas ˇc´astice pˇrekroˇc´ı urˇcitou hodnotu, ˇc´astice zanikne. U ˇc´ asticov´eho syst´emu si budeme definovat i emitor. V emitoru se vytv´aˇr´ı ˇc´astice. Pokud ˇc´ astice zanikne objev´ı se nov´a s poˇc´ateˇcn´ım nastaven´ım v emitoru.
3.11
Elastick´ e syst´ emy
Elastick´e syst´emy slouˇz´ı k simulaci tˇeles jako je l´atka, tkanina, lana, ale i rosol. Elastick´ y objekt mˇen´ı sv˚ uj tvar v pr˚ ubˇehu ˇcasu. Proto je v´ ypoˇcet jeho pohybu odliˇsn´ y od v´ ypoˇctu dynamiky tuh´eho tˇelesa. Pohyb tuh´eho tˇelesa si m˚ uˇzeme rozloˇzit na posuvnou rychlost a rotaˇcn´ı rychlost. Pokud na takov´e tˇeleso p˚ usob´ıme silou, jsou body tˇelesa pˇr´ımo ovlivˇ nov´any. Elastick´e tˇeleso je sloˇzeno z bod˚ u a vazeb, pˇriˇcemˇz kaˇzd´ y bod m´a vlastn´ı v´ ypoˇcet dynamiky. Pokud tedy na elastick´e tˇeleso p˚ usob´ıme silou, u ´ˇcinky s´ıly jsou postupnˇe distribuov´any pomoc´ı vazeb do bod˚ u. Elastick´ y syst´em si m˚ uˇzeme pˇredstavit jako speci´aln´ı obdobu ˇc´asticov´eho syst´emu. ˇ astice (uzly) pˇredstavuj´ı vrcholy objektu, vrcholy troj´ C´ uheln´ık˚ u. Kaˇzd´a ˇc´astice m´a svoji 27
hmotnost, pozici a rychlost. Oproti ˇc´asticov´ ym syst´em˚ um obsahuje ˇc´astice i seznam vazeb, kter´e ovlivˇ nuj´ı jej´ı pohyb. Vazba je spoj mezi dvˇema ˇc´asticemi. Nese informaci o sv´e poˇc´ateˇcn´ı d´elce a sv´e tuhosti. D´ ale obsahuje informaci, kter´e dva uzly spojuje. Elastick´ y syst´em je tedy sloˇzen ze dvou z´ akladn´ıch druh˚ u element˚ u: uzl˚ u a spoj˚ u. Pohyb elastick´eho syst´emu si pop´ıˇseme diferenci´aln´ımi rovnicemi. Kaˇzd´a ˇc´astice m´ a svoji pozici p a rychlost v. Pro v´ ypoˇcet nov´e pozice p(t + dt) potˇrebujeme rychlost v(t) a krok ˇcasu dt. Pro v´ ypoˇcet nov´e rychlosti v(t + dt) potˇrebujeme zrychlen´ı a(t) a krok ˇcasu dt. Diferenci´ aln´ı rovnice pro v´ ypoˇcet pozice: ∂p =v ∂t
(3.9)
Rovnici 3.9 zintegrujeme a dostaneme tvar: t
Z
v(t)dt
p(t) = p(0) +
(3.10)
0
V rovnici 3.10 je p(0) poˇc´ ateˇcn´ı pozice ˇc´astice v ˇcase t = 0. p(t) respektive v(t) je pozice respektive rychlost v ˇcase t. Rovnici 3.10 si m˚ uˇzeme vyj´adˇrit sch´ematem s integr´atorem na obr´azku 3.24. Diferenci´ aln´ı rovnice pro v´ ypoˇcet rychlosti: p(0) v(t)
p(t)
Obr´ azek 3.24: Integr´ator reprezentuj´ıc´ı rovnici 3.10 ∂v =a ∂t
(3.11)
Rovnici 3.11 zintegrujeme a v´ ysledn´ y tvar je: Z
t
v(t) = v(0) +
a(t)dt
(3.12)
0
a(t) v rovnici 3.12 reprezentuje zrychlen´ı, v(0) poˇc´ateˇcn´ı rychlost a v(t) rychlost v ˇcase t. Sch´ema pro rovnici 3.12 je obdobn´e sch´ematu 3.24. Sch´emata m˚ uˇzeme spojit v jedno, kter´e je zn´ azornˇen´e na obr´ azku 3.25 Jelikoˇz vytv´aˇr´ıme elastick´ y syst´em v trojrozmˇern´em prostoru je zrychlen´ı, rychlost a pozice tˇr´ısloˇzkov´ y vektor. Sch´ema 3.25 n´am jiˇz dok´ aˇze vypoˇc´ıtat pozici jedn´e ˇc´ astice v ˇcase t. Zb´ yv´a zjisti zrychlen´ı, tedy vstup integr´atoru (0). Zrychlen´ı ˇc´ astice se odv´ıj´ı od druh´eho Newtonova z´akonu o p˚ usoben´ı s´ıly na hmotn´e tˇeleso: a=
1 ·F m
(3.13)
Nyn´ı jiˇz v´ıme, jak se ˇc´ astice (uzel elastick´eho syst´emu) zachov´a, pokud na ni zap˚ usob´ıme silou. S´ıla je sloˇzena z gravitaˇcn´ı s´ıly Fg = m · g, kter´a je pro dan´ y uzel konstantn´ı a s´ıly
28
p(0)
v(0) v(t)
a(t) (0)
p(t) (1)
Obr´ azek 3.25: Sch´ema pˇredstavuj´ıc´ı spojen´ı rovnic 3.10 a 3.12 vyvolan´e spoji dan´eho uzlu. Spoj mezi dvˇema uzly si m˚ uˇzeme pˇredstavit jako pruˇzinu. S´ılu, kterou pruˇzina p˚ usob´ı na dva uzly si vyj´adˇr´ıme vztahem: F = −k · x
(3.14)
Ve vztahu 3.14 je k tuhost pruˇziny (nebo spoje) a x = l0 − l je v´ ychylka pruˇziny z rovnov´ aˇzn´eho stavu. l0 je poˇc´ ateˇcn´ı d´elka spoje a l je aktu´aln´ı d´elka spoje v ˇcase t. Absolutn´ı velikost s´ıly vyvolan´e spoji na uzel i je: |Fi | =
n X
−ki,j · (l0i,j − |pi pj |) · si,j
(3.15)
j=1
n je poˇcet uzl˚ u. l0i,j je poˇc´ ateˇcn´ı d´elka spoje mezi uzly i, j. pi , pj jsou pozice uzl˚ u a si,j = 1 pokud je mezi uzly i, j spoj. Jinak je si,j = 0. Stejnˇe jako pro pozici a rychlost, je i s´ıla tˇr´ısloˇzkov´ y vektor. Oznaˇcme ei,j = (pj − pi )/|pi pj | normalizovan´ y vektor spoje z uzlu i do j. V´ ysledn´ a s´ıla p˚ usob´ıc´ı na uzel i je: Fi =
n X
−ki,j · (l0i,j − |pi pj |) · si,j · ei,j =
j=1
n X
−si,j · ki,j
j=1
l0i,j − 1 (pj − pi ) |pi pj |
(3.16)
Nyn´ı jiˇz zn´ ame vˇse, abychom mohli vytvoˇrit sch´ema obecn´eho elastick´eho syst´emu. Sch´ema je zn´azornˇen´e na obr´ azku 3.26 Diferenci´ aln´ı rovnice mus´ıme vyˇreˇsit pomoc´ı numerick´ ych metod. Existuje nˇekolik druh˚ u numerick´ ych metod. Nejzn´ amˇejˇs´ı je Eulerova metoda. Pˇresnost numerick´ ych metod z´avis´ı na velikosti kroku ˇcasu dt a stupnˇe metody.
3.11.1
Eulerova metoda
Eulerova metoda je jednoduch´ a numerick´a metoda pro ˇreˇsen´ı diferenci´aln´ıch rovnic. Je d´ana vztahem: y0 = y(0) yn+1 = yn + dt · f (tn , yn ) f (tn , yn ) je aproximace derivace yn0 . V naˇsem pˇr´ıpadˇe je to vstup integr´ator˚ u ve sch´ematu 3.26. Eulerova metoda je rychl´ a na v´ ypoˇcet a jednoduch´a na implementaci. Proto m˚ uˇze b´ yt vhodn´a pro intra. Jej´ı nev´ yhodou je mal´a pˇresnost. Proto je nutn´e volit menˇs´ı krok ˇcasu neˇz u jin´ ych metod.
29
v1(0) F1
F1
1/m1
a1(t)
p1(0) v1(t)
p1(t) 1
p2(0)
v2(0) F2
F2
1/m2
a2(t)
v2(t)
2
vn(0) Fn
Fn
1/mn
p2(t)
an(t)
pn(0) vn(t)
pn(t) n
Obr´azek 3.26: Sch´ema obecn´eho elastick´eho syst´emu. Jednotky F1 − Fn poˇc´ıtaj´ı s´ılu podle vztahu 3.16
3.11.2
Runge Kutta metoda
Runge Kutta metoda ˇctvrt´eho stupnˇe je d´ana vztahem: y0 = y(0) 1 yn+1 = yn + (k1 + 2k2 + 2k3 + k4 ) 6 k1 = dtf (tn , yn ) k2 = dtf (tn + dt/2, yn + k1 /2) k3 = dtf (tn + dt/2, yn + k2 /2) k4 = dtf (tn + dt, yn + k3 ) Runge Kutta metoda je obecnˇe pˇresnˇejˇs´ı neˇz Eulerova metoda. Je ale v´ ypoˇcetnˇe n´aroˇcnˇejˇs´ı. Pro v´ ypoˇcet n´ asleduj´ıc´ı hodnoty integr´atoru je zapotˇreb´ı ˇctyˇrikr´at vyˇc´ıslit jeho vstup.
3.11.3
Stabilita numerick´ ych metod
Numerick´e metody nemus´ı b´ yt stabiln´ı. Pro nˇekter´e rovnice se rozkmitaj´ı. N´aˇs elastick´ y syst´em se pro nevhodnˇe zvolen´e koeficienty rozkmit´a a n´aslednˇe rozpadne. Mus´ıme spr´avnˇe zvolit koeficienty tuhosti spoj˚ u a hmotnosti uzl˚ u. Velk´ y vliv na stabilitu m´a krok ˇcasu dt. Elastick´ y syst´em je tuh´ y syst´em, pokud jsou hmotnosti uzl˚ u mal´e nebo pokud jsou tuhosti spoj˚ u velk´e. Tato skuteˇcnost vypl´ yv´a z rovnic 3.13 a 3.14. Pokud obˇe rovnice spoj´ıme z´ısk´ame koeficient c = k/m, kde k je tuhost spoje a m hmotnost uzlu. Tento koeficient pˇribliˇznˇe popisuje zes´ılen´ı zpˇetn´e vazby vyznaˇcen´e ˇcervenou barvou v obr´azku 3.26. 30
V programu jsem nejprve naimplementoval Eulerovu numerickou metodu. Jej´ı nejvˇetˇs´ı nev´ yhoda byla nestabilita. Pokud jsem v pr˚ ubˇehu animace zvyˇsoval tuhosti spoj˚ u, v jednom okamˇziku se elastick´ y syst´em choval dle oˇcek´av´an´ı. Pokud ale tuhost pˇrerostla urˇcit´ y pr´ ah, syst´em se velice rychle rozkmital a rozpadl a animaci jsem musel pusti znovu. Proto jsem se rozhodl zkusit implemetovat Runge Kutta ˇctvrt´eho ˇr´adu. U Runge Kutta metody elastick´ y syst´em reaguje na nevhodnˇe zvolen´e tuhosti a hmotnosti pomaleji. Proto je moˇzn´e se jeˇstˇe z rozkmitan´eho stavu vr´ atit zpˇet. Testoval jsem tak´e rychlost. Vˇedˇel jsem, ˇze u Runge Kutta metody potˇrebuji vyˇc´ıslit ˇctyˇri koeficienty. V´ ypoˇcet jednoho kroku je tak pˇribliˇznˇe ˇctyˇrikr´ at n´ aroˇcnˇejˇs´ı neˇz u metody Eulerovy. Experiment´alnˇe jsem si srovnal v´ ysledky pro stejn´ y elastick´ y syst´em s Eulerovou metodou pro krok dt a Runge Kutta metodou pro krok 4dt. Sledoval jsem, pˇri jak´em nastaven´ı tuhosti spoj˚ u se syst´em rozkmit´a. V´ ysledky pro metodu Runge Kutta byly m´ırnˇe lepˇs´ı neˇz pro Eulerovu metodu, proto jsem se rozhodl jej ve v´ ysledn´e aplikaci vyuˇz´ıvat. Tak´e velmi z´aleˇzelo na tvaru elastick´eho syst´emu.
3.12
Kolize
Bez koliz´ı se neobejde t´emˇeˇr ˇz´ adn´a fyzik´aln´ı simulace. Napˇr´ıklad ˇc´asticov´ y syst´em d´ıky koliz´ım interaguje s okol´ım. Kolize b´ yvaj´ı sloˇzit´e na v´ ypoˇcet a proto je potˇreba algoritmy zefektivˇ novat. Jedn´ım z vylepˇsen´ı algoritm˚ u detekc´ı koliz´ı jsou obalov´a tˇelesa. Dalˇs´ım vylepˇsen´ım m˚ uˇze b´ yt hierarchick´e rozdˇelen´ı sc´eny. V intru jsou kolize poˇc´ıt´ any jen pro ˇc´asticov´e a elastick´e syst´emy. Tyto syst´emy koliduj´ı s geometri´ı jeskynˇe a t´ım se odr´aˇz´ı od jej´ıho povrchu. Pro jednoduchost budeme kolize poˇc´ıtat jen pro body. Abychom zjistili, zda je bod v kolizi s jeskyn´ı, mus´ıme zjistit, se kter´ ym troj´ uheln´ıkem bod koliduje. Tento pˇr´ıstup by nebyl pˇr´ıliˇs rychl´ y a implementace algoritmu by zabrala pˇr´ıliˇs m´ısta. M´ısto toho pouˇzijeme jednoduch´ y zp˚ usob. Souˇradnice bodu, pro kter´ y poˇc´ıt´ ame kolizi, m˚ uˇzeme pouˇz´ıt jako index do volumetrick´e reprezentace jeskynˇe. Pokud hodnota na souˇradnic´ıch bodu pˇrekroˇc´ı urˇcit´ y pr´ah (stejn´ y pr´ah je pouˇzit i pro algoritmus Marching Tetrahedra) je v dan´em m´ıstˇe kolize. Nejprve jsem navrhl obecn´ y algoritmus, kter´ y dok´azal z´ıskat hodnotu pro neceloˇc´ıseln´e souˇradnice z d dimenzion´ aln´ıho pole. Tento algoritmus byl rekurzivn´ı, relativnˇe mal´ y a d´ıky sv´e obecnosti znovupouˇziteln´ y. Nicm´enˇe nebyl pˇr´ıliˇs rychl´ y. Proto jsem navrhl algoritmus, kter´ y je rychlejˇs´ı, ale pracuje jen pro trojrozmˇern´e pole. P0 = (p0 , p1 , p2 ) je bod, pro kter´ y poˇc´ıt´ame kolizi. Nejprve pˇresuneme bod do rozsahu r = (r0 , r1 , r2 ) (ˇs´ıˇrka, v´ yˇska, d´elka) podle vztahu: P1 = ((P0 %r) + r)%r. Operace modulo % pracuje po sloˇzk´ach vektoru. Pot´e z´ısk´ame nejvyˇsˇs´ı celoˇc´ıseln´ y index I = (i0 , i1 , i2 ) = bP1 c, kter´ y je menˇs´ı neˇz P1 . Rozd´ıl v = (v0 , v1 , v2 ) = P1 − I ud´ av´ a pomˇer m´ıch´an´ı hodnot na indexech o jedniˇcku vyˇsˇs´ıch neˇz I v nˇekter´e ose. Hodnota h(P0 ) trojrozmˇern´eho pole v bodˇe P0 je d´ana vztahem: h0 = (1 − v0 )h(I) + v0 h(Ix ) h1 = (1 − v0 )h(Iy ) + v0 h(Iyx ) h2 = (1 − v0 )h(Iz ) + v0 h(Izx ) h3 = (1 − v0 )h(Izy ) + v0 h(Izyx ) h01 = (1 − v1 )h0 + v1 h1 h23 = (1 − v1 )h2 + v1 h3 h(P0 ) = (1 − v2 )h01 + v2 h23 Doln´ı sufix indexu I ud´ av´ a, ke kter´e sloˇzce indexu I je pˇriˇctena jedniˇcka. Napˇr´ıklad pro 31
index Izx = (i0 + 1, i1 , i2 + 1). Abychom mohli spr´ avnˇe reagovat na kolizi, mus´ıme zn´at i norm´alu povrchu. Norm´ alu povrchu m´ ame uloˇzenou tak´e v trojrozmˇern´em poli, proto m˚ uˇzeme pouˇz´ıt stejn´ y algoritmus. Reakce na kolizi spoˇc´ıv´ a v pˇresunut´ı bodu na povrch jeskynˇe a otoˇcen´ı jeho rychlosti ´ podle norm´ aly. Uhel dopadu se pˇritom mus´ı rovnat u ´hlu odrazu. V´ yslednou rychlost jeˇstˇe zmenˇs´ıme o ztr´ aty. Ovlivnˇen´ı rychlosti u ˇc´asticov´ ych syst´emu je pˇr´ımoˇcar´e. U elastick´ ych syst´em˚ u si ale mus´ıme d´ at pozor. Ovlivˇ nujeme rychlosti uzl˚ u externˇe, mimo v´ ypoˇcetn´ı model elastick´eho syst´emu. Toto m˚ uˇze potenci´alnˇe v´est ke vzniku nestability.
3.13
Voda
Voda se v intru vyskytuje ve dvou form´ach. V podobˇe vodn´ı hladiny a v podobˇe tekouc´ı vody pˇredstavuj´ıc´ı vodop´ ady. Vodn´ı hladina je v intru pouˇzita pro reprezentaci moˇre v ˇc´asti s pˇr´ımoˇrskou oblast´ı. D´ ale pak pro vizualizaci jez´ırek v pˇr´ıvodn´ım tunelu do jeskynˇe a v jeskyni. Tekouc´ı voda se vyskytuje aˇz v posledn´ı ˇc´asti intra - v jeskyni. V jeskyni je nˇekolik m´ıst, kde vyvˇer´ a voda. Voda st´ek´a po stˇen´ach, kterou zvlhˇcuje.
3.13.1
Vodn´ı hladina
Vodn´ı hladina je reprezentov´ ana prost´ ym ˇctvercem. Leskne a odr´aˇz´ı se na ni okol´ı. Odraz na vodn´ı hladinˇe lze vytvoˇrit nˇekolik zp˚ usoby. Jedn´ım z nejjednoduˇsˇs´ıch zp˚ usob˚ u je zrcadlovˇe pˇrevr´atit sc´enu a vykreslit ji znovu. Mus´ıme si d´ at pozor na to, abychom vykreslovali obraz jen v oblasti vodn´ı plochy. M˚ uˇzeme toho dos´ ahnou pomoc´ı stencil testu. D´ale mus´ıme vykreslovat jen odraz. Nesm´ı se st´at, aby odraz ”vyl´ezal”z vodn´ı plochy. Pˇr´ıklad takto vytvoˇren´eho odrazu je vidˇet na obr´azku 3.27. V´ yhoda metody spoˇc´ıv´ a v jednoduch´e implementaci. Nev´ yhoda je nemoˇznost pˇridat na
Obr´azek 3.27: Jednoduch´ y odraz na vodn´ı hladinˇe vytvoˇren´ y pomoc´ı pˇreklopen´ı sc´eny. hladinu vlnˇen´ı. Vlnˇen´ı by se muselo pˇrid´avat dodateˇcnˇe, jinou metodou. Dalˇs´ı nev´ yhoda je
32
nutnost rasterizace odrazu. Pokud se v hladinˇe odr´aˇz´ı cel´a sc´ena m˚ uˇze n´am v´ ykon klesnou i na polovinu. Jin´ ym zp˚ usobem, jak vizualizovat odraz, je vytvoˇrit kolem vodn´ı plochy skybox. Na tomto skyboxu je vykresleno okol´ı, kter´e se na vodn´ı hladinˇe odr´aˇz´ı. Paprsek od kamery se podle norm´ aly vodn´ı hladiny odraz´ı a smˇeruje do urˇcit´eho m´ısta skyboxu. T´ımto z´ısk´ame barvu. Jelikoˇz pracujeme s fragmenty a ne s celou sc´enou, lze pomˇernˇe snadno vytvoˇrit na hladinˇe vlnˇen´ı. Pokud vytvoˇr´ıme skybox pˇri inicializaci a nech´ame jej statick´ y, uˇsetˇr´ı n´am to v´ ykon. Nemus´ıme sc´enu pˇrekreslovat pro vizualizaci odrazu. Nev´ yhoda metody se skyboxem je, ˇze se na hladinˇe nem˚ uˇze odr´aˇzet pohybliv´ y pˇredmˇet. Dalˇs´ı nev´ yhoda spoˇc´ıv´ a v nepˇresnosti odrazu. Skybox si vytvoˇr´ıme jen pro jeden konkr´etn´ı bod hladiny. Spr´avnˇe ˇ ım vzd´alenˇejˇs´ı je zkouman´ bychom si jej mˇeli vytvoˇrit pro vˇsechny body hladiny. C´ y bod na hladinˇe od bodu, kolem kter´eho je vytvoˇren skybox, t´ım je odraz zkreslenˇejˇs´ı. Pokud ale hladinu vody zvln´ıme, nemus´ı b´ yt tento nedostatek patrn´ y. Metodu se skyboxem budeme v intru pouˇz´ıvat. Efekt vlnˇen´ı na hladinˇe je vytvoˇren pomoc´ı ovlivˇ nov´an´ı norm´aly. Podobnˇe jako u bump mappingu je na hladinu namapov´ana bump mapa. Bump mapa n´am lok´alnˇe ovlivˇ nuje norm´alu, proto se povrch zd´ a zakˇriven´ y. Abychom hladinu rozpohybovali, potˇrebovali bychom sekvenci bump map, kter´e na sebe navazuj´ı v ˇcase. Sekvenci bump map si m˚ uˇzeme pˇredstavit jako trojrozmˇernou texturu. Trojrozmˇern´a textura obsahuje vrstvy bump map v z souˇradnici.
Obr´ azek 3.28: Vlnˇen´ı odrazu na hladinˇe s pouˇzit´ım skyboxu s pr˚ uhlednost´ı.
3.13.2
Tekouc´ı voda
Tekouc´ı voda je ˇc´ asticov´ y syst´em. Textura ˇc´astic je v prav´e ˇc´asti obr´azku 4.4. Jedin´ y rozd´ıl je v tom, ˇze textura nen´ı zelen´ a ale b´ıl´a. Tekouc´ı voda se vyskytuje v podobˇe vodop´adu v posledn´ı sc´enˇe intra.
3.14
Ter´ en
Ter´en budeme v intru pouˇz´ıvat ve dvou sc´en´ach: hory a pˇr´ımoˇrsk´a oblast. Geometrie ter´enu je vytvoˇrena z mˇr´ıˇzky troj´ uheln´ık˚ u. Body troj´ uheln´ıku na ose y reprezentuj´ıc´ı v´ yˇsku hor
33
vych´ yl´ıme pomoc´ı v´ yˇskov´e mapy. V´ yˇskov´a mapa je dvojrozmˇern´e pole, kde hodnoty v prvc´ıch neud´ avaj´ı barvu ale v´ yˇsku. Pro vygenerov´an´ı v´ yˇskov´e mapy m˚ uˇzeme pouˇz´ıt algoritmy popsan´e v sekci 3.5 o generov´an´ı textur. Velikost pole urˇcuje poˇcet troj´ uheln´ık˚ u. Pro pole velikost w × h je potˇreba 2 · (w − 1) · (h − 1).
3.15
Pohyb kamery
Aby bylo intro dynamick´ a, potˇrebujeme v n´ı pohyb. Jedn´ım ze zp˚ usob˚ u, jak toho m˚ uˇzeme dos´ahnout je pohybovat s kamerou. Spr´avn´ y pohyb kamery m˚ uˇze vytvoˇrit i z nezaj´ımav´e sc´eny akˇcn´ı pod´ıvanou. Kamera v pr˚ ubˇehu ˇcasu sleduje jistou trajektorii. Jelikoˇz m´a intro omezenou velikost, nem˚ uˇzeme si uloˇzit pro kaˇzd´ y krok ˇcasu, pozici kamery. M´ısto toho, si budeme ukl´ adat jen kl´ıˇcov´e body a m´ısta mezi nimi budeme vypoˇc´ıt´avat z okoln´ıch kl´ıˇcov´ ych bod˚ u. Jeden kl´ıˇcov´ y bod si m˚ uˇzeme pˇredstavit jako deset ˇc´ısel K = (p, z, y, a). Vektor p = (px , py , pz ) reprezentuje pozici kamery. Vektor z = (zx , zy , zz ) reprezentuje pohledov´ y vektor neboli smˇer, kam je kamera nasmˇerov´ana. Vektor y = (yx , yy , yz ) je vektor urˇcuj´ıc´ı ˇ ıslo a ud´av´a zorn´ smˇer nahoru. Tento vektor ud´ av´ a natoˇcen´ı kamery pod´el osy z. C´ yu ´hel. Sekvence kl´ıˇcov´ ych bod˚ u definuje pohyb kamery. Mezi kl´ıˇcov´ ymi body budeme interpolovat. Pro interpolaci pouˇzijeme Catmull-Rom interpolaci popsanou v [8]. Pro v´ ypoˇcet interpolace z hodnoty v1 do hodnoty v2 pouˇz´ıv´ a metoda tak´e hodnoty v0 , v3 . 0 2 0 0 v0 v0 1 −1 0 1 0 · v1 = C(t) · v1 v(t) = [t0 , t1 , t2 , t3 ] · · (3.17) 2 −5 4 −1 v2 v2 2 −1 3 −3 1 v3 v3 Hodnoty v0 , v1 , v2 , v3 jsou kl´ıˇcov´e hodnoty. Hodnota v(t) je interpolovan´a hodnota mezi v1 , v2 . Parametr t m˚ uˇze nab´ yvat hodnot t ∈ h0, 1i. Pokud je parametr t = 0 je hodnota v(t) = v1 . Pokud je parametr t = 1 je hodnota v(t) = v2 . Funkce C : h0, 1i → R4 vrac´ı vektor vah pro parametr t. Pokud m´ ame v´ıce neˇz ˇctyˇri kl´ıˇcov´e hodnoty, interpolujeme po ˇc´astech. Napˇr´ıklad m´ame n kl´ıˇcov´ ych hodnot v1 , v2 , . . . , vn . Celkov´a d´elka je Tmax . Pokud budeme potˇrebovat hodnoty v1−a respektive vn+a , a ∈ N, pouˇzijeme v1 respektive vn . V´ ysledn´a hodnota v m´ıstˇe t je d´ana podle vztahu: vi vi+1 t −i · (3.18) v(t) = C (n − 1) vi+2 Tmax vi+3 Index i ∈ {0, 1, . . . , n − 2} ud´ av´ a segment, ve kter´em se interpoluje z kl´ıˇcov´ ych hodnot. Jeho hodnota je: t i= · (n − 1) (3.19) Tmax Interpolaci budeme prov´ adˇet pro vˇsech deset ˇc´ısel kl´ıˇcov´eho bodu. Z´ısk´ame tak pro ˇcas t pˇresn´ y popis kamery.
34
3.15.1
Efekty kamery
Pokud jiˇz m´ ame vyˇreˇsen´ y pohyb kamery, je vhodn´e jej dobˇre pouˇz´ıt. V intru m˚ uˇzeme pouˇz´ıt nˇekolik efekt˚ u, kter´e vid´ıme napˇr´ıklad ve filmech. Prvn´ım z nich je efekt, kdy se kamera pˇribliˇzuje k objektu a jej´ı zorn´ yu ´hel se zvˇetˇsuje. Situace je zn´azornˇena na obr´azku 3.29. Objekt by se d˚ usledkem zmenˇsen´ı vzd´alenosti od kamery mˇel zvˇetˇsovat. Pokud budeme ale z´aroveˇ n zvˇetˇsovat zorn´ yu ´hel, z˚ ustane stejnˇe velk´ y. Okol´ı kolem objektu se ale bude roztahovat do ˇs´ıˇre. Obdobn´ y efekt lze vytvoˇrit obr´acenˇe. M´ısto abychom se k objektu pˇribliˇzovali, budeme se vzdalovat a zorn´ yu ´hel zmenˇsovat. Tento efekt je obl´ıben´ y mezi filmaˇri. Efekt b´ yv´a vyuˇz´ıv´ an v chodb´ ach, tunelech a podobn´ ych prot´ahl´ ych prostor´ach, kde je zv´ yraznˇen.
směr posunu kamery a1
a2
Obr´azek 3.29: Efekt kamery s vyuˇzit´ım zorn´eho u ´hlu. Kamera se posouv´a zleva doprava. Jej´ı zorn´ yu ´hel se pˇritom zvˇetˇsuje a1 < a2 Dalˇs´ı efekt je rovnˇeˇz hojnˇe pouˇz´ıvan´ y ve filmech. Kamera se zamˇeˇr´ı na jeden objekt, pˇribl´ıˇz´ı na nˇej pomoc´ı zmenˇsen´ı zorn´eho u ´hlu a rotuje kolem nˇej. Efekt je zn´azornˇen obr´azkem 3.30. Objekt je sn´ım´ an na stejn´em m´ıstˇe. Vzd´alen´a krajina se ale rychle pohybuje na pozad´ı. B´ yv´ a pouˇz´ıv´ an v exteri´erech, kdy v´ yznaˇcn´ y objekt stoj´ı na vrcholku hory nebo kopce.
směr posunu kamery
P
Vzdálené okolí
Obr´azek 3.30: Efekt kamera kdy se kamera zamˇeˇr´ı na jeden bod P a rotuje kolem nˇej.
3.16
Texty
Texty jsou v intru sp´ıˇse doprovodn´e prvky. Font textu je uloˇzen ve statick´ ych datech. Jedn´ a se o mal´ y bitov´ y obr´ azek s vybran´ ymi znaky. Z obr´azku vytvoˇr´ıme ˇctverce, na kter´e je namapov´ ana textura jednoho p´ısmena. Font, kter´ y je v intru pouˇzit je zobrazen na obr´azku 3.31
Obr´azek 3.31: P´ısmenka fontu.
35
Kapitola 4
Implementace Vˇetˇsinu projektu jsem implementoval pod syst´emem Ubuntu Linux. Pro vytvoˇren´ı okna pod Linuxem je pouˇzita knihovna SDL. U syst´emu Windows je to WINAPI. Pro spuˇstˇen´ı programu je vyˇzadov´ ano OpenGL minim´alnˇe ve verzi 3.3. Program jsem ladil pro Windows 7. Verze pro Linux neobsahuje hudbu a je tak´e vˇetˇs´ı. D˚ uvod je ten, ˇze knihovna pro pˇrehr´av´ an´ı hudby byla naps´ ana pro syst´em Windows. Tak´e komprimaˇcn´ı program kkrunchy slouˇz´ı pro komprimov´ an´ı bin´ arn´ıch spustiteln´ ych soubor˚ u syst´emu Windows.
4.1
Hudba
Pro pˇrehr´ av´ an´ı hudby v intru jsem pouˇzil knihovnu libv2 od nˇemeck´e skupiny Farbrausch [4]. Ke knihovnˇe je dod´ av´ an i pˇr´ıklad pˇrehr´avaˇce soubor˚ u v2m. Pˇrehr´avaˇc byl naps´an v jazyce C pro Visual Studio. Nˇekter´e ˇc´asti k´odu byly naps´any v jazyce assembler a ty bylo nutn´e pˇrepsat. Pro skl´ ad´ an´ı hudby je ke knihovnˇe pˇrid´an i VSTi plugin, zobrazen na obr´azku 4.1. Hudbu jsem skl´ adal v demo verzi programu FL Studio [7] a pouˇzil jsem tento VSTi plugin.
Obr´ azek 4.1: VSTi plugin pro tvorbu hudby pro knihovnu libv2.
36
4.2
Sc´ eny intra
Intro obsahuje ˇctyˇri sc´eny. Horskou sc´enu, pˇr´ımoˇrskou sc´enu, tunel a jeskyni. Mezi sc´enami je plynule pˇrep´ın´ ano pomoc´ı zatm´ıvaˇcek. Zatm´ıvaˇcka je ˇcern´a plocha. Tato plocha je kreslena s vypnut´ ym hloubkov´ ym testem. Ovlivˇ nov´an´ım pr˚ uhlednosti m˚ uˇzeme plynule pˇrej´ıt mezi sc´enami. V intru se vyskytuj´ı tyto objekty: hory, kopce, skybox, vodn´ı hladina, vodop´ady, bublinky ve vodˇe, chom´ aˇce rostlin, li´anov´e rostliny, bedny, tunel, jeskynˇe a zavˇeˇsen´e barevn´e koberce.
4.2.1
Horsk´ a sc´ ena
Sc´ena s horskou sc´enou je na obr´azku 4.2. Pro vytvoˇren´ı ter´enu je pouˇzita v´ yˇskov´a mapa. V´ yˇskov´ a mapa je vytvoˇrena ze vzd´alenostn´ıho pole Voron´eho diagram˚ u, prav´a strana obr´azku 3.4. Ve vzd´ alenostn´ım poli se vyskytuj´ı ˇspiˇcky (horsk´e ˇst´ıty) a propoje (hˇrebeny). Na hory je namapov´ ana bump mapa, kter´a vytv´aˇr´ı sk´aly. Barva hor je vytvoˇrena dvojic´ı barevn´ ych pˇrechod˚ u. Jeden barevn´ y pˇrechod je pouˇzit stejn´ ym zp˚ usobem jako na obr´azku 3.9. T´ımto zp˚ usobem z´ısk´ ame barvu s nadmoˇrskou v´ yˇskou. Druh´ y barevn´ y pˇrechod je pouˇzit pro obarven´ı sr´ az˚ u. V´ ybˇer barvy z pˇrechodu je stejn´ y jako u prvn´ıho pˇrechodu - pomoc´ı v´ yˇsky. Barva je ale pˇrim´ıch´ av´ ana pomoc´ı pr˚ uhlednosti. Pr˚ uhlednost je urˇcena podle strmosti sr´azu - podle norm´ aly n = (u, v, w). Pokud je sloˇzka |v| = 1 je pr˚ uhlednost maxim´aln´ı. Pˇri |v| = 0 je pr˚ uhlednost minim´ aln´ı. Kolem hor je skybox, kter´ y je zobrazen na obr´azku 3.18. S rostouc´ı vzd´ alenost´ı se hory noˇr´ı do mlhy. Hustota mlhy je vyˇsˇs´ı s menˇs´ı nadmoˇrskou v´ yˇskou.
Obr´azek 4.2: Horsk´a sc´ena.
4.2.2
Pˇ r´ımoˇ rsk´ a sc´ ena
Pˇr´ımoˇrsk´ a sc´ena zobrazena na obr´azku 4.3 je vytvoˇrena pomoc´ı v´ yˇskov´e mapy vytvoˇren´e ze ˇsumu. Stejnˇe jako u hor, jsou pro obarven´ı pouˇzity dva barevn´e pˇrechody. Skybox kolem 37
pˇr´ımoˇrsk´e oblasti m˚ uˇzeme vidˇet na obr´azku 3.23.
Obr´azek 4.3: Pˇr´ımoˇrsk´a sc´ena.
4.2.3
Tunel, jeskynˇ e
Tunel i jeskynˇe jsou vytvoˇreny stejn´ ym zp˚ usobem, pomoc´ı algoritmu Marching Tetrahedra. Rozd´ıl spoˇc´ıv´ a ve vytvoˇren´ı trojrozmˇern´eho pole volumetrick´e reprezentace. U jeskynˇe je zp˚ usob vytvoˇren´ı pole jednoduch´ y. Vygenerujeme trojrozmˇern´ y ˇsum pomoc´ı algoritmu ˇ p˚ ulen´ı intervalu. Sum pot´e vyhlad´ıme pomoc´ı glob´aln´ı transformace. Pot´e budeme hodnoty pole n´asobit koeficientem k = h0, 1i. Hodnota koeficientu k kles´a, pokud se vzdalujeme od stˇredu krychle obsahuj´ıc´ı ˇsum. T´ımto zajist´ıme, aby se jeskynˇe uzavˇrela a nemˇela ve stˇen´ ach d´ıry. V´ yslednou objemovou reprezentaci jeskynˇe pˇrevedeme pomoc´ı algoritmu Marching Tetrahedra na troj´ uheln´ıky. Objemov´ a reprezentace tunelu je vytvoˇrena jin´ ym zp˚ usobem. Nejprve vytvoˇr´ıme trojrozmˇern´ y ˇsum stejnˇe jako u jeskynˇe. Hodnoty ˇsumu zmenˇs´ıme tak, aby nebyly vˇetˇs´ı neˇz pr´ ah ’ pro algoritmus Marching Tetrahedra. Pokud bychom ted provedli pˇrevod na troj´ uheln´ıky, ˇz´adn´ y troj´ uheln´ık by nevznikl. Nyn´ı do pole vykresl´ıme tunel. Tunel budeme vykreslovat po bodech. Body leˇz´ı na kˇrivce podobn´e jednomu vl´aknu blesku. Konce kˇrivky um´ıst´ıme na opaˇcn´e rohy krychle ˇsumu. Kˇrivka je reprezentov´ana dvˇema jednorozmˇern´ ymi ˇsumy. Jeden ovlivˇ nuje natoˇcen´ı kolem spojnice poˇc´ateˇcn´ıho a koncov´eho bodu kˇrivky. Druh´ y ovlivˇ nuje vzd´alenost od spojnice. Tuto kˇrivku vykresl´ıme do pole nˇekolikr´at a vznikne n´am tak tunel zobrazen´ y na obr´ azku 4.6 Textury v tunelu jsou rozm´ıstˇeny stejnˇe jako v jeskyni. Jeskynˇe je obarvena pomoc´ı nˇekolika textur: Textury stropu, textury stˇen a textury zemˇe. Kaˇzd´a z tˇechto textur m´ ak sobˇe i bump mapu. Dalˇs´ı textura je jednorozmˇern´a a je um´ıstˇena vertik´alnˇe. Pˇredstavuje geologick´e vrstvy. Dalˇs´ı textura je trojrozmˇern´a. Je vytvoˇrena pomoc´ı distanˇcn´ıho pole z Voron´eho diagram˚ u a reprezentuje kaustiky. Textura je trojrozmˇern´a, abychom mohli kaustiky animovat. Posledn´ı textura je tak´e trojrozmˇern´a a je dynamicky mˇenˇena. Pˇredstavuje vlhkost stˇen jeskynˇe. Vodop´ady do n´ı zapisuj´ı hodnoty a textura samotn´a ovlivˇ nuje 38
m´ıru odlesk˚ u a tmavost povrchu. V tunelu jsou um´ıstˇeny chom´ aˇce rostlin. Jedn´a se o ˇc´asticov´ y syst´em, jehoˇz ˇc´astice jsou statick´e. Textura ˇc´ astic je zobrazena v lev´e ˇc´asti obr´azku 4.4. Na konci tunelu je vodn´ı hladina. V tunelu se vyskytuje i pavuˇcina. Pavuˇcina je sloˇzena z elastick´eho syst´emu a m˚ uˇzeme ji vidˇet uprostˇred obr´ azku 4.6. V jeskyni jsou zavˇeˇseny li´ anov´e rosliny. Rostliny jsou sloˇzeny z elastick´eho syst´emu, jehoˇz tvar je v prav´e ˇc´ asti obr´ azku 4.4. Jeden ˇcl´anek rostliny je sloˇzen ze dvou spojen´ ych ˇctyˇrstˇen˚ u. V bodech je um´ıstˇena textura rosliny zobrazena v lev´e ˇc´asti obr´azku 4.4. Dalˇs´ım objektem jeskynˇe je zavˇeˇsen´ y koberec. Koberec je tak´e sloˇzen z elastick´eho syst´emu ve tvaru mˇr´ıˇzky. Na koberec je nanesena textura na obr´azku 4.5
Obr´azek 4.4: Vlevo: textura rostlin. Vpravo: rozloˇzen´ı uzl˚ u a spoj˚ u elastick´eho syst´emu li´anov´e rostliny.
Obr´ azek 4.5: Textura zavˇeˇsen´eho koberce.
4.3
GLSL
V intru jsem pouˇzil sedm shader program˚ u. Tˇri z nich pouˇz´ıvaj´ı i geometry shader. Jsou to shader programy vyuˇz´ıvan´e ˇc´ asticov´ ymi syst´emy. O vytvoˇren´ı ˇc´astice (ploˇsky) se star´a geometry shader. Pro ˇc´ asticov´e syst´emy je vyhrazen vlastn´ı shader program. Pomoc´ı uniformu lze nastavit, jestli se ˇc´ astice nat´ aˇc´ı ke kameˇre ˇci udrˇzuje svoji orientaci. Shader program, kter´ y v intru pouˇz´ıv´ame pro vykreslen´ı jeskynˇe m´a nejsloˇzitˇejˇs´ı ˇc´ ast fragment shader. Jeskynˇe obsahuje pomˇernˇe mal´e mnoˇzstv´ı troj´ uheln´ık˚ u a pˇresto je nejsloˇzitˇejˇs´ı na vykreslen´ı. Sn´ıˇzen´ım poˇctu troj´ uheln´ık˚ u bychom sloˇzitost nesn´ıˇzili. Jednou
39
Obr´azek 4.6: Tunel. moˇznost´ı je optimalizovat fragment shader. Vhodnou optimalizac´ı m˚ uˇze b´ yt minimalizace vˇetven´ı programu pouˇzit´ım vestavˇen´ ych funkc´ı. Pˇr´ıklad vˇetven´ı: if (red_flag == 1){ color = vec3(1,0,0); }else{ color = texture(wall,coord); } V´ yˇse uveden´ y u ´sek programu obsahuje vˇetven´ı pomoc´ı uniformu red f lag. M˚ uˇzeme se vˇetven´ı zbavit vyuˇzit´ım vestavˇen´e funkce mix. color=mix(vec3(1,0,0),texture(wall,coord),red_flag); Dalˇs´ı funkce, kter´e se daj´ı pouˇz´ıt pro odstranˇen´ı vˇetven´ı jsou min, max, clip, clamp a dalˇs´ı. Jinou moˇznost´ı je omezen´ı pouˇz´ıv´an´ı mnoˇzstv´ı normalizaˇcn´ı funkce: normalize. Urychlen´ı vykreslen´ı sc´eny se sloˇzit´ ym fragment shaderem m˚ uˇzeme udˇelat i jinak. Urychlen´ı spoˇc´ıv´ a v omezen´ı mnoˇzstv´ı fragment˚ u, kter´e mus´ıme vykreslit. Pˇri vykreslov´an´ı se st´av´a, ˇze jsou troj´ uheln´ıky kresleny ve ˇspatn´em poˇrad´ı. Vykreslujeme nˇekter´e fragmenty, kter´e jsou pozdˇeji ˇ sen´ı m˚ pˇreps´any nov´ ymi hodnotami. Reˇ uˇze existovat v algoritmu ˇrazen´ı troj´ uheln´ık˚ u. Potom staˇc´ı vykreslovat od nejbliˇzˇs´ıch troj´ uheln´ık˚ u. V pˇr´ıpadˇe, ˇze je nˇejak´a ˇc´ast troj´ uheln´ıku ˇ zakryta, je vykreslov´ an´ı zastaveno hloubkov´ ym testem. Razen´ ı troj´ uheln´ık˚ u je ale sloˇzit´e na v´ ypoˇcet a zbyteˇcnˇe by n´ am zabralo m´ısto v programu. Jeskynˇe ale obsahuje m´ alo troj´ uheln´ık˚ u, proto vykresl´ıme nejprve hloubkov´ y buffer s vypnut´ ym z´apisem barvy. T´ım se pˇreskoˇc´ı ˇc´ ast s fragment shaderem. Pot´e vykresl´ıme sc´enu znovu, tentokr´at jiˇz s povolen´ ym z´apisem barvy. T´ımto zajist´ıme, ˇze se v´ ypoˇcet fragment shaderu prov´ad´ı jen pro nezbytnˇe nutn´e mnoˇzstv´ı fragment˚ u. 40
Obr´azek 4.7: Jeskynˇe.
4.4
Rozdˇ elen´ı projektu a FPS
Zdrojov´e k´ ody pˇresahuj´ı 20 000 ˇr´ adk˚ u k´odu, proto je bylo potˇreba kv˚ uli pˇrehlednosti rozdˇelit do logick´ ych celk˚ u. Projekt je rozdˇelen do velk´eho mnoˇzstv´ı knihoven. Ve zdrojov´ ych k´odech pro Linux jsou knihovny rozdˇeleny do nˇekolika sloˇzek: app V t´eto sloˇzce jsou funkce pro obsluhu vytvoˇren´ı okna a ˇcasov´an´ı. winwindow Knihovna obsahuje funkce pro vytvoˇren´ı okna, nastaven´ı obsluˇzn´ ych funkc´ı. D´ ale obsahuje ˇr´ızen´ı ˇcasem. Knihovna je preprocesorem rozdˇelena do dvou ˇc´ ast´ı. Jedna ˇc´ ast je pro syst´em Windows 7 a obsahuje k´od ve WINAPI. Druh´ a ˇc´ ast je pro syst´em Linux a vyuˇz´ıv´a funkc´ı knihovny SDL. main Obsahuje hlavn´ı ˇc´ ast programu, vˇetˇsinu inicializac´ı a krokov´an´ı. Obsahuje kresl´ıc´ı funkci. adt Sloˇzka obsahuje abstraktn´ı datov´e typy. list2 Obsahuje obecn´ y dvousmˇern´ y seznam. relist Reprezentuje obecn´e pole s automatick´ ym zvˇetˇsov´an´ı velikost. Oproti list2 je rychlejˇs´ı ˇcten´ı, ale pomalejˇs´ı vkl´ad´an´ı doprostˇred pole. ntree Pˇredstavuje obecn´ y strom a obsluˇzn´e funkce. adtfce, adt Obsahuj´ı rozhran´ı a funkce spoleˇcn´e pro abstraktn´ı datov´e typy. elastic Sloˇzka obsahuje pouze jednu knihovnu, kter´a implementuje elastick´ y syst´eme a jeho obsluˇzn´e funkce enviroment Ve sloˇzce nalezneme knihovny pro grafick´e objekty intra. box swarm Knihovna obsahuje funkce pro inicializaci, um´ıstˇen´ı, vykreslen´ı a pˇrepoˇc´ıt´ an´ı haldy beden. 41
bubble Knihovna obsahuje ˇc´asticov´ y syst´em reprezentuj´ıc´ı bublinky ve vodˇe. carpet Objekt zavˇeˇsen´eho koberce je obsahem t´eto knihovny. cave Obsahuje funkce pro vygenerov´an´ı jeskynˇe. collide Obsahuje kolizn´ı syst´em. fade Zatm´ıvaˇcka, kter´ a slouˇz´ı pro pˇrechod mezi sc´enami font Obsahuje funkce a font pro vykreslen´ı textu. geometry V knihovnˇe m˚ uˇzeme naj´ıt funkce pro v´ ypoˇcet norm´al a v´ ypoˇcet spoj˚ u pro elastick´ y syst´em. lake Vodn´ı hladina a obsluˇzn´e funkce jsou obsaˇzeny v t´eto knihovnˇe. moss Obsahem knihovny je objekt mechu nebo kˇrov´ı. mountain, waterside Obsahuj´ı funkce pro vytvoˇren´ı v´ yˇskov´ ych map hor a pˇr´ımoˇrsk´ ych kopc˚ u. object Soubory knihovny reprezentuj´ı obecn´ y objekt, kter´ y vyuˇz´ıv´a elastick´ y syst´em. particle Nalezneme zde obecn´ y ˇc´asticov´ y syst´em, kter´ y je vyuˇz´ıv´an napˇr´ıklad v knihovnˇe bubble. plant Rostlina sloˇzen´ a z elastick´eho syst´emu. skybox Obsahuje funkce pro vykreslen´ı skyboxu. skyboxgenerate Vytvoˇren´ı skyboxu je souˇc´ast funkc´ı v souborech t´eto knihovny. spiderweb Knihovna reprezentuje pavuˇcinu. terrain Vykreslen´ı a vytvoˇren´ı geometrie ter´enu pomoc´ı v´ yˇskov´ ych map. tunnel Obdobnˇe jako cave obsahuje knihovna funkce pro vygenerov´an´ı tunelu. gen Sloˇzka obsahuje nˇekter´e obecn´e algoritmy pro generov´an´ı. color Obsahuje funkce pro pr´aci s HSV barevn´ ym modelem. map, colormap Funkce pro pr´aci s barevn´ ym pˇrechodem. midpoint Algoritmus pro generov´an´ı ˇsumu pomoc´ı p˚ ulen´ı intervalu. voronoi Generov´ an´ı Voron´eho diagram˚ u. gpu Sloˇzka obsahuje knihovny pro komunikaci s grafickou kartou. gpuattribute Funkce pro pr´aci s atributy shader programu. gpubuffer Obsahuje funkce pro spr´avu buffer˚ u na grafick´e kartˇe. gpushaderprogram Obsahuje obsluˇzn´e funkce pro shader programy. gputexture Inicializace a spr´ava textur. gputextureunit Obsluha texturovacich jednotek. index Knihovny pro pr´ aci s v´ıcerozmˇern´ ymi daty. index Knihovna obsahuje obecn´ y d dimenzion´aln´ı index. nsize Rozmˇery d dimenzion´aln´ıch dat. marchingtetra Sloˇzka obsahuje algoritmus Marching tetrahedra. 42
mt core Algoritmus Marching tetrahedra. pack Algoritmus pro spojov´an´ı spoleˇcn´ ych vrchol˚ u troj´ uheln´ık˚ u. music Sloˇzka obsahuje pˇrehr´ avaˇc a hudebn´ı soubory. music Funkce pro inicializace a pˇrehr´an´ı hudby. songs Hudebn´ı skladby. v2mplayer Pˇrehr´ avaˇc hudby. mymath Sloˇzka obsahuje matematick´e knihovny. camera Kamera sc´eny. cameracontrol Syst´em pro pohyb kamery. vector, matrix Operace s vektory a maticemi. stdmath Z´ akladn´ı matematick´e vztahy. transform Transformace sc´eny. mymem Sloˇzka obsahuje knihovnu pro pr´aci s pamˇet´ı a zastˇreˇsuje rozd´ıly mezi syst´emy Windows a Linux. shaderprogram Obsahem sloˇzky jsou vertex, geometry a fragment shadery. std Z´akladn´ı funkce. Funkce pro generov´an´ı n´ahodn´eho ˇc´ısla. Funkce pro zobrazen´ı grafu naˇc´ıt´ an´ı. texturefactory Sloˇzka obsahuje knihovny pro generov´an´ı textur. colorbuffer Obsahuje funkce pro pr´aci s d rozmˇern´ ymi poli pro vytvoˇren´ı textur. convolution Obsahuje d rozmˇernou konvoluci. fastgetvalue Obsahuje obtimalizovan´e funkce pro pˇr´ıstup k d rozmˇern´ ym pol´ım. globaltransform Obsahuje glob´aln´ı transformaˇcn´ı funkce pro tvorbu textur. localtransform Obsahuje lok´aln´ı transformaˇcn´ı funkce pro tvorbu textur.
43
4.4.1
FPS
V grafu zobrazen´em na obr´ azku 4.8 m˚ uˇzeme vidˇet pr˚ ubˇeh poˇctu sn´ımku za sekundu (FPS) v ˇcase. V prvn´ıch dvou ˇc´ astech grafu FPS hodnˇe kol´ıs´a. V ostatn´ıch ˇc´astech FPS udrˇzuje pˇribliˇznˇe konstantn´ı hodnotu. Prvn´ı dvˇe sc´eny zobrazuj´ı horskou a pˇr´ımoˇrskou krajinu. Kaˇzd´a z tˇechto sc´en je sloˇzena z 130 050 troj´ uheln´ık˚ u. Z´aleˇz´ı proto na pozici a z´abˇeru kamery, jak velk´ a bude hodnota FPS. Lok´aln´ı maxima poukazuj´ı na m´ısta v intru, kde kamera zab´ır´ a jen zlomek sc´eny. Pˇr´ıkladem m˚ uˇze b´ yt ˇspiˇcka v druh´e sc´enˇe. V pˇr´ımoˇrsk´e oblasti se kamera chv´ıli d´ıv´ a jen na skybox. To vysvˇetluje velk´ y n´ar˚ ust FPS. V posledn´ıch dvou sc´en´ ach: tunelu a jeskynˇe je ˇr´adovˇe m´enˇe troj´ uheln´ık˚ u. Proto tolik nez´avis´ı na z´abˇeru kamery. Prvn´ı dvˇe sc´eny jsou n´ aroˇcnˇejˇs´ı z pohledu mnoˇzstv´ı troj´ uheln´ık˚ u. Posledn´ı dvˇe sc´eny pak z pohledu shader programu, kter´ y je sloˇzitˇejˇs´ı.
I
II
III
IV
FPS
350
250
150
50
t Obr´azek 4.8: Pr˚ ubˇeh poˇctu sn´ımku za sekundu v ˇcase. Graf je rozdˇelen do ˇctyˇr ˇc´ast´ı podle sc´en.
44
Kapitola 5
Z´ avˇ er ˇ ast textu jsem pˇrevzal s drobn´ C´ ymi u ´pravami ze semestr´aln´ıho projektu. Jedn´a se o ˇc´asti aˇz po sekci Generov´ an´ı geometrie 3.6. Text semestr´aln´ıho projektu proˇsel u ´pravami a byl pˇreps´an do syst´emu Latex. Celkov´a velikost intra nepˇres´ahla 64kB. Intro obsahuje 4 sc´eny. Kaˇzd´a z nich je ozvuˇcen´ a hudbou, kterou jsem sloˇzil. V pr˚ ubˇehu projektu mne napadlo velk´e mnoˇzstv´ı rozˇs´ıˇren´ı a vylepˇsen´ı. Nˇekter´e jsem implementoval a na nˇekter´e nezbyl ˇcas. Moˇzn´ ym rozˇs´ıˇren´ım intra by mohlo b´ yt pˇrid´ an´ı statick´ ych a dynamick´ ych st´ın˚ u. Jin´e rozˇs´ıˇren´ı by spoˇc´ıvalo v implementaci SSAO (screen space ambient occlusion). Dalˇs´ı moˇznost´ı by mohlo b´ yt generov´an´ı geometrie v pr˚ ubˇehu animace. Naimplementovat Marching Tertahedra algoritmus v shader programu OpenGL. Naimplementovat jin´e ˇsumy. Pˇr´ıkladem m˚ uˇze b´ yt Simplex Noise. Tento ˇsum implementovat v shader programu. Vhodn´a by mohla b´ yt implementace ˇsumu, kter´ y netrp´ı aliasing efektem. Pˇripojit dynamiku rigidn´ıch tˇeles a spojit ji s dynamikou elastick´ ych tˇeles. Pˇridat sloˇzitˇejˇs´ı detekci koliz´ı. Pˇrev´est v´ ypoˇcet elastick´ ych syst´emu do OpenCL a t´ım jej urychlit. Pˇresunout ˇcasov´ an´ı do zvl´aˇstn´ıho vl´akna. Vyzkouˇset dalˇs´ı numerick´e metody pro ˇreˇsen´ı diferenci´ aln´ıch rovnic. Napˇr´ıklad implicitn´ı Eulerovu metodu nebo metodu s vyuˇzit´ım Taylorova rozvoje. Rozˇs´ıˇren´ı projektu z jin´eho u ´hlu pohledu by mohlo spoˇc´ıvat v automatizovan´em generov´ an´ı hudby. Vytvoˇren´ı algoritm˚ u pro generov´an´ı zvuk˚ u. Pˇrid´an´ı ˇziv´ ych organizm˚ u s umˇelou inteligenc´ı: ryby ve vodˇe, pavouk, poletuj´ıc´ı muˇsky... M´ısto rozˇsiˇrov´ an´ı intra by bylo moˇzn´e nˇekter´e vlastnosti oddˇelit a vyv´ıjet je jako samostatn´ y projekt. Napadlo mˇe nˇekolik takov´ ych projekt˚ u. Efektivn´ı generov´an´ı textur v shader programu. Fyzik´aln´ı engine. Prozkoum´ an´ı d dimenzion´aln´ı alternativy algoritmu Marching Tetrahedra. V pr˚ ubˇehu projektu jsem se nauˇcil hodnˇe nov´ ych vˇec´ı a vyzkouˇsel nˇekolik r˚ uzn´ ych alternativn´ıch ˇreˇsen´ı probl´emu. Pˇr´ıkladem necht’ je algoritmus Marching tetrahedra, kter´ ym jsem nahradil Marching cubes. Dalˇs´ı pˇr´ıkladem je implementace numerick´e metody Runge Kutta, kter´ a nahradila Eulerovu metodu. Implementoval jsem dobr´ y z´aklad pro generov´ an´ı textur, kter´ y je dostateˇcnˇe obecn´ y, aby byl znovupouˇziteln´ y. Implementoval jsem generov´ an´ı Voron´eho diagramu a ˇsumu obecn´e dimenze. Vytvoˇril jsem funkce, kter´e dok´aˇzi s d dimenzion´aln´ımi daty pracovat. Vytvoˇril jsem obecn´ y elastick´ y a ˇc´asticov´ y syst´em. Rozˇs´ıˇril jsem si svoje znalosti jazyka GLSL a spr´avy velk´eho projektu jako takov´eho. Bˇehem pr´ace na projektu jsem ˇreˇsil ˇradu probl´em˚ u v podobˇe pˇreklep˚ u nebo pouˇzit´ı nevhodn´e metody. Nejvˇetˇs´ı probl´em ale byl ukonˇcit tv˚ urˇc´ı ˇcinnost v urˇcit´em bodˇe a projekt dokonˇcit. Napadalo mne hodnˇe vylepˇsen´ı a rozˇs´ıˇren´ı a bylo tˇeˇzk´e se rozhodnout je jiˇz do projektu nezahrnovat. Pˇres vˇsechny probl´emy jsem se pˇri vyv´ıjen´ı projektu bavil a co je nejd˚ uleˇzitˇejˇs´ı - rozˇs´ıˇril jsem si znalosti.
45
46
Literatura [1] Aurenhammer, F.: Voronoi Diagrams – A survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 1991. [2] Chernyaev, E. V.: Marching Cubes 33: Construction of Topologically Correct Isosurfaces. Institute for High Energy Physics, 1995. [3] Elias, H.: Perlin Noise. http://freespace.virgin.net/hugo.elias/models/m_perlin.htm. [4] Farbrausch: V2 synthesizer system. http://1337haxorz.de/products.html. [5] Geiss, R.; Thompson, M.: Cascades. NVIDIA Corporation, 2006. [6] Giesen, F.: kkrunchy. http://www.farbrausch.de/~fg/kkrunchy/. [7] Image-Line: FL Studio. http://www.image-line.com/index.html. [8] Joy, K. I.: Catmull-Rom splines. 2002. [9] Lewiner, T.; Lopes, H.; Vieira, A. W.; aj.: Efficient implementation of Marching Cubes’ cases with topological guarantees. Laborat´orio MatM´ıdia, 2003. [10] Mateas, M.; Montfort, N.: A Box, Darkly: Obfuscation, Weird Languages, and Code Aesthetics. Proceedings of the 6th Digital Arts and Culture Conference. IT University of Copenhagen, 2005. [11] Milet, T.: Grafick´e intro 64KB s pouˇzit´ım OpenGL [bakal´ aˇrsk´ a pr´ ace]. FIT VUT, 2010. [12] Moln´ ar, L.; Reiser, J. F.: Ultimate Packer for eXecutables. http://upx.sourceforge.net/. [13] Perlin, K.: Making Noise. http://www.noisemachine.com/talk1/index.html. [14] Scott, J.: Making Cellular Textures. http://www.blackpawn.com/texts/cellular/default.html.
47
