6 ms·

TeX line breaking algorithm in JavaScript (and HTML5 Canvas)

86 points by bramstein 17y ago

patrickg 17y ago
This is great news. However, having a Knuth & Plass line breaking algorithm without hyphenation is like sex without a partner. Pretty much useless. The good points you get from using a total fit algorithm is much less then you lose from lack of hyphenation. If hyphenation is implemented, this will be very great!
- mbrubeck 17y ago
  Now that Firefox 2.0 is history, you can reliably use soft hyphens to hyphenate HTML text, and there are JavaScript libraries to do the hyphenation on the client: http://www.mnn.ch/hyph/hyphenation1.html http://www.mnn.ch/hyph/hyphenation1.html
- jacobolus 17y ago
  Well, hyphenation isn’t too hard, since there are reasonable solutions that can be used directly or easily ported. (There are existing javascript hyphenation libraries floating around.) The real problem with all of this is that everything is being done in a canvas element, which means no text selection, no searching, etc. etc.
  - bramstein 17y ago
    Hyphenation is definitively on my to-do list. As you said, it will improve the output of the canvas tremendously. The canvas is just a way to show the output of the line breaking algorithm. Earlier I had an example on my website of a dynamically created DOM paragraph using the Knuth & Plass algorithm. That way, the rendering was done by your browser (i.e. select, searching, etc. was possible) while the line breaks were handled by the algorithm. Unfortunately I haven't been able to get it reliable on all browsers, so I took it out before I posted this item. It's still on my Github repository: http://github.com/bramstein/javascript/tree/master/src/typeset/ http://github.com/bramstein/javascript/tree/master/src/types...
    - elblanco 17y ago
      I'm definitely following this and waiting for when you get the browser rendering complete. The could be really great.
ZeroGravitas 17y ago
Does the TeX algorigthm reduce rivers in the text, or is that just a coincidence? http://en.wikipedia.org/wiki/River_(typography) http://en.wikipedia.org/wiki/River_(typography) edit: re-reading this seems to follow naturally from reducing the size of the gaps between words, which the algorithm does.
- patrickg 17y ago
  As you said: the Knuth/Plass algorithmn does not reduce or even detect rivers. Detecting rivers can be done in linear time, but reducing is very likely to put the algorithm in a higher time complexity class (which is almost linear with input length for the normal algorithm!).
- jacobolus 17y ago
  Rivers are killed naturally except for pathological edge cases when you (a) do proper hyphenation, and (b) do something like the TeX algorithm for paragraph layout, and (c) adjust inter-letter space as well as inter-word space.
stralep 17y ago
Why current browsers are not using this, or some improved version of this algorithm?
- jacobolus 17y ago
  The claimed reasons are (a) it would take work to implement, and (b) it would be slower than the current method. Both seem like pretty weak excuses to me. The main real reason is likely that most users don’t care, and so they can get away with it.
  - lambda 17y ago
    Speed is a pretty important reason, and users not caring is also a pretty important reason. Users do care about speed, and don't care about absolutely ideal line breaking; so why trade off something they do care about for something they don't?
    - jacobolus 17y ago
      Well, it was an important reason in 1990, maybe, or even 1995. But we’ve had a couple of orders of magnitude improvement in computing speed since then. There’s no reason to favor some marginal speed advantage (tenths or hundredths of a second) to better layout.
      - lambda 17y ago
        Tenths of a second can be pretty damn significant. Every tenth of a second extra load time leads to approximately a 1% drop in sales, according to research done by Amazon. One of the big points of competition between browsers these days is in speed. Part of the reason people switch from IE to one of the more modern browsers is because they are just that much snappier.
        jacobolus 17y ago
        Maybe. Though the only time there’s going to be a noticeable slowdown is when you’re dealing with huge amounts of text. Like an amount that will take 20 minutes or an hour to read. At that point, an extra 10th of a second to render, in return for a much more pleasant reading experience seems like a no-brainer trade-off. On a typical Amazon page the difference is going to be unnoticeable.
