5 ms·

i was trying to build a word cloud algorithm and then I had a question: how do you rasterize letter shapes? I looked at pyCairo but I couldn't figure out how t

i was trying to build a word cloud algorithm and then I had a question: how do you rasterize letter shapes? I looked at pyCairo but I couldn't figure out how to use it. http://cairographics.org/documentation/pycairo/3/ http://cairographics.org/documentation/pycairo/3/ I asked on StackOverflow no answer http://stackoverflow.com/questions/21915335/getting-the-bitmask-of-a-text-string-in-python http://stackoverflow.com/questions/21915335/getting-the-bitm... i found the true-type format shape files and extracted polygons from those - which i also don't know how to rasterize. i know this not really a response to the posted link - which is very low level and interesting - but maybe someone here knows an answer.

ginko 13y ago
For concave shapes like letters the best choice would probably be a scanline-based rasterization algorithm. Sort all polygon edges from top to bottom and walk through that list line-by-line, keeping track of all active edges for each scanline. For those you can then find all intersections and fill the ranges in-between. By using an even-odd rule you can make sure that concave polygons and polygons with holes are filled properly.
- ginsweater 13y ago
  I wrote one of those once! It was a nightmare morass of one-pixel errors. Maybe there was some clever simplification I missed that would have made it all easy, but these days I use the libraries. :P I know that's how stb_truetype's renderer works, incidentally. Don't know if Freetype is the same, but I'd be mildly surprised to find it wasn't.
ANTSANTS 13y ago
I think FreeType is the go-to solution for text rendering. http://www.freetype.org/ http://www.freetype.org/ My take on the word cloud problem: 1. Sort words by frequency. Map the highest and lowest frequencies to some maximum and minimum font size. 2. Render each word into an individual image with FreeType. 3. Find some pleasing way to arrange the word images using only their bounding boxes. 4. Render the word images into a final image, picking a random pleasant color to tint each word as you go. EDIT: Or did you mean, "how does font rendering work"? In that case, I think it mostly boils down to rasterizing line segments and Bezier curves, along with algorithms for kerning and for trying to fit the text to the pixel grid. FreeType's documentation goes into great detail about what exactly a modern text renderer has to deal with, yet I found it to be very accessible as someone with little prior knowledge of the field. I recommend giving it a look: http://www.freetype.org/freetype2/documentation.html http://www.freetype.org/freetype2/documentation.html
cscheid 13y ago
If you have access to a GPU (or can evaluate quadratic functions of barycentric coordinates) Loop and Blinn's 2005 algorithm is brilliant http://research.microsoft.com/en-us/um/people/cloop/loopblinn05.pdf http://research.microsoft.com/en-us/um/people/cloop/loopblin...
- dman 13y ago
  That technique is patented.
ginsweater 13y ago
I like stb_truetype myself. It's C so you'll have to bind it if you're using any other language, but it's a lot simpler than Freetype. (Less features too, but it'll take a .ttf and return a bitmap, which sounds like what you want.) http://nothings.org/stb/stb_truetype.h http://nothings.org/stb/stb_truetype.h
- userbinator 13y ago
  It's always great to see things that people would consider nontrivial programming tasks being done with a much smaller amount of code than they would expect from looking at the more "mainstream" libraries that do it. Public domain is a big bonus too. In comparison, Freetype is absolutely monsterous; it is a few times faster according to some benchmarks I've found, but a few orders of magnitude bigger too. Sometimes you don't need the fastest, you just want something simple that works.

ginko 13y ago

For concave shapes like letters the best choice would probably be a scanline-based rasterization algorithm. Sort all polygon edges from top to bottom and walk through that list line-by-line, keeping track of all active edges for each scanline. For those you can then find all intersections and fill the ranges in-between. By using an even-odd rule you can make sure that concave polygons and polygons with holes are filled properly.

ginsweater 13y ago
I wrote one of those once! It was a nightmare morass of one-pixel errors. Maybe there was some clever simplification I missed that would have made it all easy, but these days I use the libraries. :P I know that's how stb_truetype's renderer works, incidentally. Don't know if Freetype is the same, but I'd be mildly surprised to find it wasn't.

ANTSANTS 13y ago

I think FreeType is the go-to solution for text rendering. http://www.freetype.org/ http://www.freetype.org/ My take on the word cloud problem: 1. Sort words by frequency. Map the highest and lowest frequencies to some maximum and minimum font size. 2. Render each word into an individual image with FreeType. 3. Find some pleasing way to arrange the word images using only their bounding boxes. 4. Render the word images into a final image, picking a random pleasant color to tint each word as you go. EDIT: Or did you mean, "how does font rendering work"? In that case, I think it mostly boils down to rasterizing line segments and Bezier curves, along with algorithms for kerning and for trying to fit the text to the pixel grid. FreeType's documentation goes into great detail about what exactly a modern text renderer has to deal with, yet I found it to be very accessible as someone with little prior knowledge of the field. I recommend giving it a look: http://www.freetype.org/freetype2/documentation.html http://www.freetype.org/freetype2/documentation.html

cscheid 13y ago

If you have access to a GPU (or can evaluate quadratic functions of barycentric coordinates) Loop and Blinn's 2005 algorithm is brilliant http://research.microsoft.com/en-us/um/people/cloop/loopblinn05.pdf http://research.microsoft.com/en-us/um/people/cloop/loopblin...

dman 13y ago
That technique is patented.

ginsweater 13y ago

I like stb_truetype myself. It's C so you'll have to bind it if you're using any other language, but it's a lot simpler than Freetype. (Less features too, but it'll take a .ttf and return a bitmap, which sounds like what you want.) http://nothings.org/stb/stb_truetype.h http://nothings.org/stb/stb_truetype.h

userbinator 13y ago
It's always great to see things that people would consider nontrivial programming tasks being done with a much smaller amount of code than they would expect from looking at the more "mainstream" libraries that do it. Public domain is a big bonus too. In comparison, Freetype is absolutely monsterous; it is a few times faster according to some benchmarks I've found, but a few orders of magnitude bigger too. Sometimes you don't need the fastest, you just want something simple that works.