Beräkningen av geodesiska banor och avstånd på triangelmaskor är en vanlig operation i många datorgrafikapplikationer. Vi presenterar flera praktiska algoritmer för beräkning av sådan geodesik från en källa till en eller alla andra punkter effektivt. För det första beskriver vi en implementering av den exakta algoritmen "one source, all destination" som presenteras av Mitchell, Mount och Papadimitriou (MMP). Vi visar att algoritmen går mycket snabbare i praktiken än vad som föreslås av värsta fall analys. Därefter utökar vi algoritmen med en sammanslagningsoperation för att erhålla beräkningseffektiva och korrekta approximationer med begränsat fel. Slutligen, för att beräkna den kortaste vägen mellan två givna punkter, använder vi en lägre bunden egenskap hos vår ungefärliga geodesiska algoritm för att effektivt beskära gränsen för MMP algoritmen, vilket ger en exakt lösning ännu snabbare.
REF observerade att den värsta drifttiden för MMP-algoritmen är sällsynt, och i praktiken kör algoritmen i subkvadratisk tid.
Fast exact and approximate geodesics on meshes
{'venue': "SIGGRAPH '05", 'journal': None, 'mag_field_of_study': ['Computer Science']}