Zápoctové úkoly z Javy (skolní rok 2000/2001)
PRO ZIMU 2000/2001: ukolem kazdeho studenta bude udelat minimalne dva moduly do vyukoveho
systemu JaGrLib. Kazdou ulohu muze resit
paralelne nekolik studentu, ja si nakonec vyberu nejzdarilejsi implementace a zahrnu
je do distribuce systemu JaGrLib.
Jeden ukol muze byt lehci (oznaceny pismenem
A nebo B), druhy musi
byt tezsi (alespon C).
PRO LÉTO 2000/2001: vyberte si tema podle zajmu (3D nebo 2D grafika). Pro nektera temata
(od C vyse) se predpoklada tym >= 2 studentu. Vlastni napady
jsou vitany, jakoz i jakekoli pripominky nebo dalsi namety. Vsechny ulohy, ktere si vyberete
(a zejmena pripadna spolecna temata pro PGR004 a PGR007), konzultujte se mnou!
Technicke a organizacni podrobnosti viz "kucharka".
Vzdycky je potreba dodrzovat konvence systemu JaGrLib, zejmena:
- odvozovat nove moduly ze spolecneho predka
Piece
.
- snazit se psat kod prehledne, bude slouzit hlavne pro cteni clovekem!
Rychlost provadeni nema v nasi knihovne nejvyssi prioritu (vyjimky jsou vyslovne oznaceny).
- pokud je to mozne, navrhovat algoritmy a datove struktury maximalne obecne,
snazit se zachovat moznost napojeni na ruzne jine "krabicky".
- komentovat dusledne zdrojovy kod pomoci konvenci systemu JavaDoc
(viz me soubory - autor "PE").
- uvadet ve vsech zdrojovych kodech sve jmeno a e-mail (v komentari
@author
).
- pri kazde zmene prepsat datum posledni modifikace a oznacit pouzitou verzi
knihovny JaGrLib (komentar
@version
).
- pouzivat kontejnery z
package java.util
: (BitSet), HashMap,
HashSet, ArrayList, LinkedList, apod. + prislusne Iterator
. I zde jsou samozrejme
vyjimky potvrzujici pravidlo..
- pamatovat na to, ze zdarile moduly budou zaclenovany do distribuce JaGrLib
v
package cz.cuni.jagrlib.piece
. Pocitejte s tim, jen
v pripade nejnutnejsi potreby si vytvorte svoji "soukromou" package
uvnitr
cz.cuni.jagrlib.piece
.
Podrobnejsi zasady najdete v "kucharce".
Návrhy úloh:
Schemata uvnitr slozenych zavorek "{ }
" ukazuji navrhovane pouziti
interface. Nektere interface jeste nemusi byt naprogramovany (nebo se vyjimecne mohou stat
predmetem mensich uprav). Hranate zavorky "[ ]
" vyznacuji nepovinnou
nebo volitelnou cast.
Temata pro 3D a pokrocilou 2D grafiku jsou ohodnocena kody A
az E podle poctu lidi v tymu (A nebo B .. vlk
samotar, C nebo D .. dva studenti, E nebo F .. tri a vice studentu).
- ZÁKLADY POCÍTACOVÉ GRAFIKY (Pocítacová grafika I):
- C:
Kresleni usecky nekterym vicekrokovym algoritmem (nebylo detailne na prednasce, je treba
najit a prostudovat literaturu)
{
LineRender
nebo
LineXRender
-> BitMask
}
.
- B:
Kresleni usecky s anti-aliasingem
{
LineRender
-> AlphaMask
}
.
- A:
Kresleni kruznice Bresenhamovym algoritmem
{
CircleRender
-> BitMask
}
.
- B:
Kresleni kruznice Bresenhamovym algoritmem ve variante X (pouze dva zaznamy na radce
= pro vyplnovani)
{
CircleXRender
-> BitMask
}
.
- B:
Kresleni kruznice nejakym alternativnim algoritmem (parametricka
krivka, ..)
{
CircleRender
-> BitMask
}
.
- B:
Kresleni kruznice s anti-aliasingem
{
CircleRender
-> AlphaMask
}
.
- B:
Kresleni kruhoveho oblouku. Oblouk je zadany dvema uhly (ve stupnich) a muze
se kreslit proti nebo po smeru hodinovych rucicek
{
ArcRender
-> BitMask
}
.
- B:
Kresleni kruhoveho oblouku. Oblouk je zadany dvema uhly (ve stupnich) a muze
se kreslit proti nebo po smeru hodinovych rucicek,
varianta X
{
ArcXRender
-> BitMask
}
.
- C:
Kresleni kruhoveho oblouku s anti-aliasingem (viz predchozi ulohy)
{
ArcRender
-> AlphaMask
}
.
- A:
Kresleni elipsy s osami rovnobeznymi s X,Y
{
EllipseRender
-> BitMask
}
.
- B:
Kresleni elipsy s osami rovnobeznymi s X,Y, varianta X
{
EllipseXRender
-> BitMask
}
.
- C:
Kresleni elipsy s anti-aliasingem
{
EllipseRender
-> AlphaMask
}
.
- C:
Kresleni eliptickeho oblouku. Oblouk je zadany dvema uhly (ve stupnich) a muze
se kreslit proti nebo po smeru hodinovych rucicek
{
EllipticArcRender
-> BitMask
}
.
- C:
Kresleni eliptickeho oblouku. Oblouk je zadany dvema uhly (ve stupnich) a muze
se kreslit proti nebo po smeru hodinovych rucicek,
varianta X
{
EllipticArcXRender
-> BitMask
}
.
- D:
Kresleni eliptickeho oblouku s anti-aliasingem
{
EllipticArcRender
-> AlphaMask
}
.
- C:
Kresleni kubicke (Bezierovy) krivky: diferencni algoritmus (po pixelech nebo kratkych useckach),
vhodna implementace aritmetiky v pevne radove carce
{
CubicCurveRender
-> BitMask
}
.
- D:
Kresleni kubicke (Bezierovy) krivky s anti-aliasingem
{
CubicCurveRender
-> AlphaMask
}
.
- D:
Kresleni hranice podle kubicke (Bezierovy) krivky
{
CubicCurveXRender
-> BitMask
}
.
- C:
Vyplnovani n-uhelnika v rovine (radkovy rozklad), prepinani dvou metod: parita, stupen
obtoceni. Osetreni disjunkce sousednich n-uhelniku, implementace "fixed-point"
nebo "floating-point" aritmetikou..
{
PolygonFillRender
-> BitMask
}
.
- C:
Srafovani vnitrku mnohouhelnika (uhel a frekvence srafu). Obe metody - viz predchozi bod.
Presnost (=rovnobeznost) srafovani
{
PolygonHashRender
-> BitMask
}
.
- D:
Vyplnovani n-uhelnika v rovine s anti-aliasingem
{
PolygonFillRender
-> AlphaMask
}
.
- A:
Vyplnovani souvisle oblasti v rovine ("flood-fill") - ruzne definice hranic,
4-souvislost i 8-souvislost, ruzne algoritmy (rozdelit do nekolika uloh). Klasifikacni objekt:
{
RasterGraphics,
Property
-> BitMask
}
, vlastni vyplnovaci algoritmus: {
FloodFillRender,
BitMask
-> BitMask
}
.
- E:
Kresleni True-type pisma (kompletni font-manager vcetne cache). Cteni
.TTF
souboru, osetreni ruznych kodovani, zadavani velikosti a orientace pismen. Prevod
z True-type reprezentace do vektoroveho formatu... {
TextRender
-> BitMask
nebo AlphaMask
nebo VectorGraphics
}
.
- A:
Orezavani usecek algoritmem "Cohen-Sutherland" (kody oblasti). Vysledky v desetinne
aritmetice.
{
LineRender,
RectangleWindow
-> LineRender
}
nebo {
VectorGraphics,
RectangleWindow
-> VectorGraphics
}
.
- B:
Orezavani usecek algoritmem "Cyrus-Back" (parametricke orezavani). Vysledky v desetinne
aritmetice.
{
LineRender,
PolygonWindow
-> LineRender
}
nebo {
VectorGraphics,
PolygonWindow
-> VectorGraphics
}
.
- B:
Orezavani usecek algoritmem "Liang-Barsky" (parametricke orezavani pro obdelnikove
okno). Vysledky v desetinne aritmetice.
{
LineRender,
RectangleWindow
-> LineRender
}
nebo {
VectorGraphics,
RectangleWindow
-> VectorGraphics
}
.
- C:
Orezavani usecek nejakym jinym algoritmem (z literatury). Vysledky v desetinne aritmetice.
{
LineRender
[ PolygonWindow ]
-> LineRender
}
nebo {
VectorGraphics
[ PolygonWindow ]
-> VectorGraphics
}
.
- B:
Orezavani polygonu v rovine - "Sutherland-Hodgman" (proudove orezavani). Vysledky
v desetinne aritmetice.
{
PolygonRender,
RectangleWindow
-> PolygonRender
}
nebo {
VectorGraphics,
RectangleWindow
-> VectorGraphics
}
.
- C:
Orezavani polygonu v rovine podle konvexniho polygonu - alternativa algoritmu
"Sutherland-Hodgman" (proudove orezavani). Vysledky v desetinne aritmetice.
{
PolygonRender,
PolygonWindow
-> PolygonRender
}
nebo {
VectorGraphics,
PolygonWindow
-> VectorGraphics
}
.
- D:
Orezavani polygonu v rovine podle nekonvexniho polygonu (algoritmy najit v literature).
Vysledky v desetinne aritmetice.
{
PolygonRender,
PolygonWindow
-> PolygonRender
}
nebo {
VectorGraphics,
PolygonWindow
-> VectorGraphics
}
.
- A az C:
Pultonovani a rozptylovani - ruzne algoritmy (=mnoho uloh!).
{
Pen,
Brush,
BitMask
-> RasterGraphics
}
nebo {
RasterGraphics
-> RasterGraphics
}
.
- A az B:
Konverze mezi barevnymi systemy RGB, CMY[K], HSV, HLS apod. (ne vse bylo na prednasce).
{
ValueTransferFunction
}
nebo {
RasterGraphics
-> RasterGraphics
}
.
- B:
Zobrazovani true-color obrazku s pomoci barevne palety: pevna ("a priori") paleta -
3-3-2, 6x7x6 apod., zobrazovani v jinych barevnych systemech, ..
{
Pen,
Brush,
BitMask,
ColormapStore
-> RasterGraphics
}
nebo {
RasterGraphics,
ColormapStore
-> RasterGraphics
}
.
- B:
Barevny dithering (s nejakou pevnou paletou). Jakakoli vhodna metoda.
{
Pen,
Brush,
BitMask,
ColormapStore
-> RasterGraphics
}
nebo {
RasterGraphics,
ColormapStore
-> RasterGraphics
}
.
- C:
Konstrukce adaptovane barevne palety. Nekolik variant: Heckbertuv algoritmus ("median
cut"), octree, shlukova analyza ("clustering"), ..
{
RasterGraphics
-> RasterGraphics
[ ColormapStore ]
}
nebo {
RasterGraphics
-> ColormapStore
}
.
- B:
Vypocet animace pomoci palety - vstupem je serie obrazku, vystupem jedna bitmapa animovana
pomoci zmeny palety.
{
RasterGraphics*
-> RasterGraphics,
ColormapStore
}
.
- B:
Objekt realizujici pruchod obdelnikovou bitmapou (scanline, serpentine, Morton, interlace-GIF,
apod.).
{
Order2D
}
.
- B az C:
Kodovani a dekodovani rastroveho obrazku pomoci RLE. Obecny pruchod daty (scanline, serpentine,
Morton, ..).
{
RasterGraphics,
Order2D
-> BitStream
}
a zpet.
- C:
Algoritmus LZW (kompatibilni s internim koderem formatu GIF). Pokud mozno ho zobecnit
(neomezena velikost slovniku, prosty vystupni format - bez "paketu", ..).
{
EntropyCodec
-> BitStream
}
a zpet.
- D:
Jine kompresni algoritmy: [dynamicke] Huffmanovo kodovani, [dynamicke] aritmeticke kodovani,
slovnikove metody ruzne od LZW, ..
{
EntropyCodec
[ EntropyHistogram ]
-> BitStream
}
a zpet.
- C:
Kodovani a dekodovani rastroveho obrazku pomoci kvadrantoveho stromu. Velikost: mocniny 2 nebo
obecna (2 ruzne ulohy).
{
RasterGraphics
-> QuadTree
}
a zpet nebo {
BitMask
[ -> QuadTree ]
}
.
- C:
Mnozinove operace provadene nad kvadrantovym stromem. Obecna mnozinova operace zadavana
parametrem.
{
QuadTree*
-> QuadTree
}
.
- A:
Ukladani a nahravani rastroveho obrazku v nejakem grafickem formatu. Vlastni algoritmy se prevezmou
z nejake GPL knihovny (GIF viz predchozi ulohy).
{
RasterGraphics
-> BitStream
}
a zpet.
- C:
Ukladani a nahravani rastroveho obrazku v nejakem grafickem formatu. Algoritmy kodovani je potreba
naprogramovat.
{
DataFileFormat
-> RasterGraphics
[ BitStream ]
}
a zpet.
3D GRAFIKA (Pocítacová grafika II, III, atd.):
- A:
Viditelnost - plovouci horizont. Horizonty reprezentovany rastrove, carova i vyplnovaci varianta,
rastrovy vystup.
{
Property,
Trigger
-> FunctionR2ToR,
RasterGraphics
}
.
- B:
Viditelnost - plovouci horizont. Horizonty reprezentovany vektorove (lomene cary), vektorovy
vystup.
{
Property,
Trigger
-> FunctionR2ToR,
VectorGraphics
}
.
- B:
Viditelnost - Appeluv algoritmus. Vstup lze predpokladat v topologicke reprezentaci
(winged-edge), vektorovy vystup.
{
Property,
Trigger
-> Brep,
VectorGraphics
}
.
- A:
Viditelnost - Z-buffer. Pro kresleni viditelnych casti se vola externi "vyplnovaci
rutina" (kvuli stinovani apod.).
{
Property,
Trigger
-> Brep,
FaceRender
}
.
- B:
Viditelnost - maliruv algoritmus. Pro zacatek staci bez prosekavani sten a bez rozsekavani cyklu.
Externi "vyplnovaci rutina" (kvuli stinovani apod.).
{
Property,
Trigger
-> Brep,
FaceRender
}
.
- B:
Viditelnost - Watkinsuv algoritmus (radkovy rozklad). Zatim bez prosekavani sten.
Externi "off-line vyplnovaci rutina" (kvuli stinovani apod.).
{
Property,
Trigger
-> Brep,
FaceRender
}
.
- B:
Viditelnost - Warnockuv algoritmus ("rozdel a panuj").
Externi "off-line vyplnovaci rutina" (kvuli stinovani apod.).
{
Property,
Trigger
-> Brep,
FaceRender
}
.
- A az C:
Jakykoli dalsi algoritmus na viditelnost - podle literatury.
{
Property,
Trigger
-> Brep,
FaceRender
}
nebo {
Property,
Trigger
-> Brep,
VectorGraphics
}
.
- Nekolik uloh B:
Vypocet vrzenych stinu - ruzne algoritmy (stinovy Z-buffer, stinova telesa, BSP reprezentace
stinu, apod.).
{
Property,
Trigger
-> Brep
}
nebo {
Property,
Trigger
-> Brep,
RasterGraphics
}
.
- A:
Prevod izolovane B-rep do topologickeho tvaru (winged-edge). Duraz by mel byt kladen na rychlost
prevodu (napr. hasovanim).
{
Property,
Trigger
-> Brep,
EulerOperators,
Brep
}
.
- B:
Kompetni sada Eulerovskych operaci (vcetne inverznich) nad topologickou B-rep (wiged-edge).
Derave steny i derava telesa!
{
Brep,
EulerOperators
}
.
- C:
Prevod CSG reprezentace na B-rep - implementace mnozinovych operaci nad mnohosteny. Nejlepsi je
pracovat s topologickou B-rep (winged-edge). Zamerit se na rychlost vypoctu!
{
Property,
Trigger
-> CSGNode,
Brep
[ EulerOperators ]
}
.
- Nekolik uloh B az C:
Ruzne typy aproximacnich a interpolacnich krivek a ploch - Bezierovy, B-spline, NURBS.
Parametricka reprezentace, nektere zakladni algoritmy - inverzni transformace, adaptivni prevod
do B-rep, .. Prevod do B-rep
{
Property,
Trigger
-> Interpolation2D,
Brep
[ EulerOperators ]
}
, jednotlive krivky {
Interpolation1D
}
nebo plochy {
Interpolation2D
}
.
- Nekolik uloh B az C:
Lokalni model osvetleni - Strauss, Torrance-Cook apod. Pristup po vzorcich (konkretni smer
pohledu) nebo globalni vysledek (aproximace kompletni BRDF v danem bode - napr. pro dalsi
vzorkovani v Monte-Carlo metodach).
{
LightModel
}
.
- A:
Vyplnovaci rutina - konstantni stinovani. On-line (polygon+maska) i off-line (nekolik volani
pro dany polygon) varianta.
{
FaceRender
-> Brep,
RasterGraphics
}
.
- B:
Vyplnovaci rutina - Gouraudovo stinovani. On-line (polygon+maska) i off-line (nekolik volani
pro dany polygon) varianta.
{
FaceRender
-> Brep,
RasterGraphics
}
.
- B:
Vyplnovaci rutina - Phongovo stinovani. On-line (polygon+maska) i off-line (nekolik volani
pro dany polygon) varianta.
{
FaceRender
-> Brep,
RasterGraphics
}
.
- Nekolik uloh B:
Vypocet pruseciku paprsku s ruznymi elementarnimi telesy - krychle, kuzel, paraboloid, toroid, ..
Vysledkem je mnozina pruseciku (useku na poloprimce) + 2D povrchove souradnice + normalove vektory
apod.
{
Solid
}
.
- B az C:
Vypocet pruseciku paprsku s rotacni plochou. Rotacni plocha je zadana (rovinnou nebo prostorovou)
krivkou a osou rotace.
{
Solid
}
.
- C:
Vypocet pruseciku paprsku s Bezierovou (B-spline) bikubickou plochou. Plocha je zadana matici
ridicich bodu.
{
Solid
}
.
- D:
Vypocet pruseciku paprsku s NURBS plochou. Plocha je zadana matici ridicich bodu a dvema uzlovymi
vektory.
{
Solid
}
.
- C az D:
Vypocet pruseciku paprsku s implicitne zadanou plochou. Ruzne moznosti zadani implicitni plochy
(pevny format - "blobs" nebo libovolny aritmeticky vyraz), ..
{
Solid
}
.
- A az C:
Jednoduche textury modifikujici barvu - pocitane (sachovnice, pruhy, kruhy, apod.) nebo zadane
bitmapou (prip. MIP-mapou).
{
Texture
}
.
- B:
Bump-map textury - pocitane nebo zadane bitmapou.
{
Texture
}
.
- B az C:
Jakekoli slozitejsi textury - modifikace optickych vlastnosti materialu, kombinace s bump-mapou,
apod.
{
Texture
}
.
- B az C:
Texturovaci funkce - fraktaly, sumove funkce, slozitejsi funkce syntetizovane z sumu, ..
{
Texture
}
.
- Nekolik uloh B:
Ruzne vzorkovaci algoritmy pro anti-aliasing (2D vzorkovani). Staticke, inkrementalni nebo
adaptivni varianty (nemusi obsahovat zjemnovaci orakulum).
{
ImageSynthesizer
-> ImageFunction
}
.
- Nekolik uloh B az C:
Ruzne N-rozmerne vzorkovaci algoritmy. Staticke nebo dynamicke varianty (nemusi obsahovat
zjemnovaci orakulum). Neco jako
{
ImageSynthesizer
}
.
- B:
Vypocet mekkych stinu v Ray-tracingu. Neco jako
{
ImageSynthesizer
}
.
- B:
Simulace opticke hloubky ostrosti v Ray-tracingu. Neco jako
{
ImageSynthesizer
}
.
- B:
Vypocet rozmazani rychlym pohybem sceny v Ray-tracingu. Neco jako
{
ImageSynthesizer
}
.
- B:
Vypocet neostreho odrazu/lomu v Ray-tracingu (podle obecne BRDF). Neco jako
{
ImageSynthesizer
}
.
- B:
Vypocet spektralniho rozkladu svetla v Ray-tracingu (rozklad svetla podle vlnove delky). Neco
jako
{
ImageSynthesizer
}
.
- B az C:
Obecne schema pro distribuovany Ray-tracing - libovolna kombinace predchozich metod (vcetne
anti-aliasingu). Nezavisle vzorkovani ve vice dimenzich (stratified sampling). Neco jako
{
ImageSynthesizer
}
.
- Nekolik uloh B:
Ruzne netradicni generatory primarnich paprsku (kamery) pro Ray-tracing - napodobeni objektivu
"rybi oko" a jinych nelinearnich projekci, ..
{
RayGenerator
}
.
- Nekolik uloh B az D:
Jednotlive urychlovaci metody pro Ray-tracing - obalova telesa, hierarchie obalovych teles,
prostorove adresare (staticke i adaptivni), smerove urychlovaci metody, ..
{
Intersectable
-> RTScene
}
.
- C az F:
Perzistence pro Ray-tracing - navrh koncepce a implementace. Zadani geometrie sceny, libovolnych
dalsich parametru (materialove konstanty, textury, kamera), konfigurace vlastniho vypoctu
(anti-aliasing, distribuovany vypocet, vzorkovaci metody). Priprava pro animaci. Ulozeni stavu
vypoctu, paralelni distribuovany vypocet (cluster na siti LAN).
- Nekolik uloh B az C:
Import sceny pro Ray-tracing z ruznych formatu (3DS, Pov-Ray, RenderMan, RayShade, Blender, VRML,
apod.). Pripadne uvazovat i o exportu.
- Nekolik uloh B az D:
Aproximacni a interpolacni objekty (interpolatory) - 1D, 2D i vice-dimenzionalni (napr.
interpolacni polynomy, B-spline, wavelety, ..). Interpolace ve sferickych souradnicich.
{
Interpolation1D
}
nebo {
Interpolation2D
}
.
- C:
Kvaterniony a jejich interpolace - pro reprezentaci orientace telesa ve 3D.
{
Interpolation2D
}
.
- B:
Odhad konfiguracniho faktoru mezi dvema ploskami (bez viditelnosti).
{
xxx
-> Brep
}
.
- Nekolik uloh B az C:
Vypocet konfiguracniho faktoru z plosky do zbytku sceny - ruzne algoritmy (polokrychle, Sillion,
Monte-Carlo, ..).
{
xxx
-> Brep
}
.
- B:
Pocatecni rozdeleni B-rep sceny na plosky (konecne prvky) pro radiacni metodu. Jednoducha
parametrizace ulohy - rizeni mezniho rozmeru nebo objemu plosek.
{
yyy
-> Brep
}
.
- D:
Pocatecni rozdeleni B-rep sceny na plosky podle odhadu hranic nespojitosti stinu. Na vstupu musi
byt oznaceny plosky, ktere jsou zdrojem svetla (na jejichz hranici je implicitni nespojitost
svetla).
{
yyy
-> Brep
}
.
- B:
Klasicky vypocet radiacni metody (metoda konstantnich elementu) - staticke deleni sceny, nejaka
bezna (numericka) metoda reseni soustavy rovnic (sbirani energie).
- C:
Adaptivni zjemnovani do klasicke radiacni metody (sbirani energie). Orakulum rozhodujici o deleni
plosky, zjemneni site, prepocitani radiosit (musi fungovat uprostred numericke iterace).
- B:
Prevod konstantnich radiosit na hodnoty ve vrcholech sceny (pro Gouraudovo stinovani).
- B:
Reseni radiacni soustavy metodou strileni a trideni (varianta Southwellovy metody). Staticke
deleni sceny.
- C:
Adaptivni zjemnovani do strilejici radiacni metody. Orakulum rozhodujici o deleni
plosky, zjemneni site, korektni prepocitavani radiosit.
- B:
Modul pro prestrelovani (hyper-relaxaci) v radiacni metode. Adaptivni rizeni prestrelovaciho
koeficientu, prirozeny odhad podle celkoveho objemu dosud nezpracovane energie ve scene
(Purgathofer, Feda).
- B:
Dvoustupnova hierarchicka radiacni metoda - staticke rozdeleni sceny na plosky a elementy,
libovolna staticka metoda reseni mensi soustavy, prepocitani radiosit do elementu.
- C:
Obecna hierarchicka radiacni metoda - staticka varianta. Prvotni rozdeleni sceny podle odhadu
konfiguracniho faktoru (F-pravidlo). Vypocet strilenim.
- C az D:
Obecna hierarchicka radiacni metoda - adaptivni varianta. Prvotni rozdeleni sceny podle odhadu
konfiguracniho faktoru (F-pravidlo). V prubehu vypoctu adaptivni zjemnovani podle BF-pravidla.
Prestrelovani.
- C az E:
Obecna hierarchicka radiacni metoda - dualni varianta. Prvotni rozdeleni sceny podle odhadu
konfiguracniho faktoru (F[I]-pravidlo). V prubehu vypoctu adaptivni zjemnovani podle BFI-pravidla.
Paralelni vypocet radiosity B a dulezitosti I - ve scene musi byt definovana kamera.
- C az E:
Monte-Carlo radiacni metoda - propagace svetla nahodnymi paprsky (nemusi se pocitat konfiguracni
faktory). Adaptivni deleni (na ploskach se musi pamatovat vsechny dopady paprsku), dualni varianta
(propagace dulezitosti = potencialu opacnym smerem), ..
2D GRAFIKA (Pokrocilá 2D pocítacová grafika, atd.):
- B:
Kompozice rastrovych obrazku pomoci alfa-kanalu: bezne unarni i binarni operace (pracujici na
datech s predem vynasobenym alfa).
{
Property,
Trigger
-> RasterGraphics
[ RasterGraphics ]
RasterGraphics
}
.
- B:
Klicovani pres modre pozadi ("blue-screen") - automaticka extrakce objektu v popredi.
Pozadi je zadane zakladni barvou a povolenym rozptylem (klasifikace pixelu pozadi lze oddelit).
{
Property,
Trigger
-> RasterGraphics,
AlphaMask,
RasterGraphics
}
.
- C:
Klasifikacni rutina pro "blue-screen" klicovani - hleda pixely pozadi, popredi a
obrysu. Vysledek vraci protokolem
AlphaMask
(jen hodnoty 0.0
,
0.5
a 1.0
). {
Property,
AlphaMask
-> RasterGraphics
}
.
- B:
Vyplnovaci rutina - mapovani jednoduche bitmapove textury. On-line (polygon + maska) i off-line
(nekolik volani pro dany polygon) varianta.
{
FaceRender
-> Brep,
RasterGraphics
}
.
- C:
Vyplnovaci rutina - kombinace stinovani s mapovanim jednoduche bitmapove textury.
On-line (polygon + maska) i off-line (nekolik volani pro dany polygon) varianta.
{
FaceRender
-> Brep,
RasterGraphics
}
.
- C:
Vyplnovaci rutina - kombinace stinovani s MIP-mapovanou texturou.
On-line (polygon + maska) i off-line (nekolik volani pro dany polygon) varianta.
{
FaceRender
-> Brep,
RasterGraphics
}
.
- B:
Prepocitavani rastroveho obrazku podle zadane deformace (warping). Zpetny algoritmus s filtraci
a interpolaci (staci bilinearni a bikubicka).
{
Property,
Trigger
-> FunctionR2ToR2,
RasterGraphics,
RasterGraphics
}
.
- C:
Prepocitavani rastroveho obrazku podle zadane deformace (warping). Dopredny algoritmus s filtraci
a interpolaci (staci bilinearni a bikubicka).
{
Property,
Trigger
-> FunctionR2ToR2,
RasterGraphics,
RasterGraphics
}
.
- Nekolik uloh B az C:
Vicekrokovy warping (rozklad deformacni funkce na radkove a sloupcove kroky) - mechanismus vypoctu
{
Property,
Trigger
-> FunctionR2ToR2,
RasterGraphics,
RasterGraphics
}
a priklady konkretnich deformaci {
FunctionR2ToR2
}
.
- B:
Warping - deformace trojuhelnikove site (barycentricke souradnice, nespojitost prvni derivace).
{
FunctionR2ToR2
}
.
- C:
Warping - sit spline krivek (B-spline krivky, dvoukrokovy algoritmus).
{
FunctionR2ToR2
}
.
- C:
Warping - spline plochy (deformace zdrojove i cilove site, nutnost inverzni spline-transformace
- numericky algoritmus).
{
FunctionR2ToR2
}
.
- C:
Warping - "feature-based" (0D i 1D "features", vazeny prumer s pomoci
"funkci vlivu", parametrizace).
{
FunctionR2ToR2
}
.
- D:
Metamorfoza polygonu v rovine - zalozena na fyzikalnim modelu (deformacni prace). Vypocet
optimalniho prirazeni vrcholu i vlastni metamorfoza (morphing).
{
Interpolation1D
-> Brep
}
.
- D:
Geometricky morphing soustavy "features" - vymyslet rozumne hladke reseni bez
singularit.
{
Interpolation1D
-> Brep
}
.
- B:
Implementace vlastniho vypoctu morphingu - dan je parametrizovany warping a dva rastrove
obrazky.
{
Property,
Trigger
-> FunctionR2ToR2,
RasterGraphics,
RasterGraphics,
RasterGraphics
}
.
- Mnoho uloh B az D:
Implementace datovych struktur: Region-quadtree, MX-quadtree, Point-Region-quadtree,
Point-quadtree, pseudo-quadtree, K-D-tree, A-K-D-tree, BSP-tree (ruzne varianty), Range-tree
(ruzne varianty), R-tree, .. Konstrukce (operace insert, delete), vyvazovani, lokalizace,
pruchod ze stredu nebo "sweep".
{
GeometrySearch
-> Brep
}
.
- C:
Strip-tree: konstrukce, detekce a vypocet pruseciku dvou krivek.
{
GeometrySearch
-> Brep
}
.
- Nekolik uloh C:
PMx-tree (polygonalni mapy): konstrukce, lokalizace bodu, mnozinove operace apod.
{
GeometrySearch
-> Brep
}
, mnozinove operace nejak jinak.
- Mnoho uloh B az D:
Transformacni funkce pro kompresi obrazu - dekorelace dat, separace podle dulezitosti. Globalni
transformace, blokova transformace, [1D], 2D, [3D], dopredna i zpetna transformace. Konkretni
pristupy: Fourierova, sinova, cosinova, Hartleyova, Walshova, Hadamardova, Haarova,
Karhunen-Loewyho, waveletove, apod. transformace. Rychly vypocet O(N log N), celociselna
aritmetika (kde je to mozne).
{
Property,
Trigger
-> SampleData,
SampleData
}
.
- Nekolik uloh B:
Pruchody 2D rastrovou matici (space-filling curves): Z-order, Morton, Peano-Hilbert, cik-cak,
apod. Osetreni libovolne velikosti 2D oblasti. Ekvivalentni s ulohou 37.
{
Order2D
}
.
- Nekolik uloh B az C:
1D predikce - linearni konecny prediktor, polynomialni prediktor, staticke a adaptivni varianty.
{
Property,
Trigger
-> SampleData,
SampleData
}
.
- Nekolik uloh B az D:
2D predikce - linearni nebo polynomialni prediktory, staticke a adaptivni varianty, 1-bitove
prediktory.
{
Property,
Trigger
-> SampleData,
SampleData
}
.
- Nekolik uloh B:
Skalarni kvantovace - linearni, nelinearni, mrtva zona rizena parametrem, ..
{
Property,
Trigger
-> SampleData,
SampleData
}
.
- Nekolik uloh B az C:
Obecne vektorove kvantovace - uniformni a adaptivni, konstrukce podle hustoty pravdepodobnosti
nebo vzorku dat, .. Principy: shora dolu, shlukova analyza, iteracni algoritmy, neuronove site,
apod.
{
Property,
Trigger
-> SampleData,
SampleData
}
.
- Nekolik uloh B az C:
Vektorove kodery (bitova alokace) - pevne prirazeni, dynamicka alokace (podle amplitudy =
energie), ..
{
Property,
Trigger
-> SampleData
[ Order2D ]
EntropyCoder
}
.
- Nekolik uloh B az C:
Kodovani ridkeho souboru dat ([1D], 2D, [3D]) - preskakovani nulovych useku, 1-bitova a
vice-bitova data, staticke i adaptivni kodovani, ..
{
Property,
Trigger
-> SampleData
[ Order2D ]
EntropyCoder
}
.
- Nekolik uloh C az E:
Implementace konkretnich kompresnich standardu (nemusi byt nutne 100% bitove kompatibilni, ale
urcite musi byt ekvivalentni) - baseline JPEG, losless JPEG, JPEG-2000, .. Modularni konstrukce
kodeku: priprava pro experimenty (vymena jednotlivych modulu), provedeni jednoduchych mereni
a porovnani. Priblizne (bez vymennych modulu) -
{
Property,
Trigger
-> SampleData,
BitStream
}
.
- Nekolik uloh B az C:
Kodovani paletoveho obrazku (cartoon, vystup kresliciho programu, jednoducha business grafika) -
quad-tree, pruchod daty + nektera slovnikova metoda (viz ulohy 39. - 40.), apod.
{
Property,
Trigger
-> SampleData
[ Order2D ]
EntropyCoder
}
.
- C az D:
Segmentace obrazku pro vysoce ztratovou kompresi - hledani homogennich oblasti a hranic mezi nimi.
Metody: narustani oblasti, soft-fill, apod. Redukce poctu oblasti, ..
{
Property,
Trigger
-> SampleData,
SampleData
}
.
- Nekolik uloh B az D:
Hledani co nejpodobnejsiho bloku v obrazku - v celem obrazku nebo jen omezene, moznost zmeny
meritka nebo jednoduche afinni transformace. Kompletni vyhledavani (kvalita) nebo sub-optimalni
reseni (rychlost).
{
zzz
-> SampleData,
SampleData
[ SampleData ]
}
.
- Nekolik uloh B az D:
Fraktalni komprese obrazu - pevne delani, quad-tree, jine segmentace. Ruzne metody kodovani,
rizeni kvality vysledku nebo kompresniho pomeru. Superpozice vice zdrojovych bloku.
- C az D:
Fraktalni komprese videa - zavislosti uvnitr BOP (block of pictures), automaticke urcovani hranic
mezi BOP, moznost intra-bloku a intra-snimku, prenos bloku v meritku (1:1), ..
- B az D:
Klasicka komprese videa s predikci pohybu - referencni snimky, dopredna a zpetna predikce pohybu,
kodovani rozdilovych bloku (specialni pripad: bloky bez predikce = intra-bloky),
- B:
Jednoducha rychla predikce mezi sousednimi pulsnimky (fields) prokladaneho video-signalu - moznost
pouzit tez predchoziho kompletniho snimku.
{
Property,
Trigger
-> SampleData,
SampleData,
EntropyCoder
}
.
- C az D:
Kompenzace pohybu ve waveletovem rozkladu snimku (frames) nebo pulsnimku (fields) - Mallatuv
rozklad, nejaky jednodussi wavelet, omezene prohledavani, hierarchicke hledani, ..
Dalsi ukoly (vizualizace objemu,..) budou
pridany nekdy pozdeji
[Cvicení PGR003, PGR004, PGR007]
[Prednáska PGR003]
[Prednáska PGR004]
[Prednáska PGR007]
[Projekt JaGrLib]
[Skupina CGG na MFF]
Copyright (c) 2000-2003 Josef Pelikán,
poslední změna: 17.10.2003