In letzter Zeit hat sich hier einiges getan, sowohl am Projekt als auch bei mir

Als erstes habe ich die Physikintegration erweitert, so dass sie nun Kollisionen korrekt lösen kann. Kollisionen haben bisher zwar gut funktioniert, aber sobald man Gravitation einschaltete, fingen die Objekte an, auf dem Boden herumzuzittern (das Zittern von Physikobjekten kennt man bestimmt aus dem einen oder anderen Spiel, Hellgate London war da besonders schlimm). In der Verletintegration löste sich das von selbst, hier muss ich nachhelfen, indem ich den exakten Zeitpunkt der Kollision bestimme und von da an weiterrechne.
Im Moment ist es aber noch nicht so exakt, wie es sein sollte - Objekte fangen nach Stillstand wieder leicht an zu Zittern und bewegen sich dadurch wieder - aber das muss ich wohl durch einen kleinen Workaround lösen.

Screenshot:

Download
Mit Linksklick kann man zufällige Kräfte auf die Objekte einwirken lassen und die gelegentlich auftretenden Physikfehler bewundern

Des weiteren habe ich mir diese Woche BlitzMax zugelegt. Nach 2.5 Jahren B3D dachte ich mir, es sei Zeit, auf den Zug aufzuspringen. Die Sprache gefällt mir bisher sehr gut, für praktisch alles, wo ich in B3D noch Workarounds brauchte, gibt es in BMax eine elegante Lösung.
Ich weiss nicht, ob ich die Physiksimulation portiere und parallel in beiden Sprachen weiterentwickle oder aber ganz auf die B3D - Version verzichte, das kommt ganz auf meine Motivation an.

Als wohl grösste Umwälzung wurde ich diesen Monat bei Chaos Interactive aufgenommen. Für mich, der ich ja zum Zeitpunkt der Anfrage noch nicht mal BMax besass, ist das natürlich eine grosse Ehre und ich freue mich, von nun an mit den Jungs von CI zusammenarbeiten zu dürfen.

Nachdem ich in letzter Zeit viel mit der Physik - DLL herumgespielt, -probiert und programmiert habe, komme ich schlussendlich auf den Schluss, die Entwicklung vorerst einzustellen.
Das liegt nicht etwa an einem Motivationsloch, sondern daran, dass mir die Verlet - Integration immer mehr missfällt. Keine 100%ig stabilen Objekte garantieren zu können ist das eine, zum anderen kommt es mir mehr und mehr wie Voodoo - Hokuspokus vor; man kann nicht direkt nach Gesetzen der Physik rechnen, sondern bewegt einen Punkt mal hier und mal dahin, und schaut dann, was passiert.

Ich habe mich daher entschlossen, die Engine von Grund auf neu zu schreiben, und zwar aufbauend auf einer neuen Herangehensweise, die als 'Rigid Body Simulation' bekannt ist.
Ein Objekt wird dabei als komplett starr (eng. 'rigid' - daher der Name) angesehen und die bekannten Gesetze der Physik darauf angewendet.
Das ist zwar um einiges komplizierter, aber die ersten Ergebnisse sprechen für sich - zumindest aus meiner Sicht den Mehraufwand komplett wert.

Ich möchte hier aber nicht einfach so mit leeren Händen und Zukunftsvisionen auftreten. Gestern habe ich nämlich die ersten korrekt berechneten Kollisionen zwischen beliebigen konvexen Objekten hinbekommen; glücklicherweise konnte ich Teile der alten Kollisionsroutine wiederverwerten, ansonsten wäre sicher eine zusätzliche Woche dabei draufgegangen

Screenshot:


Download

Wie man in der Demo vielleicht sieht, sind die Objekte komplett starr. Ausserdem bleibt die Gesamtenergie komplett erhalten, während sich in der Verlet - Integration mit der Zeit eine leichte Dämpfung einstellt, wodurch die Objekte langsam zum Stillstand kommen. Ausserdem ist der Rechenaufwand (noch) sehr viel kleiner, da man relativ viele Verbindungen einsparen kann, die in der Verlet - Integration benötigt werden, um Objekte einigermassen zu stabilisieren (die Anzahl benötigter Verbindungen sinkt von N! auf N-1, wer es genau wissen will; N=Anzahl Vertices).

Bis ich mit der neuen Herangehensweise auf dem Stand der alten Engine bin, wird es wohl noch eine Weile dauern. Beispielsweise die Kollisionsberechnung wird noch einiges an Arbeit benötigen, da ich ein paar wichtige Aspekte bisher ausser Acht lasse (fällt im Moment noch nicht auf, aber fliegt einem um die Ohren, sobald man Gravitation einschaltet). Ich arbeite aber daran - versprochen

