UL/FRI/UNI-RI/RG

Stran vsebuje pregled snovi, ki se obravnava pri predmetu Računalnika grafika. Povzetek je narejen po zgoščenih prosojnicah s predavanj.

Predmeti v prostoru

• koordinatni sistem (2D, desnoročni 3D, levoročni 3D)
• osnovne transformacije (translacija, rotacija, zrcaljenje, striženje, povečava, identiteta)
• homogene koordinate, afine transformacije (dodamo še eno dimenzijo, za lažje računanje)
• sestavljanje afinih transformacij - množenje matrik (vrstni red množenja je pomemben!)
• afine transformacije so linearne (ravne črte ostanejo ravne, ohranja se vzporednost, razmerja)
• Eulerjev teorem: Poljubna rotacija (ali zaporedje rotacij) okrog neke točke je ekvivalentna eni sami rotaciji okrog neke osi skozi to točko.
• poljubno 3D rotacijo lahko dosežemo z vrtenji okoli osi x, y in z
• problem kardanske zapore (dve osi vrtenja se poravnata med seboj)
• kvaternioni
  • rešitev problema s kardansko zaporo
  • namesto vrtenja predmeta z zaporedjem rotacij, omogoča kvaternion vrtenje predmeta preko ene same poljubne osi
  • os vrtenja podana kot enotin vektor → lahko uporabimo vektorsko matematiko ali sferične koordinate
  • razširitev kompleksnih števil, četvorček [s,x,y,z] oziroma dvojček [s,v] - s je skalar, v vektor
• cevovod gledanja (viewing pipeline)
• stožec gledanja (frustrum)

Tehnike izločanja

• clipping - obrezovanje primitivov
• obrezovanje črt
  • Cohen-Sutherland algoritem (kodiranje področij)
  • Cyrus-Beck algoritem (parametrizacija)
  • (Liang-Barsky - izboljšan Cyrus-Beck algoritem)
• obrezovanje poligonov
  • Sutherland-Hodgeman (režemo po robovih okna)
  • pri 3D obrezovanju poligonov je dovolj, da režemo glede na stožec gledanja - uporabimo Cohen-Sutherland algoritem s 6-bitno kodo področij

• izločanje nevidnih ploskev
  • predmeti izven stožca gledanja
  • zakrite ploskve
    • prostor predmetov (pred rasterizacijo, na matematičnem nivoju objektov)
    • prostor slike (po rasterizaciji, na točkah)
  • zadnje ploskve (normala kaže stran od točke gledanja)
• algoritmi izločanja zakritih ploskev
  • Z-buffer
  • slikarjev algoritem, urejanje po globini (Depth sort)
  • BSP drevesa
  • delitev površine (Warnock)
  • obsegi, test minmax
  • tabela oglišč in ploskev

• izločanje podrobnosti
• celice in portali

Modeliranje

• modeliranje je proces tvorbe 3D objektov

• predstavitve modelov:
  • poligonske mreže (oglišča, ploskve, normale; največkrat množica trikotnikov - vedno so ravninski, grafične kartice so optimizirane za delo z njimi)
  • trdni modeli (CSG - constructive solid geometry)
  • tehnike s porazdeljevanjem prostora (prostor razdelimo na veliko majhnih koščkov, kockic; voksli ≈ '3D piksli')
  • implicitne predstavitve (implicitne enačbe, meta krogle... - uporaba predvsem v animacijah, kjer objekti spreminjajo obliko)
  • parametrične krpe (uporabno za modeliranje glajenih ukrivljenih ploskev, oblika se lahko dinamično spreminja)

• triangulacija - ustvarjanje trikotnikov na množici površinskih točk
• matematična generacija modela (vrtenine in "izrivanje")
• NURBS krivulje in ploskve
• koniki, kvadrniki, superkvadrniki
• metode 3D digitalizacije:
  • slike z označenimi robovi
  • skeniranje resničnih objektov (laser, CT, MRI, radar)
  • SIFT algoritem (Scale Invariant Feature Transform - razpoznavanje objektov, panoram...)

