pixel perfect collision detection bei rotierenden Bildern

[Marti]

Ich versuche gerade eine Art Asteroidspiel in Java zu realisieren.
Für meine Raketen die als BufferedImage vorliegen wird einmalig ein Rotationswinkel festgelegt, der sich durch den Abschusswinkel ergibt.
Ich benutze die Kollisionserkennung aus dem Spieletutorial des Users Quaxli.
Dort wird (wohl die gebräuchliste Form) aus den beiden sich überlappenden rechtecken, der jeweiligen Spriteobjekten (dass sie von der Klasse Rectangle2d.double erben) ein entsprechendes rechteck erzeugt. Mit dem Maßen des Rechtecks werden dann aus den Bildern Subimages erzeugt,über die sich eine Kollisionserkennung erkannt werden kann, wenn an gleicher Position nichttransparente Pixel erkannt werden.
Um diese SubImages zu erzeugen wird das Bild übergeben.
Das kann bei einem rotierten Bild nicht klappen, weil es eben nicht im rotierten Zustand vorliegt.
Nun habe ich kleine Methode in die Spriteobjekte implementiert, die das rotierte Bild zurück geben soll.
Aber es klappt nicht so recht. Ich erhalte immer noch die Fehlermeldung, dass außerhalb des Bildrasters ausgelesen werden soll.

Kurz die kleine Funktion, die das Bild im rotierten Zustand zurückgeben soll.
pic und affineTransform sind Objektvariablen. (pic ist das Originalbild).

   public  BufferedImage rotatedImage() {

        BufferedImage rotatedImage = new BufferedImage((int)this.pic.getWidth(),(int) this.pic
                .getHeight(), BufferedImage.TYPE_INT_ARGB);
        Graphics2D g = (Graphics2D) rotatedImage.getGraphics();
        g.setTransform(this.affineTransform);
        g.drawImage(pic, 0, 0, null);
        return rotatedImage;

}

Das müßte doch eigentlich funktionieren, oder?

 

[Quaxli]

Das kannst Du doch ganz einfach selbst rauskriegen: Einfach das erzeugte Bild abholen und temporär irgendwo auf Deinen Screen pinseln. Dann siehst Du sofort, ob es funktioniert oder nicht.

 

[Steev]

Das müßte doch eigentlich funktionieren, oder?

Nein, eigendlich nicht. Angenommen du hast ein Bild das 100x25 Groß ist. Wenn du es nun mit deiner Methode um 90° rotierst, dann werden große Teile deines Bildes abgeschnitten, weil du das rotierte Bild wieder in ein 100x25 Pixel großes Bild zurückschreibst.

Mein Vorschlag:
[Java]
public void yourPaint(Graphics2D g2) {
g2.rotate(yourRadians);
g2.drawImage(yourImage, etc.);
}
[/Java]

Mal ganz abgesehen davon, dass du die Position, an der du die Kollision überprüfen willst, mit rotierien musst. Dann wirst du das Problem bekommen, dass din Rechteck, anhand dessen du ja einen BB-HitTest machst, ebenfalls in nicht rotierter Form vorliegt. Das muss ebenfalls rotiert werden.
Alternativ kannst du aber auch für die entsprechenden Rotationen Bilder erstellen und diese dann unrotiert "wie es ist" wie oben beschrieben verwenden.

Für eine Rotation kannst du ja lineares algebra (Rotationsmatrix) verwenden.

 

[Marti]

Ich denke, ich habe es jetzt "fast".
Die BB lasse ich mir über eine Methode in den Spriteobjekten zurück geben:

  public Rectangle2D.Double collisionRect() {

            Shape shape = affineTransform
                    .createTransformedShape(this);

            Rectangle2D.Double collisionRect = (Double) shape.getBounds2D();
            return collisionRect;
    }