Mit der neuen Methode besteht vieleicht sogar die Möglichkeit, die Physikberechnung um eine Dimension zu erweitern. Allerdings konzentriere ich mich vorerst mal auf 2D, um die Grundlagen zu begreifen.

In den letzten Tagen habe ich die neue Berechnungsart mit Fragmenten weiter optimiert und verbessert, damit es einigermassen benutzbar wird. Lustigerweise läuft die Berechnung nun schneller als vorher, obwohl es eigentlich langsamer sein müsste (durch die Fragmente entsteht ein nicht unerheblicher Mehraufwand bei der Berechnung); ich hinterfrage das mal nicht. Solange es schneller läuft, kann ich ja zufrieden sein

Die einzelnen Fragmente eines Physikobjekts können nun untereinander beliebig viele Vertices und Edges teilen, was man dazu ausnutzen kann, komplexere Objekte zu erstellen als bisher. In einem Auto beispielsweise teilt sich das Chassis mit den beiden Rädern jeweils einen Vertex. Die Räder sind nun nicht fix am Auto befestigt, sondern können sich beliebig um den geteilten Vertex drehen; die geteilten Vertices werden zur Dehachse der Räder.
Das habe ich natürlich gleich ausgetestet und eine kleine Demo zusammengestellt:



Download

Die Bedienung ist relativ einfach: Mit Pfeiltaste Links/Rechts kann man den Wagen beschleunigen und mit Pfeiltaste nach oben kann man den Wagen wieder aufrichten, falls er auf dem Rücken liegt.

Wie man der Demo entnehmen kann, habe ich der Funktion NNP_DebugRender zwei Parameter für Scrolling verpasst (stand schon lange auf meiner Liste). Auf Hinweis von ToeB habe ich ausserdem eingebaut, dass man Vertices einzeln befestigen kann anstatt nur das Objekt als ganzes.
Bevor ich aber die nächste Version herausbringen kann, muss ich noch die Funktion einbauen, die konkave Objekte automatisch in Fragmente zerlegt, da es von Hand ziemlich aufwändig ist.

Letzten Montag habe ich ausserdem die Note für meine Arbeit erfahren - eine 5.5 (Schweizer Note! In Deutschland eine 1.5). Kritisiert wurde vor allem der fehlende Schritt von Theorie zu Programmcode, sprich, ich hätte noch beschreiben sollen, wie ich die Theorie dann schlussendlich umgesetzt habe.
In drei Wochen steht dann die Präsentation der Arbeit an, die mit 50% zur Maturarbeitsnote dazuzählt. Was genau ich während des 10-minütigen Vortrags machen will, weiss ich noch nicht so genau, aber so langsam sollte ich mir mal Gedanken darüber machen.

Ich habe die letzten Tage verschiedene Herangehensweisen auf dem Papier durchgespielt, um die optimale Methode für konkave Objekte zu finden.
Schlussendlich habe ich mich dazu entschieden, die DLL nochmal kräftig umzuschreiben. Neu besteht ein Entity jetzt aus einzelnen Fragmenten. Ein Fragment kann beliebig viele Vertices und Edges des Elternobjekts enthalten und wird bei der Kollision einzeln betrachtet.

Das kann man dazu verwenden, ein konkaves Objekt in einzelne konvexe Fragmente zu zerteilen. Die Kollisionsberechnung verlangt nämlich immer noch konvexe Polygone; da sie aber die Fragmente einzeln betrachtet, ist ein konkaves Objekt trotzdem möglich, solange die Fragmente alle konvex sind.

Die Objekte muss man im Moment noch von Hand in Fragmente zerteilen, wenn sie nicht konvex sind. Das ist eine Heidenarbeit, eine Funktion, die das automatisch erledigt, ist aber schon in Arbeit

Ich habe mal eine kleine Demo zusammengestellt, um das zu testen. Sie läuft leider unvorstellbar langsam im Vergleich, da ich die Objekte halbautomatisiert in Dreiecke zerlegen lasse und jedes Dreieck als ein Fragment hinzufüge.
Dadurch enthält jedes Objekt doppelt so viele Fragmente, wie in einer optimierten Konstellation möglich wären - ausserdem ist die DLL auf das neue System mit Fragmenten noch gar nicht optimiert.
Mittlerweile bin ich einfach froh, dass es überhaupt läuft, und gönne mir jetzt erst Mal eine Verschnaufpause

