# Pixelgenaue Kollision



## Turakar (31. Okt 2012)

Hallo,

ich wollte (unter naderm um andere Threads zu schonen) hier einen Thread auf machen, wo Fachsimpler über das Theama pixelgenaue Kollision reden können. Mit pixelgenauer Kollision ist gemeint, das man überprüft, ob die beiden Texturen der Objekte sich überschneiden, oder nur deren Form.

Ich denke das folgende Themen die Hauptprobleme sein werden:
-wirklich pixelgenau
-Matrixe
-Arbeitsspeicher/CPU-Auslastung

Bitte postet hier eure Ideen über die Probleme und verbessert andere!

Sobald ich eine favoriesierte Methode sehe, werde ich sie hier posten.

Übrigens, KSKBs oder APIs helfen in SEHR vielen Fällen wirklich weiter!

WICHTIG: Ich möchte an dieser Stelle noch einmal an die Nettiqutte(Nettiquette#2), die hier gültig ist, erinnern!

Viel Spaß beim Posten und diskutieren!


----------



## Helgon (31. Okt 2012)

pixelgenaue kollision überprüft man in dem man den die textur (array) durchläuft von beiden objekten und schaut ob der alpha wert in beiden 0 ist (mal ganz grob)

was aber viel verbreiterter ist und sinn macht(in punkte performance) collision boxes oder circles

also einfach rechteckige boxen oder elipsen um das objekt (abhängig von der größe des objekts) und dann gucken ob die sich schneiden)


----------



## Turakar (31. Okt 2012)

Ja, das ist das grundlegen e Prinzip, aber sagen wir, ich würde jeden tick alle Elemente durchlaufen und dann nochmal alle deren Pixel dann alle pixel der anderen (was ich momentan machen würde, weil mir nichts einfällt) hätte ich bei 100 Elementen und 20x20 texturen 100x20x20x100x20x20 Berechnungen, also 1600000000.

Ein bisschen viel oder?
Ganz abgesehen davon hab ich keine Ahnung was ich mit einem Matrix machen soll.

Irgendwelche Ideen dies zu optimieren?
???:L


----------



## Marco13 (31. Okt 2012)

Wenn du mit "Matrixe" Matrizen meinst, mit denen die Objekte rotiert sein können, wird's wirklich schwierig. Natürlich nicht unmöglich: Wenn man die Matrix invertiert, kann man vom einen Bild ins andere umrechnen, und demnach noch die Vergleiche machen - aber ... ich würde spontan sagen, dass man (speziell dann) schlicht keine Pixelgenaue Kollisionserkennung machen sollte. Ich kann mir kaum vorstellen, wann man die wirklich "braucht". Aber wenn man sie machen will: Natürlich testet man NUR die Objekte pixelweise, deren Bounds sich überschneiden (sei es als Rectangle2D, oder rotierte Rectangles in Form von Shapes)).


----------



## Turakar (31. Okt 2012)

Ja, aber auch dies könnte bei 100 Elementen die nah beieander liege (Schwärme oder so) komplieziert werden. Desweiteren würde ich mich auch echt über nen paar Zeilen Code freuen. :toll:

(Übrigens, ja ich meine Matrizen)


----------



## Marco13 (31. Okt 2012)

Ingesamt unterscheidet man ja bei Kollisionserkennung (ich meine bei der _richtigen_ Kollisionserkennung) zwischen der "Broad Phase" und der "Narrow Phase". 

In der Broad Phase schmeißt man erstmal alles weg, was man schnell ausschließen kann. Das kann z.B. mit Bounding Box Tests gemacht werden. Bei großen, komplexen oder gar deformierbaren Objekten verwendet man dazu meistens eine Bounding Volume Hierarchy. Bei Bounding volume hierarchy - Wikipedia, the free encyclopedia wird das nicht so suggestiv deutlich: Damit wird dann tatsächlich auch ein einzelnes Objekt in mehrere Teile zerlegt - und NICHT nur jeweils ein ganzes Objekt mit einer Bounding Box umschlossen. Schon allein dafür gibt es mehr Literatur, als man je wirklich lesen können wird. Das meistzitierte Paper dürfte da IEEE Xplore - Efficient collision detection using bounding volume hierarchies of k-DOPs sein (verfügbar unter http://ftp.ams.sunysb.edu/geometry/jklosow/tvcg98_paper.ps.gz ), und natürlich hat sich in den letzten 15 Jahren da noch einiges getan  

Bei Schwärmen würde sich vielleicht eher ein Spatial Hashing anbieten, da findet man im Web schnell einiges dazu, z.B. Spatial hashing implementation for fast 2D collisions  The mind of Conkerjo , aber auch entsprechende Literatur, wo steht, was es noch alles für Designfreiheitsgrade gibt. 

In der Narrow Phase macht man dann die exakten Tests. Bei komplexeren 3D-Objekten wären dann die Tests, ob z.B. ein Punkt und ein Dreieck sich berühren. Im 2D-Fall könnte das ein Pixel-Test sein. Aber die sind eben i.A. so aufwändig, dass man möglichst viele dieser Tests schon in der Broad Phase ausschließen will. Konkret für die Pixelgenauen Tests: Meistens hätte man da ja ein Bild, das "fast überall" gefüllt ist, und z.B. nur am Rand (durch die Transparenz definiert) irgendwelche komplexen Formen hat. Wenn man nun so ein 1000x1000-Bild testen will, bei dem nur ein 100 Pixel breiter Rand _überhaupt_ transparente Pixel enthält, braucht man den pixelgenauen Test ja auch nur in diesem schmalen Rand. Man würde dann (sinngemäß-vereinfacht) den komplett ausgefüllten Bereich durch ein Rechteck definieren, und könnte das (mit ein paar wenigen if-Abfragen) auf Überschneidungen mit einem anderen Bereich testen. Den Rand würde man z.B. in 100*100 Pixel große "Kacheln" zerlegen (ggf. auch kleinere), und auch dort immer erstmal testen, ob diese Kachel eine andere Kachel überschneidet - und wenn ja, NUR für diese kleinen Kacheln die pixelgenauen Tests machen. 

Der Pixelgenaue Test ist aber, wie angedeutet, nicht immer der beste Weg. Wenn man nur ein PNG zur Verfügung hat, scheint er sich zwar anzubieten, aber wenn man ihn beschleunigen will, muss man sich ohnehin um die übergeordneten Broad Phase Strukturen kümmern. Und - oft kommt es auf 3, 4 Pixel gar nicht an, d.h. in so einem Fall KÖNNTE (das weiß ich nicht) eine BVH mit einer Gitterzellengröße von z.B. 4 schon reichen, so dass man im Endeffekt gar keine exakten Test mehr machen muss. Aber genauso wie der Pixelgenaue Test für gedrehte Bilder aufwändig ist, ist die Behandlung und ggf. Aktualisierung einer BVH für sich drehende Bilder alles andere als trivial...

Ich habe in den letzten Wochen ein bißchen was zu 2D-Kollisionstests gemacht. Eigentlich für Shapes und nicht für Bilder, aber es sollte klar sein, dass bestimmte Konzepte (eben die Broad Phase) da weitgehend unabhängig sein können. Für den Fall, dass die Shapes nur verschoben werden können, habe ich einfach eine BVH aus AABBs (Rectangle2D) gebastelt. Für den Fall, dass sie auch gedreht werden können habe ich eine (für meinen Anwendungsfall zum Glück stark vereinfachte, und nur 2-stufige) Variante einer BVH mit OBBs verwendet (da gibt's auf flipcode - 2D OBB Intersection eine nette Implementierung, die recht trickreich viele Divisionen, Normalisierungen und Dot-Products vermeidet). Der Gedanke, das zu einer allgemeine(re)n 2D-Kollisionserkennungs-Lib aufzubohren kam mir zwar, aber im Moment ist das eigentlich eher Mittel zum Zweck, und hat geringere Priorität, als das, wofür ich es (in der aktuellen, speziellen Form) verwenden will.


----------