• hierarhična struktura:
  • drevesna struktura modela
  • hierarhije obsegajočih volumnov (BVH - Bounding Volume Hierarchies)
  • dvojiška drevesa za delitev prostora (BSP trees - Binary Space Partitioning Trees)
    • glavni namen je sortiranje po globini
    • osno poravnana BSP (AABB - Axis-Aligned BSP Trees, rekurzivna delitev na majhne pravokotnike)
    • poligonsko poravnana BSP (kot delilnik vzamemo ravnino v kateri leži nek poligon; če kakšen poligon seka ravnino, ga moramo razdeliti; to počnemo rekurzivno, dokler niso vsi poligoni v drevesih BSP)
  • osmiška drevesa (octrees, podobna osno poravnanim BSP drevesom)

• modeliranje osebkov: skelet (uporabimo zrcaljenje), napenjanje kože, geometrije

Nivo podrobnosti

• LOD - level of detail
• grafični sistemi so preplavljeni s podatki o modelih, s podrobnostmi
• poenostavimo geometrijo poligonov za majhne in oddaljene objekte, za ekscentrične in premikajoče se objekte, objekte izven območja fokusa

• statična ločljivost ne zadošča (model uporabljamo v različnih kontekstih), potrebujemo večresolucijske modele
  • diskretni LOD
    • za vsak objekt tvorimo skupino nivojev podrobnosti
    • preklopi med modeli lahko povzroči "pokanje"
    • prehode lahko mehčamo z mešanjem slik
    • prednosti: v času izvajanja izberemo le nivo podrobnosti, vsak nivo lahko prevedemo v trakove trikotnikov
    • slabosti: ročno je treba določiti razdalje preklapljanja, pravilna razdalja pa se s pogledom in ločljivostjo lahko spreminja, problem velikih in majhnih objektov
  • zvezni LOD
    • tvorimo podatkovno strukturo, iz katere lahko v času izvajanja dobimo želeni nivo podrobnosti
    • objekti uporabljajo le toliko poligonov, kolikor je potrebno; boljša izraba virov
    • boljša zrnatost → večja vernost, mehkejši prehodi
  • LOD, odvisen od pogleda
    • rešitev problema pri zelo velikih objektih
    • bližnji deli objekta so prikazani v višji ločljivosti, oddaljeni bolj grobo
    • z večjo ločljivostjo prikazujemo obrobna področja predmeta
  • hierarhični LOD
    • rešitev problema z zelo majhnimi objekti
    • poenostavljamo sestave in ne posameznih predmetov

• metode poenostavljanja:
  • ročno poenostavljanje (dobro, a drago!)
  • združevanje oglišč (prostor razdelimo v celice in združujemo oglišča znotraj iste celice)
  • redčenje oglišč (razvrstimo jih glede na pomembnost, izbiramo in odstranjujemo najmanj pomembne)
  • iterativno krčenje
    • na vsakem koraku: skrčimo rob, ki najmanj stane in ažuriramo cene robov
    • preprečevanje inverzije mreže
  • krčenje parov oglišč (združujemo tudi nepovezane regije)
• algoritem VDS (variable depth search)
  • hierarhija, drevo vseh oglišč - predstavlja celoten model
  • krčimo vse pod rezom; aktivni listi predstavljajo trenutno poenostavitev
  • rez premikamo za vsako sličico posebej (optimizacija: izkoriščamo časovno koherenco, delamo le inkrementalne spremembe)
  • zapiranje vozla (folding) skrči njegova oglišča v približek, razpiranje (unfolding) pa razdeli približek spet na oglišča
  • livetris (ploskve, ki po zapiranju izginejo) in subtris (ploskve, ki po zapiranju spremenijo obliko)
