Welcome  |  Students  |  Experiences  |  Publications  |  GeomForge  |  Links  |  Contact
Diskrétne geometrické štruktúry

Podmienky:
  • Známka z predmetu sa udelí len na základe ohodnotenia implementačného projektu.
  • Budú dané 4 zadania projektov, každý študent dostane náhodne jedno zadanie na vypracovanie.
  • Ak nechápete niektorým častiam zadania, treba sa ozvať na mail, spýtať na prednáške alebo prísť osobne.
  • Pri implementácii sa priamo v časti kódu, ktoré riešia zadané geometrické problémy, nemôžu použiť externé zdroje ako externá knižnica, časť kódu z internetu, spolužiakov kód. Pri nájdení takýchto “externých” častí sa projekt ohodnotí Fx. (a hrozí disciplinárne konanie)
  • Vsetky projekty sú v 2D a musia obsahovať interaktívne ovládanie a aj vizuálnu časť, t.j. grafické zobrazenie zadaných aj výsledných prvkov.
  • Po implementácii sa výsledné dielo odovzdá cez stránku NAIS
  • Do hodnotenia sa bude brať len prvý uploadnutý súbor, žiadne dalšie odovzdávania žiadnou formou potom nie sú možné. Dobre si skontrolujte čo posielate a či je tam všetko a v správnej forme.
  • Na stránke NAIS sa zaregistrujete pod svojim menom, môžete použiť existujúce konto ak ste už daný systém používali.
  • Na stránke NAIS uploadnete súbor s názvom dgs_priezvisko.zip obsahujúci zdrojový kód, spustitelný súbor vytvorený v Release konfigurácii pre Win platformu a podrobný návod na ovládanie aplikácie.
  • Projekty sa odovzdávajú počas skúškového obdobia, od 1.1.2015, musia byť odoslané najneskôr 8.2.2015 do 23:59.
  • Po odovzdaní projektu bude hodnotená vizuálna stránka, funkcionalita podľa zadania, spôsob implementácie daného algoritmu, správanie sa programu pri vačšom počte vstupných údajov, ošetrenie “patologických” konfigurácií.
  • Výslednú známku si budete môcť pozrieť pod svojím kontom na stránke NAIS. Projekty sa budú hodnotiť naraz, čiže hodnotenie bude dostupné až niekoľko dní po ukončení odovzdávania.

Prezentácie:

0. Úvod - pdf-en, pdf-sk
1. Intervalové, segmentové, range stromy - pdf-en, pdf-sk
2. Quadtree, k-d stromy - pdf-en, pdf-sk
3. BSP stromy - pdf-en, pdf-sk
4. Ohraničujúce objemy - pdf-en, pdf-sk
5. Reprezentácia objektov I - pdf-sk
6. Reprezentácia objektov II - pdf-sk
7. Dištančné polia - pdf-sk
8. Proximity graphs - pdf-sk
9. Structures on GPU. Články:

Projekty:

1.  Delaunayova triangulácia + Voronoiov diagram
  • Do okna sa budú klikať body. Keď sa naklikne tretí vrchol, z daných troch vrcholov sa vyrobí a zobrazí trojuholník. Po každom ďalšom nakliknutí nového bodu je potrebné vložiť nový bod do predchádzajúcej Delunayovej triangulácie tak, aby sme aj po vložení dostali Delaunayovu trianguláciu.
  • Treba ošetriť aj prípady, keď viacero (>2) daných bodov leží na jednej priamke.
  • Nájdenú trianguláciu je potrebné zobraziť spoločne s naklikanými bodmi a je potrebné zobraziť aj opísanú kružnicu pre každý trojuholník v triangulácii.
  • Zároveň musí projekt obsahovať aj zobrazenie Voronoiovho diagramu, pričom je možné zobraziť oba grafy naraz rôznymi farbami alebo každý graf zvlášť a zvýrazniť vrcholy Voronoiovho diagramu.
  • Voronoiov diagram sa určí ako duálny graf k Delaunayovej triangulacii.
  • Po nakliknutí 1 bodu pravým tlačítkom sa určí bunka Voronoiovho diagramu, ktorá tento bod obsahuje. Bunka sa farebne zvýrazní spoločne s jej stredným určujúcim vrcholom.
  • Časová zložitosť vytvorenia Delaunayovej triangulácie nesmie prekoročiť zložitosť O(n^2)
2.  Marching squares + Quadtree
  • V okne sa bude generovať automaticky pravidelná mriežka, pričom sa bude dať zadávať rozmer mriežky v tvare (2^n + 1) x (2^n + 1). Pri zmene rozmerov sa nové hodnoty v mrežových bodoch dopočítaju zo starých hodnôt bilineárnou interpoláciou.
  • V každom mrežovom bode bude nejaká reálna hodnota, defaultne 0.
  • Hodnota v každom mrežovom bode sa bude musiet dat zmenit nakliknutím na bod a vypísaním novej hodnoty.
  • Mrežové body budú navzájom farebne odlíšené podľa aktuálnej hodnoty.
  • Po stlačeni pravého tlačítka sa nad pravidelnou mriežkou vygeneruje izokontúra pomocou algoritmu marching squares, pričom izohodnota sa zadá tiež používatelom.
  • Nájdená izokontúra sa vykreslí v okne ako zvýraznená lomená čiara.
  • Pri generovaní pomocou marching cubes sa použije quadtree na urýchlenie generovania izokontúry t.j. preskočenia tých častí mriežky, kde sa izokontúra určite nenachádza.
  • Pri generovaní izokontúry pomocou marching cubes sa použije lineárna interpolácia na hraniciach buniek.
  • Po nakliknutí 1 bodu stredným tlačítkom do okna sa vypíše hodnota pre tento bod, ktorá sa určí bilineárnou interpoláciou v príslušnej bunke.
  • Projekt bude obsahovať aj 3 dalšie tlačítka, ktoré po stlačení vyplnia mriežku hodnotami funkcií x^2+2y^2-1, x^3-y, sin(x)-y^2, pričom x a y sú z intervalu <-1,1>.
