[C#] [SourceCode] Pixelgenaue Kollisionserkennung mit Laufzeit O(1) Version 1.1

    • C#

    Es gibt 32 Antworten in diesem Thema. Der letzte Beitrag () ist von nikeee13.

      [C#] [SourceCode] Pixelgenaue Kollisionserkennung mit Laufzeit O(1) Version 1.1

      @Mods
      Es gibt leider keinen SourceCodeAustausch für "weitere Programmiersprachen", deswegen hab ich das hier reingepackt.
      Wenns doch in den normalen SourceCodeAustausch gehört, kann das ja verschoben werden.

      Beschreibung:
      Mit diesem Code hier könnt ihr Pixelgenau bestimmen, ob ein bestimmter Punkt eines Bildes ein Kollision verursacht oder nicht. Er ist vollständig kommentiert.
      Da ich LockBits in Verbindung mit Unsafe verwendet habe, kann er leider nicht ohne weiteres nach VB konvertiert werden, dafür ist das ganze um einiges schneller.
      Die Laufzeit beträgt O(1), also sie ist für beliebig große Bilder gleich schnell. Nur die Initialisierung benötigt bei größeren Bildern länger.
      Spoiler anzeigen

      C#-Quellcode

      1. /// <summary>
      2. /// Führt pixelgenaue Kollisionserkennungen für Bitmaps aus.
      3. /// </summary>
      4. public class CollisionObject
      5. {
      6. byte[] bytes;
      7. int width, height;
      9. /// <summary>
      10. /// Erstellt ein neues CollisionObject aus der angegebenen Bitmap.
      11. /// </summary>
      12. /// <param name="bmp"></param>
      13. public CollisionObject(Bitmap bmp)
      14. {
      15. //Höhe und Breite des Bildes Speichern
      16. width = bmp.Width;
      17. height = bmp.Height;
      19. //LockBits für bessere Performance
      20. var data = bmp.LockBits(new Rectangle(0,0,bmp.Width,bmp.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
      22. //Byte-Array erstellen
      23. bytes = new byte[(width * height + 7) / 8]; //Bytes anlegen
      24. int index = 0; //Position im Array
      25. int posInByte = 0; //Position des aktuellen Bits im Byte
      26. unsafe
      27. {
      28. for (byte* alpha = (byte*)data.Scan0 + 3, lastAlpha = alpha + width * height * 4; alpha < lastAlpha; alpha += 4 )
      29. {
      30. //Alphakanal des aktuellen Pixels prüfen
      31. if (*alpha > 0)
      32. bytes[index] = (byte)(bytes[index] | (1 << posInByte)); //wenn Pixel nicht transparen, Bit auf 1 setzen
      34. posInByte++; //Bitposition erhöhen
      36. //wenn Byte voll, nächstes auswählen
      37. if (posInByte == 8)
      38. {
      39. index++;
      40. posInByte = 0;
      41. }
      42. }
      43. }
      45. bmp.UnlockBits(data); //Bild freigeben
      46. }
      48. /// <summary>
      49. /// Bestimmt, ob das Bild an einer angegebenen Stelle transparent ist oder nicht.
      50. /// </summary>
      51. /// <param name="pos"></param>
      52. /// <returns></returns>
      53. public bool PixelVisible(Point pos)
      54. {
      55. if (pos.X < 0 || pos.Y < 0 || pos.X >= width || pos.Y >= height)
      56. return false; //Punkt liegt außerhalb der Bildes
      58. //Position des Bits berechnen
      59. var bitIndex = pos.Y * width + pos.X; //Gesammtindex berechnen
      60. var byteIndex = bitIndex / 8; //Index des Bytes im Array berechnen
      61. var posInByte = bitIndex % 8; //Index des Bits im Byte berechnen
      63. //Prüfen, ob das Bit 1 ist
      64. var val = (byte)(1 << posInByte);
      65. return (bytes[byteIndex] & val) == val;
      66. }
      67. }

      Verwendung ist denke ich mal klar.
      Erst eine neue Instanz mit dem gewünschten Bild erstellen, dann kann einfach mit PixelVisible abgefragt werden, ob ein bestimmter Punkt sichtbar ist oder nicht.

      Edit Version 1.1: dank ~blaze~ konnte ich den Code noch etwas optimieren, die Initialisierung sollte nun nur noch etwa ein Drittel der alten Zeit brauchen.

      Das ganze ist übrigens durch diesen Thread entstanden.
      Dateien

      Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von „Artentus“ ()

      na, das ließe sich schon auch in vb schreiben, und wäre auch nicht langsamer.
      höchstens die Initialisierung, aber die auch nur paar %.

      Wenn du ein Testprojekt anhängst (inklusive Bildle), kannichdas mal probieren.


      Wassich dir empfehlen kann: guck dir mal die Klasse BitArray an.

      Ich bezog mich auch nur auf den unsafe-Teil. Dass der Rest in VB auch geht, ist mir schon klar.
      Allerdings dürften das doch mehr als ein paar Prozent sein, denn Marshalling ist im Vergleich zu Pointern enorm langsam.

      Testprojekt kann ich schnell schreiben, schien mir halt bei dem bisschen Code nicht nötig.

      Und ja, BitArray wurde mir schon empfohlen, aber ich werde das jetzt nicht mehr umschreiben, funktioniert ja tadellos und dürfte sogar etwas schneller sein.

      Warum machst du es so, dass man es "nicht ohne weiteres" nach VB konvertieren kann? Somit ist dein Code ziemlich unnütz, solange man ihn nicht in eine .dll packt, somit könntest du diese eigentlich auch gleich als .dll veröffentlichen.

      Hi
      Marshalling wäre halt dann einfach Marshal.Copy in ein Integer-Array und dann das gleiche auf dem Integer-Array. Ist effizienter, als jedes mal einen Aufruf von Marshal.ReadInt32 oder so zu machen.
      C# wurde btw. vmtl. verwendet, weil es für diese Art der Anwendung sinnvoller ist, als VB.

      Gruß
      ~blaze~

      Hi
      hier wär' mein Ansatz:

      C#-Quellcode

      1. using System;
      2. using System.Drawing.Imaging;
      3. using System.Drawing;
      5. namespace CollisionTest
      6. {
      7. public class CollisionObject
      8. {
      9. int[] _buffer;
      10. int _length, _width;
      12. public CollisionObject(Bitmap bmp)
      13. {
      14. int width = bmp.Width;
      15. int height = bmp.Height;
      17. BitmapData data = bmp.LockBits(new Rectangle(0, 0, bmp.Width, bmp.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
      19. int[] outp = new int[(width * height + 31) / 32];
      20. int index = 0;
      21. unsafe
      22. {
      23. //Alphakanal ist an Offset 3
      24. for (byte* cp = (byte*)data.Scan0 + 3, targetptr = cp + width * height * 4; cp < targetptr; cp += 4, index++)
      25. if (*cp == 0)
      26. outp[index / 32] |= 1 << (index % 32); //man koennte, wen mans uebertreiben will, noch die % 32 in eine extra loop auslagern
      27. }
      29. _length = width * height;
      30. _width = width;
      31. _buffer = outp;
      33. bmp.UnlockBits(data);
      34. }
      36. public bool IsVisible(Point pos)
      37. {
      38. return IsVisible(pos.X, pos.Y);
      39. }
      41. public bool IsVisible(int x, int y)
      42. {
      43. int index = x + y * _width;
      44. if (x < 0 || y < 0 || x >= _width || index > _length)
      45. return false;
      47. return (_buffer[index / 32] & (1 << (index % 32))) == 0;
      48. }
      50. public bool this[Point pos]
      51. {
      52. get { return IsVisible(pos); }
      53. }
      55. public bool this[int x, int y]
      56. {
      57. get { return IsVisible(x, y); }
      58. }
      59. }
      60. }

      bei Artentus Code waren noch einige unnötige Konvertierungen und über Zeigerarithmetik lässt sich das schöner lösen ;). Von der Geschwindigkeit her hab' ich's nicht getestet.

      Gruß
      ~blaze~

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „~blaze~“ ()

      ...und sollte wegen Zeile 38 beim Aufruf der Funktion in Zeile 36 nem Stackoverflow erzeugen;
      wohl den falschen Overload genommen. :P

      Edit: So, jetzt stimmt's. :D
      Von meinem iPhone gesendet

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „nikeee13“ ()

      @~blaze~
      Ich hab mir deine Version mal genauer angeschaut und einiges daraus in meinen Code eingearbeitet, sind jetzt nur noch 50 gegen 90 Ticks. :P
      Wo die restlichen 40 Ticks bei dir herkommen hab ich übrigens keine Ahnung.

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Artentus“ ()

    Facebook
    Telefonspende