• progresivne mreže

Krivulje

• eksplicitna, implicitna, parametrična predstavitev
• običajno uporabimo kubične parametrične polinome
• mešalne funkcije - polinomi, ki jih uporabimo namesto statičnih koeficientov
• iskanje krivulje skozi točke - interpolacija
  • linearna interpolacija
  • kubična Hermitova interpolacija (4 koeficienti - dve končni točki in dva odvoda krivulje)
  • interpolacija krivulj z rekurzivno pod-delitvijo, primer: DeCasteljau Recursive Subdivision Algorithm )
• iskanje krivulje, določene s kontrolnimi točkami - aproksimacija
  • Bezierove krivulje (podobne Hermitovim, 4 kontrolne točke, od teh sta dve končni točki)
  • B-zlepki (B-Splines)
• delne (segmentne) parametrične polinomske krivulje:
  • na različnih delih krivulje uporabimo različne polinomske funkcije
  • prednosti: prilagodljivost, nadzor
  • problem: zveznost na stikih
• zveznost C⁰ (skupen stik), C¹ (skupen stik in 1.odvod), C² (skupen stik ter 1. in 2.odvod)
• zlepki (splines) - funkcije, ki interpolirajo/aproksimirajo
  • C² interpolacijski zlepki
  • Bezierovi in Hermitovi zlepki
  • Catmull-Rom in Kochanek-Bartels zlepki
  • Beta zlepki (β-Splines)
  • B-zlepki
    • rešujejo 2 glavna problema pri Bezieru: globalna kontrola kontrolnih točk in odvisnost med stopnjo krivulje in številom kontrolnih točk
    • podamo število kontrolnih točk, nato se avtomatsko konstruira nabor kubičnih krivulj, za katere velja C²
    • ne interpolirajo (se ne dotikajo) nobene od kontrolnih točk
  • uniformni B-zlepki (Uniform B-Splines, vse mešalne funkcije so enake)
  • NURBS (Non-Uniform Rational B-Splines - ne-uniformni racionalni B-zlepki; zelo popularna predstavitev krivulj)
• racionalne krivulje (definirane v 4D prostoru in projicirane v 3D prostor - lahko določimo uteži na kontrolne točke)

Ploskve

• predstavitve ploskev:
  • poligonske mreže (hitrost, poljubno šivanje, strojna podpora, a slaba zveznost, težavno globalno urejanje)
  • eksplicitno izražene meje ploskev
  • implicitno izražene meje ploskev (lahko modeliramo gumijaste objekte, matematično trivialno, a slab nadzor, težko modeliranje podrobnosti)
  • parametrične ploskve
  • kvadrične ploskve
• koordinatni sistem HUV - uporaben za točke na površini; parametra u in v ustrezata širini in dolžini, h pa kaže smer normale
• izo-parametrične krivulje (en od parametrov je konstanten, drugi se spreminja)
• parametrične krpe
• Coonsove krpe (Bilinear Blended Surfaces)
  • tvorijo pravokotno mrežo, interpolirano med štirimi mejne krivulje
  • omogočajo omejeno možnost zveznega prehoda med krpami)
  • prednosti: hitrost, enostavnost, zveznost omejena le z mejnimi krivuljami
  • slabosti: ne minimizirajo energije(?), pri ekstrapolaciji v približno singularnih ogliščih lahko pride do pregiba
• Bézierove krpe (temeljijo na Bézierovih krivuljah)
• krpe z B-zlepki (B-Spline Patches)
  • matematično elegantne formule, dobro poznana tehnika, zveznost C², a težko modeliranje ostrih in zavitih robov, zahtevajo odpravo špranj
• ploskve NURBS
  • uteži, ostri robovi, dobra kontrola, podpora v knjižnicah, a težka implementacija, orodja premalo napredna
