Signed distance field rendering (Blending question)

Graphics and GPU Programming Programming

Started by simotix December 10, 2010 04:00 PM

15 comments, last by simotix 13 years, 4 months ago

52,717

December 15, 2010 03:44 AM

Yeah it's a pretty intense process if you don't optimise the hell out of it.

There's not much to learn, it's a fairly straightforward idea - for each pixel, find the distance to the closest pixel with a different value.

for each pixel  closest = max number  for each other pixel    if pixel contents != other pixel contents      D = distance(this pixel, other pixel)       if D < closest        closest = D

The problem is that this is an O(n^2) algorithm -- that is, as you increase the number of pixels linearly, the workload increases exponentially.

By using a limited search area, it's O(n*m), which is still pretty bad.

Some other things you can try:
* Get rid of the square-root operation from the loop. You can perform the search using squared-distances, and then when you've got the final results, go through and perform a square-root for each distance value.

* Get rid of as many ifs as possible. Actually, get rid of as much of the code inside the inner loop (i.e. CalculateSignedDistance). You can simplify it quite a bit, though it'll still probably be unbearably slow...

        float CalculateDistance(Bitmap image, int imageX, int imageY, int scanSize)        {            Color baseColor = image.GetPixel(imageX, imageY);            float closestDistance = float.MaxValue;            int startX = imageX - halfScanSize;            int endX = startX + scanWidth;            int startY = imageY - halfScanSize;            int endY = startY + scanHeight;            // No need in searching past the images bounds            startX = max(0, startX);            startY = max(0, startX);            endX = min(image.Width, endX);            endY = min(image.Height, endY);            for (int x = startX; x < endX; ++x)            {                for (int y = startY; y < endY; ++y)                {                    Color texelColor = image.GetPixel(x, y);                    if (baseColor.R != texelColor.R)                    {                            float dx = imageX - x;                            float dy = imageY - y;                            float dist = dx*dx+dy*dy;                            closestDistance = min(dist, closestDistance);                    }                }            }            return closestDistance;        }........            for (int x = 0; x < signedDistanceBitmap.Width; ++x)            {                for (int y = 0; y < signedDistanceBitmap.Height; ++y)                {                    float distance = CalculateDistance(bitmap, x, y, halfScanSize);                    signedDistances[x, y] = distance;                }            }            for (int x = 0; x < textureOutWidth; ++x)            {                for (int y = 0; y < textureOutHeight; ++y)                {                    float distance = distances[x, y];                    if (distance == float.MaxValue)                        distance = 1.0f;                    else                    {                        distance = Math.Sqrt(distance);                        distance /= halfScanSize;                    }                    if(bitmap.GetPixel(x, y).R == 0)                        distance = -distance;                    distance /= 2;                    distance += 0.5f;                    // Set the signed distance into the alpha channel                    signedDistanceBitmap.SetPixel(x, y, Color.FromArgb((int)Math.Round(distance * 255), 255, 255, 255));                }            }

* Another optimisation I did was to make an array that was a fraction of the size of the original, e.g. [Bitmap.Width/16, Bitmap.Height/16].
In this smaller array, I stored a value indicating whether each 16x16 block of pixels was all solid, all empty, or a mixture of both. Then I could use this information to do much less calculations on the blank areas of my font textures.

...but after doing all this, and getting my tool to run in a few minutes instead of hours, I just use Photoshop these days, which does it instantly ;/

. 22 Racing Series .

unbird

8,359

December 15, 2010 05:22 AM

Yeah, the naive approach is indeed painful. Though probably not as fast as the photoshop/image processing hack, I found this quite useful:
The dead reckoning signed distance transform(pdf)
Since you are using C# - and the source code link in that paper's dead anyway - here's my implementation. I hope I successfully stripped it from my lib stuff.

    public class DistanceField2D    {        public DistanceField2D(int width, int height)        {            Width = width;            Height = height;            bitmap = new bool[width, height];            initDist = new float[width, height];            d = new float[width, height];            p = new Point[width, height];            Reset();        }        public static DistanceField2D FromImage(Bitmap bitmap)        {            return FromImage(bitmap, 128);        }        public static DistanceField2D FromImage(Bitmap bitmap, byte threshold)        {            DistanceField2D result = new DistanceField2D(bitmap.Width, bitmap.Height);            float scale = 1f / 255;            for (int y = 0; y < result.Width; y++)            {                for (int x = 0; x < result.Height; x++)                {                    int colorValue = bitmap.GetPixel(x, y).R;                    result.bitmap[x, y] = colorValue > threshold;                    result.initDist[x, y] = colorValue * scale;                }            }            return result;        }        void Reset()        {            for (int y = 0; y < Height; y++)            {                for (int x = 0; x < Width; x++)                {                    d[x, y] = float.MaxValue;                    p[x, y] = new Point(-1, -1);                }            }        }        void DeadReckoningPropagateSafe(int x, int y, int dx, int dy, float distance)        {            if (Between(x + dx, 0, Width - 1) && Between(y + dy, 0, Height - 1))                DeadReckoningPropagate(x, y, dx, dy, distance);        }        void DeadReckoningPropagate(int x, int y, int dx, int dy, float distance)        {            if (d[x + dx, y + dy] + distance < d[x, y])            {                Point pp = p[x + dx, y + dy];                p[x, y] = pp;                d[x, y] = Distance(x - pp.X, y - pp.Y);            }        }        public void DeadReckoning()        {            Reset();            float d1 = 1f;            float d2 = Distance(1, 1);            // init            for (int y = 1; y < Height - 1; y++)            {                for (int x = 1; x < Width - 1; x++)                {                    if (                        bitmap[x, y] != bitmap[x + 1, y] ||                        bitmap[x, y] != bitmap[x - 1, y] ||                        bitmap[x, y] != bitmap[x, y - 1] ||                        bitmap[x, y] != bitmap[x, y + 1]                       )                    {                        d[x, y] = 0;                        p[x, y] = new Point(x, y);                    }                }            }            // forward pass            for (int y = 0; y < Height; y++)            {                for (int x = 01; x < Width; x++)                {                    DeadReckoningPropagateSafe(x, y, -1, -1, d2);                    DeadReckoningPropagateSafe(x, y, 0, -1, d1);                    DeadReckoningPropagateSafe(x, y, +1, -1, d2);                    DeadReckoningPropagateSafe(x, y, -1, 0, d1);                }            }            // backward pass            for (int y = Height - 2; y >= 0; y--)            {                for (int x = Width - 2; x > 0; x--)                {                    DeadReckoningPropagate(x, y, +1, 0, d1);                    DeadReckoningPropagate(x, y, -1, +1, d2);                    DeadReckoningPropagate(x, y, 0, +1, d1);                    DeadReckoningPropagate(x, y, +1, +1, d2);                }            }            // final pass, detect interiour/exterior             for (int y = 1; y < Height - 1; y++)            {                for (int x = 1; x < Width - 1; x++)                {                    float v = d[x, y];                    if (!bitmap[x, y])                    {                        v = -v;                    }                    d[x, y] = v;                }            }        }        public Bitmap ToImage()        {            return ToImage(1f / Width);        }        public Bitmap ToImage(float scale)        {            Bitmap result = new Bitmap(Width, Height, System.Drawing.Imaging.PixelFormat.Format32bppArgb);            Graphics g = Graphics.FromImage(result);            g.Clear(Color.Black);            g.Dispose();            for (int y = 0; y < Height; y++)            {                for (int x = 0; x < Width; x++)                {                    if (x == 0 || y == 0 || x == Width - 1 || y == Height - 1)                        continue;                    float v = d[x, y];                    if (System.Math.Abs(v) < float.MaxValue)                    {                        int c = (int)(255f * System.Math.Max(0, System.Math.Min(1, v * scale + 0.5f)));                        Color color = Color.FromArgb(c,c,c);                        result.SetPixel(x, y, color);                    }                }            }            return result;        }        bool Between(int value, int min, int max)        {            return value >= min && value <= max;        }        float Distance(int dx, int dy)        {            return (float)System.Math.Sqrt(dx * dx + dy * dy);        }        public bool[,] bitmap;        public float[,] initDist;        public float[,] d;        public Point[,] p;        public int Width;        public int Height;    }

And here's an example how to use:

	int size = 1024;	var original = new Bitmap(size, size);	var graphics = Graphics.FromImage(original);	System.Drawing.Font font = new System.Drawing.Font("Times New Roman", size * 0.4f);	string text = "X";	var f = graphics.MeasureString(text, font);	var p = new PointF();	p.X = (size - f.Width) * 0.5f;	p.Y = (size - f.Height) * 0.5f;	graphics.Clear(Color.Black);	graphics.TextRenderingHint = System.Drawing.Text.TextRenderingHint.SingleBitPerPixelGridFit;	graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.None;	graphics.DrawString(text, font, Brushes.White, p);	graphics.Dispose();	var field = DistanceField2D.FromImage(original);	field.DeadReckoning();	var image = field.ToImage(4f / size); // <------ play with this value!!!	image.Save("big.png");	int smallSize = 64;	Bitmap small = new Bitmap(smallSize, smallSize);	graphics = Graphics.FromImage(small);	graphics.PixelOffsetMode = System.Drawing.Drawing2D.PixelOffsetMode.Half;	graphics.InterpolationMode = System.Drawing.Drawing2D.InterpolationMode.Bilinear;	graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.HighQuality;	RectangleF destRectangle = new RectangleF(0, 0, smallSize, smallSize);	RectangleF sourceRectangle = new RectangleF(0, 0, image.Width, image.Height);	graphics.DrawImage(image, destRectangle, sourceRectangle, GraphicsUnit.Pixel);	graphics.Dispose();	small.Save("small.png");

This 1024x1024 image takes about 5 secs on my Intel DualCore 2GHz. Could probably optimized further if the need arises. Hodgman's last idea with the smaller array sounds interesting :)

Make sure to play around with the scale parameter of ToImage (or even the 0.5f offset in said function). I realized when playing with anti-alias/outline/shadow variants of the shader, sometimes I re-introduced jaggies.

simotix

142

Author

December 15, 2010 04:42 PM

I am looking into both suggestions you gave, there is certaintly a lot of information to read.

Something I noticed is that there is an issue with my blending. I was moving the camera around and I noticed the images are over lapping the previous image. Does anyone know what could be causing this?

Hodgman

52,717

December 16, 2010 05:31 PM

Looks like the depth test might be enabled.

. 22 Racing Series .

simotix

142

Author

December 16, 2010 05:41 PM

That was exactly the issue, I figured that since these were going to be decals in the world and not GUI items that depth testing could still be on. Does depth testing need to be disabled for all objects with alpha?

Hodgman

52,717

December 16, 2010 09:04 PM

No, but alpha-blended objects do need to be drawn sorted from furthest-from-the-camera to closest-to-the-camera.

. 22 Racing Series .

simotix

142

Author

December 18, 2010 03:35 AM

Has anyone ever created a full length character sheet with using any signed distance field? I am interested to know how big they made their initial image. I am doing a 4096x4096 which can take a little bit of time with any size. I am doing it so I may fit all 256 characters on it.

Signed distance field rendering (Blending question)

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Signed distance field rendering (Blending question)

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines