Wie implementiere ich einen Constraint-Solver für 2D-Geometrie?

Ich würde versuchen, einen ähnlichen Ansatz wie dies zu verwenden.

1. Jeder Schieberegler zieht alle Schieberegler zurück

   mit der Kraft, die durch den Abstand ^ 2 skaliert wird, wie alle von ihnen würden die gleiche Polarität elektrische Ladung oder Federn haben, die zwischen einander angebracht sind.

2. Hinzu kommt Reibung, die durch die Geschwindigkeit skaliert wird

   spielt keine Rolle, wenn Luft v^2 oder flüssig v^3

   ist

3. implementiert kinematische Einschränkungen

   nur horizontal und vertikal gleiten sollte es wirklich einfach sein.

4. Führen Sie eine physische Simulation durch und warten Sie, bis sie in den stabilen Zustand v=~0

   konvergiert

   Wenn lokale Min / Max getroffen wird, schüttle die ganze Sache ein wenig oder ordne die ganze Sache zufällig an und versuche es erneut. Sie können dies auch tun, um eine andere Lösung zu erhalten.

[Bearbeiten4] C ++ - Lösungsbeispiel

1. Strukturen / Klassen zur Darstellung des Slider-Systems

   Um späteren Code zu erleichtern, unterstütze ich keine geschlossenen Schleifen oder doppelte Verankerung. Deshalb ist der i1-Schieberegler (am meisten rechts) nicht an irgendetwas verankert (wird nur forcefield bereitstellen). Ich habe am Ende diese Slider-Definition:

   

   Sehen Sie sich die Quelle von class _slider für weitere Informationen an.

2. rendern

   Dash-Dash bedeutet fester Schieberegler. Die silbernen sind horizontal, aqua bedeutet vertikal und gelb wird mit der Maus ausgewählt. Mag später rot sein bedeutet eine Art von Fehler / stecken oder etwas für Debug-Zwecke. Bei Kraftfeldlösern füge ich manchmal die Feldstärke als rot-blaue Skala hinzu, bin mir aber nicht sicher, ob ich sie hier implementieren werde oder nicht.

   Um dies einfach zu halten, werde ich keine Zoom / Pan-Funktionen implementieren, da Ihre Dimensionen für das direkte Rendern ohne Transformationen praktisch sind.

   

3. Ersteinrichtung implementieren

   %Vor%

   Dabei ist ia der übergeordnete Index und ib ist der untergeordnete Index (die Slider-Klasse selbst enthält ib als übergeordnetes Element, aber das wäre für init verwirrend, da Sie mit einem Element verknüpfen müssten, das noch nicht existiert ib Transformation wird in der Funktion sys.add behandelt). sys ist eine Klasse, die das ganze Ding enthält, und sys.add fügt nur einen neuen Schieberegler hinzu und gibt seinen Index von Null zurück. Das x,y ist die relative Position zum übergeordneten Element.

   Um den Umfang des Codierens zu verringern, darf dieses Setup die Beschränkungen nicht in Konflikt bringen. Die Übersicht über dieses Setup befindet sich im vorherigen Abschnitt.

   Achten Sie darauf, dass die Reihenfolge der Schieberegler für horizontale Schieberegler vertikal und von oben nach unten links ist, um korrekte Abhängigkeitsfunktionen zu gewährleisten.

4. Mausinteraktion

   nur einfache Slider-Bewegung zum Debuggen und Anpassen der anfänglichen Setup-Werte. Und oder Handhabung von Kisten. Sie müssen mit Mausereignissen umgehen und den nächsten Schieberegler auswählen, wenn Sie ihn nicht bereits bearbeiten. Und wenn die Maustaste gedrückt wird, verschieben Sie den ausgewählten Schieberegler an die Mausposition ...