• problem modeliranja s premiki oglišč
• problemi z zlepki in krpami:
  • težavno lepljenje (ohranjanje zveznosti, obrezovanje)
  • težavno modeliranje kompleksnih objektov
• pod-deljenje ploskev (subdivision)
  • princip: povečevanje števila kontrolnih točk in boljši vpliv na obliko krivulje
  • prednosti: enostavna metoda za opisovanje kompleksnih ploskev, relativno enostavna implementacija, zagotovljena zveznost, ni špranj, multiresolucija, omogoča ostre robove, poljubna topologija
  • slabosti: intuitivna specifikacija, parametrizacija, presečišča
• sheme pod-deljenja ploskev:
  • rezanje vogalov (Doo-Sabin, Mid-Edge)
  • dodajanje oglišč z interpolacijo (triangle based Butterfly, quad based Kabbelt)
  • dodajanje oglišč z aproksimacijo (triangle based Loop, quad based Catmull-Clark) - hitrejša konvergenca in boljše matematične lastnosti

Osvetljevanje, senčenje, upodabljanje

Osvetljevanje

• key, fill, back light
• dve komponenti osvetljevanja:
  • model osvetljevanja ali model senčenja (kako računamo intenzivnost točke na površini)
  • metoda upodabljanja ploskev (kako računamo intenzivnost v vsaki točki)
• lastnosti okolja in snovi:
  • barva okolja (ambient) - predstavlja približen prispevek svetlobe k splošni sceni, približek vseh indirektnih odbojev
  • difuzni odboj (model difuzne svetlobe: Lambertov cosinusni zakon)
  • zrcalni odboj (Phongov model osvetljevanja - empirični model za izračun osvetlitve točke na površini: približek jakosti zrcalnega odboja je sorazmerje s cosⁿΦ)
  • žarjenje, sijaj, barva oddajane svetlobe
• kar vidi opazovalec = svetloba okolja + difuzna svetloba + zrcalna svetloba
• jakost svetlobe slabi z oddaljevanjem (1/d²)

Senčenje

• plosko senčenje
  • računamo Phongovo osvetljevanje enkrat za celoten poligon
  • poudari posamezne poligone
  • prednosti: hitro, dobro za nekatere predmete
  • slabosti: nenadna sprememba jakosti na robovih, zrcalni odboji so slabo predstavljeni
• mehko senčenje (mehča robove med poligoni):
  • Gouradovo senčenje
    • računamo osvetlitev v ogliščih in nato interpoliramo osvetlitev vzdolž poligona
    • problem: slabo povprečenje oglišč
  • Phongovo senčenje
    • NI isto kot Phongovo osvetljevanje!
    • interpolacija normal vzdolž poligona in uporaba Phongovega osvetljevanja
    • bolj realistična, mehka slika, vendar računsko zahtevnejše, časovno potratno
• senčniki (shaders) - enoten opis senčenja (modeli odboja, teksture, sheme izbočenosti in odmikov, luči, atmosfera)

Teksture

• 2D in 3D lepljenje
• lepljenje tekstur (texture mapping - podrobnosti simulirane z barvo, ki se spreminja vzdolž ploskve)
• lepljenje izboklin (bump mapping - podrobnosti simulirane z normalami na ploskev, ki se spreminjajo vzdolž ploskve)
• lepljenje odmikov (displacement mapping)
• problem s 3D teksturami: kako doseči, da predmet ne bo 'plaval' skozi teksturo?
• celularne teksture
• proceduralne teksture
• uporaba šuma, šumnih funkcij

Upodabljanje

