Západočeská univerzita
Katedra informatiky výpočetní techniky

APG - Algoritmy počítačové grafiky

2009/2010
Rozsah: 3 + 2 , 6 kreditů

NEWS

POPIS

APG je 6-ti kreditový předmět, jehož účelem je analýza algoritmů počítačové grafiky a vizualizace dat, návrh možných modifikací a jejich vyhodnocení. Rozvoj tvůrčích schopností studentů v oblasti návrhu algoritmů.

Předpokládá se:

• použití programovacích prostředků pod MS Windows (C#, VC++ apod.) a s použitím knihovny DirectX, resp. OpenGL,
• základní znalost lineární algebry (včetně znalosti vektorové a maticové notace), datových struktur,
• základů počítačové grafiky na úrovni předmětu KIV/ZPG.

Absolvováním předmětu rozvinete schopnost

• analyzovat problém a najít odpovídající algoritmy k řešení netriviálních problémů,
• realizovat netriviální algoritmy počítačové grafiky.

Pokud Vaše práce bude úspěšná, lze ji rozšířit v rámci předmětu KIV/OP, resp. OP-G (Oborový projekt-grafika) a později i na diplomovou práci se mnou, která bude realizována jako součást projektu s případným finančním ohodnocením.

ZÁPOČET

V rámci tohoto předmětu se všechny dokumenty ukládají na PORTAL.

• realizují se drobné úlohy, které je nutné odevzdat v uspokojivé kvalitě, včetně tištěné a elektronické dokumentace.
  Tyto úlohy může vyučující v případě nadprůměrné kvality ohodnotit dodatečnými body, pozdní odevzdání (kromě nemoci apod.) se penalizuje.
  
  
• student sám nebo ve skupině vypracovává řešení netriviálního úlohy - semestrální práci na zadané téma. Práce zahrnuje zejména:
  1. rešerši publikací o metodách řešících daný nebo obdobný problém,
  2. teoretické porovnání vlastností známých metod,
  3. návrh modifikace vybraného relevantního algoritmu, resp. návrh vlastního řešení,
  4. implementaci a experimentální ověření vlastností implementace,
  5. vyhodnocení a řádnou dokumentací (doporučení: použité materiály přiložte v elektronické podobě)
  6. seznam použité literatury s řádnou citací atd.
  7. prezentaci výsledků na odborném semináři - předposlední výukový týden semestru,
     trvání jedné prezentace 20 min + 10 min. diskuze.
     Aktivní účast všech studentů je povinná, omlouvá pouze nemoc - doklad o pracovní neschopnosti od lékaře, či jiné velmi závažné důvody.
  8. celkovou dokumentaci, včetně prezentace ve formátu PowerPoint, je nutné odevzdat před odborným seminářem a to jak v elektronické podobě, tak i tištěné podobě (oboustranný tisk vítán).
     
• realizované úlohy a "semestrální práce" se odevzdávají v tištěné podobě (oboustranný tisk - programy se netisknou, jen klíčové sekvence, pokud jsou nutné k pochopení) ve formátu uvedeném níže a s titulní stranou, obsahem, použitou literaturou atd.
  
  Elektronická forma se ukládá na PORTAL

Struktura jména souborů pro uložení na PORTAL
<předmět>_<šk.rok>_<č.úlohy>_<přijmení>_<jméno>_<čislo studenta>
např.
APG_2008_1_Novak_Josef_A235478
ve formatu *.ZIP

Malé samostatné práce mají zjednodušený formát - viz http://herakles.zcu.cz/~skala/First_report_page.rtf

Semestrální práce obsahuje závěrečnou zprávu, která je po formální stránce obdobná požadavkům na DP, viz http://www.kiv.zcu.cz/studies/dp/pokyny.php  s následujícím změnami:

• vazba měkká, stačí pevně sešít sešívačkou, tisk oboustranný (kroužková vazba akceptovatelná, ale špatně se to skladuje)
• zadání práce / úkolu bez kulatého razítka :-)
• místo "Diplomová práce" je všude uvedeno "Semestrální práce"
• "State of the art" daného problému, známé metody řešení, v čem je těžiště práce atd.
• co se chce experimenty prokázat, popis experimentů
• dosažené výsledky a porovnání, obrázky, tabulky a grafy
• seznam použité literatury
• musí obsahovat Prohlášení o použitých zdrojích
  
  Prohlášení:
  Prohlašuji, že jsem tuto práci vypracoval(a) samostatně a výhradně s použitím citovaných pramenů a nebyla/byla součástí prací jiných předmětech (případně vyjmenovat předměty a specifikovat co bylo součástí jiného předmětu).
  
  V Plzni dne: datum, jméno a přijmení, vlastnoruční podpis
  
  
