draw_line function algorithm

[bobli1986]

Hi,
I am working on implementing this library on my hardware platform. To get higher performance, I plan to harden some calculation function in FPGA. The function draw_line looks suitable for harden. However, I noticed that the 2d raycasting is customized algorithm. Could you help provide some reference for understanding the algorithm? what's the pros/cons for this algorithm compared to other legacy algorithm such as Xiaolin-Wu algorithm?

Thanks for the help.

[tomolt]

Huh, I never thought anyone would try to accelerate libschrift with FPGAs, that's pretty neat.

It's important to understand that in TrueType,
glyphs are represented as concave polygons, and only their outline is actually stored in the font file.

This means that the problem we have to solve is fundamentally a different one:
we don't need to draw anti-aliased lines. We need to rasterize concave polygons.
Algorithms like Xiaolin-Wu solve a different problem.

The traditional algorithm for rasterization of concave polygons is Scanline rendering.
I believe it is still used by some other font rendering libraries.
I decided against scanline rendering in libschrift because it sacrifices both performance and simplicity just to make
sure that pixels are written in a sequential order, which we simply don't need.

Instead, libschrift and others split drawing into two separate steps:
only draw the outline first, then fill in the pixels inside the outline.

When we draw the outline, we can't just directly anti-aliase it.
Instead, we store extra information for each pixel.
When filling in, we can use this extra information to compute how much of
the area of each pixel is covered by the glyph.
One nice property of this method is that the resulting anti-aliasing is "pixel-perfect".

Sean Barrett, the creator of stb_truetype, has written a good explanation of how
this two-step drawing/anti-aliasing technique works:
https://nothings.org/gamedev/rasterize/
The "New" algorithms he describes here uses more or less the same calculations
for anti-aliasing as libschrift does.

Note however that Barrett does in fact use scanline rendering to rasterize the outline.
For libschrift I replaced the scanline algorithm with a 2D raycasting algorithm.

Raycasting is a classic and well-understood algorithm as well.
It works superficially similar to Bresenham, but it makes absolutely sure to visit every
pixel on the line exactly once, which Bresenham does not guarantee.

You can find a lot of information on the Internet about how 2D raycasting works in
old FPS games like Wolfenstein 3D. The way the level geometry is rasterized onto the
screen without proper 3D graphics is exactly the same way libschrift draws outlines.

https://lodev.org/cgtutor/raycasting.html
This in particular is a great write-up that explains the geometric calculations needed.
They give example code that looks a lot like the line renderer in libschrift, albeit more
cumbersome and less optimized.

Hope this helps.

[bobli1986]

Thanks for the reply. Actually I am not going to implement the whole lib in hardware. That is really too complicated. Instead the rasterization of straight line is a good start point. In the render_outline function, the points are transformed according to the matrix and curves are simplified to multiple lines. Finally the draw_line and post_process function rasterize the lines to pixel image. I am trying to understand the draw_line and post_process function and doing some hardware acceleration if possible.
I will do more research on the website you mentioned. I think they are really helpful. For me, these are really new knowledge :P. Thanks again for your help.