Rechteckkollision, Ermitteln des Überschneidungsrechtecks

[Thorium]

Was ist der optimale Weg das Überschneidungsrechteck (nennt man das überhaupt so?) zweier sich überlappender Rechtecke zu ermitteln?

Hier mal ein Beispielbild was ich meine:

Das blaue und grüne Rechteck überlappen sich. Was ich nun brauche ist das dadurch entstandene grau gefüllte Rechteck. Und zwar alle 4 Punkte des Rechtecks 2 mal. 2 mal weil ich sie einmal relativ zum oberen linken Eckpunkt des blauen und einmal relativ zum oberen linken Eckpunkt des grünen Rechtecks brauche.

Meine Überlegung ist es die Koordinaten der Eckpunkte miteinander zu subtrahieren. Dabei kommen ein paar negative Werte raus, die dann Abhängig vom Eckpunkt auf 0 gesetzt werden oder die Länge/Höhe des Rechtecks zu dem negativen Wert addiert wird.
Das scheint auch zu funktionieren. Nur gibt es sicherlich eine wesentlich elegantere Methode, die mit weniger Prüfen auskommt oder sogar ganz ohne. Allein schon das ich auf negative Werte prüfen muss würde ich gerne vermeiden. Von Mathe versteh ich recht wenig, von daher frag ich einfach mal hier. ^^

Das ganze ist für die Vorbereitung zu einem Pixelkollisionstest gedacht.
Ich hab ne gute Idee für einen wahnsinnig schnellen Pixelkollisionstest, der bis zu 128 Pixel mit nur einem Vergleich testen kann. Nur brauche ich unbedingt dieses Überschneidungsrechteck, zum einen zur Optimierung aber noch viel wichtiger dazu nicht auf Speicher ausserhalb der Sprites zuzugreifen, sonst krachts.

[TomS]

Bißchen andere Aufgabenstellung, aber evtl kannst du was mit dem Link oder dem Code anfangen.
http://purebasic-lounge.com/viewtopic.php?t=6311

[STARGÅTE]

Das ergebnis wäre indem du beide Seitenprojektionen benutzt,
daraus kannst du ermitteln wie sie die beiden Seiten überlappen und damit dnan das recheck erstellen.

EDIT:
Hier ein Link dazu:
Kollision zweier Rechtecke erkennen

[GPI]

So würde ich das Lösen:

Code: Alles auswählen

p1x=100:p1y=100:p1w=200:p1h=200
p2x=200:p2y=150:p2w=200:p2h=100

If p1x>p2x 
  p3x=p1x
Else
  p3x=p2x
EndIf

If p1y>p2y 
  p3y=p1y
Else
  p3y=p2y
EndIf

If p1x+p1w<p2x+p2w
  p3w=p1w-(p3x-p1x)  
Else
  p3w=p2w-(p3x-p2x)
EndIf

If p1y+p1h<p2y+p2h
  p3h=p1h-(p3y-p1y)  
Else
  p3h=p2h-(p3y-p2y)
EndIf

Debug Str(p3x)+" "+Str(p3y)+" "+Str(p3w)+" "+Str(p3h)

