Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Signed Distance Field in Metal/Swift
public class FontAtlas: NSObject, NSSecureCoding {
public static var supportsSecureCoding: Bool { get { return true } }
static let atlasSize: Int = 2048 // 4096 runs out of mem...
var glyphs : [GlyphDescriptor] = []
let parentFont: UIFont
var fontPointSize: CGFloat
let textureSize: Int
var textureData: [UInt8] = []
/// Compute signed-distance field for an 8-bpp grayscale image (values greater than 127 are considered "on")
/// For details of this algorithm, see "The 'dead reckoning' signed distance transform" [Grevera 2004]
private func createSignedDistanceFieldForGrayscaleImage(imageData: UnsafeMutablePointer<UInt8>, width: Int, height: Int) -> [Float] {
let maxDist = hypot(Float(width), Float(height))
// Initialization phase
// distance to nearest boundary point map - set all distances to "infinity"
var distanceMap = [Float](repeating: maxDist, count: width * height)
// nearest boundary point map - zero out nearest boundary point map
var boundaryPointMap = [int2](repeating: int2(0,0), count: width * height)
let distUnit :Float = 1
let distDiag :Float = sqrtf(2)
// Immediate interior/exterior phase: mark all points along the boundary as such
for y in 1..<(height-1) {
for x in 1..<(width-1) {
let inside = imageData[y * width + x] > 0x7f
if (imageData[y * width + x - 1] > 0x7f) != inside
|| (imageData[y * width + x + 1] > 0x7f) != inside
|| (imageData[(y - 1) * width + x] > 0x7f) != inside
|| (imageData[(y + 1) * width + x] > 0x7f) != inside {
distanceMap[y * width + x] = 0
boundaryPointMap[y * width + x].x = Int32(x)
boundaryPointMap[y * width + x].y = Int32(y)
}
}
}
// Forward dead-reckoning pass
for y in 1..<(height-2) {
for x in 1..<(width-2) {
let d = distanceMap[y * width + x]
let n = boundaryPointMap[y * width + x]
let h = hypot(Float(x) - Float(n.x), Float(y) - Float(n.y))
if distanceMap[(y - 1) * width + x - 1] + distDiag < d {
boundaryPointMap[y * width + x] = boundaryPointMap[(y - 1) * width + (x - 1)]
distanceMap[y * width + x] = h
}
if distanceMap[(y - 1) * width + x] + distUnit < d {
boundaryPointMap[y * width + x] = boundaryPointMap[(y - 1) * width + x]
distanceMap[y * width + x] = h
}
if distanceMap[(y - 1) * width + x + 1] + distDiag < d {
boundaryPointMap[y * width + x] = boundaryPointMap[(y - 1) * width + (x + 1)]
distanceMap[y * width + x] = h
}
if distanceMap[y * width + x - 1] + distUnit < d {
boundaryPointMap[y * width + x] = boundaryPointMap[y * width + (x - 1)]
distanceMap[y * width + x] = h
}
}
}
// Backward dead-reckoning pass
for y in (1...(height-2)).reversed() {
for x in (1...(width-2)).reversed() {
let d = distanceMap[y * width + x]
let n = boundaryPointMap[y * width + x]
let h = hypot(Float(x) - Float(n.x), Float(y) - Float(n.y))
if distanceMap[y * width + x + 1] + distUnit < d {
boundaryPointMap[y * width + x] = boundaryPointMap[y * width + x + 1]
distanceMap[y * width + x] = h
}
if distanceMap[(y + 1) * width + x - 1] + distDiag < d {
boundaryPointMap[y * width + x] = boundaryPointMap[(y + 1) * width + x - 1]
distanceMap[y * width + x] = h
}
if distanceMap[(y + 1) * width + x] + distUnit < d {
boundaryPointMap[y * width + x] = boundaryPointMap[(y + 1) * width + x]
distanceMap[y * width + x] = h
}
if distanceMap[(y + 1) * width + x + 1] + distDiag < d {
boundaryPointMap[y * width + x] = boundaryPointMap[(y + 1) * width + x + 1]
distanceMap[y * width + x] = h
}
}
}
// Interior distance negation pass; distances outside the figure are considered negative
for y in 0..<height {
for x in 0..<width {
if imageData[y * width + x] <= 0x7f {
distanceMap[y * width + x] = -distanceMap[y * width + x]
}
}
}
return distanceMap
}
// ...
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment