Pixel Perfect Collision Best way

[Hellhound]

Ich versuche mich grad an der Pixel Perfect Collisionsberechnung für 2D Sprites.
Für "normale" Sprites klappt alles hervorragend. Nur wie gehe ich am Besten mit
skalierten und/oder rotierten Sprites um?

PPC ist ja so schon recht Kostenintensiv. Was ist hier der beste Weg? Sollte ich
über den Pixelbuffer gehen oder irgendwie gegen die Original Bilddaten
approximieren?

Für rotierte Sprites habe ich einen guten XNA Artikel gefunden, bei dem die
Rotation per Trigonometrie zurückgerechnet wird, d.h. hier könnte ich einfach
gegen die Originaldaten gehen.

[Sacaldur]

ich habe selbst eigentlich noch keine Erfahrungen mit Pixelperfekter Kollisionserkennung, allerdings:
wie gehst du mit Transparenz in Bildern um? und wie wird skaliert/rotiert?
bei einer Pixelwiederholung müsste einfach genauso vorgegangen werden, wie sonst auch
bei einer Interpolation (oder anderen Filtern, die einen Übergang zwischen transparent und deckend erzeugen würden) müsstest du nur einen Grenzwert für die Transparenz zur Kollisionsprüfung heranziehen
das wiederum wird dann (bei Interpolation) problematisch, wenn die Transparenz sich aus einem fest vorgegebenen Farbwert ergeben, aber dann dürfte man auch Darstellungsprobleme haben ;)

eine andere Frage: wofür die Pixelgenaue Kollisionserkennung?
ich kenne zwar den konkreten Anwendungsfall nicht, aber ich meine behaupten zu können, dass man die Kollisionsabfrage auch unabhängig von der visuellen Repräsentation eines Objekts durchführen kann
diese Informationen "zu drehen" dürfte auch weniger Rechenintensiv sein, vielleicht sogar weniger als PPC auf ungedrehten und unskalierten Grafiken (hängt ja wiederum von den Grafiken ab)

[Schrompf]

Pixelperfekte Kollision brauchst Du nicht überall, behaupte ich. Ich brauche die bei Strahltests (Schüsse und sowas), aber nur für Tiles. Alles Bewegliche ist bereits mit ein paar Grundkörpern angenähert und für Sichtberechnungen willst Du üblicherweise ein eher diffuses Ergebnis und kein perfektes einer unendlich dünnen Linie haben.

Wenn Du pixelperfekte Kollision wirklich brauchst, dann bau sie doch erstmal per linearem Test ein und schau, wie schnell sie ist. Danach kannst Du immernoch auf detailreduzierte Vortests umsteigen. Ich vermute, eine MipMap-Kaskade der Kollisionsmap entlang zu testen sollte hinreichend schnell sein.

[Hellhound]

Ich werde mich hüten die PPC überall zu verwenden ;) Aktuell kann ich bei mir pro Sprite definieren, ob ein PPC erfoderlich ist oder nicht und dann wird das PPC auch nur durchgeführt wenn bereits der Rect-Bounds Test positiv ist. Zudem berücksichtige ich beim PPC einen prozentualen Tolleranzwert für den Alpha Test:

Code: Alles auswählen

bool brSprite::intersect(float x, float y)
{
        // first check if bounding rect collides with point positions
        bool collision = this->contains(x, y);
  
        // perform pixel perfect collision if required
        if(collision && m_usePPC)
        {
      /* Substract actual rectangle position from point position value to
           reduce intersection point to image dimensions in range: [0,width]
           and [0,height].
          
           Please take note that we also have to regard the region x,y
           position values to determine correct image position in atlas
           textures and a scaling of the sprite.
                */
                int pos_x = (int)((x - m_x)+m_region.getX()/m_scale.m_fX);
                int pos_y = (int)((y - m_y)+m_region.getY()/m_scale.m_fY);
        
                if(pos_x<m_width && pos_y<m_height){

                        // define alpha compareable
                        int alpha = 0;
                        if(m_ppcTolerance>0){
                                alpha = (255 * m_ppcTolerance)/100;
                        }

                        // perform pixel perfect collision check
                        brColor color = m_region.getImage()->getPixelColor(pos_x,pos_y);
                        if(color.getAlpha()>alpha){
                                collision = true;
                        }
          else{
                collision = false;
          }
                }       
        }  
        return collision;
}

Auch die Performance ist soweit i.O.. Nur sind die Tests leider zu ungenau. Bei einzelnen skalierten Sprites kann ich diesen Mechanismus ganz gut benutzen, bei Anderen wiederum wird mir Kollision gemeldet obwohl dies nicht der Fall ist. D.h. die Umrechnung ist zu ungenau. Hier suche ich nun nach optimierten Ansätzen. Meine Überlegungen sind z.Z. direkt auf den Pixelbuffer zurückzugreifen, da habe ich ja die exakten Texturdaten, d.h. Skalierung und Rotation sind schon berücksichtigt, oder aber evtl. über die Objektransformation Matrizen die Prüfung durchführen ...