Brauche eure Ratschläge bezüglich Einarbeiten in Kollisionserkennung

Guten Tag

Ich habe mir ein kleines Programm zum Editieren und Überprüfen von CNC-Programmen geschrieben.
Aktuell wird nur der Programmtext an sich überprüft.
Ich möchte jetzt die CNC-Programme auf Kollision überprüfen.

Um dies zu verwirklichen möchte ich mir zuerst einmal die Grundlagen aneignen.
Ja, ich weis dass man die über Google finden kann.
Doch das Internet ist groß und die Informationsfülle überwältigend.

Da die Kollisionsüberprüfung in der Spieleprogrammierung nicht wegzudenken ist, könnt ihr mir sicher ein paar Tips geben.
Kann mir bitte jemand Informationsquellen nennen um diese Aufgabe umsetzen zu können?

Zu den vorkommenden Körpern:
Werkzeuge:
Oft zylindrisch, immer rotationssymetrisch

Vorrichtungen:
Quaderförmige Körper, aus mehreren Quadern zusammengesetzte Körper und zylindrische Körper.

Werkstücke:
50% Quaderförmige Körper
50% Komplexe aus Rundungen zusammengesetzte Körper

Ich weis dass ich kleine Brötchen backen muss und mit simplen Aufgaben beginnen muss.
Da diese Materie für mich neu ist bin ich für jede Hilfe, die mich in die richtige Richtung weist sehr dankbar.
Denn aktuell weis ich nicht wirklich wonach ich suchen muss um die benötigten Informationen zum Umsetzen der Aufgabe zu finden.
Es scheitert z.B. schon daran das richtige Format der 3D Daten zu wählen um sie zu bearbeiten.
(Punktwolke, Körper aus Dreiecken, Freiformflächen, aufeinander geschichtete 2D Konturen,...)
Auch über die zu verwendenden Mittel grüble ich noch.
Sollte ich in OpenGL oder DirectX einarbeiten oder doch lieber alles selbst erstellen?

Eine grafische Ausgabe / Simulation ist aktuell nicht wirklich notwendig.
Es reicht, wenn ich erfahre in welcher Programmzeile die Kollision auftritt.

http://www.codezealot.org/archives/88

mehr brauchst du nicht.

kenner der algorithmen schrieb:

mehr brauchst du nicht.

Vielleicht noch einen Octtree um die Geschwindigkeit hochzukriegen. Oder ein einfaches Raster.

Danke für eure Hilfe
Mal schaun wie lange ich brauche bis ich es hinbekome.

octupus schrieb:

kenner der algorithmen schrieb:

mehr brauchst du nicht.

Vielleicht noch einen Octtree um die Geschwindigkeit hochzukriegen. Oder ein einfaches Raster.

Ja.

@BarnyF Generell läufts überall so ab: Zu jedem Objekt speichert man neben den eigentlich Dreicksdaten noch eine Zusatzinformation: Ein "Bounding Volume", also ein Volumen, dass das originale Objekt komplett umschliesst. Dieses Volumen hat den Zweck, eine "grobe" Kollisionsabfrage zu vereinfachen, mit der man zunächst Paare an Objekten ausfindig macht, bei denen eine genauere, hochdetailierte (z.B. mit GJK) Kollisionsabfrage überhaupt in Frage kommt. Deshalb handelt es sich bei diesem Bounding Volume allgemein entweder um eine Kugel ("Bounding Sphere") oder ein Schachtel, die parallel zu allen drei Koordinaten-Achsen ist ("Axis Aligned Bounding Box"), weil Kollisionsabfragen zwischen zwei Kugeln oder zwei AABBs sehr, sehr einfach und rechenarm sind.

Bei n Objekten macht man jetzt aber trotzdem nicht einfach eine Abfrage von jedem Objekt mit jedem anderen Objekt in der Szene ( O(n^2)), sondern benutzt etwas das sich "Spatial Partitioning Algorithm" nennt um die Szene in bestimmte Untereinheiten aufzuteilen, welche die Anzahl der benötigten Abfragen weiter reduziert. Im einfachsten Fall ist das einfach ein Gitter. Da ist jedes Objekt in einem oder mehreren Gittern untergeordnet (mehrere wenn es zwischen den Grenzen zweier Gitter ist), und wenn du rausfinden willst mit welchen Objekten ein anderes Objekt kollidiert, kannst du zuerst schauen, mit welchen Gitterzellen es kollidiert, musst dann nur mit allen Elementen des jeweiligen Gitters genauer prüfen, und so eine große Anzahl von Kollisionsabfragen ausschalten.

Wenns noch toller (und speichersparsamer) sein soll, dann nimmt man (für 3D) normalerweise einen Octree her. Das ist einfach sowas wie ein unbalancierter Binärbaum, nur dass jeder Knoten 8 Kinder haben kann und dass man keinen Schlüssel für einne Knoten hat, sondern wieder ein Bounding Volume für einen Knoten.

Wenn man wissen will, mit welchen Objekten ein Objekt o kollidiert, dann ist der Ablauf folgender:

- Abfragen im Spatial Partitioning System, mit welchen Blättern o kollidiert und die jeweiligen Knoten zurückgeben
- in den erhaltenen Knoten Objekt o mit allen Elementen der jeweiligen Knoten vergleichen, und zwar erst mit den Bounding Volumes von Objekt o und den Elementen der Knoten
- daraus erhält man eine Liste an Kollisionspaaren, welche für eine genaue Untersuchung in Frage kommen.
- Diese Liste erschlägt man mit GJK, und weiss dann definitiv welche Objekte mit o im Detail kollidieren.

Danke für deine Hilfe.