• Pokud student vychází z podkladů vedoucího práce, resp. kolegy, např.Josefa Vomáčky jasně vyznačí v textu ... dle [Vom99a] ...a v seznamu použité literatury  uvede
  [Vom99a] Vomáčka,J.: Jak jsem letěl na měsíc, neveřejné zdroje/osobní komunikace/pracovní materiály apod.
  Doporučuji citace realizovat dle: http://www.bath.ac.uk/library/guides/references.pdf

Hodnoceni

Možný bodový zisk

• malé samostatné práce
  • 1.úloha 5 bodů
  • 2.úloha 10 bodů
    v případě pozdního odevzdání je bodový zisk 0 bodů,
    úloha se však musí odevzdat v uspokojivé kvalitě
• semestrální práce
  • základní část až 25 bodů
    • teoretická část až 10 bodů
    • finální část až 15 bodů (posuzuje se i formální ypracování dosažené výsledky, implementace a  dokumentace v programech atd.)
  • variace, doplnění, netradiční řešení, formální zpracování atd. až 10 bodů
  • pozdní odevzdání (-10) bodů
• zkouška až 50 bodů

K získání zápočtu je nutné získat alespoň 25 bodů ze cvičení
U zkoušky je nutné získat alespoň 25 bodů

ZKOUŠKA

Studenti se na zkoušku zapisují standardním způsobem přes PORTAL, nedostavení se na zkoušku bez vážného důvodu je hodnoceno známkou neprospěl.
Před zkouškou musí být zapsán zápočet v indexu.

Předběžně (není přidělená místnost v rezervačním systému),
definitivní údaje na PORTALu

Studenti se shromáždí před posluchárnou minimálně 10 min. před zahájením zkoušky. 

Upozornění:

• Opisování, resp. poskytování informací k opisování bude u všech případů řešeno okamžitým ukončením zkoušky a hodnocením NEPROSPĚL u všech zúčastněných. Zkoušku z předmětu bude možno opakovat až následující rok.

HODNOCENÍ ZKOUŠKY

• Ze zkoušky je možné získat max. 50 bodů, na zkoušce je nutné získat min. 25 bodů
• Body ze zkoušky se při více pokusech nesčítají.
• Celkové hodnocení S je součtem bodů získaných ze cvičení a ze zkoušky, a to:

výborně:	S > 85 bodů
velmi dobře	S > 75 bodů
dobře:	S > 50 bodů
neprospěl:	S <= 50 bodu včetně

Obecná pravidla

• účast na přednáškách/cvičeních je nepovinná, nicméně je doporučená, neboť některé partie jsou obtížné, samostatné studium je časově podstatně více náročné,
• knihovna ZČU areál Bory je perfektně vybavená českou a zahraniční odbornou literaturou z oblasti počítačové grafiky pro prezenční studium, mnohé publikace lze krátkodobě půjčit,
• účast na cvičeních bude evidována, nicméně nemá vliv na hodnocení,
• zadávání úloh je výhradně na cvičení a "nevyzvednutí" úlohy není důvodem k prodloužení termínu odevzdání,
• úlohy se odevzdávají výhradně dle pokynu cvičícího,
• v případě úrazu, zdravotních či jiných velmi vážných důvodů uvědomte okamžitě příslušného cvičícího, který zváží Vaše důvody a rozhodne o případném prodloužení termínu odevzdání úlohy, resp. o novém zadání a formě náhradního řešení,
• zkouška probíhá hromadně - termíny jsou určeny na počátku semestru,
• počet míst na zkoušku není omezen, je však nutné mít zapsaný zápočet a na zkoušku se přihlásit přes PORTAL
  (z důvodu namnožení zkušebních archů apod.),
