Berechnung kürzester Pfade auf einem Mesh
Verfasst: 08.07.2011, 00:17
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.
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.