cavac has asked for the wisdom of the Perl Monks concerning the following question:

I'm the first to admit that my math skills are limited. "Normal" math is no problem, nor is writing software that deals with stuff like basic accounting or sensor data conversion. But i'm completely stumped by linear algebra and matrix multiplication.

I own a Boox Note Air, and there is python code that can render notes from the old export format. I'm currently in the process of reverse engineering the new format(*), and i think i found nearly all the data i need to write a new renderer in Perl. From what i can tell, the export format has changed, but the internal representation of the data in the software (and the rendering process) has stayed pretty much the same.

Unfortunately, the points that define a drawn line aren't saved as coordinates per se, but need to go through some matrix math before the screen coordinates are obtained. I think that's so that you can scale or rotate a line without loosing the original coordinates or something along that.

The old program has this python code:

if matrix is None: # Compatibility with older note format matrix = np.eye(3,3) else: matrix = np.asarray(json.loads(matrix)["values"], +dtype=np.float32).reshape(3,3) d = np.frombuffer(points, dtype=np.float32) d = d.byteswap() d = d.reshape(-1, 6) pressure = (d[:,2] / pressure_norm) ** pressure_pow # Projection matrix points = d[:, :2] points = np.concatenate((points, np.ones([points.shape +[0],1])), axis=1) points = points @ matrix.T points = points[:, :2]

As i said, i don't understand enough about matrices (or python for that matter) to translate that code to Perl. Can anyone help me on that?

Here is the code i have so far for reading the basic SQLite databases, Testfiles and some of my guesses on the format of the binary "points" blobs:

I generated a number of test files for the basic drawing system. The tarball is available on my webserver and it also includes the PNG export of all pages generated by the Android app.

The ShapeDatabase.db holds the list of all notes (and a list of their pages) as well as virtual directories and stuff. I deleted everything except the test files.

The next step is to open the SQLite database corresponding to the UID of the note. This then holds the data for all the shapes (and images and text) on each of the pages of that note. Each shape also comes with a transformation matrix (for resize and rotation i guess) plus a lot of flags (if the shape is visible and whatnot).

The binary "point cloud" file then holds the points lists for each drawn shape.

My current code for finding the proper UIDs is the following proof-of-concept mess. I started implementing to do the actual drawing, but got stuck while reverse-engineering the math:

#!/usr/bin/env perl use v5.38; use strict; use warnings; use DBI; use DBD::SQLite; use Data::Dumper; use JSON::XS; use Carp; my $basedir = 'Testfiles'; if(!defined($ARGV[0])) { croak("No note name given!"); } #my ($WIDTH, $HEIGHT) = (XXXXXXX my $notename = $ARGV[0]; my ($noteuid, $pages) = getUID($basedir, $notename); print "Note has UID ", $noteuid, " with ", scalar @{$pages}, " pages: +", join(', ', @{$pages}), "\n"; my $pagecount = 0; foreach my $page (@{$pages}) { my $pagefname = '' . $notename . '_page' . $pagecount . '.png'; $pagefname =~ s/\ /_/g; renderPage($basedir, $noteuid, $page, $pagefname); } sub renderPage($basedir, $noteuid, $page, $pagefname) { print "******* $pagefname *******\n"; my $fname = $basedir . '/' . $noteuid . '.db'; if(!-f $fname) { croak("File $fname not found!"); } my $dbh = DBI->connect("dbi:SQLite:dbname=$fname","","") or croak( +$!); my $selsth = $dbh->prepare("SELECT * FROM NewShapeModel WHERE docu +mentUniqueId = ? AND pageUniqueId = ? ORDER BY id") or croak($dbh->errstr); if(!$selsth->execute($noteuid, $page)) { print $dbh->errstr, "\n"; $dbh->disconnect; croak("DB Error"); } my @lines; while((my $line = $selsth->fetchrow_hashref)) { # de-JSON certain fields foreach my $key (qw[boundingRect matrixValues shapeLineStyle s +hapeCreateArgs]) { if(!defined($line->{$key}) || $line->{$key} eq '') { $line->{$key} = {}; } else { my $tmp = decode_json $line->{$key}; $line->{$key} = $tmp; } push @lines, $line; } } #$img = GD::Image->new($self->{width}, $self->{height}); #$imgblack = $self->{img}->colorAllocate(0, 0, 0); #$imgwhite = $self->{img}->colorAllocate(255, 255, 255); return; } sub getUID($basedir, $name) { my $fname = $basedir . '/ShapeDatabase.db'; if(!-f $fname) { croak($fname . " not found"); } my $dbh = DBI->connect("dbi:SQLite:dbname=$fname","","") or croak( +$!); my $selsth = $dbh->prepare("SELECT * FROM NoteModel WHERE title = +?") or croak($dbh->errstr); if(!$selsth->execute($name)) { print $dbh->errstr, "\n"; $dbh->disconnect; croak("DB Error"); } my $line = $selsth->fetchrow_hashref; $selsth->finish; $dbh->disconnect; #print Dumper($line); if(defined($line) && defined($line->{uniqueId})) { my $pages = []; if(defined($line->{pageNameList})) { my $json = $line->{pageNameList}; #print "JSON: $json\n"; my $decoded = decode_json $json; #print "Decoded: ", Dumper($decoded); if(!defined($decoded->{pageNameList})) { print "BLI\n"; } else { print "BLA\n"; $pages = $decoded->{pageNameList}; } } print Dumper($pages); return ($line->{uniqueId}, $pages); } croak("Note not found in ". $fname); }

