Signed Distance Field generator for Unity with Burst support

BurstSDFGenerator.cs

/*
	Based on the Anti-aliased Euclidean distance transform described by Stefan Gustavson and
	Robin Strand. For further information, see https://contourtextures.wikidot.com/ and
	https://web.archive.org/web/20220503051209/https://weber.itn.liu.se/~stegu/edtaa/

	The algorithm is an adapted version of Stefan Gustavson's code, it inherits the copyright
	statement below, which applies to this file only.

	The rewrite with Unity Burst support makes the execution 40 times faster by default,
	and 75 times faster if the passed in textures are both of type TextureFormat.RGBAFloat.
	In the former case, much of the 40x speedup was gained by getting and setting all pixels
	at once instead of with individual GetPixel/SetPixel calls.

	Copyright (C) 2024 Rune Skovbo Johansen (https://runevision.com) for Unity Burst support.
	Copyright (C) 2012 Jasper Flick (https://catlikecoding.com) for adaptation to C# for Unity.
	Copyright (C) 2009 Stefan Gustavson ([email protected])

	This software is distributed under the permissive "MIT License":

	Permission is hereby granted, free of charge, to any person obtaining a copy
	of this software and associated documentation files (the "Software"), to deal
	in the Software without restriction, including without limitation the rights
	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
	copies of the Software, and to permit persons to whom the Software is
	furnished to do so, subject to the following conditions:

	The above copyright notice and this permission notice shall be included in
	all copies or substantial portions of the Software.

	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
	THE SOFTWARE.
 */

using Unity.Burst;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;
using UnityEngine;

namespace SDF {

	/// <summary>
	/// How to fill the RGB channels of a generated singed distance field texture.
	/// </summary>
	public enum RGBFillMode {
		/// <summary>
		/// Set the RGB channels to 1.
		/// </summary>
		White,
		/// <summary>
		/// Set the RGB channels to 0.
		/// </summary>
		Black,
		/// <summary>
		/// Set the RGB channels to the generated distance field.
		/// </summary>
		Distance,
		/// <summary>
		/// Copy the source texture's RGB channels.
		/// </summary>
		Source
	}

	/// <summary>
	/// Utility class for generating signed distance field textures from anti-aliased alpha maps.
	/// </summary>
	/// <description>
	/// Although the generator can be used at run-time, the current version isn't convenient nor optimized for it.
	/// </description>
	[BurstCompile]
	public static class BurstSDFGenerator {
		
		private struct Pixel {
			public float alpha, distance;
			public Vector2 gradient;
			public int dX, dY;
		}
		
		/// <summary>
		/// Fill a texture with a signed distance field generated from the alpha channel of a source texture.
		/// </summary>
		/// <param name="source">
		/// Source texture. Alpha values of 1 are considered inside, values of 0 are considered outside, and any other values are considered
		/// to be on the edge. Must be readable.
		/// </param>
		/// <param name="destination">
		/// Destination texture. Must be the same size as the source texture. Must be readable.
		/// The texture change does not get applied automatically, you need to do that yourself.
		/// </param>
		/// <param name="maxInside">
		/// Maximum pixel distance measured inside the edge, resulting in an alpha value of 1.
		/// If set to or below 0, everything inside will have an alpha value of 1.
		/// </param>
		/// <param name="maxOutside">
		/// Maximum pixel distance measured outside the edge, resulting in an alpha value of 0.
		/// If set to or below 0, everything outside will have an alpha value of 0.
		/// </param>
		/// <param name="postProcessDistance">
		/// Pixel distance from the edge within which pixels will be post-processed using the edge gradient.
		/// </param>
		/// <param name="rgbMode">
		/// How to fill the destination texture's RGB channels.
		/// </param>
		public static void Generate (
			Texture2D sourceTex,
			Texture2D destinationTex,
			float maxInside,
			float maxOutside,
			float postProcessDistance,
			RGBFillMode rgbMode) {

			if(sourceTex.height != destinationTex.height || sourceTex.width != destinationTex.width){
				Debug.LogError("Source and destination textures must be the same size.");
				return;
			}

			int width = sourceTex.width;
			int height = sourceTex.height;
			PointerArray2D<Pixel> pixels = new PointerArray2D<Pixel>(width, height, out NativeArray<Pixel> pixelNativeArray);

			if(sourceTex.format != TextureFormat.RGBAFloat || destinationTex.format != TextureFormat.RGBAFloat){
				GeneratePartiallyWithBurst(
					sourceTex, destinationTex, ref pixels,
					maxInside, maxOutside, postProcessDistance, rgbMode);
			}
			else {
				NativeArray<Color> sourceNative = sourceTex.GetRawTextureData<Color>();
				NativeArray<Color> destinationNative = destinationTex.GetRawTextureData<Color>();
				PointerArray2D<Color> sourcePA, destinationPA;
				
				unsafe {
					sourcePA =
						new PointerArray2D<Color>((Color*)sourceNative.GetUnsafePtr(), width, height);
					destinationPA =
						new PointerArray2D<Color>((Color*)destinationNative.GetUnsafePtr(), width, height);
				}

				GenerateFullyWithBurst(
					ref sourcePA, ref destinationPA, ref pixels,
					maxInside, maxOutside, postProcessDistance, rgbMode);
			}

			pixelNativeArray.Dispose();
		}