In der Kollisionsprüfung wird das collisionRect abgefragt um dann ggf. sich das Bild über folgende Methode zu holen.

 public  BufferedImage rotatedImage() {

        BufferedImage rotatedImage = new BufferedImage((int)this.collisionRect().getWidth(),(int)this.collisionRect().getHeight()
                 BufferedImage.TYPE_INT_ARGB);
        Graphics2D g = (Graphics2D) rotatedImage.getGraphics();
        g.rotate(Math.toRadians(degree),pic.getWidth()/2, pic.getHeight()/2);
        g.drawImage(pic, 0,0, null);
        return rotatedImage;

}

Ich gebe dem Bild die Außmaße meiner BB und male das Bild dort transformiert rein.
Ich bekomme auch keine Fehlermeldungen mehr. Das ganze läuft recht gut.
Nur das Bild ist leider noch ein wenig angeschnitten. Ich darf es nicht an den Nullpunkt zeichnen.
Ich muss der Rotation und der kleinen Bildverschiebung irgendwie gerecht werden.

 

[Steev]

Nochmal mein Vorschlag: Rotiere das Bild erst zur Laufzeit und rechne die Koordinaten um, das ist effektiver. Wenn du ein rotiertes Bild ständig in ein neues Bild zeichnest, dann hast du zu viele ungenutzte Pixel.

Für die Berechnung der Position eines rotierten Punktes würde ich so etwas benutzen:

[Java]
double theta = PI / 180. * yourRotationInDegres;
double sin = Math.sin(theta);
double cos = Math.cos(theta);
double anchorx = yourX;
double anchory = yourY;
yourX = anchorx * cos + anchory * sin;
yourY = anchory * cos - anchorx * sin;
[/Java]

 

[Marti]

Also um letzlich überflüssige Kollisionsprüfungen zu vermeiden. Ja, das wäer sicher geschickter.
Um das Bild auf die Bühne zu zeichnen, habe ich ja schon die von Dir beschriebene Funktion implementiert (bzw, ich hatte sie ja schon):