• sledenje žarku (Ray Tracing)
  • metoda upodabljanja prizora, dobra za upodabljanje površin, ki so tako odbojne kot prosojne
  • lahko realiziramo globalno osvetlitev
  • računamo le pot žarkov, ki dosežejo kamero (in ne vseh, ker bi bilo računsko prezahtevno)
  • začnemo pri kameri in ugotavljamo, kaj zadane drugi "konec" žarka
  • osvetlitev računamo rekurzivno
  • prednosti: prosojnost, odbojnost, sence
  • slabosti: težko pohitriti, ni popolna globalna osvetlitev, počasnost
  • tehnike pohitritve:
    • hitrejša sekanja
    • manj žarkov (nadzorovana globina drevesa, prilagodljivo glajenje robov)
    • posplošitev žarkov (sledenje snopu, sledenje stožcu, sledenje žarkom, ki gredo skozi skupno točko)
    • razdelitev prostora (testiranje samo na objektih, ki so vidni iz trenutnega položaja)
    • obsegajoči volumni (Bounding Volumes - le če žarek seka omejujoči volumen, testiramo tudi sam objekt)
  • sledenje žarkov deluje lažno: nazobčani robovi, trde sence, vse je v žarišču, predmeti povsem mirni, površine bleščeče, steklo povsem prozorno
• porazdeljeno sledenje žarka (žarek zamenjamo s porazdelitvijo žarkov)
  • supersampling, mehke sence, difuzno steklo, blesteče površine, zameglitev zaradi gibanja (Motion Blur), globina vidnega polja
• sevalna metoda (Radiosity)
  • upošteva tudi sevalnost, difuzno svetlobo → mehke sence, prelivanje barv, indirektna difuzna svetloba
  • enačbo upodabljanja računamo kot problem matrik
  • postopek: razdelitev ploskve na mrežo ploskev, izračun faktorjev oblike ploskev, izračun sevanja, izris
  • poenostavitev računanja faktorjev oblike:
    • algoritem polkocke (reševanje oblik, velikosti, orientacije in zakrivanja v enotnem okolju, a zobčenje robov, bližnje luči povzročajo pasove)
    • polkrogla, streljanje žarkov (boljši približek od polkocke, ni pomnjenja krp, pokrivanje računamo lažje, sledenje žarka pa je počasnejše)

Posebni učinki

• 2D krivljenje (warping)
  • 2D geometrijska transformacija, ki ob uporabi na neki sliki tvori popačeno sliko
  • dva načina:
    • preslikava naprej (forward mapping)
    • preslikava nazaj (reverse mapping) - enostavnejše
  • lahko se več točk preslika v isto območje, nastajajo pa lahko tudi luknje
  • ponovno vzorčenje (resampling): vzorčenje točk, trikotni filter, Gaussov filter
• 2D preobrazba (morphing)
  • kombiniranje objektov
  • tehnike preobrazbe slike: Cross-dissolve, Field morphing, Mesh morphing, Radial Basis Functions (RBF), Energy minimization, Multilevel Free-Form Deformation (MFFD)
  • ne ohranja nujno trdnih teles v vmesnih sličicah
• 3D krivljenje
  • glavna pristopa: deformacija modela ↔ deformacija slike (že po upodobitvi objekta)
  • manipulacija kontrolnih točk
  • krivljenje prostora, v katerem se nahajajo objekti:
    • nelinearno globalno preoblikovanje
    • Free Form Deformation (FFD)
  • krivljenje, temelječe na fiziki
• 3D preobrazba
  • interpolacija oblike in lastnosti objektov (barva, teksture...)
  • uporaba: znanost, izobraževanje, zabava, animacija
  • klasifikacija metod:
    • na osnovi predstavitve z robovi (Boundary representations-based approaches)
    • na osnovi volumna (Volume-base approaches)
  • mehka animacija objektov (za vsako sličico je ustvarjen drugačen model)
  • naivna 3D preobrazba (problem korespondence)
  • preobrazba na osnovi poligonov

Animacija

• tehnike animacije:
  • vodene s strani uporabnika: ključne sličice (keyframing), pot po krivulji, zajem gibanja (motion capture)
  • proceduralne animacije: fizikalna simulacija, sistemi delcev (paticle systems), obnašanje množic (crowd behavior)
  • podatkovno vodene animacije