		static void GeneratePartiallyWithBurst (
			Texture2D sourceTex,
			Texture2D destinationTex,
			ref PointerArray2D<Pixel> pixels,
			float maxInside,
			float maxOutside,
			float postProcessDistance,
			RGBFillMode rgbMode) {

			int width = sourceTex.width;
			int height = sourceTex.height;
			Color[] source = sourceTex.GetPixels();
			Color[] destination = destinationTex.GetPixels();
			int x, y;
			float scale;
			Color c = rgbMode == RGBFillMode.White ? Color.white : Color.black;
			for(y = 0; y < height; y++){
				for(x = 0; x < width; x++){
					pixels[x, y] = new Pixel();
				}
			}
			if(maxInside > 0f){
				for(y = 0; y < height; y++){
					for(x = 0; x < width; x++){
						Pixel p = pixels[x, y];
						p.alpha = 1f - source[y * width + x].a;
						pixels[x, y] = p;
					}
				}
				ComputeEdgeGradients(ref pixels);
				GenerateDistanceTransform(ref pixels);
				if(postProcessDistance > 0f){
					PostProcess(ref pixels, postProcessDistance);
				}
				scale = 1f / maxInside;
				for(y = 0; y < height; y++){
					for(x = 0; x < width; x++){
						c.a = Mathf.Clamp01(pixels[x, y].distance * scale);
						destination[y * width + x] = c;
					}
				}
			}
			if(maxOutside > 0f){
				for(y = 0; y < height; y++){
					for(x = 0; x < width; x++){
						Pixel p = pixels[x, y];
						p.alpha = source[y * width + x].a;
						pixels[x, y] = p;
					}
				}
				ComputeEdgeGradients(ref pixels);
				GenerateDistanceTransform(ref pixels);
				if(postProcessDistance > 0f){
					PostProcess(ref pixels, postProcessDistance);
				}
				scale = 1f / maxOutside;
				if(maxInside > 0f){
					for(y = 0; y < height; y++){
						for(x = 0; x < width; x++){
							c.a = 0.5f + (destination[y * width + x].a -
								Mathf.Clamp01(pixels[x, y].distance * scale)) * 0.5f;
							destination[y * width + x] = c;
						}
					}
				}
				else{
					for(y = 0; y < height; y++){
						for(x = 0; x < width; x++){
							c.a = Mathf.Clamp01(1f - pixels[x, y].distance * scale);
							destination[y * width + x] = c;
						}
					}
				}
			}
			
			if(rgbMode == RGBFillMode.Distance){
				for(y = 0; y < height; y++){
					for(x = 0; x < width; x++){
						c = destination[y * width + x];
						c.r = c.a;
						c.g = c.a;
						c.b = c.a;
						destination[y * width + x] = c;
					}
				}
			}
			else if(rgbMode == RGBFillMode.Source){
				for(y = 0; y < height; y++){
					for(x = 0; x < width; x++){
						c = source[y * width + x];
						c.a = destination[y * width + x].a;
						destination[y * width + x] = c;
					}
				}
			}

			destinationTex.SetPixels(destination);
		}