OpenWindow(0,0,0,500,500,"Dummy",#PB_Window_ScreenCentered|#PB_Window_SystemMenu)
InitSprite()
OpenWindowedScreen(WindowID(0),0,0,500,500,0,0,0)
While WindowEvent()<>#PB_Event_CloseWindow
  StartDrawing(ScreenOutput())
  Box(p1x,p1y,p1w,p1h,RGB(255,0,0))
  Box(p2x,p2y,p2w,p2h,RGB(0,255,0))
  If i
    i=0
    Box(p3x,p2y,p3w,p3h,RGB(0,0,255))
  Else
    i=1
  EndIf
  StopDrawing()
  FlipBuffers()
Wend

  

wenn p3w oder p3h 0 oder negativ sind, gabs keine Überschneidung.

Achtung nicht voll getestet.

[Thorium]

Das ergebnis wäre indem du beide Seitenprojektionen benutzt,
daraus kannst du ermitteln wie sie die beiden Seiten überlappen und damit dnan das recheck erstellen.

Kannst du das etwas genauer ausführen, ich versteh nur Bahnhof. Wird dich vieleicht schocken aber meine Schulbildung ist grad mal Hauptschule. Und in Mathe hab ich mich danach nicht selbst weitergebildet. ^^

Hier ein Link dazu:
Kollision zweier Rechtecke erkennen

Die Seite kenne ich.
Ich nutze auch den Kollisionstest der dort vorgeschlagen wird um erstmal zu prüfen ob überhaupt eine Überschneidung vorliegt. Das heisst auf Überschneidung muss nicht mehr geprüft werden. Es geht rein darum möglichst effizient die Koordinaten der Eckpunkte des 3. Rechtecks relativ zum 1. und 2. Rechteck zu bekommen.

So würde ich das Lösen:

Vielen Dank für deinen Lösungsvorschlag aber ich habe an einen mehr mathematischen Weg gedacht, du prüft auch viel = viele Branches. Desdo weniger Branches desdo besser (schneller).
Zudem brauch ich nicht die absoluten Koordinaten des Rechtecks sondern ich brauche das Rechteck zweimal. Wie ich oben geschrieben habe. Ich brauche die Koordinaten des 3. Rechteck jeweils relativ zum 1. und zum 2. Rechteck. Absolute Koordinaten interessieren mich nicht. Ich muss wissen welche Pixel der Sprites ich gegeneinander testen muss.

wenn p3w oder p3h 0 oder negativ sind, gabs keine Überschneidung.

Auf Überschneidung muss nicht mehr getestet werden, das eine Überschneidung stattfindet ist in schon klar, an dieser stelle. Wird vorher mit einfacher Rechteck-Rechteck-Kollision geprüft.

[GPI]

Ich glaube rein mathematisch wirst du kaum eine Chance haben. Ich kenn zumindest keine Formel die ein Rechteck beschreiben würde.

Wenn du die absoluten Koordinaten hast, haste auch die relative

bei den oberen if-abfragen für x/y kannst du bestimmen, welcher Kasten in den anderen ist.

Blöde Frage, warum nimmst du eigentlich nicht die in PB verbauten routinen?

edit: Achso eigene Routine. Darf man fragen wie?

[Thorium]

Blöde Frage, warum nimmst du eigentlich nicht die in PB verbauten routinen?

Weil ich gerne das Rad neu erfinde. ^^

Im grunde gehts mehr oder weniger auch nur um einen "proof of concept".
Hab halt ne Idee und will sehen wieviel schneller die wirklich ist als die in PB integrierte Pixelkollision.
Ich schätze so auf 30 mal schneller, vieleicht auch mehr.

Wirklich viel nützlicher ist sie aber nicht, da sie auch keine Rotation, Zoom, Spieglung, etc. handlen kann.
Könnte man implementieren. Aber dann würde die Performance dahinschmelzen nicht nur weil die Rotation an sich performance kostet sondern auch weil ich dann nicht mehr mit so kleinen Einheiten arbeiten kann ohne masive Performaceeinbrüche.

Die Idee dahinter ist eigentlich nichts neues.
Ist mir eingefallen hab dann im Internet gesucht und natürlich hatte vor langer Zeit schon jemand anders die Idee. Aber is ja egal, ich will trotzdem ein POC machen. ^^

Anstatt das die wirklichen Pixeldaten verglichen werden wird eine Collisionmap jedes Sprites angelegt. Die muss im Optimalfall nur einmal beim Laden des Sprites angelegt werden. Dadurch brauchen die Spritedaten nicht mehr von der Grafikkarte zurück in den Hauptspeicher übertragen werden. Aber das ist nicht der eigentliche Trick. Der eigentliche Trick ist das ein Pixel in der Collisionmap nur 0 (transparent) oder 1 (sichtbar) hat. Dadurch lässt sich 1 Pixel in 1 Bit speichern. Nun nehmen wir uns die 128bit XMM Register und laden da 128 pixel aus der collisionmap rein und testen die gegen ein zweites 128bit XMM Register mit einer AND operation. Ist unser XMM Register nach der AND operation ungleich 0 haben wir eine Kollision. Natürlich gibt es einen gewissen Overhead beim beladen der Register, da wir auf jeden fall shiften müssen und mindestens 2 mal auf den Speicher zugreifen müssen um ein 128bit Register vollzuladen. Esseiden wir haben glück und die Pixel der Sprites sind glücklich alignt. Dann reicht auch ein Speicherzugriff.

Aber in jedem Fall führen wir nur einen Vergleich für 128 Pixel aus!

[GPI]

dann schau dir meinen code an.

Beim test welches X1 weiter rechts ist, weist du dann, welcher Sprite unverändert übernommen werden kann und welcher um wieviel (der unterschied) gekürzt werden muss

Beim Test auf Y kannst du rausfinden, welcher SPrite bei 0 beginnt und welcher ein offset hat (auch der unterschied)

Die Breite brauchst du nicht! - Die höhe allerdings schon.

dann eine Schleife auf höhe und testen...

So würd ichs machen - den Kollisionstest kannste ja dann knicken und das kombiniern (mußt dann doch die Breite kurz überprüfen) - würdest dann zeit sparen.

Edit: ähnliche Idee hatte ich schon auf den Atari ST

[Thorium]

Ich hab grad gesehen einen Vorteil hätte meine Implementation schon, neben der höheren Geschwindigkeit unterstützt sie den Alphakanal. Unterstützt werden 8bit, 16bit, 24bit und 32bit.
Bei 8, 16 und 24 muss eine Transparente Farbe angegeben werden bei 32 muss ein Schwellenwert angegeben werden ab welcher Transparenz ein Pixel als durchlässig gild. Das ist soweit auch schon programmiert.

Laut PB-Hilfe unterstützt SpritePixelCollision keinen Alphakanal.

[#NULL]

du hast 2 rechtecke (mit jeweils 4 punkten), macht 8 punkte die du mindestens einmal auslesen musst.
du willst 2 rechtecke (mit jeweils 4 punkten), macht mindestens 8 berechnungen oder zuweisungen.
du musst arithmetische operatoren benutzen.
den rest musst du mit entweder mit If oder mit logischen operatoren machen. probier halt was schneller ist, ich schätze mal If.
GPI's lösung lässt sich meiner meinung nach nicht mehr vereinfachen.