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

APG - Algoritmy počítačové grafiky

Rozsah (přednášky - cvičení / laboratoř - samostatná práce) 3 + 2 + 3

Informace o předmětu na STAGu
http://deucalion.zcu.cz/apps/stag/prohlizeni/pg$_prohlizeni.ch_predm?kat=KIV&predm=APG

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í.

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 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 realizují drobné úlohy (s délkou řešení cca na 14 dní), 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, viz níže.
  
• student sám nebo ve skupině vypracovává řešení netriviálního úlohu - semestrální práci. Toto zahrnuje obsahuje 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 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 alespoň den předem do 8:30 a to jak v elektronické podobě, tak i tištěné podobě.
     
• 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é) ve formátu a s titulní stranou, obsahem.
  
  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čná zpráva studenta 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, tisk oboustranný, kroužková vazba akceptovatelná (špatně se to skladuje)
• zadaní práce / úkolu bez kulatého razítka :-)
• tisk oboustranný
• místo "Diplomová práce" je všude uvedeno "Oborový projekt"
• abstrakt v angličtině (soubor Abstract.htm), text zprávy v PDF formátu (soubor Report.pdf)
• "state of the art" daného problému, známé metody řešení, v čem je těžiště práce atd.
• popis experimentu
• dosažené výsledky a porovnání, obrázky, grafy, seznam použité literatury
• je přiložena programová dokumentace včetně CD ROM (i s elektronickými podklady a finální verzi prezentace)
• 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 byla (vyjmenovat předměty) / nebyla  součástí semestrálních prací v jiných předmětech mého studia studia.
  
  V Plzni dne datum jméno, vlastnoruční podpis "
  
• Pokud student vychází z podkladů vedoucího práce 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 http://www.bath.ac.uk/library/guides/references.pdf
•  

Hodnoceni

• malé samostatné práce celkově 2 x 5 = 10 bodů
• semestrální práce
  • základní část až 20 bodů
  • variace, doplnění, netradiční řešení atd. až 20 bodů
• zkouška až 50 bodů

Penalizace

• pozdní odevzdání (-1 bod / každý započatý kalendářní den včetně ode dne řádného odevzdání)
• vrácení
  • první vrácení - 5 bodů
  • druhé vrácení - 10 bodů

Na získání zápočtu je nutné získat alespoň 30 bodů ze cvičení

ZKOUŠKA

TERMÍNY

Studenti se na zkoušku zapisují standardním způsobem přes STAG, 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.

Je nutné počítat s tím, že termíny se mohou se z velmi vážných důvodů změnit, případné změny budou oznámeny předem na přednášce, resp. na STAGu.

Upozornění:

Opisování, resp. poskytování informací k opisování bude u všech zúčastněných řešeno okamžitým ukončením zkoušky a hodnocením NEPROSPĚL.

HODNOCENÍ ZKOUŠKY

• Ze zkoušky je možné získat max. 50 bodů, na zkoušce je nutné získat min. 20 bodů
• Body ze zkoušky se při více pokusech nesčítají.
• Odmítnutá / nezapsaná ("nevyzvednutá") známka se zapisuje do studijních záznamů jako nevyhověl.

• Vaše celkové hodnocení S je součtem bodů získaných ze cvičení a ze zkoušky, a to:

výborně:	S > 75 bodů
velmi dobře	S > 60 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 STAG
  (z důvodu namnožení zkušebních archů apod.),
• zkouška probíhá písemnou formou, výsledky zkoušky budou k dispozici cca do 10 dní,
• zápis výsledku zkoušky do indexu bude probíhat pouze v oznámených termínech. V prípadě, že máte jiné povinnosti v daném termínu, lze požádat kolegu o doručení indexu; známky se mimo vyhlášené termíny nezapisují (kromě vážných důvodů) a předpokládá se, že získané hodnocení není vámi akceptováno a do archu se zapisuje "neprospěl/neprospěla"

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

(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. Affiní, Eukleidovský a projektivní prostor, homogenní souřadnice. Vektory, matice a operace s nimi. Geometrické transformace a jejich reprezentace, reprezentace bodů a vektorů. Dualita, geometrická interpretace a použití.
   
2. 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).
   
3. Výpočet průsečíků přímky a roviny v Eukleidovském a projektivním prostoru. Algoritmus Cyrus-Beck pro ořezávání přímky v konvexním n-úhelníkem a mnohostěnem, modifikace pro projektivní prostor, výpočet průsečíku přímky s kvadratickou plochou
   
4. Interpolace s lineární a nelineární parametrizací, použití homogenních souřadnic, Plueckerovy souřadnice pro reprezentaci přímek v E3. Metody ořezávání v E2 a E3.
   
5. Testy a výpočty průsečíků přímek (paprtsků) s objekty, metody detekce kolizí
   
6. 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
   
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 a aplikace pro metodu Ray Tracing, metoda binárních masek a její použitelnost.
   
8. Pohyb pevných těles, kinematika, inverzní kinematika, dynamika, deformace objektů.
   
9. Povrchové modely, trojúhelníkové sítě, metody redukce sítí, metody zobrazování, paměťové nároky.
   
10. 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.
    
11. Modely stínování a osvětlení. Barvy a barevné systémy a jejich aplikace v zobrazovacích systémech
    
12. Prezentace semestrálních prací
    
13. Rezerva - programování GPU - Cg & High Level Shading Language (výtah "základu základů" z předmětu KIV/GRG)

V průběhu semestru budou realizovány vybrané přednášky kolegů a 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. cvičení

Předpokládám, že se někteří studenti účastní soutěže o nejlepší studentskou vědeckou práci, obvykle v období duben / květen.

Poslední změna stránky: 10. říjen 2006