		[BurstCompile]
		static void GenerateFullyWithBurst (
			ref PointerArray2D<Color> source,
			ref PointerArray2D<Color> destination,
			ref PointerArray2D<Pixel> pixels,
			float maxInside,
			float maxOutside,
			float postProcessDistance,
			RGBFillMode rgbMode) {

			int width = source.Width;
			int height = source.Height;
			int x, y;
			float scale;
			Color c = rgbMode == RGBFillMode.White ? Color.white : Color.black;
			for(y = 0; y < height; y++){
				for(x = 0; x < width; x++){
					pixels[x, y] = new Pixel();
				}
			}
			if(maxInside > 0f){
				for(y = 0; y < height; y++){
					for(x = 0; x < width; x++){
						Pixel p = pixels[x, y];
						p.alpha = 1f - source[x, y].a;
						pixels[x, y] = p;
					}
				}
				ComputeEdgeGradients(ref pixels);
				GenerateDistanceTransform(ref pixels);
				if(postProcessDistance > 0f){
					PostProcess(ref pixels, postProcessDistance);
				}
				scale = 1f / maxInside;
				for(y = 0; y < height; y++){
					for(x = 0; x < width; x++){
						c.a = Mathf.Clamp01(pixels[x, y].distance * scale);
						destination[x, y] = c;
					}
				}
			}
			if(maxOutside > 0f){
				for(y = 0; y < height; y++){
					for(x = 0; x < width; x++){
						Pixel p = pixels[x, y];
						p.alpha = source[x, y].a;
						pixels[x, y] = p;
					}
				}
				ComputeEdgeGradients(ref pixels);
				GenerateDistanceTransform(ref pixels);
				if(postProcessDistance > 0f){
					PostProcess(ref pixels, postProcessDistance);
				}
				scale = 1f / maxOutside;
				if(maxInside > 0f){
					for(y = 0; y < height; y++){
						for(x = 0; x < width; x++){
							c.a = 0.5f + (destination[x, y].a -
								Mathf.Clamp01(pixels[x, y].distance * scale)) * 0.5f;
							destination[x, y] = c;
						}
					}
				}
				else{
					for(y = 0; y < height; y++){
						for(x = 0; x < width; x++){
							c.a = Mathf.Clamp01(1f - pixels[x, y].distance * scale);
							destination[x, y] = c;
						}
					}
				}
			}
			
			if(rgbMode == RGBFillMode.Distance){
				for(y = 0; y < height; y++){
					for(x = 0; x < width; x++){
						c = destination[x, y];
						c.r = c.a;
						c.g = c.a;
						c.b = c.a;
						destination[x, y] = c;
					}
				}
			}
			else if(rgbMode == RGBFillMode.Source){
				for(y = 0; y < height; y++){
					for(x = 0; x < width; x++){
						c = source[x, y];
						c.a = destination[x, y].a;
						destination[x, y] = c;
					}
				}
			}
		}
		
		[BurstCompile]
		private static void ComputeEdgeGradients (ref PointerArray2D<Pixel> pixels) {
			int width = pixels.Width;
			int height = pixels.Height;
			float sqrt2 = Mathf.Sqrt(2f);
			for(int y = 1; y < height - 1; y++){ 
				for(int x = 1; x < width - 1; x++){
					Pixel p = pixels[x, y];
					if(p.alpha > 0f && p.alpha < 1f){
						// estimate gradient of edge pixel using surrounding pixels
						float g =
							- pixels[x - 1, y - 1].alpha
							- pixels[x - 1, y + 1].alpha
							+ pixels[x + 1, y - 1].alpha
							+ pixels[x + 1, y + 1].alpha;
						p.gradient = new Vector2(
							g + (pixels[x + 1, y].alpha - pixels[x - 1, y].alpha) * sqrt2,
							g + (pixels[x, y + 1].alpha - pixels[x, y - 1].alpha) * sqrt2
						).normalized;
						pixels[x, y] = p;
					}
				}
			}
		}
		