Some observations/best guesses about the points cloud format:

(*) Reverse engineering the SQLite databases and the binary points lists is comparatively easy. All it takes is a few basic tools, a desktop calculator, half a dozen pages of notes in my absolutely awful handwriting, and the assumption that a good software dev is a lazy bum who just serializes their internal data representation to a binary file...

PerlMonks XP is useless? Not anymore: XPD - Do more with your PerlMonks XP

Replies are listed 'Best First'.
Re: Translating python math to Perl
by bliako (Abbot) on Aug 25, 2023 at 11:00 UTC
    • matrix = np.eye(3,3) creates a 3D 3x3 (thanks hv) matrix with 1's in the diagonal and 0 elsewhere. (or load it from JSON).
    • you mentioned points being byte data, np.frombuffer(points, dtype=np.float32) converts it into a list of float32. And then it swaps the bytes - re: little endian etc.
    • d.reshape(-1,6) converts above list into a matrix with number of cols = 6 and any number of rows it can fit.
    • d[:,2] the 3rd column of matrix d
    • pressure = (d[:,2] / pressure_norm) ** pressure_pow create a pressure vector based on d where each item is divided by pressure_norm and then raise to pressure_pow power. (I guess ** is raising to a power)
    • points.shape[0] is the number of rows of points (remember it was reshaped to have 6 columns and any number of rows it fits).
    • np.ones([points.shape[0],1]), create a vector of 1s (i,e. a matrix of 1 column, that's the '1' in the expression) with as many rows as the reshaped points of the last bullet
    • append that vector into points hence increase the number of rows by 1 adding a vector of 1s at the end.
    • points @ matrix.T I guess it transposes points (rows become columns) it is multiplying the matrix 'points' by the transpose of 'matrix' (see NERDVANA's Re: Translating python math to Perl).
    • points = points[:, :2] get the 3rd column (0-based indexing) of the current points

    my python is very limited so all above with caution. All the above can be done with pure perl but perhaps a dedicated module or PDL can be employed.

      Did a quick search and found that the '@' operator is matrix multiplication.

      So that line points @ matrix.T is multiplying the matrix 'points' by the transpose of 'matrix'.

      I'd say this really should be translated to PDL, because otherwise it's going to get very verbose. That's the real reason people use matrices in linear algebra - it is just too much fiddly math otherwise, and it's all fairly repetitive. Mathmaticians created "matrix math" just to simplify the notation for these common formulas. Unfortunately I don't know PDL so I can't help there.

        Jeez! my search was talking about overwriting methods.Talk of the snake with the forked tongue. I will update my answer.

Re: Translating python math to Perl
by NERDVANA (Priest) on Aug 25, 2023 at 21:06 UTC

    You might take another crack at linear algebra. It shows up fairly often in graphics, and isn't too hard to reason about once you create a mental model around what is happening.

    In case it helps, here is my mental model in a nutshell. Suppose you have an (x,y,z) point in a room. Suppose you are standing in that room at point (x2,y2,z2). The direction you are facing and angle of your head is represented as a 3x3 matrix. (ignore its contents for the moment) Suppose your task is to figure out what the coordinates of that point would be to the coordinate system of your eye. (in other words, imagine a coordinate system where your eye is (0,0,0) and forward 1 meter along your line of sight is (0,0,1) and so on) So you could describe any point in the room relative to the room, or describe it relative to your line of sight.

    You solve that problem by subtracting your eye (in room coordinates) from the point (in room coordinates) then multiply that by the matrix that represents the direction you are looking. Now you have a point relative to your eye's coordinate system.

    Now, what is the 3x3 matrix describing the direction you are looking? Well, the top row is the (x,y,z) vector (in room coordinates) sideways (leftward) from your eye. The second row is the (x,y,z) vector (room coordinates) if what your eye considers to be "up". And the third row of the matrix is the (x,y,z) vector (room coordinates) of what your eye considers to be "forward".

    So remember that initial subtraction we had to do before multiplying by the matrix? It turns out you can hide that step if you upgrade the matrix to 4x4 and write your point as (x,y,z,1). The same happens in 2D, by upgrading to a 3x3 matrix with points as (x,y,1). I think this is what you're seeing in that code above with the funny stuff it does before multiplying the point by the matrix. This wastes a few multiplications, but lets you describe it in one operation.

    If you want to map a point back out of a coordinate space, you just multiply by the "transpose" of the matrix. (swapping the columns and rows)

    You can map a coordinate space into or out of a coordinate space! Remember how the matrix is really just three vectors described in the parent coordinate space? Well if you map those 3 vectors into some other matrix, now you've mapped the whole coordinate space into the other coordinate space. This turns out to happen automatically by normal matrix multiplication. Just multiply a matrix by a matrix and you've got a new matrix that represents performing both translations. Now (if you have a lot of points to remap) you can actually save multiplications by only needing to multiply each point by one matrix instead of a chain of matrix multiplications.

    If that all made relative sense, then the rest is just implementation details which you can safely forget until you need them.

      You might take another crack at linear algebra.

      And here is the problem: I've never taken a crack at linear algebra. Believe it or not, i left school quite early. I just couldn't deal with the pressures due to my mental state, see also PerlMonks - my haven of calmness and sanity.

      I'm pretty sure your explanation is perfectly reasonable. I'm trying to wrap my head around it, but so far all i managed to do is give myself a headache.

      While i usually don't ask for other people to do my work for me, since this is going to be an open source project i don't have that much qualms about it: Could you, uhm, provide a code example on how the python code translates into actual perl code?

      PerlMonks XP is useless? Not anymore: XPD - Do more with your PerlMonks XP

        You've got me thinking about linear algebra, and I happened to doodle this up when I ought to have been doing work:

        package QDMatrix; use v5.36; sub new($class, $n_minor, $values) { if (ref $values->[0]) { $#{$values->[$_]} == $n_minor or die "Irregular column len in +matrix: $#{$values->[$_]} != $n_minor" for 0..$#$values; $values= [ @$values ]; } else { @$values % $n_minor == 0 or die "Un-rectangular number of values in data: ".scalar( +@$values)." / $n_minor = ".(@$values/$n_minor); $values= [ map [ @{$values}[$_*$n_minor .. ($_+1)*$n_minor-1] ], 0 .. int($#$values/$n_minor) ] } bless $values, $class; } sub flatten($self) { map @$_, @$self } sub clone($self) { bless [ map [ @$_ ], @$self ], ref $self; } sub dims($self) { scalar @$self, scalar @{$self->[0]} } sub major($self, $i) { @{$self->[$i]} } sub minor($self, $i) { map $_->[$i], @$self } sub mul($self, $m2) { my ($maj, $min)= $self->dims; my ($m2_maj, $m2_min)= $m2->dims; $min == $m2_maj or die "Incompatible matrix sizes: ($maj,$min) X ($m2_maj,$m2_ +min)"; my @ret; for my $i (0 .. $maj-1) { for my $j (0 .. $m2_min-1) { my $sum= 0; $sum += $self->[$i][$_] * $m2->[$_][$j] for 0 .. $min-1; $ret[$i][$j]= $sum; } } bless \@ret, ref $self; } sub transpose($self) { bless [ map [ $self->minor($_) ], 0 .. $#{$self->[0]} ], ref $self +; } my $identity= QDMatrix->new(3, [ 1,0,0, 0,1,0, 0,0,1 ]); my $x= QDMatrix->new(3, [ 4,5,1 ])->mul($identity->mul(QDMatrix->new(3 +, [ 1,0,0, 0,1,0, 2,0,1 ]))); use DDP; p $x;
        Well, yeah I probably could, although I don't really have time to learn PDL right now so it would just be some messy plain-old-perl. But maybe you like fewer dependencies anyway.

        Could you put together a unit test? Like maybe run through it once with Python and log the interesting variables at each line and then I can work toward making the perl generate the same values and not need to consult too many implementation details of Python?

        I'd be very happy to give this a go myself in due course, if you can show the python code with inputs and outputs.

        As shown elsewhere, I remain a bit of a noob at linear algebra (LA) myself. This includes IndexedFaceSet to 3D lines in two lines of PDL and the follow-on work in updating PDL's 3d demo, for which I needed to actually learn some LA. One really helpful resource for this was the YouTube channel 3blue1brown, and in particular his linear algebra series which visualises the geometric stuff that underpins LA: https://www.youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab.

Re: Translating python math to Perl
by Anonymous Monk on Aug 25, 2023 at 22:34 UTC

    I see some familiar motifs. Since this all is about scribblings in 2D plane, to quote PDF (same with Postscript) Reference (relevant pages are very simple and concise, no math):

    PDF represents coordinates in a two-dimensional space. The point (x, y) in such a space can be expressed in vector form as [ x y 1 ]. The constant third element of this vector (1) is needed so that the vector can be used with 3-by-3 matrices in the calculations described below.

    The transformation between two coordinate systems is represented by a 3-by-3 transformation matrix written as follows:

    | a b 0 |
    | c d 0 |
    | e f 1 |
    

    Because a transformation matrix has only six elements that can be changed, it is usually specified in PDF as the six-element array [ a b c d e f ].

    Coordinate transformations are expressed as matrix multiplications:

    | a b 0 | [ x' y' 1 ] = [ x y 1 ] x | c d 0 | | e f 1 |

    "e f" are to translate, "a d" to scale (let's omit rotation and skewing for simplicity). Suppose I want to translate by (32,64) and then scale by factor of 3:

    pdl> p $m = pdl '3 0 0 ; 0 3 0 ; 32 64 1' [ [ 3 0 0] [ 0 3 0] [32 64 1] ]

    And I have this dumb set of points:

    pdl> p $points = rint transpose cat sequence(10),sequence(10)/3 [ [0 0] [1 0] [2 1] [3 1] [4 1] [5 2] [6 2] [7 2] [8 3] [9 3] ]

    Then:

    pdl> p $points->append(1) x $m [ [32 64 1] [35 64 1] [38 67 1] [41 67 1] [44 67 1] [47 70 1] [50 70 1] [53 70 1] [56 73 1] [59 73 1] ]

    See? Coordinates were modified as requested.

    "Six numbers per row/point" are six numbers (3 x,y pairs) required to append a cubic bezier curve segment to path -- this is another one which rings the bell, but maybe it's false alarm and I misread what they are trying to accomplish.

Re: Translating python math to Perl
by harangzsolt33 (Deacon) on Sep 04, 2023 at 02:58 UTC