Berechnung kürzester Pfade auf einem Mesh

[zaiph]

Hallo zusammen,

mein erster Post hier, drum hoffe ich einfach mal, das richtige Unterforum getroffen zu haben :)

Es geht darum, dass ich in meinem Programm durch einen Anwender Linien bzw. Kurven auf ein Mesh zeichnen lassen möchte. Dafür müssen zwischen zwei durch den Anwender definierten Punkten auf dem Mesh kürzeste Pfade berechnet werden. Dabei sollen die Pfade aber quasi "durch" die Dreiecke hindurch führen und nicht an den Kanten entlang, da man dann ja Dijkstra oder ähnliches nutzen könnte.
Meine Frage ist jetzt, ob ihr eine effiziente Möglichkeit oder Idee habt/kennt, das zu bewerkstelligen? Ich hatte zunächst die Idee, zunächst einen initialen Pfad zu schätzen, indem man mittels Dijkstra einen kürzesten Pfad entlang der Kanten berechnet. Dann würde man die Pfadvertices und die dazu adjazenten Vertices in eine Graphdatenstruktur einfügen und diesen Graph dann mittels Subdivision zu verfeinern. Auf dem Ergebnis könnte man wieder den Dijkstra berechnen und dann den Vorgang iterativ wiederholen, bis keine Veränderung der Pfadlänge mehr auftritt.
Dieses iterative Vorgehen ist aber wohl eher wenig effizient und nicht so richtig für Echtzeitanwendungen geeignet. Habt ihr andere/bessere Ansätze?
Danke schonmal für eure Anregungen.

[dot]

Schau dir mal an wie man das bei Navigation-Meshes macht. Du willst mit deinem Mesh zwar offenbar was Andres anstellen aber die lösen dort, denk ich, das gleiche Problem.

[eXile]

Suche benutzen, Profit einstreichen (der Link ist hierhin umgezogen). Die dortige Methode funktioniert auf beliebigen Punktwolken (die selber haben dort MLS surfaces generiert), aber auch auf Dreiecksnetzen.

Besser finde ich aber, was Hoppe hier veröffentlicht hat. Das ganze gibt es hier als technical report. Leider schreibst du nicht, wie groß deine Meshes sind, daher kann ich keine Aussagen zur Echtzeitfähigkeit machen.

[zaiph]

Danke euch beiden erstmal für die Antworten. Navigation Meshes scheinen ja ein ähnliches Problem zu lösen. Müsste ich mal gucken, ob ich das übertragen könnte.

eXile:
Also die Meshes, auf denen ich zeichnen möchte, haben so einige wenige 100 bis maximal etwa 100k Dreiecke. Kannst du mir sagen, warum du die Arbeit von Hoppe besser findest? Hast du sowas schon mal implementiert? Oder hast du Erfahrung mit der Performance der Ansätze?