Signed Distance Field from Bezier curves

01_prototype.jl

function bezier(points::Vector{T}, N = 100) where {T <: Point}
    out = zeros(T, N)
    r = range(0, 1, length = N)
    n = length(points)

    for i in 1:n
        p = binomial(n-1, i-1) * points[i]
        for j in 1:N
            t = r[j]
            out[j] += (1-t)^(n-i) * t^(i-1) * p
        end
    end

    return out
end

function deriv_bezier(points::Vector{T}, N = 100) where {T <: Point}
    out = zeros(T, N)
    r = range(0, 1, length = N)
    n = length(points)

    for (i, t) in enumerate(r)
        out[i]   = -(n-1) * (1-t)^(n-2) * points[1]
        out[i] =  (n-1) *    t^(n-2)  * points[end]
    end

    for i in 2:n-1
        p = binomial(n-1, i-1) * points[i]
        t = r[i]
        for j in 1:N
            t = r[j]
            out[j] += ((i-1) * t^(i-2) * (1-t)^(n-i) - t^(i-1) * (n-i) * (1-t)^(n-i-1)) * p
        end
    end

    return out
end

norm2(p::Point2) = p[1] * p[1] + p[2] * p[2]
function bezier_distance(ref::T, points::Vector{T}, N = 100) where {T <: Point}
    if length(points) == 2 # line
        dir = points[2] - points[1]
        t = dot(ref - points[1], dir) / norm2(dir)
        P = points[1] + dir * clamp(t, 0, 1)
        dist = P - ref
        # dot(cross(dir, [0,0,1]), P - ref)
        _sign = sign(dir[2] * dist[1] - dir[1] * dist[2])
        return _sign * norm(dist)

    # elseif length(points) == 3
        # https://blog.gludion.com/2009/08/distance-to-quadratic-bezier-curve.html

    else
        # calculate distances at sample points
        distances = fill(-ref, N)
        r = range(0, 1, length = N)
        n = length(points)

        for i in 1:n
            p = binomial(n-1, i-1) * points[i]
            for j in 1:N
                t = r[j]
                distances[j] += (1-t)^(n-i) * t^(i-1) * p
            end
        end

        # get minimum of those
        idx = 1
        dist2 = Inf
        for i in eachindex(distances)
            d2 = dot(distances[i], distances[i])
            if d2 < dist2
                dist2 = d2
                idx = i
            end
        end

        # TODO
        # use Newton method to get better estimate of point
        # i.e. minimize norm2(P - ref) where P is a bezier point around r[idx]

        # calculate derivative at minimum distance
        t = r[idx]
        deriv = -(n-1) * (1-t)^(n-2) * points[1] + (n-1) * t^(n-2) * points[end]
        for i in 2:n-1
            p = binomial(n-1, i-1) * points[i]
            deriv += ((i-1) * t^(i-2) * (1-t)^(n-i) - t^(i-1) * (n-i) * (1-t)^(n-i-1)) * p
        end

        # dot(cross(derivative, [0,0,1]), closest_point - ref)
        _sign = sign(deriv[2] * distances[idx][1] - deriv[1] * distances[idx][2])
        return _sign * sqrt(dist2)
    end
end

function merge_sdf_pixels(a, b)
    if (a < 0) && (b < 0) # inside of both
        return max(a, b)
    elseif a <= 0 # outisde of b
        return b
    elseif b <= 0 # outside of a
        return a
    else # outside of both
        return min(a, b)
    end
end


begin
    # Bezier 1
    points = Point2f[(0,0), (-0.2, 1), (1, 1),  (1.5, 0), (2, 0.8)]
    ps = closed_bezier(points)

    # Bezier 2
    points2 = Point2f[(2, 0.8), (1, -1), (0,0)]
    ps2 = closed_bezier(points2)
    
    dists = zeros(51, 51)
    xrange = range(-1, 3, length=size(dists, 1))
    yrange = range(-1, 2, length=size(dists, 1))
    for (i, x) in enumerate(xrange)
        for (j, y) in enumerate(yrange)
            dists[i, j] = merge_sdf_pixels(
                bezier_distance(Point2f(x, y), points),
                bezier_distance(Point2f(x, y), points2),
            )
        end
    end

    fig = Figure()
    sl = Slider(fig[1, 1:2], range=range(minimum(dists), maximum(dists), length=100))
    ax = Axis(fig[2, 1])
    ax2 = Axis(fig[2, 2])

    heatmap!(ax, -1..3, -1..2, dists, colorrange=(-3, 3), colormap = (:red, :white, :blue))
    lines!(ax, ps, color = :black)
    scatter!(ax, points, color = :black)

    # derivs = deriv_bezier(points)
    # dirs = [p + 0.1 * b*v for (p, v) in zip(ps, derivs) for b in 0:1]
    # linesegments!(ax, dirs)

    lines!(ax, ps2, color = :white)
    scatter!(ax, points2, color = :white)

    # Signed Distance Field picking
    heatmap!(ax2, -1..3, -1..2, map(v -> dists .> v, sl.value), colormap = (:white, :black))

    fig
end

02_char_hack.jl

