Hi,

kennt jemand einen guten algorithmus um punkte zu relaxen?
Also, sagen wir ich habe ein 10x10 vertices wo jeder vertex einen abstand von 1 zu seinen nachbar vertices hat.

Jetzt will ich die Vertices alle ein wenig hin und herschieben und am ende via Relax wieder so zurecht schieben, dass sie alle wider einen abstand von 1 haben.


Im moment mache ich das via Gause-Siedel Relaxion Algorihmus, aber der hat für mich einen ganz großen nachteil.. er basiert auf iterationen.. das heißt, desto feiner die fläche unterteilt ist, desto höher muß ich die iterationen stellen... kann man zwar machen, find ich aber unpraktisch :/

Ich könnte natürlich auch den algo solange laufen lassen, bis jeder abstand wieder 1 ist... aber, ich dachte.. evtl kennt ja jemand noch einen anderen guten Algorithmus dafür..

Aya~

Also Prinzipiel Würde ich da Verlet Integration vorschlagen, bzw. einen Teil davon.
Da:
http://graphics.cs.cmu.edu/nsp/course/15-869/papers/jakobsen.htm

Die Verlet integration beruht im Wesentlichen darauf, das zwischen Massepunkten feste Entfernungen definiert sind. wenn ein Massepunkte verschoben wird, dann wird ein allogrithmus durchlaufen, der alle andere, mit denen er in Verbindung steht einschließlich dem Punkte selbst wieder ein Stück auseinanderschiebt. Das wird dann noch mit alles anderen Punkte gemacht. Wenn man den Allgorithmus einige male Durchläuft, werden alle Abstände gut an den erwünschten angenähert.
Je nach gewünschter Genauigkeit kannst du den Allogithmus eben öfter oder weniger oft durchlaufen. Meistens liefern aber etwa 5 durchläufe eine ziemlich gute Genauigkeit. Alles in allem geht das auch ziemlich schnell.

Aus persönlicher Erfahrung kann ich sagen, dass das ziemlich genial ist. Ich hab damit mal das Umblättern einer Buchseite simuliert. Das sah ziemlich echt aus.

_________________
Es gibt eine Theorie, die besagt, wenn jemals irgendwer genau rausfindet, wozu das Universum da ist und warum es da ist, dann verschwindet es auf der Stelle und wird durch etwas noch Bizarreres ersetzt.
Es gibt eine andere Theorie, die besagt, dass das schon passiert ist.

Die Verlet Integration hat zunächst einmal nichts mit Feder-Masse Systemen zu tun. Sie beschreibt eine gleichförmig beschleunigte Bewegung mittels der jetzigen Position des Objektes x, der vorigen x* und der Beschleunigung a, sowie dt.
Somit kommt man ohne explizite Betrachtung von Geschwindigkeiten aus.

Der Trick bei der Sache ist nun, dass wenn man x verändert, sich die Geschwindigkeit automatisch anpasst, da:

x' = 2 * x - x* + a * dt²

Wenn man nun zwei Partikel nimmt und diese damit simuliert, so schiebt man sie einfach in jedem Zeitschritt so zusammen, dass der Abstand dem geforderten entspricht. Alles andere wird von der Verlet Integration automatisch angepasst. Das gleiche gilt für z.B. Kollisionen. Man stellt sich halt vor, dass man die Partikel mit Federn verbindet (die in diesem Fall unendlich starr sind).

Ich habe das Ganze in meiner Cloth Simulation verwendet und arbeite momentan an einer 2D Rigid Body Simulation, hier gibt es die Cloth Demo:

http://www.delphi-forum.de/topic_Realtime+Cloth+Simulation_81903.html

Bei Bedarf kann ich gerne auch Auszüge aus dem Quelltext posten. (Bei der Demo wird 10-faches Subsampling verwendet. Also wird der Code zur Relaxion insgesamt 10 mal aufgerufen, damit auch wirklich alles seine Richtigkeit hat und die Stabilität der Simulation gewährleistet ist)

mfg