How I used linear algebra to build an interactive diagramming editor | Hacker News Reader

How I used linear algebra to build an interactive diagramming editor

medium.com

298 pointsbinshu46 comments

Cool, hadn't heard of Schemio before! https://schem.io/

Very slick look and feel :D

And it doesn't boast about it, but it's open source https://github.com/ishubin/schemio

Thanks! Schemio is open-sourced with the exception of the backend part of https://schem.io. But the frontend code is completely open and you can even host your own server. Although in that case it would simply use a file system as a storage, so no database and no user management.

Do you mean that there are two servers:

1. a basic open source one you can self-host,

2. and another closed-source one with accounts and other features that schem.io uses?

And (I'm just thinking out loud, and don't want to encourage any development as I am not a real user) is there a server-less embeddable version that perhaps just saves/loads locally with a javascript API for use in other apps?

Yes, but there is more than that. Actually there are 6 types of deployments of Schemio

1. Self-hosted, there is even a docker container available (https://hub.docker.com/r/binshu/schemio/tags). It does not have authorization and user-management, stores all diagrams on a file system. But it allows you to run server in write and read-only mode

2. https://schem.io - a service for collaborative editing and sharing of diagrams. This is obviously a closed-source for now and it uses the open-source frontend of Schemio

3. Schemio as a js library. Although I am not really releasing it to npm, just hadn't the time to work this out. But there is an option to build a js lib that lets you use Schemio as a Vue component. That's actually how I made it work on https://schem.io

4. https://schemio.app - Google Drive based frontend. All your diagrams are stored on Google Drive. Obviously you cannot share your diagrams, as they are only available to you. This is completely open-sourced and you can even build it yourself with npm

5. Static deployment. If you use option 1, you can export all of your diagrams into a static deployment and even host it on Github pages.

6. Standalone player of Schemio that lets you embed a single diagram on your website

I actually forgot about the 7th option - desktop app built with Electron. Unfortunately it's been broken for a while and the electron build fails with some weird error message. I just didn't have enough time to look into it since I am currently a single developer working on it.

That’s amazing!

Hats off to you for getting as far as you have, and don’t sweat the stuff you haven’t been able to get to yet. Nobody (hopefully) expects you to freely share the code you write in any sort of expected time frame.

These things take as long as they take :)

Is it possible to use programmatically? Basically I've been wanting to create an HDL diagram (for FPGA development) from source code to visualise the block interactions. It would be great to have a bit of interaction with the blocks that are created. No other tool I've seen can really do what's wanted.

Do you mean diagrams as code? something like PlantUML https://pdf.plantuml.net/1.2020.22/PlantUML_Language_Referen... ?

If that's what you mean, then no. I do have plans to work on this in the future, but I am not sure when I'll get the time for that.

Or do you mean just generating a diagram and posting it to Schemio programatically? This is possible, but it's not documented.

All diagrams are stored in JSON by the way and the structure is quite straightforward, so it shouldn't be too difficult to generate it yourself

I'm not sure honestly. I basically want to connect nodes with arrows and lines and have the resultant thing look sensible, and ideally interactive.

Oh, I forgot about another aspect of Schemio. You can make use of scripts and functions using SchemioScript language. Not sure if that is going to be helpful for your case, but you can take a look at this demo: https://schem.io/projects/schemio-demo-2tABbv50x2tGRHpS/docs...

If you go to edit mode and select the "Ball" object (in the top hiearchy), then go to behavior panel, you will find that it has a "script" action in the "Play" event. You can take a look at how I implemented that scene and perhaps get some insights for yourself.

Also I had a small section about SchemioScript in this article: https://medium.com/@ivan.ishubin/interactive-diagrams-for-co...

I use it when I need to build complex templates or interactive learning demonstrations like on Brilliant. For example a friend of mine is preparing similar interactive demos with Schemio for kids at school.

Another thing that Schemio has is the concept of classes, functions and arguments bindings. Unfortunately I did not have a chance to write an article or prepare a video for this. But the idea is that you can prepare a class, with complex behavior and even its own configurable arguments, and then you can select any object on the scene and specify that it uses that class. Again, I don't know your exact situation, but just laying out the options

That looks cool, thanks!

Maybe something like JointJS (https://www.jointjs.com/demos) or LiteGraph.js (https://github.com/jagenjo/litegraph.js) or DiagramMaker (https://awslabs.github.io/diagram-maker/?path=/story/docs-in...)

Isn't this normally particle at synthesis time?

If you want open source alternatives, I remembered seeing now a little while ago this https://blog.eowyn.net/netlistsvg/ but never tried it myself, you might give it a go.

I love the way you can zoom in for a diagram with more detail and them easily zoom back out. This is what I wanted from Obsidian but it isn't quite as slick.

This idea came to me after my first on-call, when I had to quickly figure out what is going on in a distributed system of 200+ micro-services. That's why I focused on embedding documentation into a diagram and being able to zoom into the parts of a complex system as much as you can. So that you stay focused on the entire picture. The alternative is to jump between multiple Google Docs/Wiki/Readmes for multiple services and read tones of text.

Transformation matrices were popularized by Adobe PostScript in the 1980s. SVG heavily borrows from PostScript imaging model. See links below for PostScript's use of 2D matrices:

https://personal.math.ubc.ca/~cass/graphics/text/old.pdf/las...

https://scientificgems.wordpress.com/2014/11/28/mathematics-...

Popularised by Adobe?

Don’t you just learn transformation matrices in algebra?

You learn matrix multiplication in algebra, not its application to do affine transforms in 2D graphics.

I started learning rotations, translations, scaling, shears using matrices in high school.

Affine transforms are apparently attributed to Mobius and Gauss. That’s like the 1700s.

What is vector based 2D graphics if not a direct application of geometry? Were we not using well known maths results when 2D graphics was first implemented on a computer?

Nearly all modern 2D graphics systems are modeled after PostScript, including PDF, SVG, Java's Graphics2D, etc. In fact, Adobe employees contributed to the specifications of those technologies. Based on that I'd say PostScript popularized it. Other 2D graphics libs such as X-Windows, AWT, Windows GDI, Apple QuickDraw etc. didn't support transformation matrices. Maybe they never heard about Mobius and Gauss?

> What is vector based 2D graphics if not a direct application of geometry? Were we not using well known maths results when 2D graphics was first implemented on a computer?

We were, but in high school, they aren't teaching you computer graphics, they're teaching you how to apply weirdly specific rules to transform some scribbles into more scribbles, for no good reason - hence the common student question, "what will I ever need that for?".

FWIW, I actually got into gamedev as a hobby as a kid, and it saved my life prospects, because it gave me a reason to be interested in trigonometry and algebra - all those random scribble transformation rules were directly applicable to problems relevant to me, such as "how do I rotate the bitmaps that are spaceships and rockets and turrets?", and such.

Author may wish to look up:

https://en.wikipedia.org/wiki/Homogeneous_coordinates

Hi, I am the author. Thanks for your suggestion! I will definitely go through that article, once I have some time. Just had a quick glance and it looks like there is also a section about transformation matrix, which is what I have been using

Great indication of the power of linear algebra! One little nitpick: not all transformations can be expressed with matrices, only the linear ones. Once you homogenize, you can get the affine ones (like linear, but allowing for translation, so that you don't need to respect a fixed origin). However, you can't, at least not without considerable violence to your coordinate system, express a transformation that, e.g., scales distances quadratically instead of linearly. Fortunately, as you suggest, this doesn't seem to be a transformation that's needed a lot in routine graphical editing.

Also, if you wanted to, you could juice up your discussion of the importance of performing transformations in the right order to introduce the idea of conjugates (https://en.m.wikipedia.org/wiki/Inner_automorphism) and commutators (https://en.m.wikipedia.org/wiki/Commutator). Although in your context introducing these explicitly might just make the exposition more complicated, they are useful tools to have in your general toolkit. (Conjugacy in particular, as you implicitly discuss, is practically built to express the idea "change from inconvenient coordinates to convenient ones, transform in convenient coordinates, then change back.")

This is cool summary of building editors. And good summary of linear algebra.

But don't all editors use linear algebra?

Technically yes, we can say that all graphical editors rely on linear algebra for various purposes. It's just that not all of the problems are obvious to anyone who starts developing something like this. That is why I decided to share some of the challenges I had encountered from a math perspective. I guess the main point I wanted to make is how matrices simplified the calculations for me even though I already used linear algebra.

Also another point is that, if you rely on SVG for rendering you could get away with just the code without thinking too much about the math involved. For instance if I wouldn't have introduced object hierarchy, I wouldn't even have to bother with math at all. SVG can take care of all the transformations, I wouldn't even have to know that matrices exist and that I could use them in svg objects 1-on-1. Dragging an object without a hierarchy would also propably be much easier, all I had to do is to change the translate(x,y) inside of the svg transform attribute.

I had a similar experience: I built dragging and handle resize, then later added rotation via a bit of trigonometry. Each operation worked fine separately, but if you tried to rotate and then resize, unexpected things happened. I left the bug for years, thinking I needed to come back and just add a bit more trigonometry to get rotated resizing working. When I finally came back to it I spent quite a while hacking at it before realizing that matrices were a much better way to describe the solution.

You might be interested in GraphBLAS (using linear algebra to run graph algorithms):

https://graphblas.org/

Take a look at QGraphicsView framework, https://doc.qt.io/qt-6/graphicsview.html it's one of the most powerful graphics frameworks I've used. In addition to scene-to-object transformations (with object hierarchies) it gives you many powerful tools to render complex, interactive scenes.

Alas, I have not found a web equivalent that works as well as QGVF.

Schemio looks cool. I've been building a lot of flow diagrams using Claude, which outputs to Mermaidjs (and renders it in the browser). I would love to do something similar with Schemio given the improved zooming in/out from flow to sequence, etc features.

A cool aspect to using 3x3 homogeneous matrices to translate in 2D is that the 2D translation is actually a shear in 3D along the z = 1 plane.

https://youtu.be/AheaTd_l5Is?t=263

On a related note, https://webglfundamentals.org/webgl/lessons/webgl-scene-grap... and everything in https://webglfundamentals.org is a great read and also provides a solid intro to (hierarchies of) transformations.

Very interesting article and software, personally has been looking for robust open source software for diagraming but strangely schemio never appeared on my radar.

I've got the feeling that it will be more intuitive to use geometric algebra instead of linear algebra for the transformation and animation [1].

[1] Projective Geometric Algebra:

https://projectivegeometricalgebra.org/

I wonder—when you move an object with a lot of children, between frames you have to update the A(i-1) term for all children (and then iteratively through the grandchildren, so on and so forth). Does this become costly? Or maybe it isn’t so bad for reasonably-sized figures?

Yes, I still have to update the transformation matrix for every children on every movement of any of their ancestors. But it doesn't cause a significant performance drop so far. Currently it is only computing it just in case, but it is actually not affecting the SVG elements at all so they do not have to be updated. The only reason for re-computing this transformation matrix is if I would have to know the local-to-world coordinates of a particular object, when readjusting the attached connector or doing some other logic based on their positioning

Equal parts cool and informative. Thanks for sharing! I've learned a lot.

Absolutely gorgeous and probably even worth actually using

> Since all the transformation matrices are 3x3, a 2D point needs to be represented as a 3x1 matrix.

I'm confused by this. Why use a 3D matrix for a 2D transformation?

It's not a 3d matrix. It's a 3x3 matrix. To do 3d transformations you need a 4x4 matrix.

OK, then I'm confused about this:

"For example, a point in space is a 3×1 matrix. To transform it, you multiply it by a 3×3 transformation matrix."

It seems we're transforming a point in 3D space using a 3x3 matrix, no?

As a sibling comment mentioned, translation is not linear so say you want to move your box a bit to the left. You can't do this by multiplication by any 2x2 matrix. This is because what you need is an affine transform and what you have is a linear transform. So you can scale things, rotate them and shear them (squish them along the diagonals) but what you can

...do is pop up a dimension, shear in that dimension, then project into your original dimension. This will make sense if we think of an example.

Say we're working in 2d and have a unit square starting at the origin and we want to translate it right by 1. This is not possible with any kind of matrix multiplication by a 2x2 matrix. That's easy to confirm if you just try it but trivially the lower right hand corner is on the origin and anything you multiply by zero is going to be zero. So any 2x2 matrix you multiply the coordinates of your square by is going to result in something where that point is still at the origin.

So instead what you do is pop your square up a dimension into 3D. So now you have a unit cube. If you do a shear of the unit cube by 1 in the x direction (which is a 3x3 matrix multiplication), you can take the projection ("shadow") of the top face of the cube to get back into 2D and you'll find it's where you wanted it (moved over by 1).

I am sorry for the confusion in my article. I should have probably clarified that this is a 2D point in a 2D space. To make the transformations work correctly you need to represent a 2D point as a 3x1 matrix. And if you want to perform the same in a 3D space, then a 3D point should be represented as a 4x1 matrix, where the last row is always 1.

Translation is not linear, but you can represent it as a linear map on n+1 dimensional projective space. "Homogeneous coordinates" is the relevant phrase for computer graphics.

Start with the desire - we want to have an algebra of 2D affine transformations with composition and (usually) inversion.

We can represent this with the trick of "homogeneous coordinates", using 3D vectors with the last entry 1 and 3x3 matrices with the last row [0, 0, 1].

This is convenient because both mathematicians and programmers are familiar with linear transforms and matrices. It's in the comfort zone. There are many libraries.

However, it's wasteful to store all those extra 1's and 0's in memory. You can always replace the matrices with

class Affine2D { Matrix2x2 linear; Vector2 shift; };

and overload all the algebraic operators, including multiplication with 2D vectors.

Reply on news.ycombinator.com