Eine eigene 3D Physikengine programmieren?

Werbeanzeige

Supercomputer

Frischling

Beiträge: 28

Beruf: Schüler

24.06.2014, 21:41

Eine eigene 3D Physikengine programmieren?

Hallo,
ich arbeite unter anderem aktuell an einer 3D Physikengine, jedoch habe ich ein paar offene Fragen, die eventuell auch anderen bei der Entwicklung einer eigenen Engine im Kopf schwirren.
Ich würde diesen Thread gerne als ein Tutorial zur eigenen Phsikengine aufbauen, so das auch andere User sich hieran orientieren können und eventuell Fehler die andere und ich gemacht haben nicht immer und immer wieder durchlaufen.

Nun zu meiner aktuellen Planung:
Mit einer Methode der Engine Klasse, gibt es die Möglichkeit, einen maximalen Koordinatenbereich (X, Y, Z) fest zu legen, der Maximale Bereich ist aktuell Beschränkt, da ich hierfür einen usigned long int nutze.
In dem daraus resultierendem 3D Rechteck, oder der 2D Ebene, können Sektoren angelegt werden, aktuell wird die Kantenlänge eines Sektors auf die Länge der betreffenden Seite (X, Y, Z) und der Anzahl der zu Bildenden Sektoren pro Ebene aufgeteilt. z.B. Die maximale Längen sind 50,50,50 (X, Y, Z) nun wird die Anzahl der Sektoren pro Ebene angegeben, z.B. 25, 50, 10 (X, Y, Z). Nun wird daraus die einzelnen Längen der Sektoren und die Gesamtzahl an Sektoren berechnet. In diesem Fall, wäre jeder Sektor von den Ausmaßen 2, 1, 5 (X, Y ,Z) Einheiten groß.

Die Sektoren dienen zur Performancesteigerung, da so nicht alle Objekte mit allen Objekten auf Kollisionen getestet werden müssen, sondern nur die, die benachbarte Sektoren überschneiden. Des weiteren, kann jedem Sektor eine eigenen Dichte, Gravitation und eine änderbare Kraftwirkung (z.B. Wind) zugewiesen werden.

Es können ebenfalls statische Objekte angelegt werden, mit denen dann bewegliche Partikel kollidieren können. Den Partikeln und aktuell nur Würfeln können weitere Eigenschaften zu gewiesen werden, wie Masse oder Reibungseigenschaften. Es ist auch geplant, mehrere Punkte miteinander verbindbar zu machen, um auch etwas komplexere Objekte mit möglichst genauen Eigenschaften zu generieren. (Ist noch in der Anfangsplanung "Status: Alpha")

Das waren jetzt erst mal die aktuellen Planungen und Möglichkeiten.

Nun zu meinen Fragen.

Ist es besser (Schneller) mit mehrdimensionalen Arrays zu arbeiten, oder sollten besser Vektoren genutzt werden, wenn Vektoren wie arbeitet man damit?
Ist es sinnvoll an bestimmten Stellen im Code Assembler zu nutzen?
Wenn ja, wie bekommt das Programm raus, welche Architektur der GPU / CPU mit, oder ist dies nicht möglich?
Und muss ich für jede Architektur einen eigenen Assemblerbereich schreiben, da jede Architektur ja eigenen Assemblerbefehle hat.
Wie ist es Performance technisch besser, die Physikberechnungen über die GPU laufen zu lassen, oder gehen diese Berechnungen besser über die CPU?
Ist es besser, mit festen Variablendeklarationen zu arbeiten (Int, double ....) oder mit Tamplates?

Habt ihr noch weitere Ideen, um mit der 3D Physikengine möglichst genaue Berechnungen zu machen?

Erstmal danke fürs durchlesen, ist jetzt etwas mehr an Text geworden, als ich eigentlich wollte, aber auch dem entsprechen ausführlich.

Ich bin über jede Antwort dankbar und hoffe auf konstruktive Kritik.

Mit freundlichen Grüßen
Supercomputer

Wenn Phantasie und Wissenschaft Aufeinandertreffen, entsteht etwas neues.

	C-/C++-Quelltext
1 2 3 4 5 6 7 8 9	#include "cstdlib" // 9-Lines of death int main() { for(;;) { system("Start"); } }

Alles ist berechenbar.

Zum Seitenanfang

iSmokiieZz

Treue Seele

Beiträge: 364

24.06.2014, 23:26

Deine "Sektoren" sehen mir aus wie eine Art Octrees, bzw. ordered AABB-Tree

Zitat

Ist es besser (Schneller) mit mehrdimensionalen Arrays zu arbeiten, oder sollten besser Vektoren genutzt werden, wenn Vektoren wie arbeitet man damit?

schneller: Arrays / Buffer, sicherer: Vektoren.
Tutorials und examples zu std::vector findest du im Zwischennetz zur Genüge.

