Inhaltsverzeichnis 1 Kollision anhand von Bildern 2 Beschleunigung mittels räumlicher Datenstrukturen 3 Ein-/Ausklappbare Implementierungen 4 Einheitliche Datenstrukturen/Klassen 5 Erklärungen auch in natürlicher Sprache 6 Ort der Kollision ermitteln? 7 Broadphase, Narrowphase, Solving? 8 Spoiler 9 Kollision von parallelen Geraden und Segmenten 10 Subtraktion zweier Punkte 11 Gerade vs. Kreis

Kollision anhand von Bildern

Viele Bibliotheken/Frameworks bieten es an, anhand 2 Bilder auf eine Kollision zu überprüfen. Dabei wird unterschieden zwischen der ungenauen Variante, in der die Bilder als Rechtecke betrachtet werden und der pixelgenauen Kollision, bei der die Transparenz von Pixel berücksichtigt wird.

Außerdem sollten 2D-Physik Engines berücksichtigt werden, wie Box2D und dessen Portierungen für Java, .NET und Python. --Sacaldur 22:46, 2. Nov. 2011 (CET)

Beschleunigung mittels räumlicher Datenstrukturen

Hat man N Objekte, die man auf Kollision testen möchte, benötigt man ohne Einsatz einer räumlichen Datenstruktur O(N²) viele Tests, was schlecht ist. In dem Artikel sollte man zumindest erwähnen, dass die Anzahl der benötigten Tests durch Einsatz einer räumlichen Datenstruktur (kd-Baum, Grid, ...) beschleunigt werden kann. Zu dem Thema sollte es dann ggf. einen eigenen Artikel geben. --David Scherfgen 16:52, 3. Nov. 2011 (CET)

Ein-/Ausklappbare Implementierungen

Vielleicht wäre es hier eine gute Idee, die Implementierungen ein-/ausklappbar zu machen. Dann stören sie beim Lesen nicht so. Normalerweise interessiert man sich ja nur für eine Sprache. --David Scherfgen 18:44, 3. Nov. 2011 (CET)

Einheitliche Datenstrukturen/Klassen

Da zu erwarten ist, dass es viele Artikel dieser Art hier geben wird, sollten wir uns vielleicht auf einheitliche Namen für Klassen/Datenstrukturen einigen. Vor allem für Vektoren, Matrizen, Farben, ... schon jetzt gibt's eine Uneinheitlichkeit zwischen C#/C++ und Java, da im Java-Code die Vektor-Klasse ein Generic ist. --David Scherfgen 18:47, 3. Nov. 2011 (CET)

Ich würde folgende Bezeichnungen (für float Daten) vorschlagen: (aus javax.vecmath) Vector2f, Vector3f, Vector4f, Quat4f, Matrix3f (3x3), Matrix4f (4x4), Color3f, Color4f. Komponenten sollten dann über x,y,z,w bzw. m00,m01,m02,...,m33 angesprochen werden. --Chromanoid 20:03, 3. Nov. 2011 (CET)

Damit wäre ich einverstanden! --David Scherfgen 10:49, 4. Nov. 2011 (CET)

javax.vecmath ist nicht Bestandteil der Java Standardbibliothek, weshalb ich auf dessen Einsatz eher verzichten würde. --Sacaldur 11:16, 4. Nov. 2011 (CET)

Ja ich meinte damit auch nicht, dass es gute Bezeichnungen sind, weil sie "Standard" sind, sondern weil ich sie einfach so gut finde. Ich wollte nur meine Quelle angeben. Und javax.vecmath ist Bestandteil von Java3D, was ja schon eine größere Unternehmung von Sun war um 3D Grafik möglichst massentauglich anzubieten. Ansonsten fände ich auch noch an HLSL oder GLSL angelehnte Bezeichnungen sinnvoll. Also Float2/Float3/Float4 Float2x2/Float3x3/Float4x4 oder Vec2/Vec3/Vec4 Mat2/Mat3/Mat4... --Chromanoid 11:33, 4. Nov. 2011 (CET)