		private static float ApproximateEdgeDelta (float gx, float gy, float a) {
			// (gx, gy) can be either the local pixel gradient or the direction to the pixel
			
			if(gx == 0f || gy == 0f){
				// linear function is correct if both gx and gy are zero
				// and still fair if only one of them is zero
				return 0.5f - a;
			}
			
			// normalize (gx, gy)
			float length = Mathf.Sqrt(gx * gx + gy * gy);
			gx = gx / length;
			gy = gy / length;
			
			// reduce symmetrical equation to first octant only
			// gx >= 0, gy >= 0, gx >= gy
			gx = Mathf.Abs(gx);
			gy = Mathf.Abs(gy);
			if(gx < gy){
				float temp = gx;
				gx = gy;
				gy = temp;
			}
			
			// compute delta
			float a1 = 0.5f * gy / gx;
			if(a < a1){
				// 0 <= a < a1
				return 0.5f * (gx + gy) - Mathf.Sqrt(2f * gx * gy * a);
			}
			if(a < (1f - a1)){
				// a1 <= a <= 1 - a1
				return (0.5f - a) * gx;
			}
			// 1-a1 < a <= 1
			return -0.5f * (gx + gy) + Mathf.Sqrt(2f * gx * gy * (1f - a));
		}
		
		private static void UpdateDistance (ref PointerArray2D<Pixel> pixels, int x, int y, int oX, int oY) {
			Pixel p = pixels[x, y];
			Pixel neighbor = pixels[x + oX, y + oY];
			int closestX = x + oX - neighbor.dX;
			int closestY = y + oY - neighbor.dY;
			Pixel closest = pixels[closestX, closestY];
			
			if(closest.alpha == 0f || (x == closestX && y == closestY)){
				// neighbor has no closest yet
				// or neighbor's closest is p itself
				return;
			}
			
			int dX = neighbor.dX - oX;
			int dY = neighbor.dY - oY;
			float distance = Mathf.Sqrt(dX * dX + dY * dY) + ApproximateEdgeDelta(dX, dY, closest.alpha);
			if(distance < p.distance){
				p.distance = distance;
				p.dX = dX;
				p.dY = dY;
				pixels[x, y] = p;
			}
		}
		
