Weeknote: 2024-W15

15 April 2024

I haven’t talked much about Manyfold’s development so far other than just pushing out code, and so I thought I’d start giving weeknotes a try. Prior warning though, I’m terrible at habits like this, so this may be sporadic, or disappear into nothing. I’ll start with trying to do a weeknote each Monday about the previous week’s progress.

So, last week was an interesting one. Normally I have to focus on the next NLNet milestone so I can keep getting paid, but last week I went off-piste a bit and ended up doing a load of things that were really useful, but leave me a bit behind on the whole paying-the-bills thing.

Mesh Analysis

It started out with trying to push out the v0.60.0 release; while I’d “finished” the mesh analysis work the previous Friday, there were some bugs that had popped up over the weekend when I ran it against my own collection, so I wanted to dive into those. Notably, the “is the mesh inside out” check wasn’t working properly in a few cases. I ended up disabling that check for now, until I can fix it. I also realised I needed to add a way to rescan an individual model, so that went in, which led to a refactor of a load of the background scan job code.

I also realised I needed to be able to turn the whole manifold check on and off, and leave it turned off by default. It’s pretty computationally expensive, so I really didn’t want to suddenly grind everyone’s instances to a halt while they analysed every single mesh. Once I had that, a few bugfixes, and a nice database config PR for from Aneurin Price, the release was finally good to go.

Of course, once you get code out there, I realised that the mesh analysis was way slower than it needed to be. The analysis itself is pretty quick, but the naïve STL loader I’d written for Mittsu was… not.

STL optimisation

Generally, when you have a 3d mesh, you have a list of vertices (the corners), and a list of faces (the triangles that make up the surface itself). Each triangular face will connect three of the vertices, so normally each face would store three indexes for the vertex list, e.g. [1,2,3], not the actual vertex positions.

STL (even in binary format) is pretty inefficient; it only has a face list, not a separate vertex list, and so the coordinate of each vertex is repeated in ever face that vertex is in. This is also how you can easily end up with cracks and other errors in STL files, if the numbers don’t quite match.

So, my initial code loaded in all the faces, then ran Mittsu’s merge_vertices! method to sort out all the repetition. Worked fine. But, by loading everything first, then merging, there’s a lot more CPU and memory used than is really necessary. I realised I could do a lot better.

I changed the code so it built a vertex list as it went along, and either found an existing vertex if it existed, or added it to the hash if it didn’t. Then the faces were stored directly with the index into the combined vertex list. This is very close to the way merge_vertices! was working anyway, just it did it as it went along. No more wastage!

Only problem was, it was twice as slow. That’s not right, it’s supposed to be quicker. I know computational geometry, this should be better! What gives?

Ruby Optimisation

This meant doing some proper profiling and optimisation; it’s been a long time since I’ve had to actually do any real algorithm optimisation, and it was a really fun rabbithole. I created a test file that loaded a mesh 10 times, then used stackprof to see what was happening; it’s flamegraphs were particularly useful.

The expensive stuff ended up being the insertion into the vertex hash, with the main thing being building the hash key. Unfortunately you can’t use a tuple (or thruple) as a hash key, so I needed a string key. I started with a fairly naïve approach, just converting the vertex coordinates to strings with the default to_s and joining them together. It worked, but it’s doing a load of work we don’t need.

We don’t need this thing to be human readable; can we turn the binary vertex data into a string more efficiently? Turns out we can, using Ruby’s Array#pack method, which does a bitwise conversion from an array into a binary sequence string. I’ve used the inverse, String#unpack in the STL loader already for parsing binary vertex data into floats, this just runs the other way round.

Changing over to pack was the big win, and ended up with the STL loader being twice as fast as my first implementation. That’s more like it. It’s still not super fast, but it’s about as efficient as I can get it while still being in Ruby. In time, I might move to a Ruby-wrapped native library for mesh handling, but for now, Mittsu is keeping me moving nice and quick, so that will do fine.

Email & Password Reset

Next rabbithole was because a friend of mine forgot the password he’d set up for my personal instance, which I took as a sign that I really should set up the password recovery capability for user accounts, which I’d descoped for the initial multiuser release. I’d done that mainly because it involved setting up email capability, and I wasn’t sure how to make that optional. Rails is great at making things easy to configure, but it’s not always obvious how to make such things optional. Sometimes you want to check things at app boot, but the configuration options aren’t available yet; it can get a bit awkward.

Anyway, a day down that hole as well, and we have optional email configuration, and if email is set up, password recovery, and with that and the optimisation, out went v0.61.0.

The Back Burner Takes Control

Not content with that, on Saturday my subconscious decided to explain to me how I should be presenting images in model pages, and how easy and quick it would be to do, so naturally I had to implement that straight away to scratch the itch. That came out in v0.62.0 on Sunday night. Also randomly I decided that release notes should be on the proper website, not just GitHub, so I wrote a script to import them automatically.

Week over and a lot of useful work was done. None of which I could charge for. Oops.

What’s Next?

So, here I am at the start of this week, thinking I really need to get back on the “work I can charge for” train. Currently, I’m thinking that conversion to 3MF is pretty low hanging fruit now I have a good STL loader and 3MF exporter, so that’s probably next up, perhaps followed by some exploration of my ideas for a progressive mesh transmission format, while my head is in the computational geometry space.

Feedback

Well; that’s the first weeknote for Manyfold. Was it interesting? Too long? Too detailed? Pointless waste of bits, get back to writing code? I’m interested in your feedback, so get in touch in the Fediverse at @manyfold@3dp.chat and let me know!

Bonus Feature

This week has been brought to you by RAINBOWS by Dead Pony, which I can’t stop listening to, and who I just booked a ticket to go see live in July in Guildford. SWEET.