Screenshot:


Download

Mit der Unterstützung der Portalsadministration ist die Dokumentation der Befehle nun auch hier in der Hilfe vom BBP zu finden: Kategorie NooNooPhysics

Ausserdem musste ich einsehen (dank dem Hinweis von Smily ), dass es wohl für Programmierer einfacher wäre, wenn ich den Code unter eine Lizenz stelle. Mit Hilfe von akaz habe ich mich dann für die zlib Lizenz entschieden.
Das bedeutet also Zitat:

Zum einen erlaubt es jegliche Verwendung des Codes, inklusive Änderung, Verteilung und Verwendung in kommerziellen Projekten. Trotzdem bleibt aber der Schutz davor, dass es jemand plötzlich als sein eigenes Werk ausgibt; der Verweis zum Original und auf mich bleibt erhalten.

Die (L)GPL wollte mir nicht gefallen, da veränderte Versionen der Engine weiterhin Open Source sein müssten - das könnte Programmierer davon abschrecken, eigene Dinge einzubauen, da sie nicht unbedingt ihren Code preisgeben wollen.

Leider bin ich in der Zwischenzeit zu nicht viel anderem gekommen, ich werkle aber insgeheim an verschiedenen Methoden, nicht-konvexe (konkave) Objekte automatisch zu erkennen und in mehrere konvexe Objekte zu splitten. Die Grundlagen dafür habe ich bereits, aber ich muss noch untersuchen, wie die Kollisionsberechnung darauf reagiert, wenn zwei Objekte einen Vertex oder eine Edge teilen.

Die Variable 'CollisionEdge' würde dann von dieser Funktion automatisch gesetzt werden, um dem Programmierer die Handarbeit zu ersparen, aber trotzdem die Performance zu verbessern.

Auf meiner ToDo - Liste steht im Moment nicht viel mehr - neben der Unterstützung von konkaven Objekten nur noch kompliziertere Themen wie Luftwiderstand, Wasser und Gase.
Falls ihr noch Featurewünsche habt, bin ich ganz Ohr

PS: Ja, die ersten beiden Punkte stehen schon im Projektethread. Der Vollständigkeit halber sei es hier aber aufgeführt.

Ich habe heute noch ein wenig mit dem dritten Beispiel aus dem Downloadpaket rumgespielt und ein kleines Funpark - Level draus gebastelt.

So Zeug macht mir immer einen Heidenspass, weswegen ich auch nicht zu viel anderem gekommen bin

Screenshot:


Wer will, kann sich das noch herunterladen und auch ein wenig damit herumspielen: Download

Es ist ein gutes Level, um die Reibung zu testen - ohne Reibung würde man sich nur auf der Stelle drehen.
Vielleicht mache ich irgendwann noch ein kleines Spiel draus, aber im Moment gibt es leider noch viel zu viel zu tun.

Ich will hier gar nicht lange um den heissen Brei herumreden, sondern gleich auf den Projektthread verweisen: *klick*

Nach einem kleinen Endspurt über die letzten Tage ist meine Maturarbeit endlich fertig
Morgen werd ich sie im Copy Shop binden lassen, um am Montag endlich damit abschliessen zu können.

Ich muss noch eine Dokumentation zur DLL schreiben und natürlich noch ein paar Beispiele, damit ich die Physikengine ebenfalls am Montag für den öffentlichen Gebrauch raushauen kann.

Wer die Maturarbeit lesen will, kann dies gerne tun: Link (PDF).
Kritik und Anregungen darf man gerne in den Kommentaren posten, obwohl es dann eh zu spät ist

Ich habe nun intensiv an der Physiksandbox weitergeschraubt und sie in einen halbwegs akzeptablen Zustand gebracht.

Screenshot:


Die Bedienung ist anfangs nicht intuitiv, daher sollte man folgendes beachten:

Die Sandbox besteht aus vier Modi: Simulationsmodus, Vertexmodus, Edgemodus und Objektmodus (von links nach rechts).

Die Modi lassen sich durch Mausklick auf den entsprechenden Button auswählen.