		[BurstCompile]
		private static void GenerateDistanceTransform (ref PointerArray2D<Pixel> pixels) {
			int width = pixels.Width;
			int height = pixels.Height;
			// perform anti-aliased Euclidean distance transform
			int x, y;
			Pixel p;
			
			// initialize distances
			for(y = 0; y < height; y++){ 
				for(x = 0; x < width; x++){
					p = pixels[x, y];
					p.dX = 0;
					p.dY = 0;
					if(p.alpha <= 0f){
						// outside
						p.distance = 1000000f;
					}
					else if (p.alpha < 1f){
						// on the edge
						p.distance = ApproximateEdgeDelta(p.gradient.x, p.gradient.y, p.alpha);
					}
					else{
						// inside
						p.distance = 0f;
					}
					pixels[x, y] = p;
				}
			}
			// perform 8SSED (eight-points signed sequential Euclidean distance transform)
			// scan up
			for(y = 1; y < height; y++){
				// |P.
				// |XX
				p = pixels[0, y];
				if(p.distance > 0f){
					UpdateDistance(ref pixels, 0, y, 0, -1);
					UpdateDistance(ref pixels, 0, y, 1, -1);
				}
				// -->
				// XP.
				// XXX
				for(x = 1; x < width - 1; x++){
					p = pixels[x, y];
					if(p.distance > 0f){
						UpdateDistance(ref pixels, x, y, -1, 0);
						UpdateDistance(ref pixels, x, y, -1, -1);
						UpdateDistance(ref pixels, x, y, 0, -1);
						UpdateDistance(ref pixels, x, y, 1, -1);
					}
				}
				// XP|
				// XX|
				p = pixels[width - 1, y];
				if(p.distance > 0f){
					UpdateDistance(ref pixels, width - 1, y, -1, 0);
					UpdateDistance(ref pixels, width - 1, y, -1, -1);
					UpdateDistance(ref pixels, width - 1, y, 0, -1);
				}
				// <--
				// .PX
				for(x = width - 2; x >= 0; x--){
					p = pixels[x, y];
					if(p.distance > 0f){
						UpdateDistance(ref pixels, x, y, 1, 0);
					}
				}			
			}
			// scan down
			for(y = height - 2; y >= 0; y--){
				// XX|
				// .P|
				p = pixels[width - 1, y];
				if(p.distance > 0f){
					UpdateDistance(ref pixels, width - 1, y, 0, 1);
					UpdateDistance(ref pixels, width - 1, y, -1, 1);
				}
				// <--
				// XXX
				// .PX
				for(x = width - 2; x > 0; x--){
					p = pixels[x, y];
					if(p.distance > 0f){
						UpdateDistance(ref pixels, x, y, 1, 0);
						UpdateDistance(ref pixels, x, y, 1, 1);
						UpdateDistance(ref pixels, x, y, 0, 1);
						UpdateDistance(ref pixels, x, y, -1, 1);
					}
				}
				// |XX
				// |PX
				p = pixels[0, y];
				if(p.distance > 0f){
					UpdateDistance(ref pixels, 0, y, 1, 0);
					UpdateDistance(ref pixels, 0, y, 1, 1);
					UpdateDistance(ref pixels, 0, y, 0, 1);
				}
				// -->
				// XP.
				for(x = 1; x < width; x++){
					p = pixels[x, y];
					if(p.distance > 0f){
						UpdateDistance(ref pixels, x, y, -1, 0);
					}
				}
			}
		}
		
		[BurstCompile]
		private static void PostProcess (ref PointerArray2D<Pixel> pixels, float maxDistance) {
			int width = pixels.Width;
			int height = pixels.Height;
			// adjust distances near edges based on the local edge gradient
			for(int y = 0; y < height; y++){
				for(int x = 0; x < width; x++){
					Pixel p = pixels[x, y];
					if((p.dX == 0 && p.dY == 0) || p.distance >= maxDistance){
						// ignore edge, inside, and beyond max distance
						continue;
					}
					float
						dX = p.dX,
						dY = p.dY;
					Pixel closest = pixels[x - p.dX, y - p.dY];
					Vector2 g = closest.gradient;
					
					if(g.x == 0f && g.y == 0f){
						// ignore unknown gradients (inside)
						continue;
					}
					
					// compute hit point offset on gradient inside pixel
					float df = ApproximateEdgeDelta(g.x, g.y, closest.alpha);
					float t = dY * g.x - dX * g.y;
					float u = -df * g.x + t * g.y;
					float v = -df * g.y - t * g.x;
					
					// use hit point to compute distance
					if(Mathf.Abs(u) <= 0.5f && Mathf.Abs(v) <= 0.5f){
						p.distance = Mathf.Sqrt((dX + u) * (dX + u) + (dY + v) * (dY + v));
						pixels[x, y] = p;
					}
				}
			}
		}
	}
}

PointerArray.cs

/*
 * Copyright (c) 2024 Rune Skovbo Johansen
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */

using Unity.Burst;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;

// Unity NativeArrays can't be used directly in Unity Burst methods (only in Burst jobs),
// so we have to pass pointers to arrays instead.
// 
// This PointerArray wrapper can be created from a NativeArray via simple implicit assignment:
// 
// NativeArray<float> floatNativeArray = new NativeArray<float>(1000, Allocator.Persistent);
// PointerArray<float> floatPointerArray = floatNativeArray;
// 
// The PointerArray can then be used like an array itself, including getting the Length.
[NoAlias]
public unsafe struct PointerArray<T> where T : unmanaged {
	[NoAlias]
	public readonly T* Array;
	public readonly int Length;

	public T this[uint index] {
		get { return Array[index]; }
		set { Array[index] = value; }
	}

