Original title: Porovnání metod pro rozklad křehkých těles na GPU pomocí 3D Voroného diagramu
Translated title: Comparison of Brittle Body Decomposition GPU Based Methods Using Voronoi Diagram
Authors: Ončo, Michael ; Milet, Tomáš (referee) ; Chlubna, Tomáš (advisor)
Document type: Master’s theses
Year: 2020
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tato diplomová práce se zabývá vytvářením Voroného diagramu ve 3D pomocí grafické karty. Zaměřuje se na jednotlivé algoritmy, které z množiny bodů tento geometrický útvar vytváří a na jejich porovnání. V rámci práce jsou implementovány dva algoritmy.  První je založený na vytvoření Delaunayho tetrahedralizace pomocí paralelního štěpení a transformací čtyřstěnů. Potom je tento útvar převeden na Voroného diagram. Druhý implementovaný algoritmus paralelně vytváří jednotlivé buňky postupným vyhledáváním nejbližších bodů v jejich okolí a osekáváním modelů pomocí vzniklých rovin.  Testování poukazuje na výhody a nevýhody jednotlivých algoritmů a v jakých případech se jejich rychlosti liší. Hlavně je zde upozorněno na citlivost druhé metody s ohledem na nevhodné rozložení bodů uvnitř obalového tělesa. Dále je poukázáno na pomalejší začátek algoritmu vytvářejícího Delaunayho triangulaci. Je ale zjevná i jeho výborná optimalizace pro práci s velkým počtem bodů. Following thesis regards itself with Voronoi diagram creation in 3D using a graphics card. It focuses on and compares certain algorithms that construct the diagram when given set of points in space. For this purpose there have been two algorithms implemented.  First one creates Delaunay tetrahedralization using parallel splitting and flipping of present tetrahedra. Then it transforms it into a Voronoi diagram. The second algorithms utilizes planes to cut a mesh until required shapes are created.  Testing shows the advantages and disadvantages of these algorithms and their relative performance. Main takeaway from this work for these algorithms is the relative sensitivity of the second method to the use of inappropriate shape in relation to given set of points. For the other algorithm its slower start and relative unsuitability for use with smaller sets of points is apparent, but it is greatly optimized for big sets.
Keywords: 3D; Delaunay; GPGPU; tetrahedralization; triangulation; Voronoi; 3D; Delaunay; GPGPU; tetrahedralizace; triangulace; Voronoi

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/195010

Permalink: http://www.nusl.cz/ntk/nusl-432900


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses