4 ms·

Text layout is a loose hierarchy of segmentation (2020)

91 points by lylejantzi3rd 4y ago

nicoburns 4y ago
It's two years since this was posted, and the amazing news is that we now have not just one but two projects implementing text layout in Rust that look like they might be viable: - https://github.com/pop-os/cosmic-text/ https://github.com/pop-os/cosmic-text/ - which is still has a way to go but already complex scenarios involving asian and arabic scripts, which is impressive considering it's only a couple of months old. This one is backed by System76 for use in their new desktop environment - And https://github.com/dfrg/parley https://github.com/dfrg/parley which looks abandoned but is already impressively complete and the author has signalled they intend to revisit at the start of this year. This one is being used in the Druid toolkit mentioned in the article (and it's successor Xilem) and also the text editor https://github.com/lapce/lapce https://github.com/lapce/lapce which is based on that toolkit.
- raphlinus 4y ago
  A clarification: Druid proper uses the text layout capabilities of the platform (DirectWrite on Windows, Core Text on macOS, and Pango on Linux), while Xilem does indeed use Parley. Lapce uses a fork of Druid that, as parent states, uses Parley for text layout. It does look like a very good year coming up! I'm writing a reflection/wishes post as we speak.
  - nicoburns 4y ago
    Ah yes. I only really started following the Druid project closely recently, and I've focussed more on the newer sub-projects so my knowledge of Druid proper is limited (indeed partly because I am much more interested in "rust native" UI (to the extent that that is possible) than I am in toolkits that rely heavily on closed-source OS provided APIs.
- moloch-hai 4y ago
  It is kind of tragic when so much work gets wrapped into libraries coded in obscure languages, and so never gets out to affect much in the world. Doubtless, enormous brilliance went into Symbolics OS and UI code, all washed away when Symbolics tanked. On the up side, untold gigabytes of bad Java code were flushed in the big tech meltdown of 2000. When Twitter and Facebook go flat like inflatable lawn decorations in a cold snap, will much of anything be lost? (Anyway zstd and lz4 will survive.) How much stuff is coded in Wolfram? Obscure code today goes onto GitHub repositories rather that just evaporating, but it is more manual labor to find and transcribe to a live language than can usually be mustered.
splatzone 4y ago
I like this way of formatting ideas hierarchically. Is there an Obsidian plugin for using this kind of structure? I know there’s the graph view for seeing how notes are linked together
bfgeek 4y ago
One interesting/fun problem with text layout is that: width(A) + width(B) != width(A+B) ...which some basic text layout engines assume. The post touches on this, and is one reason why line-breaking is so difficult. If you add some text to a line, the width of the line may be longer or shorter(!) than if you measured (shaped) the parts separately. This occurs for many reasons, the post mentions splitting a ligature, can also happen with kerning (spaces can have kerning applied for example). E.g. many text layout engines will incrementally "add" to a line. However to do this correctly for all cases you need to re-shape (measure) the entire line (or from a known "safe to break" point in the shape result see: https://github.com/harfbuzz/harfbuzz/issues/224 https://github.com/harfbuzz/harfbuzz/issues/224 ). This is typically fine for latin cases, but begins to become slow for more complex scripts (Thai). Chromium kinda works backwards. It tries to fit everything in the paragraph on a single line, shapes (measures), then finds a line-break opportunity within the (potentially large) shape result which would "fit" on the line without re-shaping. Then given that line-break will reshape the entire line (using the "safe to break" API), (and remaining content for the next line), see if it will fit and repeats the process[1]. By always "removing" content from the line you end up with a correct implementation which works for all the crazy things which can happen with text rendering. [1] The content in the line may become bigger after taking a line-break, hence this needs to happen in a loop until there is one "unbreakable" piece of content in the line. This loop typically only goes through one iteration.
- amelius 4y ago
  Didn't Knuth solve this problem in his Computers & Typesetting books?
  - raphlinus 4y ago
    No. Most line breaks in English are at spaces, and the Computer Modern fonts don't have any complex shaping behavior across spaces (it's mostly complex scripts such as Nastaliq that have this behavior). I haven't checked to see whether it takes into account the kerning value with the hyphen added. The first system I know of that does solve this very well is DirectWrite. Sergey Malkin describes the solution here: https://github.com/harfbuzz/harfbuzz/issues/1463#issuecomment-505592189 https://github.com/harfbuzz/harfbuzz/issues/1463#issuecommen... It sounds like Chromium has since also adapted the "safe to break" API. Great to see people engaging these hard problems!
taeric 4y ago
Another fun problem of hyphenation in English, that I didn't see on my read through this, is that how something is hyphenated may depend on how the word is used. Easy example is "record", as a noun it will hyphenate differently than it will as a verb.
- blkhp19 4y ago
  I’m trying to figure out when “record” would ever be hyphenated. If it doesn’t fit on one line, just put it on the next, right? No need to do some weird “rec-ord” / “re-cord” hyphenation.
  - dan-robertson 4y ago
    If you’re justifying text, there may be more constraints like not wanting a big change in interword spacing between lines or avoiding spaces lining up across lines. These constraints might apply to the current line or to following lines affected by your choice of where to break. Though I think the main reason would be limited horizontal space, e.g. a table cell or narrow newspaper column.
    - taeric 4y ago
      To add to this, the point it is it trying a full page optimization, not just single lines or words. Will it be likely? Probably not, but it can happen. And I only used "record" as it was the example given to me. I'm sure there are others. Is a good example for how/why counting syllables can be harder than folks think. Well, kind of a good example; since you will get the right count, regardless.
danielvaughn 4y ago
First paragraph mentions how he couldn’t write a book on it, but honestly I’d buy that book in a heartbeat.
- raphlinus 4y ago
  Aw thanks. It remains a life goal to write a book on 2D graphics, including text layout and rendering, but I don't see any way to find time for it in the next year at least. Meanwhile I do have some pretty exciting stuff lined up, including some writing (just not a book) and will publish a blog post on my 2023 plans tomorrow.
hsn915 4y ago
My problem with this kind of essay is, even if it might contain useful information, it presents the problem as "omg this is way too complicated it's almost insurmountable". This is a common trend I keep seeing in technical blogs, and I don't understand why they do it. Look, it's not that. It's just a series of small problems. Solve each problem one at a time, and you'll approximate a complete solution as you iterate further and further. Your first iteration will not be perfect, but so what?
- csande17 4y ago
  The underlying assumption of all these "handling text is impossible" blog posts is that you're trying to write a text renderer that handles every language in the world. This is indeed very hard, as many languages require their own typesetting features and special cases. It's hard to solve this iteratively when you don't speak all of the languages involved. In some cases this is just an unspoken assumption because the blog posts are looking at, say, Firefox, and Firefox supports a lot of languages. In other cases, it's framed as a moral or professional imperative -- you're a bad developer if you don't consider the needs of Arabic users, if not a bad person. (I'm not sure how I feel about the globalist/colonialist worldview that seems to drive this idea that Arabic users won't have any software if Silicon Valley doesn't write it for them. I guess if you work at a big global megacorporation, it's your job to write big global megasoftware.) But yeah, if you aren't trying to do that, then text is a much easier problem than these posts describe. Tons and tons of embedded devices, video games, and so on get away with having much simpler text rendering and layout code that only supports a few languages. In English, you really can start with a very simple layout system, then add features like kerning and ligatures and hyphenation and watch the text get progressively nicer-looking!
  - gernb 4y ago
    Or if you're smart you won't reinvent the wheel. It's already been done. use one of them
  - hsn915 4y ago
    Supporting Arabic is not that hard. It's not as complicated as these blog posts are presenting it to be.

91 points by lylejantzi3rd 4y ago

It's two years since this was posted, and the amazing news is that we now have not just one but two projects implementing text layout in Rust that look like they might be viable: - https://github.com/pop-os/cosmic-text/ https://github.com/pop-os/cosmic-text/ - which is still has a way to go but already complex scenarios involving asian and arabic scripts, which is impressive considering it's only a couple of months old. This one is backed by System76 for use in their new desktop environment - And https://github.com/dfrg/parley https://github.com/dfrg/parley which looks abandoned but is already impressively complete and the author has signalled they intend to revisit at the start of this year. This one is being used in the Druid toolkit mentioned in the article (and it's successor Xilem) and also the text editor https://github.com/lapce/lapce https://github.com/lapce/lapce which is based on that toolkit.

raphlinus 4y ago
A clarification: Druid proper uses the text layout capabilities of the platform (DirectWrite on Windows, Core Text on macOS, and Pango on Linux), while Xilem does indeed use Parley. Lapce uses a fork of Druid that, as parent states, uses Parley for text layout. It does look like a very good year coming up! I'm writing a reflection/wishes post as we speak.
- nicoburns 4y ago
  Ah yes. I only really started following the Druid project closely recently, and I've focussed more on the newer sub-projects so my knowledge of Druid proper is limited (indeed partly because I am much more interested in "rust native" UI (to the extent that that is possible) than I am in toolkits that rely heavily on closed-source OS provided APIs.
moloch-hai 4y ago
It is kind of tragic when so much work gets wrapped into libraries coded in obscure languages, and so never gets out to affect much in the world. Doubtless, enormous brilliance went into Symbolics OS and UI code, all washed away when Symbolics tanked. On the up side, untold gigabytes of bad Java code were flushed in the big tech meltdown of 2000. When Twitter and Facebook go flat like inflatable lawn decorations in a cold snap, will much of anything be lost? (Anyway zstd and lz4 will survive.) How much stuff is coded in Wolfram? Obscure code today goes onto GitHub repositories rather that just evaporating, but it is more manual labor to find and transcribe to a live language than can usually be mustered.

splatzone 4y ago

I like this way of formatting ideas hierarchically. Is there an Obsidian plugin for using this kind of structure? I know there’s the graph view for seeing how notes are linked together

bfgeek 4y ago