public void drawObjects(Graphics2D g) {
        
        g.setTransform(affineTransform);
        g.drawImage(pic, x, y, null);

Das würde ich so lassen und die Rotationsmatrix nur für die Kollisionserkennung benutzen?
Wo bekomme ich denn meine BB her? Oder soll ich etwas bei jedem repaint, die Position des Bildes über die Rotationsmatrix neu berechnen. Sorry, ich bin gerade etwas ahnungslos.

 

[Steev]

Guten Morgen,

Das würde ich so lassen und die Rotationsmatrix nur für die Kollisionserkennung benutzen?

Ja, genauso würde ich das auch machen.

Wo bekomme ich denn meine BB her? Oder soll ich etwas bei jedem repaint, die Position des Bildes über die Rotationsmatrix neu berechnen. Sorry, ich bin gerade etwas ahnungslos.

Ich würde nicht bei jedem Repaint, sondern bei jeder Kollisionsprüfung die BB neu berechnen. Dazu würde ich einfach die vier Eckpunkte des ROTIERTEN Bildes verwenden (Für jeden einzelnen Punkt muss die absolute Position errechnet werden um diese dann mittels der oben beschriebenen "Formel" zu rotieren.)
Wenn du die vier Eckpunkte deines Bildes kennst, dann kannst du ja herausfinden, was der kleinste und was der Größte X- und Y-Wert ist. Anhand dieser Werte kannst du dir dann weiterhin die Höhe und Breite sowie die Position deiner BB ausrechnen.

 

[Marti]

Hallo,

gut, ich denke, ich habe es jetzt in etwa.
Über die Eckpunkte des Bildes errechne ich mir die Ausmaße meiner BB, die gleichzeitig auch die Ausmaße meines rotatedImage sind. Die Erstellung des rotatedImage wird einmalig über den Konstruktor aufgerufen, über eine andere Funktion kann man es sich dann abholen.
Ich habe mit getRGB und setRGB gearbeitet, die nur int-Werte zulassen.
Mein Objekt wird bei der Drehung leicht zerschlissen (leichte Risse,vereinzelte transparente Punkte) die Umrisse dürften aber noch stimmen. Das liegt evtl. daran, dass ich ausschließlich mit int-Werten gearbeitet habe. Andererseits: setRGB läßt ja eben nur int-Werte zu.
Das Objekt, dass auf die Bühne gezeichnet wird über affineTransform könnte ich mir ja jetzt im Grunde sparen, bzw. das rotatedImage auch als Bühnenbild benutzen.
Was evtl. noch erwähnenswert ist: Das JavaSpiel ist eine Blaupause für ein Flashgame. Wenn ich also nur irgendwelche Umrisse meiner Objekte nutzen würde, wäre das für mich auch ausreichend.

Danke.

 

[Steev]

Hallo,

ich muss jetzt nicht unbedingt verstehen, was du mit deinen getRGB und setRGB-Methoden bei der Darstellung vorhast. Du benötigst doch höchstens getRGB für die pixelgenaue Kollisionsabfrage.
Die BB berechnest du jetzt richtig.

Hier nochmal das Konzept:
1. Du hast ein Objekt. Dieses Objekt hat eine Position, einen Rotationspunkt und ein aktuelles Bild.
2. Du hast eine paint-Methode die das Bild des aktuellen Objektes mit der entsprechenden Rotation an der entsprechenden Position zeichnen soll.
3. Das Objekt hat eine Methode mithilfe der du die BB des Objektes ermitteln kannst (getBounds oder so). In dieser Methode nimmst du die Eckpunkte des aktuellen Bildes des Objektes und wendest die Objekttransformationen auf diese Punkte an um die BB zu ermitteln.

Fazit:
Erst bei dem Zeichnen des Objektes ist es relevant ob das Objekt rotiert wird und an welcher Position es sich befindet. Folglich sind ansätze wie "getRotatedImage" etc. nicht nötig.

Gruß
Steev

 

[Marti]

Ich verstehe das grundsätzliche Konzept bzw. 1-3.
Aber wenn es zur Kollision kommt, muss ich es doch ermöglichen ein subimage vom rotierten Bild zu erzeugen? Dieses rotierte Bild kann ich doch einmalig zuvor berechnen. Gut, ich denke, ich habe diesen Part einfach nicht wirklich verstanden.
Durch die erzeugte BB kommt es doch zu Pixelüberprüfungen, die sich aus dem Originalbild nicht ableiten lassen, weil es diese Pixel nicht kennt, weil der Ausschnitt der BB durch die Rotation größer geworden ist.
Ich wüßte nicht, wie ich das realisieren sollte.

 

[Steev]

Fange doch erst einmal klein an:
Du machst dir bei deinem Objekt eine Methode "+hitAt(x:double, y:double):boolean".

Dieser Methode wird eine absolute Position übergeben. Innerhalb dieser Methode überprüfst du dann folgendes:
1. Liegt diese Position innerhalb der BB?
1.1 BB.contains(x,y)
2. Liegt diese Position innerhalb des rotierten Bildes?
2.1 Transformiere die übergebene Position und berechne die relative Position innerhalb des Bildes
2.2 Wandle die Position in eine Ganzzahl um und prüfe, ob beide Koordinaten der Position größer als 0 und kleiner als die Breite/Höhe des Bildes sind.
2.3. Wenn dies der Fall ist, so gebe den ARGB-Wert des Pixels zurück und berechne den Alphawert.
3. Ist dieser Pixel transparent?
3.1 Wenn ja dann gebe fales zurück
3.2 Wenn nein dann gebe true zurück

Folgender Code vieleicht mal als Denkanstoß:

[Java]
import static java.lang.Math.*;

class YourGameObject {

// [...]

private static int[] temp = new int[2];

// [...]

public synchronized boolean hitAt(double x, double y) {
/*
* Prüfe, ob die Position innerhalb der aktuellen BB liegt
*/
if (!hitAtBB(x, y))
return false;

/*
* Versuche das aktuelle Bild zu ermitteln
*/
BufferedImage currImg = getCurrentImage();

/*
* Wenn es kein Bild gibt, so können wir mit der Berechnung nicht
* fortfahren und gebe false zurück.
*/
if (currImg == null)
return false;

/*
* Verwende lokale Variablen um den Code übersichtlich zu halten.
*/
double w = currImg.getWidth();
double h = currImg.getHeight();

/*
* Berechne aus der angegebenen Position die Position des entsprechenden
* Pixels.
*/
temp[0] = x;
temp[1] = y;
transform(temp, this, 0);

int nx = (int) temp[0];
int ny = (int) temp[1];

/*
* Wenn der Punkt innerhalb der Bitmap liegt, so wird der entsprechende
* RGB-Wert des Bides zurück gegeben, ansonsten wird 0x00 zurück
* gegeben.
*/
if (nx < 0 || ny < 0 || nx >= w || ny >= h)
return 0x00;

/*
* Ermitteln des Farbwertes des Pixels
*/
int argb = currImg..getRGB(nx, ny);
int alpha = (argb >> 24) & 0xff;
return alpha == 255;
}


public synchronized void transform(double[] xy) {
/*
* Verwende lokale Variablen um den Code übersichtlich zu halten.
*/
double ix = xy[0];
double iy = xy[1];

/*
* Translieren des Puktes, sodass die Objektposition der Nullpunkt ist.
*/
ix -= getX();
iy -= getY();

/*
* Negative Translation des Punktes um die Position des
* Rotationspunktes.
*/
ix -= getRotationPointX();
iy -= getRotationPointY();

/*
* Rechne die Rotation des Objektes mit in die Position mit ein.
*/
double theta = PI / 180. * getRotation();
double sin = sin(theta);
double cos = cos(theta);
double anchorx = ix;
double anchory = iy;
ix = anchorx * cos + anchory * sin;
iy = anchory * cos - anchorx * sin;

/*
* Translation des Punktes um die Position des Rotationspunktes.
*/
ix += getRotationpointX();
iy += getRotationpointY();

/*
* Gebe die errechneten Positionen zurück.
*/
temp[0] = ix;
temp[1] = iy;
}
// [...]
}[/Java]

 

[Marti]

Danke für die ausführliche Erläuterung. Ich werde das so umsetzen.
Ich transformiere also den übergebenen Punkt, falls er in der BB liegt, relativ zu meinem Bild, um dann eine mögliche Kollision festzustellen. Ich verändere also an meinem Bild nichts, sondern transformiere nur den übergebenen Punkt.
Mich irritiert das currentImage, aber das liegt wohl daran, dass ich nur mit einem einzelnen statischen Bild auskomme und dies direkt als Objektvariable übergeben kann (Möglicherweise war das auch kleines Mißverständnis, es handelt sich ja nur um das eine Bild).

Eine Frage hätte ich noch: Hast Du eine Kollisionserkennung beider BB´s schon dem ganzen vorrausgesetzt, bzw. woher ergibt sich die absolute Position? Und wenn sie sich aus der Überschneidung der beiden BB´s ergibt, kann ich mir doch eine erneute Prüfung mit der BB sparen.
Oder habe ich nun wieder etwas komplett mißverstanden? Danke für die Geduld.

 

[Steev]

Mich irritiert das currentImage, aber das liegt wohl daran, dass ich nur mit einem einzelnen statischen Bild auskomme und dies direkt als Objektvariable übergeben kann (Möglicherweise war das auch kleines Mißverständnis, es handelt sich ja nur um das eine Bild).

Ich bin einfach mal davon ausgegangen, dass zu einem Objekt beliebig viele Bilder gehören können. Dieser Ansatz erleichtert dir Später auf jedem Fall die Implementierung von Bild-Animationen. In deinem Fall wird dann halt immer die Referenz auf ein Bild zurückgegeben.

Eine Frage hätte ich noch: Hast Du eine Kollisionserkennung beider BB´s schon dem ganzen vorrausgesetzt

In obigen Ansatz gibt es erst einmal keine "beiden BB´s" sondern nur ein Objekt und ein Punkt. Es wird also überprüft, ob an einem bestimmten Punkt eine Kollision mit deinem Objekt vorliegt. Mithilfe dieser Methode müsste es eigendlich möglich sein, deine Problemstellung zu lößen.

Vom Ansatz her könnte man theoretisch zwei Objekte pixelgenau auf eine Kollision überprüfen indem man für jeden Pixel des einen Objektes prüft, ob seine absolute Position eine Kollision in dem anderen Objekt auslößt. Wie du dir aber sicher denken kannst ist dieser Ansatz sehr unperformant und sollte daher nicht verwendet werden.

Sollte dennoch eine genaue Kollisionsprüfung von einem Objekt mit einem anderen Objekt verwendet werden, so würde ich einfach eine Kollisionsfläche für jedes Objekt mitführen. Dafür bietet sich ein Shape an. Diese Kollisionsfläche muss dann entsprechend der Objekttransformation (also Position und Rotation usw.) transformiert werden.
Da der Standard-Java Algorithmus für Transformationen von Shapes allerdings zu viele Objekte erzeugt, bietet sich hier an, etwas eigenes zu schreiben. Ich würde da einfach etwas lineares ohne Splines verwenden. Dann kannst du nämlich mithilfe einer Vektorgleichung den Schnittpunkt der entsprechenden Geraden der Kollisionsfläche A mit den Geraden der Kollisionsfläche B errechnen. Existiert kein Schnittpunkt, so liegt auch keine Kollision zwischen den beiden Objekten vor.

Da dieser Ansatz wahrscheinlich für dein Spiel zu aufwendig ist, würde ich mithilfe der oben beschriebenen Methode für einige Pixel des Objektes A prüfen, ob sie eine Kollision in dem Objekt B auslößen.

Also konkret:
Ich würde für jeden Meteor - sagen wir einmal 8 Pixel - überprüfen ob diese sich innerhalb deiner Rakte befinden. Dazu musst du erst die "absolute" Position der Pixel des Meteors berechnen. Diese Position gibst du dann an die "hitAt"-Methode weiter. Diese prüft, ob an dieser Position eine Kollision vorliegt. Wenn dies der Fall ist, dann brauchst du keine Weiteren Pixel zu überprüfen, weil auf jedem Fall eine Kollision vorliegt.

Folgende Pixel (X) würde ich für dein Objekt (O) prüfen:

XOOOXOOOX
OOOOOOOOO
XOOOXOOOX
OOOOOOOOO
XOOOXOOOX

woher ergibt sich die absolute Position?

Angenommen du hast ein Objekt "O".
Dieses Objekt liegt an der Position X=100, Y=100 und hat die Ausmaße Breite=50,Höhe=25 und eine Rotation von 0°.
Nehmen wir weiter an, du hast ein Bild für dein Objekt mit denselben Ausmaßen: Breite=50,Höhe=25.
So liegt die Position des Pixels "P1" X=10,Y=10 innerhalb des Objektes relativ zur Objektposition an der Position X=10, Y=10. Das ist also die relative Position des Punktes P1.

Nun hat das Objekt aber auch eine Position X=100, Y=100. Um die absolute Position des Punktes "P1" zu erhalten muss man also die Objektposition zu der relativen Position addieren. Das bedeutet also das die absolute Position des Punktes "P1" X=110, Y=110 ist. In deinem Falle hat ein Objekt auch noch eine Rotation, diese Rotation muss ebenfalls auf den Punkt "P1" angewendet werden, da er sonst an einer falschen Stelle "vermutet" wird.

Ich hoffe, ich habe dich nicht verwirrt.

Gruß
Steev

 

[Marti]

Ok, das leuchtet mir nun alles ein. Ich war gedanklich noch auf die andere Art der Kollisionsprüfung fixiert. Die von Dir angesprochene Methode mit den Linien klingt auch interessant.
Danke, keine offenen Fragen mehr.