Im Objektmodus kann man neue Objekte erstellen und diese editieren. Wenn man 'Würfel erstellen' oder 'Kreis erstellen' angewählt hat, kann man ins Fenster klicken und mit gedrückter Maustaste das Objekt auf die gewünschte Grösse ziehen. Der Schieberegler bestimmt dabei, mit welchem Reibungsfaktor das Objekt erstellt wird. Hat man 'Objekte editieren' ausgewählt, kann man mit linker Maustaste Objekte auswählen und mit gedrückter linke Maustaste Objekte verschieben. Mit gedrückter rechter Maustaste kann man Objekte drehen. Mit Shift+Gedrückte linke Maustaste skaliert man Objekte, mit Ctrl+Gedrückte linke Maustaste kopiert man ein Objekt.
Ein ausgewähltes Objekt lässt sich jederzeit mit Delete löschen. Alle Objekte sind in grau gezeichnet, das momentan ausgewählte Objekt ist rot hervorgehoben.
Wenn man ein Objekt auswählt, lässt sich der Reibungsfaktor nachträglich noch mit dem Schieberegler ändern.

Im Edgemodus kann man mit Linksklick eine Feder des momentan ausgewählten Objekts anwählen. Mit Delete kann man diese löschen.
Mit Rechtsklick wählt man einen Vertex in der Nähe aus und mit nochmaligem Rechtsklick in der Nähe eines anderen Vertex' erstellt man eine Feder zwischen den beiden.

Im Vertexmodus kann man mit Linksklick Vertices auswählen und mit gedrückter linker Maustaste verschieben. Mit Rechtsklick erstellt man einen neuen Vertex. Mit Delete löscht man den gerade ausgewählten Vertex.

Im Simulationsmodus lässt man dann die Simulation laufen. Wenn man in das Vektorwidget klickt, kann man die Richtung der Gravitation ändern, mit dem Schieberegler die Genauigkeit der Simulation.
Mit der linken Maustaste lassen sich ausserdem noch Vertices der Objekte auswählen und mit gedrückter Maustaste kann man den ausgewählten Vertex hochheben.


Download

Bei Bugs und Anregungen bitte einen Kommentar schreiben - ich habe das Programm noch nicht gründlich austesten können, daher ist mit eventuellen Fehlern zu rechnen.
Ich wünsche dann viel Spass damit

Gestern habe ich doch tatsächlich 4 Stunden lang mit Debugging verbracht, um herauszufinden, warum die Reibung nach der Portierung in die DLL nicht funktioniert hat. Irgendwann ist mir dann aufgefallen, dass ich in einer Zeile aus Versehen X und Y vertauscht habe - das hat sich natürlich fatal auf die folgenden 100 Zeilen Code ausgewirkt, weshalb die Eingrenzung des Fehlers auch entsprechend lange ging. Aber jetzt läuft es perfekt und zieht praktisch keine Berechnungszeit, was mich erstaunt hat - ich verwende einige Funktionen aus der Trigonometrie, aber mittlerweile scheinen die auch nicht mehr so langsam zu sein.

Weiterhin habe ich eine neue Kollisionserkennung entwickelt; ich verwende zwar immer noch das Separating Axis Theorem, habe aber mithilfe der Hesseschen Normalform (die ich mittlerweile in fast jedem Programm verwende - ist wohl ein Mädchen für alles ) komplett auf die Matrizenrechnungen verzichten können. Lustigerweise hat sich das gar nicht so gross auf die Geschwindigkeit ausgewirkt, wie zuerst angenommen. Die Kollisionsberechnung ist zwar 5-10% schneller (je nach Objektkonstellation), aber ich hätte da viel mehr erwartet. Die Matrizenrechnungen waren wohl gar nicht so langsam, wie ich immer gedacht habe. Das Umsetzen der neuen Methode in C hat mir dann wieder ein paar Falten unter den Augen beschert - ich hatte nämlich in einem Moment geistiger Umnachtung eine if - Abfrage so definiert: Code: [AUSKLAPPEN] [EINKLAPPEN]
Wer nicht mit C vertraut ist: Diese Bedingung ist immer Wahr, da ich eine Zuweisung mache anstatt einer Abfrage. Richtig wäre Code: [AUSKLAPPEN] [EINKLAPPEN]
Nach zwei Stunden ist mir das dann aufgefallen. Soviel Zeit wie in den letzten zwei Tagen ist mir noch nie für Debugging draufgegangen, aber jetzt bin ich einfach froh darüber, dass es funktioniert, wie es sollte.