5. physische Abhängigkeit / Interaktion

   Ich vereinfache dies ein wenig, also habe ich gerade eine Prädikatfunktion erstellt, die für den angegebenen Schieberegler aufgerufen wird und sie zurückgibt, wenn sie oder ein Kind / Anker unter einem Konflikt mit definierten Beschränkungen steht. Dies ist viel einfacher zu codieren und dann zu debuggen, um die Position so zu aktualisieren, dass sie der tatsächlichen Bedingung entspricht.

   Die Verwendung ist dann ein bisschen mehr Code. Speichern Sie zuerst die aktuelle Position für den aktualisierten Slider. Aktualisieren Sie dann den Schieberegler auf die neue Position / den neuen Status. Wenn Einschränkungen nicht erfüllt sind, stoppen Sie die tatsächlichen Slider-Geschwindigkeiten und stellen Sie die ursprüngliche Position wieder her.

   Es wird etwas langsamer sein, aber ich bin zu faul, um den vollständigen Constraint Updater zu programmieren (dieser Code könnte wirklich komplex werden ...).

   Ich erkenne 2 Wechselwirkungen parallel und senkrecht. Die Parallele ist geradlinig. Aber die Senkrechte ist die Wechselwirkung zwischen der Kante des Schiebers und den senkrechten Schiebern in der Nähe, die die bereits schneidenden Schieber (a, b, verankert oder gerade Kreuzung) während des Anfangszustandes nicht enthalten. Also habe ich beim Start eine Liste von sich überschneidenden Slidern ( ic ) erstellt, die für diese Interaktion ignoriert werden.

6. physikalische Simulation

   Einfach Newton - D'Lambert Physik für nicht relativistische Geschwindigkeiten wird ausreichen. Setzen Sie bei jeder Iteration die Beschleunigungen ax,ay auf Feldstärke und Reibung.

7. Feldlöser

   Dies ist ein Satz von Regeln / Gleichungen, mit denen Simulationsbeschleunigungen für jeden Schieberegler auf die Lösung konvergieren. Am Ende hatte ich elektrostatische Rückholkraft F = -Q/r^2 und lineare Dämpfung der Geschwindigkeit. Außerdem wurden absolute Geschwindigkeits- und Beschleunigungsbegrenzer implementiert, um numerische Probleme zu vermeiden.

   Um die Lösungszeit und -stabilität zu erhöhen, habe ich Präzisionssteuerungsmodi hinzugefügt, bei denen die elektrische Ladung abnimmt, wenn die maximale Gesamtgeschwindigkeit der Schieberegler abnimmt.

Hier der vollständige Klassencode C ++ / VCL :

Sie können das VCL-Zeug ignorieren, es ist nur API für die Interaktion mit meinem App-Fenster und Rendering. Der Solver selbst benötigt nichts davon. Ich habe meine dynamische lineare Array-Vorlage List<T> verwendet, also hier ein paar Erklärungen:

• List<double> xxx; ist identisch mit double xxx[];
• xxx.add(5); fügt 5 zum Ende der Liste hinzu
• xxx[7] access array element (sicher)
• xxx.dat[7] access array element (unsicherer aber schneller direkter Zugriff)
• xxx.num ist die tatsächlich verwendete Größe des Arrays
• xxx.reset() löscht das Array und setzt xxx.num=0
• xxx.allocate(100) räumlicher Speicherplatz für 100 items
vor

Die Verwendung ist einfach nach der richtigen Initialisierung von bullet # 3 wie folgt:

Anstatt für den Zyklus rufe ich dies im Timer auf und zeichne das Fenster neu, so dass ich die Animation sehe:

Die Choppyness ist auf eine nicht einheitliche GIF Abtastfrequenz zurückzuführen (einige Frames aus der Simulation werden unregelmäßig übersprungen).

Sie können mit den Konstanten für vel,acc limits, dämpfenden Koeffizienten und der Modussteuerung if s spielen, um das Verhalten zu ändern. Wenn Sie auch einen Maus-Handler implementieren, können Sie die Schieberegler mit der linken Maustaste verschieben, damit Sie aus festgefahrenen Fällen herauskommen können ...

Hier steht eine eigenständige Win32-Demo (kompiliert mit BDS2006 C ++ ).

• Demo Klicken Sie auf den langsamen Download unter der großen Magenta-Taste, geben Sie den alphanumerischen Code mit vier Buchstaben ein, um den Download zu starten, ohne dass eine Registrierung erforderlich ist.

Weitere Informationen dazu, wie die Solver-Force-Berechnung funktioniert, finden Sie unter Verwandte / Folge-QA:

• Zwangsweises Layout für beschränkte rechteckige Formen erzwingen