Datové struktury počítačové grafiky

• Stránky předmětu: https://edux.feld.cvut.cz/courses/A4M39DPG/start
• Přednášející: Vlastimil Havran (web)
• Cvičící: Vlastimil Havran

středa 16:15 - 17:45, 18:00 - 19:30 v KN:E-311

v 10.týdnu, tj.21.4.2010, se píše test (60 min)

- v mailu bylo napsáno, že se píše test 5.5.. Na přednášce říkal, že to možná bude o týden dřív. Ale 21.4. podle mě rozhodně ne. — Roman Polášek 2010/04/18 12:30

- Program cvičení od 18:00 (dle mailu):

• 21/4 Konzultace k implementaci
• 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.

• 17/5 a 18/5 v dobe 12:30 az 16:30 konzultacni hodiny

• 19/5 streda v terminu 16:00 az 19:00: Predvadeni funkcnosti jiz implementovanych semestralnich praci na 10 minut.

Č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 (sesbíráno z Exfortu, snad si nebudou nárokovat autorská práva :)):

1.) Je dan hyperobdelnik pomoci 2 rohu A[N], B[N] (uhlopricne) a stred hyperkoule S[N]. Spocitej minimalni polomer koule, tak aby obdelnik lezel cely uvnitr.

2.) SAT, vysvetlit, kolik udela testu.

3.) 3 druhy rozdeleni hiearchickejch struktur.

4.) Nejblizsi priblizny soused, co to je, proc funguje.

5.) Algoritmus pro stavbu hiearchicke struktury, jaky se pouzivaj pomocny struktury.

1) Je dan hyperobdelnik pomoci min a max v kazde ose a bod. Napsat algoritmus pro vypocet vzdalenosti bodu od hyperobdelnika.

2) Cenova fuknce pri dotazu do hierarchicke datove struktury.

3) Jake vlastnosti musi mit vzdalenost, co je to metrika a metricky prostor.

4) Napsat vsechny typy objektovych obalek a pozadavky na ne.

5) Jak funguje algoritmus AESA a jakou ma pametovou slozitost. Jaky algoritmus a jak snizuje jeho pametovou slozitost.

1. Výpočet vzdálenosti bodů od AABB v N rozměrech

2. Průsečík přímky a hypersféry v N rozměrech

3. Rozdíl uniformních a neuniformních struktur

4. 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).

5. SAT, vysvětlit a napsat pseudokód kód, kolik udělá testů pokud se jedná o OBB a kolik pro AABB?

6. 3 druhy rozdělení hierarchických struktur

7. Rozdělení hierarchických struktur, tedy podle uspořádání dat a podle paměti.

8. Nejbližší přibližný soused, co to je a proč to funguje.

9. Algoritmus pro stavbu hierarchické struktury, jaký a k čemu se používají pomocný struktury.

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

11. Cenová funkce při dotazu do hierarchické datové struktury. K čemu se to používá.

12. Jaké vlastnosti musí mít vzdálenost, co je to metrika a metrický prostor.

13. Napsat všechny typy objektových obálek a požadavky na ně.

14. Jak funguje algoritmus AESA a jakou má paměťouvou složitost. Jaký algoritmus a jak snižuje jeho paměťovou složitost.

15. Co je to odhad hustoty pravděpodobnosti (density estimation) a jaký algoritmus se při něm využívá?

16. hierarchie pamětí, typické parametry

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

1. 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ů]

2. Uniformní x hierarchické x BVH struktury… Co kde, proč, složitosti, příklady… [3+2 bodů]

3. 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ů]

4. Algortimy se Z-bufferem, vyjmenovat a jeden si vybrat a vysvětlit. [5 bodů]

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

1. 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:

2

1.0 2.0 3.0

2.0 1.0 1.0

2.0 2.0 3.0

1.01 2.0 3.0

1.0 3.0 3.0

2.0 2.0 3.008

výstup:

4

1.0 2.0 3.0

2.0 1.0 1.0

2.0 2.0 3.0

1.0 3.0 3.0

2

1 2 3

1 4 3

[15 bodů]

2. Uniformní, prostorové dělení, BVH struktury. Napsat jejich vlastnosti. Napsat jejich výhody a nevýhody pro bodová a nebodová data. [3 bodů]

3. 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ů]

4. 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ů]

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

pokud by se někomu třeba hodilo..

Geometric DS for CG (.chm, 20MB, @megaupload) - je tam něco málo o octrees, height fields visualization, kd-trees, bvh…

The Design and Analysis of Spatial Data Structures od H.Sameta - myslim že Havran z toho bere minimálně některý obrázky ;). jinak si tady užijou především ti, co rádi sází stromy - hlavně kd-trees, octrees a quadtrees :) (.pdf, 23MB, @megaupload)

Real Time Collision Detection

* 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