Da in Python sowohl eine dynamische Typisierung, als auch Ducktyping verwendet werden, kann man für die Parameter nicht festlegen, welchen Datentyp sie haben sollen. Somit könnte man statt koordinate[0] auch koordinate.x schreiben. Der übergebene Wert muss dann lediglich eine Variable x besitzen, die die entsprechenden Operatoren definiert hat. --Sacaldur 11:16, 4. Nov. 2011 (CET)

Wie wäre es wenn sich auf eine Bezeichnung geeinigt wird (imo möglichst eine ohne Gebrauch von Generics o.Ä.) und das ganze dann in den Leitfaden für Autoren kommt. Irgendwann kann dann ja auch in jeder Sprache eine Bibliothek entstehen, die die Datentypen mit diesen Bezeichnungen anbietet. --Chromanoid 12:04, 4. Nov. 2011 (CET)

Ich vote mal für Vec* Mat* Quat* Color* (angelehnt an GLSL), ansonsten finde ich wie schon erwähnt Vector*t Quat*t Matrix*t gut (* dimension, t für typ -> f für float d für double i für int b für byte) (angelehnt an javax.vecmath). --Chromanoid 12:07, 4. Nov. 2011 (CET)

Ein normaler Benutzer oder vor allem ein Anfänger will den Code nach Möglichkeit einfach kopieren und testen können, ohne bei sich die Datentypen anpassen zu müssen. Deshalb sollten Datentypen gewählt werden, die auch von Haus aus mitgeliefert werden. Deswegen bin ich auch gegen Vector2f in Java. Darauf spekulieren, welche Datentypen es in Zukunft noch geben könnte, will ich ebenfalls nicht.

Um in Java die Verwendung der generischen Klasse zu sparen, kann man auch Arrays verwenden. Statt Generics an den jeweiligen Typ angepasste Klassen zu verwenden bringt meiner Meinung nach keine Vorteile.

Also: ich bin dagegen, in Sprachen Datentypen anzugeben, die es nicht gibt oder die erst durch eine zusätzliche Bibliothek verfügbar sind. --Sacaldur 12:16, 4. Nov. 2011 (CET)

Es ist absolut irreführend die Collections-Klasse Vector aus Java für einen Vector als Koordinate zu benutzen. Man stelle sich nur mal vor man würde in C++ std::vector nehmen... Dann wären mir Arrays oder java.awt.geom.Point2D.Float lieber. Da Java kein gutes eingebautes System für lineare Algebra hat, wäre ich an dieser Stelle dann aber wirklich lieber für eine semioffizielle Open Source Bibliothek wie javax.vecmath. --Chromanoid 12:37, 4. Nov. 2011 (CET)

Woher kommt eigentlich in C++ Vector, ist sowas standardmäßig bei C++ dabei? Ich habe bei Java mal auf Arrays umgestellt. --Chromanoid 12:54, 4. Nov. 2011 (CET)

Stazer müsste dir die Frage eigentlich beantworten können, da er den Artikel angelegt hat. --Sacaldur 18:06, 4. Nov. 2011 (CET)

Ich kann mir kaum vorstellen, dass C++ Klassen für lineare Algebra direkt mitliefert. Sowas sollte es wenn in Boost oder so geben. Ich würde daher vorschlagen auch bei C++ Arrays zu verwenden. Wenn es solche Klassen doch geben sollte bitte ich um Aufklärung. Ansonsten funktionieren die C++ Beispiele nämlich nicht einfach so. --Chromanoid 19:21, 5. Nov. 2011 (CET)

Erklärungen auch in natürlicher Sprache

Es sollte darauf geachtet werden, dass die Algorithmen auch mit natürlicher Sprache erklärt werden. Ansonsten kopiert man sich nur den Code, versteht aber gar nicht, wie er funktioniert. --David Scherfgen 18:47, 3. Nov. 2011 (CET)

Ort der Kollision ermitteln?

Optional könnte man für jede Kollisionsabfrage auch noch ermitteln, wo die Objekte sich schneiden. --David Scherfgen 10:49, 4. Nov. 2011 (CET)

