Closest edge search performance about msdfgen HOT 9 CLOSED

The problem definition as it is stated in the first post is no longer correct. There have been some fundamental changes to the algorithm since then, which caused that it is no longer sufficient to select edges based on their true distance, and the pseudo-distance metric sometimes comes into play.

I have given this some thought later on and found out that the real problem with the pseudo-distance metric is that it takes into account the infinite continuations of all edge segments. This means that any sort of bounding hierarchy is not applicable because the individual components are literally unbounded - they continue to infinity in two directions.

However, it would be possible to apply the relatively straightforward bounding volume hierarchy optimization to the regular SDF mode and the old version of the algorithm, which only produces imprecise results in specific scenarios (mainly #25).

from msdfgen.

I remember this problem from computational geometry, but it's been literally 20 years.

I only know the German terms, but this Wikipedia overview describes a few approaches for line segments with favourable runtimes.

https://en.m.wikipedia.org/wiki/Point_location

Regarding curves, I'm still wondering why a AABB bounding volume hierarchy could not help bring this down to m*log(n). Distance tests to reject subtrees are cheap for each AABB, and proper hierarchy means no single segment is in the same bounding volume (leaf).

I wonder what the frequency of intersecting curves is. Even then, multiple volumes could coexist as leaves on the same tree level pointing to the same curve.

PS: for Euclidean distances, circular volumes could work but I'd rather go with adjacent leaves lest finding well-fit circular or ellipsoid bounding volume can be complex for overlapping concave shapes.

from msdfgen.

Do you test directly against all segments and Bézier curves ? Would it be worth testing first Bézier curves against their bounding box and reject them early if a segment is already closest ? Of course, this add supplementary tests but on average, maybe the extra test will make things faster.

from msdfgen.

Hello I want to present my idea about it

I have a modified version of your Msdf gen.

I call it Msdf3, (PaintLab/PixelFarm#55)

I optimize 'Closest edge search' by using 'closest edges lookup table bitmap'

I have implement it here...

1. PixelFarm's LcdEffect SubPixelRendering Atlas texture

(this is just a based case)

(click on the image to see detail)

PixelFarm's LcdEffectSubPixelRendering Atlas Texture, built-time about 220ms

2. Msdf gen,C# port from original

Msdf, C# version, built-time about 7,101ms

3. a Modified version, (I call it 'Msdf3')

Msdf3, C# version, built-time about 1,096ms

Even the result images are different, but it give the acceptable glyph image,
(see later)

from msdfgen.

Msdf3

Our version is an extension to the original technique (Msdf, see https://github.com/Chlumsky/msdfgen).

It optimizes 'nearest-edge searching' by using 'classic scanline fill' and encode
the pixel-curve data into a lookup bitmap.

Then it go to original Msdf gen phase,
this time instead of checking all edges for a pixel,
it use the lookup bitmap to decode edge data that are responsible for the
specific bitmap.

With a given pixel, the choices are

1. no edge for this pixel, => finish here

2. only 1 edge for this pixel, just calculate distant from a pixel to that edge

3. more than 1 edge, just calculate the repsonsible edges (mostly just 2-3 edges, on the
   corners, esp overlap edges)

so it go faster

for Msdf, see https://github.com/PaintLab/PixelFarm/tree/master/src/PixelFarm/PixelFarm.Drawing/7_CpuBlitPainter/Msdf

and Msdf3, see https://github.com/PaintLab/PixelFarm/tree/master/src/PixelFarm/PixelFarm.Drawing/7_CpuBlitPainter/Msdf3

blue rect is original Msdf, and red rect is Msdf3

from msdfgen.

Closest Edge Lookup Table

Closest edge lookup table bitmap, each pixel contains encoding data of responsible edges
over that pixel.

This render with 'classic scanline' technqiue.

I use my PixelFarm's Agg (Antigrain geometry, C# port) the render it.

Roboto font,Closest edge lookup table bitmap

Roboto font, Msdf output, 8 times scale up, still sharp :)

Please note that this version has some artifacts, cause by lut phase, It will be fixed later

from msdfgen.

Another glyph-B, Roboto font
This shows both curve segments and line segment

Closest edge lookup table bitmap

Roboto font, Msdf output, 8 times scale up, still sharp :)

Please note that this version has some artifacts, cause by lut phase, It will be fixed later

from msdfgen.

Closest Edge Lookup Table in the form of bitmap

This is some detail about the lookup bitmap creation of glyph X, Roboto font.

(the picture is zoom in 8 times,
and increase brightness (100%) ,
increase contrast (50%) to see the detail)

see more detail PaintLab/PixelFarm#55 (comment)

1

2

3,4 ... final

final

from msdfgen.

The performance of the algorithm has been very significantly improved by 8ebb37d and subsequent tweaks, where partial results from previously computed pixels are stored and checked in order to skip edge segments that are definitely too far away to be relevant. I am currently satisfied with the algorithm's performance, so I am closing this issue. I am also working on a Vulkan-based GPU implementation which will be available in the future for those who still find the CPU implementation too slow.

from msdfgen.