• metoda s ključnimi sličicami:
  • prednosti: zelo izrazna, animator ima popoln nadzor, uporabno praktično povsod, razen za komplekse fizikalne pojave
  • slabosti: zelo delovno intenzivna, težko prikazati fizikalni realizem
• zajem gibanja:
  • prednosti: zajem tipičnega stila resničnih igralcev
  • slabosti: pogosto ne preveč izrazito, drago in časovno potratno, potrebno je veliko opreme, primeren prostor in igralci, zahtevno urejanje
  • uporabnost: animacija osebkov (character animation), medicina (kineziologija, biomehanika)
• animacija obrazne mimike: interpolacija, parametrične metode (na primer FASCIA), animacija na osnovi mišic

• kinematika upošteva le gibanje (določena s položaji, hitrostmi, pospeški), dinamika upošteva sile, ki vplivajo (računanje gibanja iz začetnih pogojev in fizike)
  • kinematika (forward kinematics - podamo pogoje v sklepih, cilj se izračuna)
  • inverzna kinematike (inverse kinematics - določimo cilj, izračunajo se pogoji, ki privedejo do cilja)

• proceduralna animacija
  • gibanje definiramo s formulami, temelječimi na fiziki, animator mora biti programer
  • tehnika ključnih sličic postane proceduralna, ko dodajamo izraze
  • pri določeni stopnji kompleksnosti, postane bolj učinkovita
  • aktivna animacija (človeški tek, plavanje ribe), pasivna animacija (listje, tekstil, delci, voda - nič mišic ali motorjev)
• sistemi delcev
  • animacija dima, ognja...
  • kompleksno (imamo množico delcev, določenih z maso, položajem, hitrostjo...)
  • poljske sile (gravitacija, veter, pritisk), viskoznost, dušenje, trki, drugi delci
  • za vsako sličico: tvorimo nove delce (okrog nekega središča, vzdolž poti...) in jim dodelimo lastnosti, zbrišemo ukinjene (po poteku življenja, naključno...), osvežimo delce glede na zakone fizike, upodobimo (prostorsko, točkovno, s črtami)
• animacija z gibanjem mišic: zelo realistično, lahko prikažemo kompleksne fizikalne pojave, a težaven nadzor in računsko intenzivno
• obnašanje množic ("delci z obnašanjem" - oseba se vede drugače če je sama ali v veliki skupini)
• visoko nivojsko obnašanje, vzajemna komunikacija, avtonomno sprehajanje, interakcija

• podatkovno vodena animacija (temelji na primer na podatkih zajema gibanja)
  • potencialno najboljša, omogoča generacijo gibanja v realnem času
  • terja veliko podatkov
  • uporaba: animacija osebkov

• umetno življenje: biomehansko modeliranje, modeliranje obnašanja, kognitivno modeliranje (UI, predstavitev znanja, razmišljanje, planiranje)

• animacije tkanin
  • pomagamo si z vzmetmi, strunami (upiranje raztegovanju, krčenju, striženju, upogibanju)
  • obnašanje tkanine: z več sosednjimi točkami kot primerjamo, bolj realistično, a zahtevnejše
  • tkanine "brez mase" (sile vplivajo na položaj točk), tkanine z maso (sile vplivajo na hitrost točk; potrebno pri dodajanju vetra)
  • problem: togost tkanin! (za reševanje uporabljamo mehke vzmeti, impulze in Jacobijevo iteracijo)

Zaznavanje trkov

