Signed distance field calculation bug

Question

I am writing an small utility to compute signed distance field textures for a graphic application. I am doing true signed distance fields, not approximations, so I first transform each glyph path to an arc spline to speed up point-to-path distance computations. Problem is that I am getting strange artifacts on some corners:

Path is extracted from an EPS generated by FontForge without any manipulation. Distance is computed finding minimum distance from each pixel coordinates to any path line segment or arc (three nested loops: for (x;...) { for (y; ...) { for (i; ...) { ... }}}). Computed per-pixel distance is iterated to extract minimum and maximum values and rescaled to 0-255 range and written directly to a raw image file and coverted to PNG with ImageMagick.

The only source of this bug I can think is a numerical error inside the function used to compute point-to-segment distance. Here it is:

double dist_to_segment(double px, double py, /* query point */
                       double x0, double y0, /* first segment end-point */
                       double x1, double y1) /* second segment end-point */
{
  const double t0 = dist2(x0, y0, x1, y1);
  if (t0 == 0.0) { return dist2(px, py, x0, x1); }
  const double t1 = dot(px-x0, py-y0, x1-x0, y1-y0)/t0;
  const double t2 = clamp(t1, 0.0, 1.0);
  const double t3 = sqrt(dist2(px, py, lerp(x0,x1,t2), lerp(y0,y1,t2)));
  const double t4 = (x1-x0)*(py-y0) - (y1-y0)*(px-x0);
  return (t4 < 0.0)? -t3 : t3;
}

Where dot, clamp, lerp are defined as in OpenGL shading language and dist2 is defined as:

double dist2(double x0, double y0, double x1, double y1)
{
  return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);
}

If I replace return (t4 < 0.0)? -t3 : t3; with return t3; on dist_to_segment I get this unsigned distance field:

EDIT

I solved small triangle-shaped artifacts adding a point-in-polygon test to the already existing edge iterating loop, so extra cost is not to high. Sharp features along the bisectors of acute angles though. There is new sample image.

Answer 1

This is an extended comment, to show how to convert gray levels to contours using netpbm tools. From OP's last image, this yields

The following Bash script uses ppmchange to remap the exact color values to color bands separated by white:

#!/bin/bash
colormap=()
for ((i = 0; i < 256; i++)); do
    colormap+=( $(printf '#%02x%02x%02x' $i $i $i) )
    if (( (i & 15) < 6 )); then
        colormap+=( $(printf '#%02x00%02x' $[(i/16)*17] $[255-(i/16)*17]) )
    else
        colormap+=( "#ffffff" )
    fi
done
exec ppmchange -closeness 0 ${colormap[@]} "$@"

I like to call it gray-to-contour. If you want to specify the exact colors, you can use

#!/bin/sh
exec ppmchange -closeness 0 \
    '#000000' '#0000ff' \
    '#010101' '#0000ff' \
    '#020202' '#0000ff' \
    '#030303' '#0000ff' \
    '#040404' '#0000ff' \
    '#050505' '#0000ff' \
    '#060606' '#ffffff' \
    '#070707' '#ffffff' \
    '#080808' '#ffffff' \
    '#090909' '#ffffff' \
    '#0a0a0a' '#ffffff' \
    '#0b0b0b' '#ffffff' \
    '#0c0c0c' '#ffffff' \
    '#0d0d0d' '#ffffff' \
    '#0e0e0e' '#ffffff' \
    '#0f0f0f' '#ffffff' \
    '#101010' '#1100ee' \
    '#111111' '#1100ee' \
    '#121212' '#1100ee' \
    '#131313' '#1100ee' \
    '#141414' '#1100ee' \
    '#151515' '#1100ee' \
    '#161616' '#ffffff' \
    '#171717' '#ffffff' \
    '#181818' '#ffffff' \
    '#191919' '#ffffff' \
    '#1a1a1a' '#ffffff' \
    '#1b1b1b' '#ffffff' \
    '#1c1c1c' '#ffffff' \
    '#1d1d1d' '#ffffff' \
    '#1e1e1e' '#ffffff' \
    '#1f1f1f' '#ffffff' \
    '#202020' '#2200dd' \
    '#212121' '#2200dd' \
    '#222222' '#2200dd' \
    '#232323' '#2200dd' \
    '#242424' '#2200dd' \
    '#252525' '#2200dd' \
    '#262626' '#ffffff' \
    '#272727' '#ffffff' \
    '#282828' '#ffffff' \
    '#292929' '#ffffff' \
    '#2a2a2a' '#ffffff' \
    '#2b2b2b' '#ffffff' \
    '#2c2c2c' '#ffffff' \
    '#2d2d2d' '#ffffff' \
    '#2e2e2e' '#ffffff' \
    '#2f2f2f' '#ffffff' \
    '#303030' '#3300cc' \
    '#313131' '#3300cc' \
    '#323232' '#3300cc' \
    '#333333' '#3300cc' \
    '#343434' '#3300cc' \
    '#353535' '#3300cc' \
    '#363636' '#ffffff' \
    '#373737' '#ffffff' \
    '#383838' '#ffffff' \
    '#393939' '#ffffff' \
    '#3a3a3a' '#ffffff' \
    '#3b3b3b' '#ffffff' \
    '#3c3c3c' '#ffffff' \
    '#3d3d3d' '#ffffff' \
    '#3e3e3e' '#ffffff' \
    '#3f3f3f' '#ffffff' \
    '#404040' '#4400bb' \
    '#414141' '#4400bb' \
    '#424242' '#4400bb' \
    '#434343' '#4400bb' \
    '#444444' '#4400bb' \
    '#454545' '#4400bb' \
    '#464646' '#ffffff' \
    '#474747' '#ffffff' \
    '#484848' '#ffffff' \
    '#494949' '#ffffff' \
    '#4a4a4a' '#ffffff' \
    '#4b4b4b' '#ffffff' \
    '#4c4c4c' '#ffffff' \
    '#4d4d4d' '#ffffff' \
    '#4e4e4e' '#ffffff' \
    '#4f4f4f' '#ffffff' \
    '#505050' '#5500aa' \
    '#515151' '#5500aa' \
    '#525252' '#5500aa' \
    '#535353' '#5500aa' \
    '#545454' '#5500aa' \
    '#555555' '#5500aa' \
    '#565656' '#ffffff' \
    '#575757' '#ffffff' \
    '#585858' '#ffffff' \
    '#595959' '#ffffff' \
    '#5a5a5a' '#ffffff' \
    '#5b5b5b' '#ffffff' \
    '#5c5c5c' '#ffffff' \
    '#5d5d5d' '#ffffff' \
    '#5e5e5e' '#ffffff' \
    '#5f5f5f' '#ffffff' \
    '#606060' '#660099' \
    '#616161' '#660099' \
    '#626262' '#660099' \
    '#636363' '#660099' \
    '#646464' '#660099' \
    '#656565' '#660099' \
    '#666666' '#ffffff' \
    '#676767' '#ffffff' \
    '#686868' '#ffffff' \
    '#696969' '#ffffff' \
    '#6a6a6a' '#ffffff' \
    '#6b6b6b' '#ffffff' \
    '#6c6c6c' '#ffffff' \
    '#6d6d6d' '#ffffff' \
    '#6e6e6e' '#ffffff' \
    '#6f6f6f' '#ffffff' \
    '#707070' '#770088' \
    '#717171' '#770088' \
    '#727272' '#770088' \
    '#737373' '#770088' \
    '#747474' '#770088' \
    '#757575' '#770088' \
    '#767676' '#ffffff' \
    '#777777' '#ffffff' \
    '#787878' '#ffffff' \
    '#797979' '#ffffff' \
    '#7a7a7a' '#ffffff' \
    '#7b7b7b' '#ffffff' \
    '#7c7c7c' '#ffffff' \
    '#7d7d7d' '#ffffff' \
    '#7e7e7e' '#ffffff' \
    '#7f7f7f' '#ffffff' \
    '#808080' '#880077' \
    '#818181' '#880077' \
    '#828282' '#880077' \
    '#838383' '#880077' \
    '#848484' '#880077' \
    '#858585' '#880077' \
    '#868686' '#ffffff' \
    '#878787' '#ffffff' \
    '#888888' '#ffffff' \
    '#898989' '#ffffff' \
    '#8a8a8a' '#ffffff' \
    '#8b8b8b' '#ffffff' \
    '#8c8c8c' '#ffffff' \
    '#8d8d8d' '#ffffff' \
    '#8e8e8e' '#ffffff' \
    '#8f8f8f' '#ffffff' \
    '#909090' '#990066' \
    '#919191' '#990066' \
    '#929292' '#990066' \
    '#939393' '#990066' \
    '#949494' '#990066' \
    '#959595' '#990066' \
    '#969696' '#ffffff' \
    '#979797' '#ffffff' \
    '#989898' '#ffffff' \
    '#999999' '#ffffff' \
    '#9a9a9a' '#ffffff' \
    '#9b9b9b' '#ffffff' \
    '#9c9c9c' '#ffffff' \
    '#9d9d9d' '#ffffff' \
    '#9e9e9e' '#ffffff' \
    '#9f9f9f' '#ffffff' \
    '#a0a0a0' '#aa0055' \
    '#a1a1a1' '#aa0055' \
    '#a2a2a2' '#aa0055' \
    '#a3a3a3' '#aa0055' \
    '#a4a4a4' '#aa0055' \
    '#a5a5a5' '#aa0055' \
    '#a6a6a6' '#ffffff' \
    '#a7a7a7' '#ffffff' \
    '#a8a8a8' '#ffffff' \
    '#a9a9a9' '#ffffff' \
    '#aaaaaa' '#ffffff' \
    '#ababab' '#ffffff' \
    '#acacac' '#ffffff' \
    '#adadad' '#ffffff' \
    '#aeaeae' '#ffffff' \
    '#afafaf' '#ffffff' \
    '#b0b0b0' '#bb0044' \
    '#b1b1b1' '#bb0044' \
    '#b2b2b2' '#bb0044' \
    '#b3b3b3' '#bb0044' \
    '#b4b4b4' '#bb0044' \
    '#b5b5b5' '#bb0044' \
    '#b6b6b6' '#ffffff' \
    '#b7b7b7' '#ffffff' \
    '#b8b8b8' '#ffffff' \
    '#b9b9b9' '#ffffff' \
    '#bababa' '#ffffff' \
    '#bbbbbb' '#ffffff' \
    '#bcbcbc' '#ffffff' \
    '#bdbdbd' '#ffffff' \
    '#bebebe' '#ffffff' \
    '#bfbfbf' '#ffffff' \
    '#c0c0c0' '#cc0033' \
    '#c1c1c1' '#cc0033' \
    '#c2c2c2' '#cc0033' \
    '#c3c3c3' '#cc0033' \
    '#c4c4c4' '#cc0033' \
    '#c5c5c5' '#cc0033' \
    '#c6c6c6' '#ffffff' \
    '#c7c7c7' '#ffffff' \
    '#c8c8c8' '#ffffff' \
    '#c9c9c9' '#ffffff' \
    '#cacaca' '#ffffff' \
    '#cbcbcb' '#ffffff' \
    '#cccccc' '#ffffff' \
    '#cdcdcd' '#ffffff' \
    '#cecece' '#ffffff' \
    '#cfcfcf' '#ffffff' \
    '#d0d0d0' '#dd0022' \
    '#d1d1d1' '#dd0022' \
    '#d2d2d2' '#dd0022' \
    '#d3d3d3' '#dd0022' \
    '#d4d4d4' '#dd0022' \
    '#d5d5d5' '#dd0022' \
    '#d6d6d6' '#ffffff' \
    '#d7d7d7' '#ffffff' \
    '#d8d8d8' '#ffffff' \
    '#d9d9d9' '#ffffff' \
    '#dadada' '#ffffff' \
    '#dbdbdb' '#ffffff' \
    '#dcdcdc' '#ffffff' \
    '#dddddd' '#ffffff' \
    '#dedede' '#ffffff' \
    '#dfdfdf' '#ffffff' \
    '#e0e0e0' '#ee0011' \
    '#e1e1e1' '#ee0011' \
    '#e2e2e2' '#ee0011' \
    '#e3e3e3' '#ee0011' \
    '#e4e4e4' '#ee0011' \
    '#e5e5e5' '#ee0011' \
    '#e6e6e6' '#ffffff' \
    '#e7e7e7' '#ffffff' \
    '#e8e8e8' '#ffffff' \
    '#e9e9e9' '#ffffff' \
    '#eaeaea' '#ffffff' \
    '#ebebeb' '#ffffff' \
    '#ececec' '#ffffff' \
    '#ededed' '#ffffff' \
    '#eeeeee' '#ffffff' \
    '#efefef' '#ffffff' \
    '#f0f0f0' '#ff0000' \
    '#f1f1f1' '#ff0000' \
    '#f2f2f2' '#ff0000' \
    '#f3f3f3' '#ff0000' \
    '#f4f4f4' '#ff0000' \
    '#f5f5f5' '#ff0000' \
    '#f6f6f6' '#ffffff' \
    '#f7f7f7' '#ffffff' \
    '#f8f8f8' '#ffffff' \
    '#f9f9f9' '#ffffff' \
    '#fafafa' '#ffffff' \
    '#fbfbfb' '#ffffff' \
    '#fcfcfc' '#ffffff' \
    '#fdfdfd' '#ffffff' \
    '#fefefe' '#ffffff' \
    '#ffffff' '#ffffff' "$@"