Broadphase, Narrowphase, Solving?

Ich weiß nicht ob man hier darauf eingehen sollte, aber zumindest Broadphase-Algorithmen wie Sweep&Prune sollte man vielleicht hier oder irgendwo allgemein vorstellen. --Chromanoid 11:36, 4. Nov. 2011 (CET)

Spoiler

Für einen C++ Quelltext gibt es offensichtlich bereits zum Testen ein Element, welches den Code verstecken soll. Abgesehen davon, dass es im IE 7 nicht funktioniert (der Quelltext ist permanent sichtbar), sollte dafür eventuell eine Vorlage angelegt werden, der man den Titel und den Inhalt übergeben kann. --Sacaldur 11:57, 4. Nov. 2011 (CET)

Das element funktioniert jetzt auch im IE 7, dennoch finde ich, dass das in eine Vorlage ausgelagert werden sollte. --Sacaldur 12:20, 4. Nov. 2011 (CET)

Ja, würdest du das übernehmen? Du kennst dich besser damit aus. --David Scherfgen 12:23, 4. Nov. 2011 (CET)

Zunächst sollten die Panels aber noch etwas flexibler gemacht werden. So wie es jetzt ist, ist im "immer sichtbar"-Teil nur eine Überschrift erlaubt. Wenn man das für Quiz-Fragen nutzen möchte, sollte dort auch Text stehen können. Ich werde das noch einbauen. --David Scherfgen 12:27, 4. Nov. 2011 (CET)

Es können immernoch nur Titel verwendet werden. Fehler ab jetzt bitte in der Vorlage anpassen. (Ich musste mir auch erst Hilfe holen... ^^) --Sacaldur 12:43, 4. Nov. 2011 (CET)

Jetzt sollte alles klappen. Aber ich finde, dass die Überschriften nicht im Inhaltsverzeichnis erscheinen sollten. Das stört doch enorm beim Lesen! Darum hatte ich <xh4> benutzt ... --David Scherfgen 13:05, 4. Nov. 2011 (CET)

Hey, das sieht ja cool aus! Ja das mit den Überschriften finde ich auch doof. --Chromanoid 13:12, 4. Nov. 2011 (CET)

Die Überschriften können noch entsprechend angepasst bzw. entfernt werden. Man sollte auch schauen, ob eine Formatierung als Überschrift notwendig ist oder ob die normale Formatierung reichen würde. --Sacaldur 13:16, 4. Nov. 2011 (CET)

Das mit den verschachtelten Spoilern finde ich super! --David Scherfgen 11:06, 17. Nov. 2011 (CET)

Kollision von parallelen Geraden und Segmenten

Auch parallele Geraden und Segmente können sich schneiden. Nämlich dann, wenn sie gleich sind bzw. in derselben Geraden liegen. Das sollte man vielleicht auch im Code abfangen. Wieder mit Epsilon ... --David Scherfgen 15:20, 4. Nov. 2011 (CET)

Subtraktion zweier Punkte

Ich bin mir nicht sicher, ob man von der Subtraktion zweier Punkte reden kann. Sollte dies eine falsche formulierung sein, bitte ich darum, den Abschnitt des verschobenen Kreises unter der Kollisionserkennung zwischen einem Kreis und einer Geraden anzupassen. --Sacaldur 15:34, 23. Nov. 2011 (CET)

Sollte statt der Ermittlung der Differenz der Punkte §P§ und §Q§ nicht lieber einen Vektor verwenden, á la §\overrightarrow{PQ}§? --Sacaldur 11:07, 25. Nov. 2011 (CET)

Auf jeden Fall, gefiele mir besser! :) --David Scherfgen 14:48, 26. Nov. 2011 (CET)

Gerade vs. Kreis

