49
$\begingroup$

Signed Distance Fields (SDFs) was presented as a fast solution to achieve resolution independent font rendering by Valve in this paper.

I already have the Valve solution working but I'd like to preserve sharpness around corners. Valve states that their method can achieve sharp corners by using a second texture channels ANDed with the base one, but lacks to explain how this second channel would be generated.

In fact there's a lot of implementation details left out of this paper.

I'd like to know if any of you could point me out a direction to get SDFs font rendering with sharp corners.

$\endgroup$
  • $\begingroup$ As a matter of fact Adam already posted source code on shadertoy. Here's the link: shadertoy.com/view/ltXSDB $\endgroup$ – Felipe Lira Aug 21 '15 at 13:02
  • $\begingroup$ You had me excited. He did post the bezier stuff on shadertoy but not the texture distance field stuff! $\endgroup$ – Alan Wolfe Aug 21 '15 at 14:33
  • $\begingroup$ @AlanWolfe I think he has done only for procedurally set bezier curves. I'm not sure the effort required to integrate this into a ttf render lib. When I have some time I'll take a look at it. $\endgroup$ – Felipe Lira Aug 21 '15 at 22:07
  • $\begingroup$ it looks he has some magic sauce on the side of actually storing and retrieving the distances from a texture. Without a texture in play, the shadertoy examples are missing that part of the equation. $\endgroup$ – Alan Wolfe Aug 21 '15 at 22:11
  • $\begingroup$ Bit late to the party but this older thread from reddit has a ton of info on various methods of improving the sharpness of SDF based rendering: reddit.com/r/gamedev/comments/2879jd/… $\endgroup$ – Necrolis Aug 31 '15 at 21:56
7
$\begingroup$

Adam Simmons has done some interesting work in this area. I don't know specifically how he's achieving it, but his SDF-based vector rendering is the sharpest I've seen in practice outside of Valve. http://twitter.com/adamjsimmons/status/611677036545863680

$\endgroup$
  • $\begingroup$ Of course I don't have all the details, but it seems to me that this person merely used a pseudo-distance field in place of a regular one, which has already been demonstrated in a 2006 paper by Qin, McCool and Kaplan, "Real-time texture-mapped vector glyphs", which is also referenced in the Valve paper. It only affects the miters of outlines and does nothing to improve the appearance of corners. I suspect the reason it looks sharp is because he uses unpractically large distance field textures. I might be wrong though. $\endgroup$ – Detheroc Mar 7 '16 at 12:21
69
$\begingroup$

EDIT: Please see my other answer with a concrete solution.

I have actually solved this exact problem over a year ago for my master's thesis. In the Valve paper, they show that you can AND two distance fields to achieve this, which works as long as you only have one convex corner. For concave corners, you also need the OR operation. This guy actually developed some obscure system to switch between the two operations using four texture channels.

However, there is a much simpler operation that can facilitate both AND and OR depending on the situation, and this is the principal idea of my thesis: the median of three. So basically, you use exactly three channels (ideal for RGB), which are completely interchangeable, and combine them using the median operation (choose the middle value out of the three).

To accomodate anti-aliasing, we don't work with just booleans, but floating point values, and the AND operation becomes the minimum, and the OR becomes the maximum of two values. The median of three can indeed do both: if a < b, for (a, a, b), the median is the minimum, and for (a, b, b), it is the maximum.

The rendering process is still extremely simple. The entire fragment shader including anti-aliasing can look something like this:

int main() {
    // Bilinear sampling of the distance field
    vec3 s = texture2D(sdf, p).rgb;
    // Acquire the signed distance
    float d = median(s.r, s.g, s.b) - 0.5;
    // Weight between inside and outside (anti-aliasing)
    float w = clamp(d/fwidth(d) + 0.5, 0.0, 1.0);
    // Combining the background and foreground color
    gl_FragColor = mix(outsideColor, insideColor, w);
}

So the only difference from the original method is computing the median right after sampling the texture. You will have to implement the median function though, which can be done with just 4 min/max operations.

Now of course, the question is, how do I build such a three-channel distance field? And this is the tricky part. The most obvious approach that I took in the beginning was to perform a decomposition of the input shape/glyph into three components, and then generate a conventional distance field out of each. The rules for this decomposition aren't that complicated. Firstly , the area with at least 2 out of 3 channels on is the inside. Then, if you imagine this as the RGB color channels, convex corners must be made of a secondary color, and its two primary components continue outward. Concave corners are the inverse: Two secondary colors enclose their common primary color, and the wedge between where both edges continue inward is white. I also found that some padding is necessary where two primary or two secondary colors would otherwise touch to avoid artifacts (for example, in the middle stroke of the "N" in the picture).

