Experiments in Constraint-based Graphic Design (2019) | Hacker News Reader

Experiments in Constraint-based Graphic Design (2019)

anishathalye.com

62 pointslosfair9 comments

Hmmmm... I can't help but feel like this technique is related to the TeX layout engine.

If you've ever read Knuth's TeX design, you'll know that TeX has a intricate solver to determine the "badness" of lines. The spaces between words (and sentences: such as the ".") will be manipulated to minimize the "rivers" of poor-justification algorithms.

Today, instead of manually writing a constraint-solver like Knuth did for TeX in the 1980s, it makes sense to leverage open-source solvers like Z3.

-----------

We can see that TeX is simply a domain-specific language that puts glyphs (in the form of letters) into a set of constraints... constraints of the form "width = target_size +/- adjustable_size".

And TeX is simply a constraint solver that iterates over all possible combinations (!!!) and selects the set of adjustable_sizes for all glyphs for the best looking paragraph (where "best looking" paragraph is a set of calculations Knuth thought looked good back in the 1970s/1980s).

Knuth proved that TeX's solver traverses across an NP complete problem. But it turns out that written paragraphs are "small enough n", and that exhaustive search (with some good heuristics to speed things up) is possible on computers, even computers 40 years ago.

-------

I also can't help but feel like a lot of UI-design is about layout engines like this. Flexbox makes my head hurt but having the web-browser "solve" constraints that I gave it is more flexible across different devices (phone vs 1080p laptops vs ultrawide desktop screens).

Constraints are already used for 3d CAD for engineers (this point must match that point. This angle must be 2/3rd of that angle. Etc. etc. Computer, now solve for the shape). Using them as 2D designs for GUIs, figures, and text only makes sense.

I think the trouble with a general purpose constraint solver is the results sometimes aren't what you expect or want. The best example of this is the Apple constraint system for screens used in XCode, so much time can be spent debugging constraints.

Certainly.

It should also be noted that 'constraints' are about as generic a word as 'Object Oriented Programming'.

Some constraints are easy to understand and use: such as TeX's constraints on spaces between words. I don't think anyone has ever really had an issue (aside from when the solver can't find a solution and you are forced to reword the paragraph). TeX "just works" and is probably the easiest constraint solver to use in practice.

In contrast, Apple constraints seem to be pretty complicated: https://developer.apple.com/library/archive/documentation/Us...

Manually selecting multipliers + constants is... non-intuitive and seemingly inflexible. Sure, its a list of constraints but that's not as useful of a search space IMO.

----------

Knuth's TeX system purposefully chooses an NP-complete representation that is well known to be "inefficient" and fails to scale.

It just so happens that paragraphs of text are naturally short enough to work with TeX in virtually every case. People don't seem to write paragraphs "too long" for the algorithm to handle.

There's an extraordinary amount of search space the algorithm is given. Its practically a "Knapsack problem" solver.

-----

So the goal is to find:

1. A system of constraints

2. That is easy to understand

3. That is powerful enough to represent "nice looking" layouts (or text, or images)

4. That may or may not be "efficient" to solve, but is "efficient enough" to work on practical problems.

This blogpost absolutely fails at #2, as it has basically created a new programming language API!! However... its probably a good stepping stone towards finding the "simple set of constraints" we want for practical use.

The next step is to probably play around with this solver ourselves, and then discover a subset of primitives that is easy to understand and describe.

AFAIK, TeX only gets really complicated when a document contains pictures (which it can move forwards or backwards relative to the text, if that leads to a better layout)

For text, https://en.wikipedia.org/wiki/TeX#Hyphenation_and_justificat... claims O(n²), with n the number of possible breaking points in a paragraph, or even O(nw), with w the width of a line.

As to the algorithm used by MacOS, that’s https://en.wikipedia.org/wiki/Cassowary_(software) (also used by the scwm window manager)

I find constraint solvers a perfect fit for window managers. For example, take a look at [1] what scwm [2] could do 21 years ago. Sadly (for me) modern window managers (on Linux or Windows) are way inferior to something we had in the past, usually employing something half-baked that often doesn't work correctly.

[1] https://www.youtube.com/watch?v=SCMUxj2f3Sc

[2] https://en.wikipedia.org/wiki/Scwm

As a Mechanical Engineer, I'm very happy to see designers discovering the joy of parametric CAD :-)

I have longed for this sort of functionality in tools like Inkscape, and have often resorted to SolidWorks, Fusion360, SolveSpace, or other engineering-focused tools for "artistic" projects, because they enabled me to quickly iterate over different parameters while respecting certain constraints and relationships (as shown in the original post).. Once I was happy with the result, I would export the design as DXF or similar, and do the final styling in Inkscape.

Previous discussion: https://news.ycombinator.com/item?id=21774018 (42 comments)

At time of previous post, the author was trying to rewrite in racket before releasing the code... did this get anywhere?

I have no entitlement at all to see it, but damn i still want to play with this!

I'm currently trying to create a programming language for UI designers, and my approach is very similar to this. Although, the language looks much less like a typical programming language since it's not meant for implementing an actual program, just an interface.

Reply on news.ycombinator.com