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.