3.  DCEL
  • V okne sa bude vykreslovať pravidelný n-uholník bez stredného bodu a zároveň nejaká jeho triangulácia, pričom n sa bude dať zadávať používatelom.
  • Nad takýmto grafom sa vždy po zmene n vygeneruje reprezentacia grafu pomocou DCEL obsahujúca polhrany.
  • Časť mimo n-uholníka treba brať ako ďalšiu oblasť.
  • V okne sa vykreslia pri vrcholoch, polhranách a oblastiach ich indexy v príslušných DCEL tabuľkách.
  • Zároveň sa vypíšu tabuľky vrcholov, polhrán a oblastí aj s príslušnými susednosťami.
  • Po nakliknutí na nejakú oblasť sa farebne zvýraznia susedné oblasti, pričom na ich vyhľadanie sa použije DCEL štruktúra.
  • Po nakliknutí na nejaký vrchol sa farebne zvýraznia všetky vrcholy spojené s daným vrcholom hranou, pričom na ich vyhľadanie sa použije DCEL štruktúra.
  • Po nakliknutí na nejakú hranu sa farebne zvýraznia všetky hrany v 2-susedstve (to sú hrany ktoré susedia s danou hranou alebo susedia so susednou hranou danej hrany), pričom na ich vyhľadanie sa použije DCEL štruktúra.
4.  kD-strom
  • V okne sa budú zadávať body nakliknutím ľavým tlačítkom body.
  • Vždy pri pridaní nového bodu sa nad danými bodmi vytvorí vyvážený kD-strom tak, aby v listoch bol nanajvýš jeden bod.
  • Hranice buniek kD-stromu sa v okne zobrazia spolu s nakliknutými bodmi.
  • Po nakliknutí 1 bodu pravým tlačítkom sa použije daný kD-strom na nájdenie k najbližších bodov (číslo k bude zadané používateľom) z daných n bodov k nakliknutému bodu v logaritmickom čase. Nájdené najbližšie body sa zvýraznia.
  • Po stlačení a držaní stredného tlačítka sa ťahaním kurzora zadá obdľžnik. Potom sa pomocou kD-stromu nájdu všetky zadané body, ktoré v danom obdĺžniku ležia a zvýraznia sa.
  • Držaním Shift klávesy a kliknutím ľavého tlačítka sa vyberá oblasť kD-stromu. Potom sa pre túto oblasť nájdu všetky susedné oblasti(ktoré predstavujú listy v strome) a vykreslia sa výraznou farbou.


Rozdelenie projektov:

Projekt 1 Projekt 2 Projekt 3 Projekt 4
Andrej Bebják Ján Baláž Samuel Adamec Jozef Bakus
Miloš Blaščák Peter Bíró Branislav Ballon Milan Darjanin
Lucia Budinská Anton Blahunka Péter Dobsa Martin Filek
Paula Budzáková Jakub Čulík Cyril Gramblička Boris Gundzík
Jakub Gaľ Lucia Ďurikovičová Katarína Iványiová Rastislav Hekel
Branislav Heriban Tomáš Gunčaga Jakub Jantošík Matej Hulička
Juraj Holas Timotej Krajči Marek Jelen Rudolf Krumpál
Michal Janáčik Pavol Kunovský Pavol Knor Eva Libantová
Martin Kalmancai Michal Rataj Marek Melicherčík Miroslav Matušťák
Miroslava Matúšková Adam Riečický Jakub Piteľ Mária Mrocková
Ľudmila Nemsilajová Lukáš Sedláček Martin Reiberger Michal Páleník
Stanislav Párnický Michal Smutný Michal Rohleder Róbert Stríbrnský
Peter Svítok Lýdia Uhrinová Martin Slavkovský Martin Štefaňák
Alexander Takács Martin Varga Tomáš Trungel Peter Šulík
Michal Zemko Matúš Vojčík Marek Zajko Ján Zelinka
Richard Dvorský


Podklady:

Základný zdroj je kniha Elmar Langetepe, Gabriel Zachmann: Geometric Data Structures for Computer Graphics, AK Peters (poskytnem na požiadanie)
Distančné polia
Geometric Data Structures
Základné štruktúry (polia, zoznamy, BPS, AVL stromy)
Geometrické štruktúry (DCEL, winged-edge, quad-edge)
Geometrické štruktúry 2 (winged-edge, half-edge, quad-edge)
Half-edge
Quad-edge (str. 19-21)
Reprezentácie telies
Quad-trees, octrees, K-d trees, BSP trees, Bounding Volumes hierarchies
Grafy