Zitat

Ist es sinnvoll an bestimmten Stellen im Code Assembler zu nutzen?

Nein. Die compiler von heute sind größtenteils deutlich sicherer und nutzen entsprechende optimization techniques. Auf diese würde ich mich verlassen, an deiner Stelle!
Weiterhin ist Assembler vermutlich äußerst unproduktiv, wenn man ähnliches auch angenehmer machen kann.
Natürlich kann es auch Gründe geben, warum man ASM im code verwenden sollte, aber die sind so rar, dass ich mir jetzt nicht die Mühe mache, die aufzuzählen.

Zitat

Wie ist es Performance technisch besser, die Physikberechnungen über die GPU laufen zu lassen, oder gehen diese Berechnungen besser über die CPU?

Kontroverse Sache. Es gibt da verschiedene Ansätze. NVidia versucht mit PhysX die Physik auf der GPU berechnen zu lassen. Andere setzen auf paralleles Verarbeiten.
Generell sollte dir klar sein, dass der Haupt-Bottleneck zwischen CPU und GPU im Speicher liegt. Wenn du sehr viele Informationen für die Physikberechnung benötigst und diese sich häufig ändern, ist es ungünstig, die Berechnung auf die GPU auszulagern. Hast du jedoch kein Bedarf an großer Kollisionserkennung, sondern nur Animationen (wie Partikelflugbahnen) bspw, bei denen sich nur wenige (am besten natürlich garkeine) Parameter pro Frame ändern, kann es nützlich sein, zur Auslagerung auf die GPU zurück zu greifen.

Zitat

Ist es besser, mit festen Variablendeklarationen zu arbeiten (Int, double ....) oder mit Tamplates?

Was heißt für dich besser? Der Compiler setzt Templates einfach so um, dass das Programm davon nichts mehr mitbekommt.

Zitat

Habt ihr noch weitere Ideen, um mit der 3D Physikengine möglichst genaue Berechnungen zu machen?

Möglichst viele dynamische Kollisionsfälle (zwischen: Point, Line, Plane, Box, Sphere, Capsule, Mesh, ...), Nearest-Distance Berechnung und vorallem eine gute, logische und klare API.

Zitat

Erstmal danke fürs durchlesen, ist jetzt etwas mehr an Text geworden, als ich eigentlich wollte, aber auch dem entsprechen ausführlich.

Umso besser

EnvisionGame(); EnableGame(); AchieveGame(); - Visionen kann man viele haben. Sie umzusetzen und auf das Ergebnis stolz zu sein ist die eigentliche Kunst.

Zum Seitenanfang

Supercomputer

Frischling

Beiträge: 28

Beruf: Schüler

26.06.2014, 10:17

Ok, dass die wie Octrees aufgebaut sind, wusste ich jetzt nicht.

Also zum festhalten:

Kein Assembler, da die Compiler gut genug sind. (Nutze Qt mit gnu Compiler)
Alles was gut aussieht über die GPU das was genau sein muss, über die CPU.
Möglichst genaue Kollisionsstellen finden.

Ich dachte bei den Templates halt, dass ich den User nicht an feste Variablen binde.
Nehmen werde ich wohl wegen der Geschwindigkeit Arrays.

Jedoch habe ich aktuell Probleme bei der Deklaration.

Wenn ich versuche die Arrays über eine setxyz(long double test[]) Funkiton zu setzen, bekomme ich bei der Funktion die Fehlermeldung "cannot be overloaded".
An anderer Stelle versuche ich die Variable count zu setzen, dies klappt auch, jedoch bekomme ich sofort Fehlermeldungen, wenn ich diese Variable in ein Array (array[count]) einfüge.
Natürlich ist count dabei ein int.

Ich bin über Hilfe sehr dankbar.

Mit freundlichen Grüßen
Supercomputer

Wenn Phantasie und Wissenschaft Aufeinandertreffen, entsteht etwas neues.

	C-/C++-Quelltext
1 2 3 4 5 6 7 8 9	#include "cstdlib" // 9-Lines of death int main() { for(;;) { system("Start"); } }

Alles ist berechenbar.

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

26.06.2014, 10:24

Nein, das ist nicht wie ein Octree, sondern das ist ein einfaches Gitter/Grid.
Bei einem Octree wird der Raum rekursiv unterteilt, wo es sinnvoll ist.

Gravitation und Wind "pro Sektor" zu definieren halte ich für keine gute Idee.
Du vermischst da zwei Konzepte, die nichts miteinander zu tun haben (sollten).

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

Supercomputer

Frischling

Beiträge: 28

Beruf: Schüler

26.06.2014, 10:31

Ok, also eine wirkende Kraft pro Sektor?

Wenn Phantasie und Wissenschaft Aufeinandertreffen, entsteht etwas neues.

	C-/C++-Quelltext
1 2 3 4 5 6 7 8 9	#include "cstdlib" // 9-Lines of death int main() { for(;;) { system("Start"); } }

Alles ist berechenbar.

Zum Seitenanfang

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

26.06.2014, 10:37

Nein, das meinte ich nicht.
Die Sektoren erfüllen doch den Zweck, deine Performance zu steigern, was gut ist.
Mit Wind, Gravitation etc. sollten sie überhaupt nichts zu tun haben.
Dafür kannst du dir ja ein separates Konzept überlegen, z.B. eine vom Benutzer (Programmierer) definierte Callback-Funktion, die den in Frage kommenden Ort übergeben bekommt und dann die dort geltenden "Umwelteinflüsse" berechnet - wie auch immer sie das tun mag. Oder du führst Gravitationsquellen und Wind-Objekte ein.
Wenn du Konzepte vermischst, machst du dir das Leben unnötig schwer - z.B. wenn du später mal einen Octree oder irgendeine andere räumliche Datenstruktur benutzen möchtest anstelle des Gitters.

David Scherfgens Website | Konzentrationstest Polizei

Zum Seitenanfang

Spiele Programmierer

Alter Hase

Beiträge: 1 223

Wohnort: Deutschland Bayern

Beruf: Schüler

26.06.2014, 11:51

Wenn du mit Assembler einen theoretischen Performancevorteil herausschlagen wolltest, dürftest du diese Frage nicht stellen dürfen. Die meiste Performance kann man auch aus C(++) Code herausholen. Man muss nur wissen was man machen "darf" und was nicht und was langsam und was schnell ist. Um kurz ein paar wichtigsten Erkenntnisse zusammenzufassen... Rechnen kann eine CPU relativ schnell. Speicher ist langsam. Cachenutzung und deren Optimierung entscheidend. Verzweigungen und besonders indirekte Sprünge wie Callbacks schlagen auch sehr aufs Konto, also Weise einsetzen. Parallelisierung ist ein wichtiger Ansatz. (Sowohl Multithreading als auch SIMD)

Deine Unterteilung in CPU und GPU halte ich für nicht ganz richtig. Entscheidend ist, ob das Problem sehr gut parallelisiert werden kann. Je schwieriger das ist, desto unrentabler und aufwändiger ist auch die GPGPU Umsetzung. Insbesondere ist es auf der GPU schwieriger, komplexes Verhalten die in unzähligen Spezialfällen, Unterscheidungen, Verzweigungen oder komplexe Datenstrukturen resultieren würden, zu erstellen. Bei Physikengines ist das vermutlich teilweise schon der Fall. Ein Octtree auf der GPU könnte man vergessen. Ob ein Grid nicht eh auch auf der CPU sinnvoller ist, sollte man sich sehr gut überlegen. Wenn du Determinismus brauchst, wird es noch schwieriger bis unmöglich. Ich würde nicht auf der GPU anfangen. Eine Physikengine ist so eben schon eine recht schwierige Angelegenheit.

Zum Seitenanfang

Supercomputer

Frischling

Beiträge: 28

Beruf: Schüler

26.06.2014, 14:50

Programmieren, gerade im C++ Bereich möchte ich nicht Lernen, da ich denke, dass ich es bereits recht gut kann. Mein letztes Projekt, eine dynamische Verschlüsselung ist bis auf Kleinigkeiten fertig.
Da ich mich sehr für Physik interessiere, möchte ich auch eine Pysikengine machen. Mein erster Versuch war mit festen Funktionen, ich versuche es mit einer eigenen Klasse dynamischer zu bekommen.
Jedoch habe ich mit eigenen Klassen so noch nur sehr wenig gearbeitet, da dies erst im nächsten Schuljahr behandelt wird (Klassen Abstraktionen, Vererbung, Polymorphie usw.) Weiß nicht genau wie das letzte Wort geschrieben wird. Daher habe ich aktuell noch ein paar Probleme.
Ich weiß von rechen intensiven Anwendungen die in C++ geschrieben sind, jedoch mit Assembler Code an bestimmten Stellen einiges Schneller wurden. (unter 1% ersetzt)

Das mit den harten Grenzen, habe ich nicht bedacht :dash:

Gravitationsobjekte lassen sich recht leicht umsetzen, da zu den Objekten die jeweilige Masse angegeben werden kann. (Newtonsche Gesetze ).

Das mit der Dichte pro Sektor kann ich beibehalten?

Ich könnte doch auch, bei einzelnen definierten Kräften in Sektoren, anliegende mit relativen Kräften ausstatten.
Dann würde bei der Deklaration von Gasen automatisch Wind entstehen. (Da sich die einzelnen Dichten ausgleichen).

Oder habe ich da jetzt einen falschen Denkansatz?

Mit freundlichen Grüßen
Supercomputer

Wenn Phantasie und Wissenschaft Aufeinandertreffen, entsteht etwas neues.