• zkouška probíhá písemnou a/nebo ústní formou, výsledky zkoušky budou k dispozici cca do 10 dní,

Upozornění:

Při získání dostatečného počtu bodů k absolvovaní předmětu může být zkouška na základě bodového hodnocení zapsána nejpozději v době posledního termínu zkoušky. Po posledním termínu zkoušky bude stanoven termín zápisu známky do indexu. Po té budou zkouškové archy uzavřeny a příslušnou známku do indexu a do archu nebude možno zapsat. Je možné požádat studijní oddělení na základě žádosti o zapsání po zaplacení administrativního poplatku.

SYLABUS

(informativní obsah a pořadí přednášek může být odlišné od pořadí v seznamu)

1. Seznámení se s problematikou předmětu a úvod do předmětu.
   Typické výpočty v počítačové grafice, přesnost numerických operací a numerická reprezentace.
   Složitosti algoritmů a jejich vlastnosti časová náročnost, robustnost, přesnost apod., způsoby posuzování algoritmů a vyhodnocování jejich vlastností.
   Základní možnosti urychlení algoritmů, předzpracování, dělení prostoru a paralelní zpracování, vliv předzpracování na run-time, programování s vlákny (threads).
    
2. Vektory, matice a operace s nimi.
   Eukleidovský prostor a jeho projektivní rozšíření, homogenní souřadnice.
   Dualita, geometrická interpretace a použití. Kvaterniony a jejich použití.
   Geometrické transformace a jejich reprezentace, reprezentace bodů a vektorů.
   
   
3. Lineární interpolace s lineární a nelineární parametrizací.
   Výpočet průsečíků přímky a roviny v Eukleidovském a projektivním prostoru. Plueckerovy souřadnice.
    
4. Metody projekce E3 do E2, typy projekcí, jejich reprezentace, pohledová pyramida, její parametry a vliv na přesnost výpočtu / zobrazení, algoritmy řešení viditelnosti, pseudo-hloubka.
    
5. Metody ořezávání v E2 a E3. Algoritmus Cyrus-Beck pro ořezávání přímky konvexním n-úhelníkem a mnohostěnem, modifikace pro homogenní souřadnice.
   
   
6. Nelineární interpolace ("spline" křivky a plochy, interpolace v rastru - obrazy)
   Radiální bázové funkce - interpolace, aplikace a rekonstrukce
    
7. Reprezentace objektů v počítačové grafice a vizualizaci dat, hranové, povrchové a objemové reprezentace, CSG stromy a implicitní reprezentace a modelování.
   Vliv datových struktur na rychlost výpočtu, eliminace duplicitních elementů, dělení prostoru.
   
   
8. Strukturované a nestrukturované sítě, reprezentace povrchu a skalárních polí, roztroušené body, radiální bázové funkce a jejich použití.
   Volumetrická data, metody a jejich aplikace. Výpočet iso-ploch, výpočet normál a gradientu,
   STL formát pro CAD systémy.
   
   
9. Metoda sledovani paprsku. Testy a výpočty průsečíků přímek (paprsků) s objekty. Výpočet průsečíku přímky s kvadratickou plochou. Metody detekce kolizí. Akcelerační techniky, metoda binárních masek a její použitelnost.
   
   
10. Barvy a barevné systémy a jejich aplikace v zobrazovacích systémech. Modely stínování a osvětlení.
     
11. Pohyb pevných těles, kinematika, inverzní kinematika, dynamika, deformace objektů.
    Programování GPU - Cg & High Level Shading Language (výtah "základu základů" z předmětu KIV/GRG)
    
    
12. Prezentace semestrálních prací
13. Prezentace semestrálních prací

V průběhu semestru budou realizovány vybrané přednášky a to i kolegů ze zahraničí pracujících na relevantních tématech. Termíny přednášky budou včas oznámeny.

ÚLOHY a SEMESTRÁLNÍ PRÁCE

Jednotlivé úlohy a semestrální práce budou oznámeny cvičícím na 1-2. cvičení

Poslední změna stránky: 26. října 2009