where the left side corresponds to each of the 256 gray levels, and the right side is the corresponding color.

If the original image is gray.png, you can create contour.png from it using

pngtopnm gray.png | ./gray-to-contour | pnmtopng -compress 9 > contour.png

As I mentioned in a comment, we humans perceive sharp changes in gradients as edges, and in OP's final image, it only looks like the angle bisectors are too light/dark. I tried to locate some references to the effect, but the terms slip by my grasp right now.

While grayscale images are easy to process and use, there are cases where our human psychovisual oddities fool us. For this reason, I personally do look at bump maps and distance fields in both grayscale and contour form; the two representations complement each other, in my opinion.

Answer 2

double dist_to_segment() returns inconsistent units.

return (t4 < 0.0)? -t3 : t3; and return t3; (OP's alternative code) return a distance.

return dist2(px, py, x0, x1); returns a distance squared. This is used when (x0,y0) and (x1,y1) are the same or very nearly so -perhaps in those pesky corners. I'd expect return sqrt(dist2(px, py, x0, x1));

---

A simplification to sqrt(a*a + b*b) is hypot(a,b)

The hypot functions compute the square root of the sum of the squares of x and y, without undue overflow or underflow. C11 §7.12.7.3 2

// example
if (t0 == 0.0) { 
  return hypot(px - x0, py - y0);
}

Answer 3

Your function appears correct to me, with the caveat that whether the sign of the result is correct depends on the segment endpoints being ordered according to the correct convention for a path around a boundary of the object. The images indeed appear to show that it produces correct results. The triangular anomalies near some corners seem likely to be related to how you combine multiple results of this function, rather than to the values returned by any individual call.

In particular, if you add the negative result of a point's distance to one segment to the positive result of a point's distance to a different segment, or if you take the minimum or maximum of the signed values of two distances, you will get meaningless results. Not only the anomalies, but also the sharp features along angle bisectors suggest that you're doing something like this.

The absence of the anomalies from the unsigned distance field is consistent with that analysis, but the persistence into that field of the sharp features along the bisectors of acute angles is curious. I haven't quite determined what you're doing, but what you should be doing is using only each point's distance to the nearest edge of the figure. You must also ensure that your line segments trace each border in the same direction relative to the interior of the figure, as the correct signs of your function's results depend on it. Additionally, to reproduce the glyph you should render all negative (interior) distances in the same shade.