	public T this[int index] {
		get { return Array[index]; }
		set { Array[index] = value; }
	}

	public PointerArray(T* pointer, int length) {
		Array = pointer;
		Length = length;
	}

	public PointerArray(T* pointer, T[] source) {
		Array = pointer;
		Length = source.Length;
	}

	public PointerArray(int length, out NativeArray<T> outputNativeArray) {
		Length = length;
		outputNativeArray = new NativeArray<T>(Length, Allocator.Persistent);
		Array = (T*)outputNativeArray.GetUnsafePtr();
	}

	public static implicit operator PointerArray<T>(NativeArray<T> a) {
		return new PointerArray<T>((T*)a.GetUnsafePtr(), a.Length);
	}

	public void Clear() {
		UnsafeUtility.MemClear(Array, Length * UnsafeUtility.SizeOf<T>());
	}
}

[NoAlias]
public unsafe struct PointerArray2D<T> where T : unmanaged {
	[NoAlias]
	public readonly T* Array;
	public readonly int Width;
	public readonly int Height;
	public readonly int Length; // Width * Height

	public T this[uint index] {
		get { return Array[index]; }
		set { Array[index] = value; }
	}

	public T this[int index] {
		get { return Array[index]; }
		set { Array[index] = value; }
	}

	public T this[uint y, uint x] {
		get { return Array[y * Width + x]; }
		set { Array[y * Width + x] = value; }
	}

	public T this[int y, int x] {
		get { return Array[y * Width + x]; }
		set { Array[y * Width + x] = value; }
	}

	public PointerArray2D(T* pointer, int height, int width) {
		Array = pointer;
		Height = height;
		Width = width;
		Length = Width * Height;
	}

	public PointerArray2D(T* pointer, T[,] source) {
		Array = pointer;
		Height = source.GetLength(0);
		Width = source.GetLength(1);
		Length = Width * Height;
	}

	public PointerArray2D(int height, int width, out NativeArray<T> outputNativeArray) {
		Height = height;
		Width = width;
		Length = Width * Height;
		outputNativeArray = new NativeArray<T>(Length, Allocator.Persistent);
		Array = (T*)outputNativeArray.GetUnsafePtr();
	}

	public void Clear() {
		UnsafeUtility.MemClear(Array, Length * UnsafeUtility.SizeOf<T>());
	}
}

[NoAlias]
public unsafe struct PointerArray3D<T> where T : unmanaged {
	[NoAlias]
	public readonly T* Array;
	public readonly int Width;
	public readonly int Height;
	public readonly int Depth;
	public readonly int Length; // Width * Height * Depth

	public T this[uint index] {
		get { return Array[index]; }
		set { Array[index] = value; }
	}

	public T this[int index] {
		get { return Array[index]; }
		set { Array[index] = value; }
	}

	public T this[uint z, uint y, uint x] {
		get { return Array[z * Width * Height + y * Width + x]; }
		set { Array[z * Width * Height + y * Width + x] = value; }
	}

	public T this[int z, int y, int x] {
		get { return Array[z * Width * Height + y * Width + x]; }
		set { Array[z * Width * Height + y * Width + x] = value; }
	}

	public PointerArray3D(T* pointer, int depth, int height, int width) {
		Array = pointer;
		Width = width;
		Height = height;
		Depth = depth;
		Length = Width * Height * Depth;
	}

	public PointerArray3D(T* pointer, T[,,] source) {
		Array = pointer;
		Depth = source.GetLength(0);
		Height = source.GetLength(1);
		Width = source.GetLength(2);
		Length = Width * Height * Depth;
	}

	public PointerArray3D(int depth, int height, int width, out NativeArray<T> outputNativeArray) {
		Depth = depth;
		Height = height;
		Width = width;
		Length = Width * Height * Depth;
		outputNativeArray = new NativeArray<T>(Length, Allocator.Persistent);
		Array = (T*)outputNativeArray.GetUnsafePtr();
	}

	public void Clear() {
		UnsafeUtility.MemClear(Array, Length * UnsafeUtility.SizeOf<T>());
	}
}