Hierarchické, víceúrovňové a level of detail struktury pro efektivní vyhledávání bodů

Written by Roman Soukal

Roman Soukal

University of West Bohemia

Seminar in Czech
May 13, 2010 at 9:30
University of West Bohemia, UK417

Abstract

Lokace bodu je velmi často řešenou úlohou v oblasti počítačové grafiky. Pro dané dělení d-rozměrného prostoru o n vrcholem a m elementech si pod lokací představíme nalezení takového elementu z daného dělení prostoru, který obsahuje hledaný bod. Na semináři se budeme zabývat především lokací bodu v rovinných triangulacích, v tetrahedronových sítích a na povrchových triangulací 3D modelů. Třetí jmenovaná kategorie bude navíc zúžena o lokaci bodu na povrchu obecného triangualizovaného star-shaped polyhedronu. Lokaci bodu lze provést mnoha možnými způsoby, ovšem optimální očekávané časové složitosti O(log n) na jeden lokalizovaný bod dosáhneme prozatím pouze s použitím speciálních datových struktur. Právě takovýmito strukturami a souvisejícími algoritmy se budeme zabývat. Nevýhodou těchto algoritmů jsou dodatečné paměťové nároky (zpravidla O(n)), které se pokusíme na semináři také prodiskutovat. Velmi úzce souvisejícím tématem je i mezi programátory velice oblíbená konstrukce triangulací pomocí inkrementálního vkládání, jejíž nedílnou součástí je právě lokace bodu. Na semináři se proto budeme i zabývat algoritmy na inkrementální konstrukci triangulací, respektive tetrahedronových sítí...