[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.

      Kannst du die Messmethode zeigen? Bei meinem Code sollten eigentlich noch weniger Berechnungen nötig sein, wenn die Compileroptimierung da nicht was dreht.
      Gerade selber mal gemessen. Bei der gleichen Bitmap sind bei meinem Code und Prozessor ca. 6500 Initialisierungen/Sekunde mehr durchgelaufen, wenn ich nicht die nicht-sichtbar-Werte mit 1 Belege, sondern mit 0.

      C#-Quellcode

      1. Stopwatch sw = new Stopwatch();
      2. int f1 = 0, f2 = 0;
      4. using (Bitmap bmp = new Bitmap(10, 10))
      5. {
      6. using (Graphics g = Graphics.FromImage(bmp))
      7. {
      8. g.DrawLine(Pens.Blue, 0, 0, 10, 10);
      9. g.DrawLine(Pens.Red, 10, 0, 0, 10);
      10. }
      11. new CollisionObject(bmp);
      12. new CollisionObjectArtentus(bmp);
      13. sw.Start();
      15. for (; sw.ElapsedMilliseconds < 1000; f1++)
      16. new CollisionObject(bmp);
      17. sw.Restart();
      18. for (; sw.ElapsedMilliseconds < 1000; f2++)
      19. new CollisionObjectArtentus(bmp);
      20. }

      Sprünge kosten bei der Ausführung afaik immer bisschen, auch wenn sie in diesem Fall wahrscheinlich weg optimiert werden.

      Gruß
      ~blaze~

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

      Ich habs so gemessen:

      C#-Quellcode

      1. var sw = new Stopwatch();
      2. var timeArtentus = new List<long>();
      3. var timeBlaze = new List<long>();
      4. for (int i = 0; i < 1000; i++)
      5. {
      6. sw.Start();
      7. new CollisionObjectArtentus(bmp);
      8. sw.Stop();
      9. timeArtentus.Add(sw.ElapsedTicks);
      10. sw.Reset();
      11. sw.Start();
      12. new CollisionObjectBlaze(bmp);
      13. sw.Stop();
      14. timeBlaze.Add(sw.ElapsedTicks);
      15. sw.Reset();
      16. }
      17. Debug.Print(timeArtentus.Average().ToString());
      18. Debug.Print(timeBlaze.Average().ToString());

      Da kommt dann das raus:

      Quellcode

      1. 91,651
      2. 51,286

      Artentus schrieb:

      Allerdings ist das bei mir überhaupt nicht 10 mal schneller, im Gegenteil. Meine Klasse braucht bei mir etwa 4500 Ticks, deine 6800.

      nanu?
      Ich messe aber doch gar keine Ticks.
      Ich messe Millisekunden, und ein sehr großes (beiliegendes) Bild braucht bei meinem Verfahren 246ms, und bei deinem 2743ms.

      Was issn jetzt der aktuellste Code der c#-Variante?

      dann läuft was falsch.
      Wie gesagt: es ist eine große Png - Datei dabei, und die sollteste mal öffnen. Dann ergibt sich eine aussagekräftige Messung.

      Aber ich hab jetzt auch @Blaze:'s Code ausprobiert, und da komme ich einfach nicht ran.
      Dafür gibts 2 Gründe:
      Der Unsafe-Code kann direkt auf den Scan-Pointern rumorgeln.
      Ich verwende zwar Bitmap.LockBits mit dem fabelhaften ImageLockMode.UserInputBuffer, und kriege so ohne Marshalling ein ordentliches Array in verwaltetem Code.
      Aber dieses LockBits ist mit diesem ImageLockMode halt langsam, nämlich in meinen Tests um ziemlich genau die 50ms, die meine schnellste Variante immer noch langsamer ist als Blazes Lösung.
      Klar - UserInputBuffer muß die BitmapDaten in ein verwaltetes Array kopieren.

      Und meine bevorzugte Lösung mittm 2-dim Array (weil der Algo transparenter ist) ist ungefähr halb so schnell wie Blazes fortschreitende Pointer, wohl weil bei 2-dimensionalität eben 2 Indexe auszuwerten sind.
      Ich habe auch mal auf ein 1-dim-Array umgestellt, das war dann genau so schnell wie Pointer-Arithmetik.

      Aufbauend auf der Version von Blaze könnte man das System architektonisch und guidelinemäßig noch etwas erweitern. Ich habe mich mal versucht:
      Ich habe mich gleich als erstes gefragt, warum man das Ganze nicht durch ein Interface vorschreibt? So könnten verschiedene Systeme verwendet werden - falls der eine Initialisierungsalgorithmus eher für größere und der ander für kleinere Bilder besser geeignet ist.
      bei der Funktion, die auf Kollision prüft, habe ich eine ArgumentException hinzugefügt, weil man ja eigentlich keine ungültigen Parameter angeben sollte.
      Spoiler anzeigen

      C#-Quellcode

      1. public interface ICollisionObject
      2. {
      3. bool DoesCollide(Point pos);
      4. bool DoesCollide(int x, int y);
      5. }
      7. public class BitmapCollisionObject : ICollisionObject
      8. {
      9. private int[] _buffer;
      10. private int _length
      11. private int _width;
      13. public BitmapCollisionObject(Bitmap bmp)
      14. {
      15. int width = bmp.Width;
      16. int height = bmp.Height;
      18. BitmapData data = bmp.LockBits(new Rectangle(0, 0, width, height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
      20. int[] outp = new int[(width * height + 31) / 32];
      21. int index = 0;
      22. unsafe
      23. {
      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);
      27. }
      29. _length = width * height;
      30. _width = width;
      31. _buffer = outp;
      33. bmp.UnlockBits(data);
      34. }
      36. public bool DoesCollide(Point pos)
      37. {
      38. return DoesCollide(pos.X, pos.Y);
      39. }
      41. public bool DoesCollide(int x, int y)
      42. {
      43. int index = x + y * _width;
      44. if (index < 0 || 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 DoesCollide(pos); }
      53. }
      55. public bool this[int x, int y]
      56. {
      57. get { return DoesCollide(x, y); }
      58. }
      59. }


      Noch was anderes:
      Wie siehts mit der Threadsicherheit aus? Habe jetzt nichts getestet, aber ich habe in die Richtung böse Befürchtungen.
      Von meinem iPhone gesendet

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

      @nikeee13
      Inwiefern sollte das nicht threadsicher sein? Der Zugriff auf das Array erfolgt ja nur lesend, also ist es egal, in welchem Thread es angelegt wurde. Du musst halt nur aufpassen, dass du nicht ließt, bevor fertig initialisiert wurde, sowas sollte aber normalerweise nicht vorkommen.

      Artentus schrieb:

      sowas sollte aber normalerweise nicht vorkommen
      ...es sei denn man arbeitet mit mehreren Threads. :P
      Vielleicht sollte man synclocken, solange die initialisierung läuft. Threadsicherheit ist nicht so mein Ding, aber ich würde mal in diese Richtung recherchieren. Für's Multithreading gibt's Guidelines, da steht das bestimmt.
      Ab .NET 4.5 kann man das Inlinen von Funktionen (und somit auch Gettern/Settern von Properties) beim JIT erzwingen. MethodImpl(MethodImplOptions.AggressiveInlining). Dass das notwendig ist, bezweifle ich aber hier.
      Von meinem iPhone gesendet

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

      nikeee13 schrieb:

      Aufbauend auf der Version von Blaze könnte man das System architektonisch und guidelinemäßig noch etwas erweitern.
      Jaja - und so fängt man dann an, die nächste Graphics-Lib zu schreiben ;)

      Und die Dinger wachsen ja ins unermessliche, erst kommen Umwandlungen der Image-Formate, dann Filter, Video, ...
      Sone Kollisions-Prüfung (ist ja eiglich keine Kollision) ist da eher noch was exotisches.
      guggetmol, wie sowas zum Lebenswerk sich auswachsen kann: LowLevelGraphicsLibrary

      Tja - mein Ansatz ist da eher gegenteilig - minimalistisch: 2 Konverter-Methoden: Eine gibt dir vonner Bitmap das Pixel-Array zurück, und eine annere baut aus dem Array wieder eine Bitmap zusammen.
      Was der programmierende User dazwischen mit dem Pixel-Array treibt ist dann seiner persönlichen Kunstfertigkeit überlassen ;)
      Convolution-Filter

      Vom logischen Verständnis her wär's lesen threadsicher. Ich hab' aber bisher noch nie überprüft, aber es wäre zumindest logisch. Ich weiß nur, dass ein Freund mal Probleme mit Vector in C++ hatte, da war der Lesevorgang scheinbar nicht threadsicher, obwohl es eigentlich keinen wirklichen Sinn macht.
      Inlining bei virtuellen Funktionen sollte nach meinem Verständnis nicht möglich sein, außer man generiert jedes mal einen Code pro Interface. D.h. das würde mit dem Interface nicht funktionieren.

      Bei meinem Code ist die Abfrage übrigens Quatsch, da X < 0, X > Width, etc. ja trotzdem möglich sind. Dass false zurückgegeben wird, macht aber schon Sinn, da dann ja überhaupt keine Kollision möglich ist. Das würde ich aber in eine andere Klasse auslagern, bei der mit einem Rectangle gearbeitet wird (sonst werden redundante Daten pro Instanz generiert, das wär' ja nicht zweckmäßig).

      Gruß
      ~blaze~

      ~blaze~ schrieb:

      Bei meinem Code ist die Abfrage übrigens Quatsch, da X < 0, X > Width, etc. ja trotzdem möglich sind. Dass false zurückgegeben wird,
      Ergibt vollkommen Sinn. Deshalb ist meine Exception da auch völlig fehl am Platz. Sorry. :P

      Edit:
      Ob das Inlining mit dem Interface funktioniert, habe ich noch nicht ausprobiert. Aber stimmt - Inlining wird bei virtuellen Methoden wohl nicht funktionieren. Schade.
      Von meinem iPhone gesendet

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

    Facebook
    Telefonspende