• pomembno zlasti v interaktivni grafiki, navideznih okoljih, robotiki, fizikalnih simulacijah
• želimo: odkrivanje, kdaj je igralec zadel ob oviro; določanje, ali je izstrelek zadel cilj; odkrivanje točke, ko se mora obnašanje spremeniti; čiščenje animacije, simulacija gibanja nekaterih oblik (npr. tkanin)
• soroden problem: ugotavljanje razdalje med objekti (npr. Lin-Canny), izogibanje objektom
• trk = dva ali več predmetov v celoti ali delno zasedajo isto lokacijo ob istem času
• rokovanje s trki = odkrivanje trkov + odziv na trk
• odkrivanje trkov:
  • intersection/interference detection - ali se dve telesi sekata?
  • collision detection - je prišlo do trka dveh gibajočih se teles? (prostor + čas!)
• testiranje vseh parov poligonov je prekompleksno (O(N²)), zato poenostavimo:
  • prostorska delitev (enakomerna delitev, hierarhična mreža, KD drevesa, BSP drevesa)
  • večfazna strategija (ugotavljamo možnost trkov med predmeti, izločimo tiste, ki ne morejo trčiti)
  • kategorizacija predmetov (dinamični, statični...)
  • časovna kohezija (zaporedne sličice se med seboj zelo malo razlikujejo)

• različne težavnosti zaznave: konveksna toga telesa → splošna toga telesa → telesa, ki se lahko deformirajo
• algoritem izbiramo glede na geometrijo, način gibanja predmetov...
• strategije odkrivanja trkov:
  • najprej hitri, preprosti testi (test obsegajočih teles: krogle, kvadri, poravnani kvadri, prekrivanje poliedrov (k-dop), definiranimi s k/2 normalami)
  • izkoriščanje podatkov o geometriji
  • izkoriščanje časovne koherence
• odkrivanje trka s hierarhijo obsegajočih volumnov
• robusten algoritem odkrivanja trkov:
  • nikoli ne pade v neskončno zanko
  • vedno da smiseln odgovor ali pove, da odgovora ne more dati
  • sposoben obravnavati poljubne geometrijske oblike
  • sposoben odkriti probleme z vhodno geometrijo
• teorem ločitvene osi: "dva konveksna objekta sta ločena le, če obstaja os, na kateri sta njuni projekciji ločeni; če take ločitvene osi ni, se objekta sekata"
• redukcija dimenzije: dva osno poravnana kvadra (AABB) se v 3D sekata samo, če se prekrivajo njune projekcije na vse tri osi
  • algoritem Sweep and Prune (drago sortiranje, a izkorišča časovno koherenco)

• odzivi na trk:
  • temelječi na omejitvah:
    • predpostavimo povsem neelastičen trk
    • hitro, ne vnaša togosti, ni potrebno dodatno dušenje
    • podpira le trke oglišč s ploskvami, ne moremo ugotavljati trkov s samim seboj
  • kazenske sile:
    • sila vzmeti, ki odriva delce med seboj
    • uporabno za vse vrste trkov, enostavno vstavljanje v obstoječi simulator
    • težavno uglaševanje (sila ne sme biti prešibka, ne premočna, sicer ne deluje oz. povzroča lebdenje, vijuganje)
  • impulzi (hipna sprememba gibalne količine)
    • korektno ustavi vse trke (ni "spolzkih" sil vzmeti)
    • numerično potratno, slabo obravnava stalen trk
  • dinamika trdnih teles
    • zamisel: če se skupina delcev, ki začne brez trka, med časovnim korakom giblje kot trdno telo, časovni korak končajo brez trka
    • v trk vključene delce obravnavamo kot skupino in jih premikamo kot trdno telo (rigid body)
  • kombiniranje metod

• zgrešeni trki:
  • zmanjšati moramo časovni korak (recimo: uporaba rekurzivnega algoritma za iskanje trka pri manjših časovnih intervalih)
  • izogibanje hitrim gibom predmetov
  • izogibanje tankim predmetom
  • projekcija obsegajočih kvadrov (pogled vnaprej)
• simulacijo zavrtimo nazaj na točko, ko je prišlo do trka

Posebna poglavja

Algoritmi rastrske grafike