Um noch mehr Geschwindigkeit rauszuholen, habe ich den Federn einen neuen Modus verpasst, ein Feld namens 'CollisionEdge'. Es bestimmt, ob die Feder zur Aussenhülle gehört oder nicht. Federn können nämlich auch im Innern des Objekts sein, um als Stützverbindungen zu dienen. Dann sind sie aber für die Kollisionsberechnung wertlos, weswegen der Programmierer bei der Erstellung der Feder bestimmen kann, ob sie zur Aussenhülle gehört oder nicht.
Eine automatische Erkennung habe ich noch nicht eingebaut, aber ich schätze, das kommt noch irgendwann. Ausserdem arbeite ich nebenbei noch an einem Algorithmus, der aus einer Punktmenge die stabilste Form berechnet (also die Federn so setzt, dass das Objekt möglichst stabil ist). Dafür verwende ich die Delaunay - Triangulation, wem das ein Begriff ist. Dieser Algorithmus garantiert ausserdem, dass das Objekt konvex ist - das ist nämlich weiterhin eine Einschränkung der Kollisionserkennung.

Des weiteren habe ich einige kleine Umstellungen gemacht, um alles ein wenig zu beschleunigen (Funktionen als Inline definiert etc.).
Alles in allem habe ich die Physikberechnungen um ~25% beschleunigen können, obwohl die Reibung neu dazugekommen ist. Vor allem der neue Modus der Federn hat relativ viel rausgeholt - ein stabiler Würfel besteht ja aus vier Federn aussen und zwei Diagonalen Federn, die ein Zusammenklappen verhindern. Durch den neuen Modus kann der Algorithmus einen Drittel der Federn verwerfen, um sich dann nur auf die relevanten zu konzentrieren - wenn man also die Möglichkeit hat, sollte man also von diesem Feature rege Gebrauch machen.

Für Spiele habe ich noch mehrere wichtige Objektmodi eingebaut namens Locked, CollisionEnabled, RotationEnabled und CollisionGroup. Objekte, die mit Locked gekennzeichnet sind, bewegen sich nicht - z.B. ein Level sollte man so definieren, sonst kann es der Spieler nach unten treten, was ja nicht sein sollte (ausser, das Spiel heisst 'Walker, Texas Ranger').
Per CollisionEnabled kann man die Kollision für einzelne Objekte ein und ausschalten, um so Leistung zu sparen. Mit RotationEnabled legt man fest, ob sich das Objekt drehen kann. Der Hauptcharakter eines Spiels sollte sich ja nach Möglichkeit nicht flach auf den Boden legen, wenn er von einer Kiste am Kopf getroffen wird, daher kann man seine Rotation sperren.
CollisionGroup schliesslich bestimmt, welche Objekte miteinander kollidieren und welche nicht. Die Variable enthält im Grunde genommen einfach eine Zahl - Objekte mit verschiedenen Zahlen kollidieren, Objekt mit der gleichen Zahl nicht. Der Wert in Collisiongroup wird von CreateEntity() automatisch verteilt, so dass Objekte standardmässig kollidieren. Wenn man das anders möchte, kann man den Wert nachher natürlich noch anpassen.

In der Include habe ich noch einige formelle Sachen berichtigt - ich verwendete nämlich einen Mischmasch von Particle/Constraint/Vertex/Edge, aber jetzt heissen Punkte definitiv Vertex und Verbindungen Edge (anfangs nannte ich die Punkte Particle und die Verbindungen Constraint, aber mittlerweile finde ich die kürzeren Begriffe Vertex und Edge schöner).
Ausserdem sind jetzt alle Funktionen mit dem Präfix NNP_ (für NooNooPhysics) versehen; neu sind ausserdem die Funktionen MoveEntity, TurnEntity, PositionEntity und FitEntity.

Die Physiksandbox, die ich noch für die Maturarbeit schreiben muss, kommt gut voran. Man kann bereits Primitiven erstellen (Würfel/Kreise/Dreiecke), diese bearbeiten (neue Punkte und Verbindungen erstellen, bestehende Punkte/Verbindungen löschen, ganze Objekte löschen, drehen, bewegen) und die Simulation anschliessend laufen lassen. Während die Simulation läuft, kann man die Objekte herumwerfen, wenn man Spass daran hat.
Was dort noch fehlt, sind Menüs, um Dinge wie Federkraft und Reibungsfaktor für jedes Objekt einstellen zu können und noch Einstellungsmöglichkeiten für die Gravitation und die Genauigkeit der Berechnungen.
Geplant sind nochTools zum kopieren und skalieren von Objekten, aber das sollte kein Problem sein.


Das war jetzt wieder ein laaanger Eintrag ohne Bilder und ohne Download - aber versprochen, im nächsten Eintrag gibt es wieder was für die Augen (und vielleicht schon eine neue Demo).