Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m39dpg [2010/05/04 13:20]
petul.ka
+++ courses:a4m39dpg [2025/01/03 18:23] (aktuální)
@@ Řádek 1: / Řádek 1: @@
 ====== Datové struktury počítačové grafiky ======
-  * Stránky předmětu: http://service.felk.cvut.cz/courses/X36DPG/
+  * Stránky předmětu: https://edux.feld.cvut.cz/courses/A4M39DPG/start
   * Přednášející: Vlastimil Havran ([[http://www.cgg.cvut.cz/members/havran/|web]])
   * Cvičící: Vlastimil Havran
@@ Řádek 16: / Řádek 16: @@
     * **28/4** Konzultace k implementaci
     * **5/5** Pisemny test na 60 minut
+    * **10/5** Prednaska - **ODPADA** (podle Havranova mailu je Bittner nemocny)
     * **12/5** Odpada (rektorsky den)
     * **17/5** pondeli do 12:45, tedy 45 minut po poledni, termin pro nahrani dat semestralni prace na service.felk.cvut.cz, na dalsi data dodana pozdeji nebude bran zretel.
@@ Řádek 25: / Řádek 26: @@
 ==== Test ====
+== 2014 ==
+Čas 90min.
+  * Je dán obdélník v prostoru Rn. V poli A[N] jsou jeho minimální souřadnice, v poli B[N] maximální. Bod je zadán v poli Q[n]. Napiště funkci, která spočítá minimální a maximální vzdálenost bodu od obdélníku (v prostoru Rn). Pokud bod leží uvnitř obdélníku, vraťte 0.
+  * AESA popsat, jak lze vylepšit pam. nároky (jak se ta vylepšená metoda jmenuje a popsat jakým způsobem se dosáhne vylepšení)
+  * Popsat co je to epsilon-neighbor
+  * Dvě základní struktury pro reprezentaci dat ve 2D a 3D, popsat vlastnosti + alespoň 1 příklad ke každé
+  * Typy obálek (bounding box), vlastnosti
+  * Cenová funkce pro jeden dotaz v regulárních a hierarchických datových strukturách, popsat co nejpodrobněji
+== možné otázky ==
 možné otázky (sesbíráno z [[http://www.exfort.org|Exfortu]], snad si nebudou nárokovat autorská práva :)):
@@ Řádek 59: / Řádek 74: @@
 . Rozdíl uniformních a neuniformních struktur
-. Je dán hyperobdélník pomocí 2 rohů A[N], B[N] (úhlopříčně) a střed hypersféry S[N]. Spočítej minimální poloměr koule tak, aby obdélník ležel celý uvnitř.
+. Je dán hyperobdélník pomocí 2 rohů A[N], B[N] (úhlopříčně) a střed hypersféry S[N]. Spočítej minimální poloměr koule tak, aby obdélník ležel celý uvnitř. Pak ještě poloměr tak, aby se koule dotýkala typicky jednoho (max. čtyř) bodů, jinak disjunktní (koule vepsaná kvádru).
 . SAT, vysvětlit a napsat pseudokód kód, kolik udělá testů pokud se jedná o OBB a kolik pro AABB?
@@ Řádek 73: / Řádek 88: @@
 . Je dán hyperobdélník pomocí min a mex v každé ose a bod. Napsat algoritmus pro výpočet vzdáleností bodu od hyperobdélníka.
-. Cenová funkce při dotazu do hierarchické datové struktury.
+. Cenová funkce při dotazu do hierarchické datové struktury. K čemu se to používá.
 . Jaké vlastnosti musí mít vzdálenost, co je to metrika a metrický prostor.
@@ Řádek 82: / Řádek 97: @@
 . Co je to odhad hustoty pravděpodobnosti (density estimation) a jaký algoritmus se při něm využívá?
+. hierarchie pamětí, typické parametry
 ===== Zkouška =====
+**2015**
+  * Opět příklad na trojúhelníky.
+  * Popsat gH-trees.
+  * Popsat 3 metody stavby BVH (top-down, bottom up, insertion).
+  * Rozdíly mezi uniformními, spatial subdivision a BVH strukturami, jejich vhodnost pro reprezentaci bodových a nebodových dat.
+  * Popsat SAH, říct k čemu je to dobré a jaké jsou jeho předpoklady (uniformní distribuce nezastíněných paprsků) napsat nějaký algoritmus stavby k-d stromu (stačil slovní popis vypadající jako algoritmus).
+**2014**
+Příklad na trojúhelníky za 11b a 5 teoretických otázek za 9b. Teoretické otázky byly ve stejném stylu, co jsou zde již napsané - 2 způsoby reprezentace těles, metody stavby BVH, regulární vs BVH struktury, nějaký otázka s rovinama u kd-stromů, pak ještě něco ke kd-stromům (způsoby štěpení mám pocit). Ústní za 5b, pro lidi co měli odevzdanou semestrálku ten samý den asi po 4h, ostatní v den prezentace semestrálky (cca týden po zkoušce).
+**Otázky ze zkouškové písemky 28.1.2008**
+. Daná koule se středem C a poloměrem R, dále zadaná přímka z O s jednotkovým směrovým vektorem. Najít nejbližší průsečík a vrátit 1, případně 0 pokud průsečík neexistuje. To celé pro N dimenzí. [10 bodů]
+. Uniformní x hierarchické x BVH struktury… Co kde, proč, složitosti, příklady… [3+2 bodů]
+. Máme AABB box s minimálními souřadnicemi A a maximálními B a dotaz Q. Spočítat vzdálenost Q od boxu a vrátit ji. Pokud je Q uvnitř AABB vrátit nulu. Vše pro N dimenzí. [6 bodů]
+. Algortimy se Z-bufferem, vyjmenovat a jeden si vybrat a vysvětlit. [5 bodů]
+. Co je to prokletí dimenzionality a jak se to projevuje na NN-search. [4 body]
+viz http://www.exfort.org/forumbb/viewtopic.php?t=4008
+**Otázky ze zkouškové písemky 6.2.2009**
+. Napsat podrobný pseudokód nebo kód v C/C++ příkladu: Vstupni soubor obsahuje počet trojúhelníků a za ním jsou vypsané všechny vrcholy tvořící dané trojúhelníky (na každém řádku 3 float hodnoty určující jeden vrchol trojúhelníku, tedy vždy 3 řádky určují jeden trojúhelník). Do výstupního souboru zapsat počet unikátních vrcholů a jejich výpis s tím, že vrcholy lišící se jen o nějaké EPSILON jsou shodné (například 1.0 2.0 3.0 je totožné jak 1.01 2.0 3.01), dále vypsat počet trojúhelníků a následně na každém řádku tři indexy ukazující na vrcholy trojúhelníku. Napsat algoritmus se složitostí menší než O(n*n)
+příklad:
+vstup:
+.0 2.0 3.0
+.0 1.0 1.0
+.0 2.0 3.0
+.01 2.0 3.0
+.0 3.0 3.0
+.0 2.0 3.008
+výstup:
+.0 2.0 3.0
+.0 1.0 1.0
+.0 2.0 3.0
+.0 3.0 3.0
+
+2 3
+4 3
+[15 bodů]
+. Uniformní, prostorové dělení, BVH struktury. Napsat jejich vlastnosti. Napsat jejich výhody a nevýhody pro bodová a nebodová data. [3 bodů]
+. Pro struktury z předchozí otázky napsat časovou složitost sestavení a paměťovou náročnost. Napsat konkrétní příklady struktur. [2 bodů]
+. Máme AABB box s minimálními souřadnicemi A a maximálními B a dotaz Q. Spočítat vzdálenost Q od boxu a vrátit ji. Pokud je Q uvnitř AABB vrátit nulu. Vše pro N dimenzí. [3 bodů]
+. Co je to prokletí dimenzionality a jak se to projevuje na NN-search. [2 body]
+Zkouškový otázky z exfortu, tak se snad nikdo nebude zlobit, že sem to sem hodil
 ===== Literatura =====
 pokud by se někomu třeba hodilo..
@@ Řádek 91: / Řádek 191: @@
 [[http://dl.dropbox.com/u/1469682/Real-Time%20Collision%20Detection.pdf|Real Time Collision Detection]]
+===== Data =====
+* 28 testovacích scén v obj, s konfiguračním souborem kde je uložena pozice kamery a případných světel: [[http://temp.keymaster.cz/scenes.zip]]
 ~~DISCUSSION~~

courses/a4m39dpg.1272972028.txt.gz · Poslední úprava: 2025/01/03 18:16 (upraveno mimo DokuWiki)

Nahoru