Název:
Generování navigační mřížky s vysokou přesností
Překlad názvu:
Generating High-Precision Navigation Mesh
Autoři:
Sanchez, Luis ; Gemrot, Jakub (vedoucí práce) ; Rittig, Tobias (oponent) Typ dokumentu: Diplomové práce
Rok:
2021
Jazyk:
eng
Abstrakt: [eng][cze] Navigation meshes are a widely used method for representing the world geometry in a format that can be used by pathfinding algorithms. Frequently used navigation mesh generation algorithms first discretize the input ge- ometry into a grid of voxels and then reconstruct the mesh out of them. This benefits the simplicity and performance of the algorithm, but comes with drawbacks. If the voxels are too large, the navigation mesh is not precise enough and may even have some pathways missing. If the voxels are too small, creation of the mesh takes too long. In this thesis we propose and implement an algorithm that creates a navigation mesh directly from the input geometry without using an intermediate voxel representation. This allows us to preserve original detail where required and results in a more precise navigation mesh. 1Navigační mřížky nebo sítě jsou jedna z běžných metod reprezentace geometrie prostředí ve formátu, který je vhodný pro vyhledávání cest. Algoritmy generující navigační mřížky často nejprve geometrii převedou do voxelové reprezentace a až potom z ní vytvářejí navigační síť. To je výhodné pro jednoduchost a výkonost algoritmu, ale přináší to jiná omezení. Pokud budou voxely moc velké, navigační síť nebude dostatečně přesná. Pokud budou voxely moc malé, vytváření sítě zabere příliš času. V této práci navrhneme a implementujeme algoritmus, který vytvoří navigační mřížku přímo z geometrie prostředí, bez použití voxelizace jako mezikroku. To nám umožní udržet detaily ze vstupních dat a tak dojde k vytvoření přesnější navigační sítě. 1
Klíčová slova:
Výpočetní Geometrie|Navigace|Umělá Inteligence; Computational Geometry|Navigation|Artificial Intelligence