Polygon um Figur bestimmen

[Cola_Colin]

Für die Kollisionserkennung benötige ich erstmal die Polygone, die meine Figuren umschließen. Nur wie bestimme ich ein Polygon aus einer Grafik ? D.h. ich muss ein Polygon um den nichttransparenten Teil erstellen, wozu mir aber keine Lösung einfällt. Die einzige Lösung die ich gefunden hab, wäre alle nicht transparenten Pixel in eine Menge zu packen und dann mit z.B. QuickHull das Polygon darum zu bestimmen. Aber das liefert ein konvexes Polygone, meine Figuren sind aber zumindest Konkav, am liebsten hätte ich auch noch löcher drinne, aber darauf kann ich glaub ich auch verzichten.

Wie krieg ich das korrekte, konkave Polygon ? Ich will nur ungern jedes Polygon manuell festlegen 😉

 

[Noctarius]

Im schlimmsten Fall kannst du das Polygon aus den einzelnen Außenpixeln zusammensetzen:

000000000000
00#######0
0#######00
0########0
000000000000

Würde als Polygon bedeuten: Ein Punkt eines Polygons ist immer Min und Max jeder Zeile, sowie Ober- und Unterkante

000000000000
00PPPPPPP0
0P#####P00
0PPPPPPPP0
000000000000

Alternativ kannst du halt weniger Polygonpunkte nutzen und nach minX und maxX und minY/maxY suchen und dann aus 4 Punkten ein grobes Rechteck herumziehen.

Ich btw würde beides machen. Eine simple Schnellabfrage mit Rechteck, ist keine Kollision der 2 Rechtecke gegeben, kann auch im inneren Polygon (was mehr Berechnungszeit braucht) keine Kollision existieren. Ist der Rechtecktest positiv würde ich entweder mit den Polygonwerten (aus obigem Beispiel) oder durch direkte Pixelkollision (je nach Spieltyp) eine Kollision berechnen, da dieser Test nur noch seltener auftritt.

 

[Spacerat]

Ich frag' mich gerade ob das mit dem Polygon "rausdrücken" überhaupt notwendig ist. Wenn die Flächen nicht allzu gross sind müsste doch eine UND-Verknüpfung zweier BigInteger, welche aus der Spritegrafik und dem Hintergrund erstellt wurden genügen.

 

[Noctarius]

Geht aber nur bei 2D 😀 Deswegen meinte ich ja auch die Pixelkollision je nach Gamestil

 

[Cola_Colin]

Ich bin in 2D, meine BitMask versuche scheitern nur an der Tatsache, das die Größe der Figuren nicht von der Texturgröße abhängig ist und die Figuren rotiert werden können. Da müsste ich andauernd neue Masken erstellen.
Oder geht das komplett Hardwarebeschleunigt ? Muss mir VolatileImage nochmal genau ansehen.
Allerdings benötige ich auch eine Kollisionsnormale und den Kontaktpunkt.

Wegen den Aussenpixeln, sowas hatte ich auch schon gedacht, nur was ist bei solchen Formen:

Da gibt es Zeilen, die mehr als zwei Randpunkte besitzen, einige meiner Sprites haben noch deutlich unschönere Formen.

Erst mal mit Bounding Volumes nen schnellen Test zu machen versteht sich von selbst 🙂

 

[Noctarius]

Da hast du halt ein großes Rechteck außen rum, das ist viel schneller abzutesten als der Pixelvergleich später. Ist es im Rechteck nicht enthalten, brauch man die Pixelkollision garnicht erst zu starten. Als Außenrechteck kannst du z.B. auch einfach das komplette Image-Height/Width nehmen (wenn du nicht zuviel Rahmen drum herum hast).

if (sprite.isQuickCollision(sprite2))
    if (sprite.isCollision(sprite2))
        // Kollisionscode

 

[Cola_Colin]

Das mach ich doch schon 😉
Nur trotzdem brauch ich ja nen Weg für den Pixelgenauen Test, hin und wieder wird es ja Kollisionen geben.

 

[Noctarius]

Überlappung berechnen und dann Pixel für Pixel, innerhalb der Überlappung, durchgehen schauen ob beide Pixel nicht durchsichtig sind (transparente Farbe muss ja berücksichtigt werden) und wenn sie es nicht sind, hast du eine Kollision. Dann kannst du den Test abbrechen und behaupten, ja.

 

[Cola_Colin]

Das ist mir schon klar ~.~
Nur was mach ich bei Rotierten Sprites und skalierten ? Immer im Speicher die ganzen Sprites neuzeichnen ist mist.

 

[Ark]

Weichen die Formen der Sprites stark von Rechtecken ab, bzw. lassen sich die Formen jeweils durch einige wenige Rechtecke annähernd beschreiben? Ist es außerdem möglich, einige Toleranzen in der Kollisionserkennung in Kauf zu nehmen? Wenn ja, würde ich eben so vorgehen und mit Rechtecken arbeiten.

Man könnte stattdessen aber auch näherungsweise Dreiecke benutzen, aus denen die Polygone gebildet werden; das erlaubt außerdem eine bessere Annäherung.

Ark

 

[Cola_Colin]

Am liebsten will ich das Separating axis theorem verwenden, nur dazu brauch ich eben Polygone. Ich glaub ich hab jetzt aber ne Vorstellung, wie ich die kriegen kann. Mal schaun, dann müssen die glaub ich auch noch Konvex sein. Vielt werde ich dann jedem Sprite mehrere konvexe Polygone zuweisen, dann brauch ich auch noch nen Algo, der ein konkaves Polygon zerlegt xD