function insert_SDF!(c::Char, sdf::Matrix)
    atlas = Makie.get_texture_atlas()
    fontname = Makie.FreeTypeAbstraction.fontname(Makie.defaultfont())
    tex_size = Vec2f(size(atlas.data) .- 1) # starts at 1

    if haskey(atlas.mapping, (c, fontname))
        idx = atlas.mapping[(c, fontname)]
        uv = atlas.uv_rectangles[idx]
        l, b = round.(Int, tex_size .* uv[Vec(1, 2)]) .+ 1
        r, t = round.(Int, tex_size .* uv[Vec(3, 4)]) .+ 1

        if atlas.data[l:r, b:t] == sdf
            @info "Glyph matches existing glyph"
            return
        elseif size(sdf) == (r-l+1, t-b+1)
            @info "Glyph replaces existing glyph"
            atlas.data[l:r, b:t] .= sdf
            return
        end
    end
    
    # from render
    rect = Rect2(0, 0, size(sdf)...)
    uv = push!(atlas.rectangle_packer, rect) # find out where to place the rectangle
    uv == nothing && error("texture atlas is too small. Resizing not implemented yet. Please file an issue at Makie if you encounter this") #TODO resize surface
    # write distancefield into texture
    atlas.data[uv.area] = sdf
    for f in get(Makie.font_render_callbacks, 64, ())
        # update everyone who uses the atlas image directly (e.g. in GLMakie)
        f(sdf, uv.area)
    end

    # from insert_glyph!
    # 0 based
    idx_left_bottom = minimum(uv.area)
    idx_right_top = maximum(uv.area)
        
    # transform to normalized texture coordinates
    # -1 for indexing offset
    uv_left_bottom_pad = (idx_left_bottom) ./ tex_size
    uv_right_top_pad = (idx_right_top .- 1) ./ tex_size

    uv_offset_rect = Vec4f(uv_left_bottom_pad..., uv_right_top_pad...)
    i = atlas.index
    push!(atlas.uv_rectangles, uv_offset_rect)
    atlas.index = i + 1
    atlas.mapping[(c, "dejavu sans book")] = i
    
    return
end

begin
    # Bezier 1
    points = Point2f[(0,0), (-0.2, 1), (1, 1),  (1.5, 0), (2, 0.8)]
    ps = closed_bezier(points)

    # Bezier 2
    points2 = Point2f[(2, 0.8), (1, -1), (0,0)]
    ps2 = closed_bezier(points2)

    dists = zeros(51, 51)
    xrange = range(-1, 3, length=size(dists, 1))
    yrange = range(-1, 2, length=size(dists, 1))
    for (i, x) in enumerate(xrange)
        for (j, y) in enumerate(yrange)
            dists[i, j] = 8 * merge_sdf_pixels(
                bezier_distance(Point2f(x, y), points),
                bezier_distance(Point2f(x, y), points2),
            )
        end
    end

    # hack in sdf
    c = Char(999_999)
    insert_SDF!(c, dists)
    
    fig = Figure()
    sl = Slider(fig[1, 1:2], range=range(minimum(dists), maximum(dists), length=100))
    ax = Axis(fig[2, 1])
    ax2 = Axis(fig[2, 2])

    colorrange = let 
        a, b = extrema(dists)
        x = max(abs(a), abs(b))
        (-x, x)
    end
    heatmap!(ax, -1..3, -1..2, dists, colorrange=colorrange, colormap = (:red, :white, :blue))
    lines!(ax, ps, color = :black)
    scatter!(ax, points, color = :black)

    # derivs = deriv_bezier(points)
    # dirs = [p + 0.1 * b*v for (p, v) in zip(ps, derivs) for b in 0:1]
    # linesegments!(ax, dirs)

    lines!(ax, ps2, color = :white)
    scatter!(ax, points2, color = :white)

    # Signed Distance Field picking
    # heatmap!(ax2, -1..3, -1..2, map(v -> dists .> v, sl.value), colormap = (:white, :black))
    scatter!(ax2, rand(10), marker = c, markersize = 100)

    fig
end

03_ring.jl

begin
    # star doesn't work like this
    # points = [Point2f(cos(-2i * pi/5), sin(-2i * pi/5)) for i in 1:5]
    # nodes = [[points[mod1(2i, 5)], points[mod1(2i+2, 5)]] for i in 1:5]

    # circle
    nodes = [
        Point2f[(-1, 0), (-1, 1), (1, 1), (1, 0)],
        Point2f[(1, 0), (1, -1), (-1, -1), (-1, 0)],
        0.5f0 * Point2f[(1, 0), (1, 1), (-1, 1), (-1, 0)],
        0.5f0 * Point2f[(-1, 0), (-1, -1), (1, -1), (1, 0)],
    ]
    
    dists = zeros(51, 51)
    xrange = range(-2, 2, length=size(dists, 1))
    yrange = range(-2, 2, length=size(dists, 1))
    for (i, x) in enumerate(xrange)
        for (j, y) in enumerate(yrange)
            p = Point2f(x, y)
            # d = bezier_distance(p, nodes[1])
            # for k in 2:length(nodes)
            #     temp = bezier_distance(p, nodes[k])
            #     d = merge_sdf_pixels(d, temp)
            # end
            d1 = merge_sdf_pixels(
                bezier_distance(p, nodes[1]),
                bezier_distance(p, nodes[2])
            )
            d2 = merge_sdf_pixels(
                -bezier_distance(p, nodes[3]),
                -bezier_distance(p, nodes[4])
            )
            dists[i, j] = merge_sdf_pixels(d1, -d2)
        end
    end

    fig = Figure()
    sl = Slider(fig[1, 1:2], range=range(minimum(dists), maximum(dists), length=100))
    ax = Axis(fig[2, 1], aspect = DataAspect())
    ax2 = Axis(fig[2, 2], aspect = DataAspect())

    heatmap!(ax, -2..2, -2..2, dists, colorrange=(-3, 3), colormap = (:red, :white, :blue))
    for n in nodes
        lines!(ax, closed_bezier(n))
        scatter!(ax, n, color = :orange)
        # scatter!(ax, n, marker = "12345", color = :orange, markersize = 20)
    end

    # Signed Distance Field picking
    heatmap!(ax2, -2..2, -2..2, map(v -> dists .> v, sl.value), colormap = (:white, :black))

    fig
end