grayrest 17y ago
Do you have any plans on intra-character spacing as well? I know this is done in print to reduce the word gaps in justified text but I'm not sure if the resolution on screen would allow it. I have a  hyphenator using Liang's algorithm as a YUI3 module if you're interested.
- lambda 17y ago
  If you used sub-pixel alignment, it might be worth it. I just wish we could get 300dpi displays for our computers already, and stop worrying about the pixel grid. But, we're going to need some better techniques for resolution independent UIs before that happens. In particular, you will probably actually need better hinting for vector based UI graphics, so that the same vector graphics that can be used for high resolution displays can also be used for lower resolution displays while still looking good.
  - jacobolus 17y ago
    It’s worth it to use some inter-letter spacing anyway, even if the spaces can only be whole numbers of pixels, because it avoids exceptionally wide or narrow word spaces.
- deleted 17y ago
  [deleted]
- bramstein 17y ago
  Not at the moment. Intra character spacing or Microtypography is a bit of a controversial subject among some typographers. Currently I'm leaning towards not doing it. Regardless of that, it would also make the implementation much more complicated (or impossible) as it requires access to the kerning tables which, as far as I know, is not possible from a canvas context. I would be very much interested in an open-source hyphenator (I'm aware of some other JavaScript implementations of Liang's algorithm) as I was planning to either use an existing one or to implement it myself.
  - jacobolus 17y ago
spicyj 17y ago
Impressive! Doesn't work in iPhone, sadly. Not sure why not, because Canvas is supported, I think. Might be possible to make text selectable, but looks like a huge chore: http://stackoverflow.com/questions/1451635/how-to-make-canvas-text-selectable/1457088 http://stackoverflow.com/questions/1451635/how-to-make-canva...
- jacobolus 17y ago
  Older versions of Webkit canvas don’t do text I don’t think. Not totally sure.
  - bramstein 17y ago
    I use the new Canvas Text API, which---I guess---isn't supported by the iPhone. It would be fairly straightforward to make it use the old text API. I chose canvas as an output format for this demonstration, the algorithm itself knows nothing of canvas, so it could be adapted to use whatever output format is suitable for a device.

86 points by bramstein 17y ago

This is great news. However, having a Knuth & Plass line breaking algorithm without hyphenation is like sex without a partner. Pretty much useless. The good points you get from using a total fit algorithm is much less then you lose from lack of hyphenation. If hyphenation is implemented, this will be very great!

mbrubeck 17y ago
Now that Firefox 2.0 is history, you can reliably use soft hyphens to hyphenate HTML text, and there are JavaScript libraries to do the hyphenation on the client: http://www.mnn.ch/hyph/hyphenation1.html http://www.mnn.ch/hyph/hyphenation1.html
jacobolus 17y ago
Well, hyphenation isn’t too hard, since there are reasonable solutions that can be used directly or easily ported. (There are existing javascript hyphenation libraries floating around.) The real problem with all of this is that everything is being done in a canvas element, which means no text selection, no searching, etc. etc.
- bramstein 17y ago
  Hyphenation is definitively on my to-do list. As you said, it will improve the output of the canvas tremendously. The canvas is just a way to show the output of the line breaking algorithm. Earlier I had an example on my website of a dynamically created DOM paragraph using the Knuth & Plass algorithm. That way, the rendering was done by your browser (i.e. select, searching, etc. was possible) while the line breaks were handled by the algorithm. Unfortunately I haven't been able to get it reliable on all browsers, so I took it out before I posted this item. It's still on my Github repository: http://github.com/bramstein/javascript/tree/master/src/typeset/ http://github.com/bramstein/javascript/tree/master/src/types...
  - elblanco 17y ago
    I'm definitely following this and waiting for when you get the browser rendering complete. The could be really great.

ZeroGravitas 17y ago

Does the TeX algorigthm reduce rivers in the text, or is that just a coincidence? http://en.wikipedia.org/wiki/River_(typography) http://en.wikipedia.org/wiki/River_(typography) edit: re-reading this seems to follow naturally from reducing the size of the gaps between words, which the algorithm does.