The following image is an example decomposition generated by the program from my thesis:

Multi-channel decomposition of glyphs

This approach however has some drawbacks. One of them is that the special effects, such as outlines and shadows will no longer work correctly. Fortunatelly, I also came up with a second, much more elegant method, which generates the distance fields directly, and even supports all of the graphical effects. It is also included in my thesis and so is also over a year old. I am not going to give any more details right now, because I am currently writing a paper that describes this second technique in detail, but I will post it here as soon as it's finished.

Anyway, here is an example of the difference in quality. The texture resolution is the same in each image, but the left one uses a regular texture, the middle one uses an ordinary distance field, and the right one uses my three-channel distance field. The performance overhead is only the difference between sampling an RGB texture versus a monochrome one.

enter image description here

$\endgroup$
  • 5
    $\begingroup$ Great first answer, welcome to the Computer Graphics SE! :) Is your thesis publicly available? (Or will it be after you've finished said paper?) If so it would probably be very helpful to link to that, too. $\endgroup$ – Martin Ender Mar 7 '16 at 13:57
  • $\begingroup$ It is supposed to be publicly available, but it seems the school hasn't put it up yet. Anyway, I would prefer not to spread it right now, since the article I'm writing will really explain the important parts much better and focus on how to implement it, and it should be complete very soon. $\endgroup$ – Detheroc Mar 7 '16 at 14:26
  • $\begingroup$ @Detheroc Please notify here and on the gamedev Q when you are done with the article. Explanation's still not 100% clear for me. I would suggest showing the composition step by step in images. $\endgroup$ – Engineer Mar 7 '16 at 15:09
  • 1
    $\begingroup$ would love to be able to replicate your current results even if they are not as good as your future results, +1 to sharing whatever details you can. very exciting. Have you considered either technique's application towards ray marching (sphere tracing)? In volume textures or similar... $\endgroup$ – Alan Wolfe Mar 7 '16 at 19:36
  • 4
    $\begingroup$ The thesis is publicly available here: dspace.cvut.cz/bitstream/handle/10467/62770/… $\endgroup$ – Romain Guy Apr 28 '16 at 22:00
43
$\begingroup$

Sorry about the long wait, but it has become obvious that although the article I have promised is basically complete, the publishing process will take some time. Therefore, I have instead prepared an open source program with my new multi-channel distance field construction algorithm, msdfgen, which you can try out right now.

It is available on GitHub: https://github.com/Chlumsky/msdfgen

(I am new to this, so please let me know if there is anything wrong with the repository.)

Someone also asked about how it compares to a larger monochrome distance field, so here is a teaser of the quality difference. However, it really depends on the particular font, and I would not say it is always worth the extra data.

Multi-channel distance field 16x16 Monochrome distance field 32x32

$\endgroup$
3
$\begingroup$

Quite interesting! I'm the author of the valve signed distance paper. Sorry that it's a little sparse on implementation details. I only included the two channel example as future work - I didn't have a generator. I figured something like generating a high res sdf and then segmenting based upon the angle of the gradient of the sdf would be a reasonable tactic. But never got to it. Any multichannel scheme has to be weighed against using higher res single channel data of the same memory footprint, for the magnification ratios your app needs.

$\endgroup$
0
$\begingroup$

I am by no means an expert on the subject, but you might be able to, at least in theory, preserve sharp corners in a monochromatic pseudo-SDF if you used either a Bilateral filter a Directional Bicubic filter instead of a standard Bilinear filter. Besides the obvious benefit of saving memory, you could also have multiple channels for multi-colored SDF decals.

Alternatively, if you don't mind using a second channel, then you could also try having one channel for Horizontal Distance and another for Vertical Distance, and use a Difference of Laplacean (DoL) energy pyramid to compress the texture so that redundant information wouldn't be recorded.

A third and final theoretical solution would be to experiment with a Hexagonally Sampled Texture via Array Set Addressing.

Unfortunately, I don't have any means of testing my ideas currently, and have been unable to find any documents describing or testing anything similar to my ideas. I will link all of the relevant articles where I got my information/ideas shortly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.