• rasterski prikazovalniki delujejo na principu mreže in že po sami naravi (za razliko od vektorskih prikazovalnikov) ne morejo prikazovati povsem gladkih krivulj oziroma črt
• piksel NI majhen kvadratek (to je le poskus predstavitve piksla)
• rasterizacija - pretvorba matematičnih definicij v piksle (le aproksimacija)
• rasterizacija črt:
  • naivna rasterizacija
  • inkrementalni algoritmi
    • DDA (Digital Differential Analyzer) - uporablja operacije s plavajočo vejico, napaka zaokroževanja se veča z dolžino črte, zaokroževanje je računsko zahtevno
    • BLA (Bresenham’s Line Algorithm, tudi Midpoint algoritem) - samo celoštevilska aritmetika; izračunamo sredino med dvema potencialnima piksloma in pogledamo, na kateri strani matematične črte leži ta točka, nato izberemo piksel, ki leži na drugi strani črte
  • približno računanje črt
• rasterizacija krogov:
  • Bresenham/Midpoint algoritem za krog
  • dovolj je, da izračunamo točke za en oktant, nato upoštevamo simetrijo
• rasterizacija poligonov:
  • splošen algoritem (Polygon scan conversion)
    • določimo presečišča skenirne vrstice (scan line) z robovi poligona, pobarvamo vmesne piksle
    • algoritem je učinkovit, vsak piksel obiščemo samo enkrat
    • če se le da, uporabimo inkrementalno celoštevilčno računanje, izkoriščamo prostorsko koherenco, koherenco prostora in skenirne vrstice
  • bilinearna interpolacija
  • vse poligone lahko razbijemo na trikotnike
• rasterizacija trikotnikov:
  • sprehod po robovih (edge walking)
    • robove rišemo vertikalno, v vsaki skenirni vrstici zapolnimo razpone
    • hitro, a lahko nastajajo luknje; nujno je izogibanje podvojenim robom
  • enačba robov (edge equation)
    • enačba roba je enačba premice, ki ta rob definira
    • trikotnik je definiran kot presečišče treh pozitivnih polprostorov
    • pobarvamo piksle, za katere se vse enačbe robov ocenijo kot >0
    • pomembna je usmeritev, površina mora biti "pozitivna"
• barvanje poligonov, barvanje področij (barvanje vseh pikslov v danem območju)

• vzorčenje in aliasing
• mehčanje robov (antialiasing)

Obdelava digitalnih slik

• preprosto spreminjanje pikslov (negativi, svetlost, kontrast, saturacija...)
• interpolacija, ekstrapolacija
• kompozicija
• konvolucija, filtri (blur, sharpen, emboss, detekcija robov...)
• razprševanje in poltoni (dithering, halftoning) - prag(threshold), Robertov algoritem, šum, urejeno razprševanje, širjenje napake
• krivljenje
• preobrazba

Nefotorealistično upodabljanje

• včasih si želimo bolj "risankasto", umetniško grafiko
• uporabimo raje koncepte iz umetnosti kot iz fizike
• silhuete in senčenje
• slikanje, uporaba plasti
• simulacija vodnih barvic, različnih vrst papirja, pigmenta...
• Cel shading - 3D objekti izgledajo kot 2D risanka

Znanstvena vizualizacija

• cilji: primerjave, razločevanje, prikaz relacij, usmeritev, predstavitev znanstvenih podatkov, izsledkov analiz, prikaz kompleksnosti, neobstoječih sistemov, rezultatov simulacij
• obrazložitev s sliko in informacijami
• vhodni podatki: izmerjeni ↔ simulirani
• klasifikacija tehnik vizualizacije:
  • tehnike s figurami (glyph techniques)
  • tehnike s ploskvami (surface methods)
  • Direct Volume Rendering
• barvne preslikave in izo površine (color maps and isosurfaces)

Dodatno branje

• Računalniška grafika
• Computer Graphics, Wikipedia