patrickg 17y ago
As you said: the Knuth/Plass algorithmn does not reduce or even detect rivers. Detecting rivers can be done in linear time, but reducing is very likely to put the algorithm in a higher time complexity class (which is almost linear with input length for the normal algorithm!).
jacobolus 17y ago
Rivers are killed naturally except for pathological edge cases when you (a) do proper hyphenation, and (b) do something like the TeX algorithm for paragraph layout, and (c) adjust inter-letter space as well as inter-word space.

stralep 17y ago

Why current browsers are not using this, or some improved version of this algorithm?

jacobolus 17y ago
The claimed reasons are (a) it would take work to implement, and (b) it would be slower than the current method. Both seem like pretty weak excuses to me. The main real reason is likely that most users don’t care, and so they can get away with it.
- lambda 17y ago
  Speed is a pretty important reason, and users not caring is also a pretty important reason. Users do care about speed, and don't care about absolutely ideal line breaking; so why trade off something they do care about for something they don't?
  - jacobolus 17y ago
    Well, it was an important reason in 1990, maybe, or even 1995. But we’ve had a couple of orders of magnitude improvement in computing speed since then. There’s no reason to favor some marginal speed advantage (tenths or hundredths of a second) to better layout.
    - lambda 17y ago
      Tenths of a second can be pretty damn significant. Every tenth of a second extra load time leads to approximately a 1% drop in sales, according to research done by Amazon. One of the big points of competition between browsers these days is in speed. Part of the reason people switch from IE to one of the more modern browsers is because they are just that much snappier.
      - jacobolus 17y ago
        Maybe. Though the only time there’s going to be a noticeable slowdown is when you’re dealing with huge amounts of text. Like an amount that will take 20 minutes or an hour to read. At that point, an extra 10th of a second to render, in return for a much more pleasant reading experience seems like a no-brainer trade-off. On a typical Amazon page the difference is going to be unnoticeable.

grayrest 17y ago

Do you have any plans on intra-character spacing as well? I know this is done in print to reduce the word gaps in justified text but I'm not sure if the resolution on screen would allow it. I have a  hyphenator using Liang's algorithm as a YUI3 module if you're interested.

lambda 17y ago
If you used sub-pixel alignment, it might be worth it. I just wish we could get 300dpi displays for our computers already, and stop worrying about the pixel grid. But, we're going to need some better techniques for resolution independent UIs before that happens. In particular, you will probably actually need better hinting for vector based UI graphics, so that the same vector graphics that can be used for high resolution displays can also be used for lower resolution displays while still looking good.
- jacobolus 17y ago
  It’s worth it to use some inter-letter spacing anyway, even if the spaces can only be whole numbers of pixels, because it avoids exceptionally wide or narrow word spaces.
deleted 17y ago
[deleted]
bramstein 17y ago
Not at the moment. Intra character spacing or Microtypography is a bit of a controversial subject among some typographers. Currently I'm leaning towards not doing it. Regardless of that, it would also make the implementation much more complicated (or impossible) as it requires access to the kerning tables which, as far as I know, is not possible from a canvas context. I would be very much interested in an open-source hyphenator (I'm aware of some other JavaScript implementations of Liang's algorithm) as I was planning to either use an existing one or to implement it myself.
- jacobolus 17y ago

spicyj 17y ago

Impressive! Doesn't work in iPhone, sadly. Not sure why not, because Canvas is supported, I think. Might be possible to make text selectable, but looks like a huge chore: http://stackoverflow.com/questions/1451635/how-to-make-canvas-text-selectable/1457088 http://stackoverflow.com/questions/1451635/how-to-make-canva...

jacobolus 17y ago
Older versions of Webkit canvas don’t do text I don’t think. Not totally sure.
- bramstein 17y ago
  I use the new Canvas Text API, which---I guess---isn't supported by the iPhone. It would be fairly straightforward to make it use the old text API. I chose canvas as an output format for this demonstration, the algorithm itself knows nothing of canvas, so it could be adapted to use whatever output format is suitable for a device.