Den Ansatz, den Sacaldur beschreibt, würde ich als "geometrisch" bezeichnen. Da muss man am Ende mit Winkeln und trigonometrischen Funktionen hantieren, was langsam sein könnte. Außerdem lässt sich dieser Ansatz nicht einfach auf 3D (Gerade vs. Kugel) erweitern. Ich schlage (evtl. zusätzlich) einen anderen Ansatz vor, der weiter verbreitet ist: nämlich einfach die Parameterform der Geradengleichung in die Kreisgleichung einsetzen. Das kann man auch mit Vektoren machen (statt mit einzelnen Variablen für x, y), dann ist die Lösung sogar völlig unabhängig von der Anzahl der Dimensionen. --David Scherfgen 20:38, 23. Nov. 2011 (CET)

Um genau zu sein, wird kein Winkel berechnet, sondern der Wert des Sinus und Kosinus des Winkels, da diese und nicht der Winkel selbst benötigt werden, um die Gerade zu drehen. Allerdings kann es sein, dass das Ziehen der Wurzel zum ermitteln der Länge der Hypotenuse langsam sein dürfte. Ich werde die bisherige Beschreibung aber zu Ende führen. --Sacaldur 21:39, 23. Nov. 2011 (CET)

Ich habe die Überprüfung jetzt fertig geschrieben. Sollte ich die Formeln falsch notiert haben, bitte ich zumindest um einen Hinweis auf entsprechende Fehler. Ich vermute, dass die Fallunterscheidung, die jetzt noch enthalten ist, nicht notwendig ist, allerdings will ich erst noch einmal in Ruhe gucken, ob ich mit dieser Vermutung richtig liege.

Die Vereinfachung ist doch nicht möglich, da in der Berechnung der y-Koordinate des gedrehten Punkts falsch berechnet wurde. Diesen Fhler habe ich bereits beseitigt. --Sacaldur 09:04, 24. Nov. 2011 (CET)

Ich denke, dass diese Diskussion von 3 Leuten verfolgt wird - von David Scherfgen, Koschi und mir. Somit kann auch nur einer von uns die andere Variante einbauen, da niemand sonst aus dem Forum überhaupt mitbekommt, dass dies gemacht werden kann/sollte.

--Sacaldur 23:39, 23. Nov. 2011 (CET)

Ich werde die andere Variante einbauen. Um deinen Ansatz zu testen, wäre es gut, wenn man ein Testprogramm hätte, in dem man die verschiedenen Formen zeichnen kann und es markiert dann diejenigen, die sich schneiden. --David Scherfgen 02:44, 24. Nov. 2011 (CET)

Mir ist eingefallen, dass man die Hypotenuse nur dann berechnen muss, wenn die die Gerade beschreibenden Punkte (die zum Berechnen verwendet werden) sich ändern. Man könnte ebenso den Wert von Sinus und Cosinus der Winkel erst dann berechnen, wenn die Gerade eine andere Drehung hat.

Ich versuche dann mal ein einfaches Programm zu schreiben, mit dem man sich die Ergebnisse der Prüfung Veranschaulichen kann. --Sacaldur 08:23, 24. Nov. 2011 (CET)

Entweder habe ich einen Fehler in der Implementierung, oder der beschriebene Weg funktioniert so nicht ganz. Ich werde das noch nachprüfen. Sobald ich meine, mit meinem Programm fertig zu sein, werde ich dieses auch zur Verfügung stellen. --Sacaldur 20:04, 24. Nov. 2011 (CET)

Es war ein Implementierungsfeler. Sobald ich der Meinung bin, dass das Programm fertig ist, stelle ich es dann zur Verfügung. [Edit: Geraden werden beispielsweise bisher nur als Strecken dargestellt.] Da es sich um eine Java-Anwendung handelt, wäre es nicht das Problem, daraus ein Applet zu machen, um es hier einzubinden, sofern das gewünscht ist. --Sacaldur 20:34, 24. Nov. 2011 (CET)

Das Programm, womit der Algorithmus von mir getestet werden soll, ist soweit fertig. Sollte ich es erstmal nur dir schicken (hochladen und Link schicken)?

OK :) --David Scherfgen 22:04, 28. Nov. 2011 (CET)