我的抖動算法超級慢

Question

所以這裏有一些上下文。我正在開發一款名爲ShiftOS的遊戲，該遊戲發生在操作系統上，該操作系統開始時作爲80s操作系統的裸機運行，功能不多。

我想添加一個機制，在用戶必須從二進制（2色）顏色深度開始，只能在屏幕上顯示黑色和白色。然後他們必須將顏色深度從1位升級到2位，再將4位升級到24位。這是一個非常整潔的機械師，但實際上這似乎是非常困難的。

當然，這段時間以前的舊系統至少做了TRY以使圖像看起來不錯，但當然它們受到工程師給出的調色板的限制，所以他們必須抖動圖像以便以某種方式排列像素使它看起來就像圖像是使用多種顏色時，在實際中很可能只使用2

於是我查閱了一些很好的抖動算法，並開始學習弗洛伊德 - 斯坦伯格算法，並很快把它移植到C#和System.Drawing。

這是我使用的代碼。

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)); 
     } 
    } 
} 

注意source是通過對功能，通過參數傳遞的Image。

此代碼工作得很好，但問題是，抖動正在單獨的線程上發生，以最大限度地減少遊戲中的減速/滯後，並且在發生抖動時，操作的常規24位顏色/圖像系統顯示。如果抖動沒有那麼長時間，這將很好。

但是我注意到這個代碼中的算法極其緩慢，並且根據圖像的大小我抖動，抖動過程可能需要一分多鐘！

我已經應用了所有我能想到的優化 - 例如在遊戲線程的單獨線程中運行某些東西，並在線程結束時調用給該函數的動作，但這隻會削弱一小段時間if任何。

所以我想知道是否有任何進一步的優化，使其運行速度更快，如果可能總共幾秒鐘。我還想指出，雖然抖動操作正在發生，但我有明顯的系統滯後 - 鼠標甚至有時會抖動和跳躍。對於那些必須擁有60FPS PC大師賽的球員來說，這並不酷。

Answer 1

首先出現在我腦海中的是處理Bitmap，因爲它是數組。默認情況下它不是一個選項，因爲沒有界面可以做到這一點，但是你可以通過一些黑客來實現這一點。快速搜索跟着我到this answer。所以，你必須將你的方法爲unsafe，與LockBits得到的像素值，並用指針數學訪問它們（指原答案的全部代碼）：

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將與有關信息的數組顏色編碼爲byte值。正如你已經看到，GetPixel和SetPixel是緩慢的，因爲他們實際上調用LockBits確保操作。數組將幫助您刪除讀取操作，但是，「SetPixel」仍然可能是瓶頸，因爲您可能需要儘快更新位圖。如果你可以一次更新它，那麼就做到這一點。

第二個想法是創建一些Task隊列，它將逐步更新您的數組。正如我所看到的，您可以從一個角度更新圖像，因此，也許可以設置更新的並行版本。也許你可以用版本控制創建一個不可變的當前狀態數組，所以最後你只需要總結一下新版本的bmp。