Mein Dithering-Algorithmus ist super langsam

Question

Also hier ist ein Zusammenhang. Ich arbeite an diesem Spiel mit dem Namen ShiftOS, das in einem Betriebssystem läuft, das als ein blanker Lauf des Betriebssystems der 80er Jahre mit nicht vielen Funktionen beginnt.

Ich versuche, eine Mechanik hinzuzufügen, wo der Benutzer mit binärer (2-Farben-) Farbtiefe beginnen muss und nur Schwarz und Weiß auf dem Bildschirm anzeigen kann. Dann müssen sie die Farbtiefe von 1-Bit auf 2-Bit auf 4-Bit bis 24-Bit aktualisieren. Es ist eine wirklich gepflegte Mechanik, aber in der Praxis scheint es extrem schwierig zu sein.

Natürlich testeten ältere Systeme zu dieser Zeit zumindest TRY, um Bilder schön zu machen, aber natürlich wurden sie durch die Farbpaletten der Ingenieure begrenzt, also mussten sie die Bilder zittern, um Pixel so anzuordnen, dass Es sah so aus, als ob das Bild mehr Farben verwendete, wenn es in aller Realität nur mit 2 verwendet werden konnte. Also habe ich ein paar gute Dithering-Algorithmen nachgeschaut und angefangen, den Floyd-Steinberg-Algorithmus zu lernen und es bald auf C# portiert System.Drawing.

Hier ist der Code, den ich verwende.

var bmp = new Bitmap(source.Width, source.Height); 
var sourceBmp = (Bitmap)source; 
int error = 0; 
for (int y = 0; y < bmp.Height; y++) 
{ 
    for (int x = 0; x < bmp.Width; x++) 
    { 
     Color c = sourceBmp.GetPixel(x, y); 
     int gray = ((c.R + c.G + c.B)/3); 
     if (gray >= 127) 
     { 
      error = gray - 255; 
      bmp.SetPixel(x, y, Color.White); 
     } 
     else 
     { 
      error = gray; 
      bmp.SetPixel(x, y, Color.Black); 
     } 
     /* 
     * Pixel error diffusion map: Floyd-Steinberg. Thanks to Wikipedia. 
     * 
     * pixel[x + 1][y ] := pixel[x + 1][y ] + quant_error * 7/16 
     * pixel[x - 1][y + 1] := pixel[x - 1][y + 1] + quant_error * 3/16 
     * pixel[x ][y + 1] := pixel[x ][y + 1] + quant_error * 5/16 
     * pixel[x + 1][y + 1] := pixel[x + 1][y + 1] + quant_error * 1/16 
     */ 

     if(x - 1 >= 0 && y + 1 != bmp.Height) 
     { 
      var bottomRightColor = sourceBmp.GetPixel(x - 1, y + 1); 
      int bottomRightGray = ((bottomRightColor.R + bottomRightColor.G + bottomRightColor.B)/3) + ((error * 3)/16); 
      if (bottomRightGray < 0) 
       bottomRightGray = 0; 
      if (bottomRightGray > 255) 
       bottomRightGray = 255; 
      sourceBmp.SetPixel(x - 1, y + 1, Color.FromArgb(bottomRightGray, bottomRightGray, bottomRightGray)); 
     } 
     if (x + 1 != sourceBmp.Width) 
     { 
      var rightColor = sourceBmp.GetPixel(x + 1, y); 
      int rightGray = ((rightColor.R + rightColor.G + rightColor.B)/3) + ((error * 7)/16); 
      if (rightGray < 0) 
       rightGray = 0; 
      if (rightGray > 255) 
       rightGray = 255; 
      sourceBmp.SetPixel(x + 1, y, Color.FromArgb(rightGray, rightGray, rightGray)); 
     } 
     if (x + 1 != sourceBmp.Width && y + 1 != sourceBmp.Height) 
     { 
      var bottomRightColor = sourceBmp.GetPixel(x + 1, y + 1); 
      int bottomRightGray = ((bottomRightColor.R + bottomRightColor.G + bottomRightColor.B)/3) + ((error)/16); 
      if (bottomRightGray < 0) 
       bottomRightGray = 0; 
      if (bottomRightGray > 255) 
       bottomRightGray = 255; 
      sourceBmp.SetPixel(x + 1, y + 1, Color.FromArgb(bottomRightGray, bottomRightGray, bottomRightGray)); 
     } 
     if (y + 1 != sourceBmp.Height) 
     { 
      var bottomColor = sourceBmp.GetPixel(x, y + 1); 
      int bottomGray = ((bottomColor.R + bottomColor.G + bottomColor.B)/3) + ((error * 5)/16); 
      if (bottomGray < 0) 
       bottomGray = 0; 
      if (bottomGray > 255) 
       bottomGray = 255; 
      sourceBmp.SetPixel(x, y + 1, Color.FromArgb(bottomGray, bottomGray, bottomGray)); 
     } 
    } 
} 