One interesting/fun problem with text layout is that: width(A) + width(B) != width(A+B) ...which some basic text layout engines assume. The post touches on this, and is one reason why line-breaking is so difficult. If you add some text to a line, the width of the line may be longer or shorter(!) than if you measured (shaped) the parts separately. This occurs for many reasons, the post mentions splitting a ligature, can also happen with kerning (spaces can have kerning applied for example). E.g. many text layout engines will incrementally "add" to a line. However to do this correctly for all cases you need to re-shape (measure) the entire line (or from a known "safe to break" point in the shape result see: https://github.com/harfbuzz/harfbuzz/issues/224 https://github.com/harfbuzz/harfbuzz/issues/224 ). This is typically fine for latin cases, but begins to become slow for more complex scripts (Thai). Chromium kinda works backwards. It tries to fit everything in the paragraph on a single line, shapes (measures), then finds a line-break opportunity within the (potentially large) shape result which would "fit" on the line without re-shaping. Then given that line-break will reshape the entire line (using the "safe to break" API), (and remaining content for the next line), see if it will fit and repeats the process[1]. By always "removing" content from the line you end up with a correct implementation which works for all the crazy things which can happen with text rendering. [1] The content in the line may become bigger after taking a line-break, hence this needs to happen in a loop until there is one "unbreakable" piece of content in the line. This loop typically only goes through one iteration.

amelius 4y ago
Didn't Knuth solve this problem in his Computers & Typesetting books?
- raphlinus 4y ago
  No. Most line breaks in English are at spaces, and the Computer Modern fonts don't have any complex shaping behavior across spaces (it's mostly complex scripts such as Nastaliq that have this behavior). I haven't checked to see whether it takes into account the kerning value with the hyphen added. The first system I know of that does solve this very well is DirectWrite. Sergey Malkin describes the solution here: https://github.com/harfbuzz/harfbuzz/issues/1463#issuecomment-505592189 https://github.com/harfbuzz/harfbuzz/issues/1463#issuecommen... It sounds like Chromium has since also adapted the "safe to break" API. Great to see people engaging these hard problems!

taeric 4y ago

Another fun problem of hyphenation in English, that I didn't see on my read through this, is that how something is hyphenated may depend on how the word is used. Easy example is "record", as a noun it will hyphenate differently than it will as a verb.

blkhp19 4y ago
I’m trying to figure out when “record” would ever be hyphenated. If it doesn’t fit on one line, just put it on the next, right? No need to do some weird “rec-ord” / “re-cord” hyphenation.
- dan-robertson 4y ago
  If you’re justifying text, there may be more constraints like not wanting a big change in interword spacing between lines or avoiding spaces lining up across lines. These constraints might apply to the current line or to following lines affected by your choice of where to break. Though I think the main reason would be limited horizontal space, e.g. a table cell or narrow newspaper column.
  - taeric 4y ago
    To add to this, the point it is it trying a full page optimization, not just single lines or words. Will it be likely? Probably not, but it can happen. And I only used "record" as it was the example given to me. I'm sure there are others. Is a good example for how/why counting syllables can be harder than folks think. Well, kind of a good example; since you will get the right count, regardless.

danielvaughn 4y ago

First paragraph mentions how he couldn’t write a book on it, but honestly I’d buy that book in a heartbeat.

raphlinus 4y ago
Aw thanks. It remains a life goal to write a book on 2D graphics, including text layout and rendering, but I don't see any way to find time for it in the next year at least. Meanwhile I do have some pretty exciting stuff lined up, including some writing (just not a book) and will publish a blog post on my 2023 plans tomorrow.

hsn915 4y ago

My problem with this kind of essay is, even if it might contain useful information, it presents the problem as "omg this is way too complicated it's almost insurmountable". This is a common trend I keep seeing in technical blogs, and I don't understand why they do it. Look, it's not that. It's just a series of small problems. Solve each problem one at a time, and you'll approximate a complete solution as you iterate further and further. Your first iteration will not be perfect, but so what?

csande17 4y ago
The underlying assumption of all these "handling text is impossible" blog posts is that you're trying to write a text renderer that handles every language in the world. This is indeed very hard, as many languages require their own typesetting features and special cases. It's hard to solve this iteratively when you don't speak all of the languages involved. In some cases this is just an unspoken assumption because the blog posts are looking at, say, Firefox, and Firefox supports a lot of languages. In other cases, it's framed as a moral or professional imperative -- you're a bad developer if you don't consider the needs of Arabic users, if not a bad person. (I'm not sure how I feel about the globalist/colonialist worldview that seems to drive this idea that Arabic users won't have any software if Silicon Valley doesn't write it for them. I guess if you work at a big global megacorporation, it's your job to write big global megasoftware.) But yeah, if you aren't trying to do that, then text is a much easier problem than these posts describe. Tons and tons of embedded devices, video games, and so on get away with having much simpler text rendering and layout code that only supports a few languages. In English, you really can start with a very simple layout system, then add features like kerning and ligatures and hyphenation and watch the text get progressively nicer-looking!
- gernb 4y ago
  Or if you're smart you won't reinvent the wheel. It's already been done. use one of them
- hsn915 4y ago
  Supporting Arabic is not that hard. It's not as complicated as these blog posts are presenting it to be.