c# - 我的抖动算法 super 慢

Question

所以这里有一些背景。我正在开发这款名为 ShiftOS 的游戏，该游戏发生在一个操作系统中，该操作系统最初是 80 年代操作系统的基本运行，功能不多。

我正在尝试添加一种机制，用户必须从二进制(2 色)颜色深度开始，并且只能在屏幕上显示黑色和白色。然后他们必须将颜色深度从 1 位升级到 2 位，再到 4 位，一直到 24 位。这是一个非常巧妙的机制，但在实践中似乎极其困难。

当然，当时的旧系统至少尝试让图像看起来不错，但当然它们受到工程师提供的调色板的限制，因此他们不得不抖动图像以按照一种方式排列像素看起来图像使用了更多颜色，而实际上它只能使用 2 种颜色。

所以我查找了一些好的抖动算法并开始学习 Floyd-Steinberg 算法并很快将其移植到 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 位颜色/图像显示。如果抖动不花费这么长时间，这会很好。

但是我注意到此代码中的算法非常慢，并且根据抖动图像的大小，抖动过程可能需要一分多钟!

我已经应用了我能想到的所有优化 - 例如在游戏线程之外的单独线程中运行事物，并在线程完成时调用提供给函数的 Action 但这只会节省一点时间(如果有的话) .

所以我想知道是否有任何进一步的优化来使这个操作更快，如果可能的话总共几秒钟。我还想指出，在进行抖动操作时，我有明显的系统延迟——鼠标有时甚至会抖动和跳来跳去。对于那些必备的 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 来确保操作。 Array 将帮助您删除读取操作，但是，“SetPixel”仍然可能是瓶颈，因为您可能需要尽快更新位图。如果您可以在最后一次性更新它，那就去做吧。

第二个想法是创建一些 Task 队列，它将逐步更新您的数组。如我所见，您从一个角度更新图像，因此，也许您可​​以设置更新的并行版本。也许你可以创建一个带有版本控制的当前状态的不可变数组，所以最后你只需总结 bmp 的新版本。