anzumerken, dass source ist ein Image, die durch auf die Funktion über ein Argument übergeben wird.

Dieser Code funktioniert ziemlich gut, aber das Problem ist, das Dithering geschieht auf einem separaten Thread, um Verlangsamungen/Verzögerung im Spiel zu minimieren, und während das Dithering auftritt, die regulären 24-Bit-Farben/Bilder des Betriebs System werden angezeigt. Das wäre in Ordnung, wenn das Dithering nicht so lange dauert.

Allerdings merke ich, dass der Algorithmus in diesem Code EXTREM langsam ist und abhängig von der Größe des Bildes, das ich dithering, könnte der Dithering-Prozess mehr als eine Minute dauern!

Ich habe alle Optimierungen angewendet, die ich mir vorstellen kann - zum Beispiel die Ausführung von Dingen in einem separaten Thread vom Spiel-Thread und das Aufrufen einer Aktion, die der Funktion gegeben wird, wenn der Thread beendet wird, aber dies spart nur ein kleines bisschen Zeit irgendein.

Also ich frage mich, ob es weitere Optimierungen gibt, um dieses schneller zu machen, ein paar Sekunden wenn möglich. Ich möchte auch darauf hinweisen, dass während der Dithering-Operation merkliche Systemverzögerungen auftreten - die Maus zittert sogar und springt manchmal herum. Nicht cool für diese 60-PS-Master-Race-Jungs.

Answer 1

Das erste, was in meinem Kopf kommt, ist mit Bitmap umzugehen, wie es Array wäre. Standardmäßig ist dies keine Option, da es keine Schnittstelle dafür gibt, aber Sie können dies mit einigen Hacks erreichen. Schnellsuche folgte mir auf this answer. So müssen Sie Ihre Methode als unsafe, erhalten die Pixelwerte mit LockBits gesetzt, und greifen Sie mit Zeigermathematik (die ursprüngliche Antwort für den vollständigen Code beziehen):

System.Drawing.Imaging.BitmapData bmpData = 
    bmp.LockBits(rect, System.Drawing.Imaging.ImageLockMode.ReadWrite, 
    bmp.PixelFormat); 
var pt = (byte*)bmpData.Scan0; 
// for loop 
var row = pt + (y * bmpData.Stride); 
var pixel = row + x * bpp; // bpp is a number of dimensions for the bitmap 

pixel wird ein Array mit Informationen über die Farben codiert in byte Werte. Wie Sie bereits gesehen haben, sind GetPixel und SetPixel langsam, weil sie eigentlich die zur Sicherung der Operation anrufen. Array wird Ihnen helfen, Leseoperationen zu entfernen, "SetPixel" ist jedoch immer noch ein Flaschenhals, da Sie die Bitmap möglicherweise so schnell wie möglich aktualisieren müssen. Wenn Sie es am Ende und auf einmal aktualisieren können, dann tun Sie das.

Zweiter Gedanke ist es, einige Task Warteschlange erstellen, die Ihr Array Schritt für Schritt aktualisieren wird. Wie ich sehen kann, aktualisieren Sie Ihr Bild aus einem Blickwinkel. Vielleicht können Sie also eine parallele Version Ihres Updates einrichten. Vielleicht können Sie mit der Versionierung ein unveränderliches Array des aktuellen Zustands erstellen, so dass Sie am Ende nur die neue Version von bmp zusammenfassen.