[HN Gopher] How I used linear algebra to build an interactive di...
___________________________________________________________________
How I used linear algebra to build an interactive diagramming
editor
Author : binshu
Score : 200 points
Date : 2024-12-17 06:10 UTC (16 hours ago)
(HTM) web link (medium.com)
(TXT) w3m dump (medium.com)
| willvarfar wrote:
| 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
| binshu wrote:
| 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.
| willvarfar wrote:
| 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?
| binshu wrote:
| 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
| hgomersall wrote:
| 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.
| binshu wrote:
| 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
| tejohnso wrote:
| 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.
| amelius wrote:
| Author may wish to look up:
|
| https://en.wikipedia.org/wiki/Homogeneous_coordinates
| binshu wrote:
| 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
| JadeNB wrote:
| 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.")
| FrustratedMonky wrote:
| This is cool summary of building editors. And good summary of
| linear algebra.
|
| But don't all editors use linear algebra?
| binshu wrote:
| 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.
| munchler wrote:
| > 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?
| umvi wrote:
| It's not a 3d matrix. It's a 3x3 matrix. To do 3d
| transformations you need a 4x4 matrix.
| munchler wrote:
| OK, then I'm confused about this:
|
| "For example, a point in space is a 3x1 matrix. To transform
| it, you multiply it by a 3x3 transformation matrix."
|
| It seems we're transforming a point in 3D space using a 3x3
| matrix, no?
| seanhunter wrote:
| 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
| seanhunter wrote:
| ...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).
|
| <meta-point: apologies - my original response seems to
| have been chopped in half. I didn't mean to submit in
| this form and I was in meetings etc so it's too old to
| edit now>
| binshu wrote:
| 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.
| ndriscoll wrote:
| 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.
| blt wrote:
| 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.
| breadwinner wrote:
| 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-...
| 2muchcoffeeman wrote:
| Popularised by Adobe?
|
| Don't you just learn transformation matrices in algebra?
| breadwinner wrote:
| You learn matrix multiplication in algebra, not its
| application to do affine transforms in 2D graphics.
| airstrike wrote:
| Equal parts cool and informative. Thanks for sharing! I've
| learned a lot.
| dekhn wrote:
| 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.
| myrloc wrote:
| 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.
___________________________________________________________________
(page generated 2024-12-17 23:00 UTC)