Musings from Carbon’s Engineers
Thermoformed Aligners
By Christian Pederkoff, February 25, 2021
The problem
When I tell people I work as a programmer at a 3D printing company they are surprised when I tell them I don’t work on the machine itself. What does a 3D printing company need with a backend engineer? Actually, a lot of work goes into building software tools to help users before, during, and after the print. Examples include aggregating and displaying data about prints, systems to quality-control printed parts, and automatically generating ready-to-print builds. I want to take you through that last one.
Another question I get asked a lot is: “When will 3D printing catch on?” It turns out there’s an industry that’s been using 3D printing to make parts for over 20 years. And you may have used these parts personally. That ~$3 billion industry is… *drumroll*… Thermoformed Aligners. The teeth straightening alternative to braces.
Dentists take a 3D scan of a patient’s teeth, make a series of 3D models with progressively straighter teeth (anywhere from six to forty-eight models, depending on the patient) and print them out.
They then form the plastic aligner over the models and give these aligners to the patient.
You might be asking “Where’s the interesting software challenge here?” I’ll get to that.
The API
We want to make our customers as efficient as possible, so we automate some of their process for them. We provide an API where they can upload groups of models belonging to the same patient, and we return ready-to-print model arrangements.
Deciding what to pack
Customers send us groups of models which can vary wildly in size. We need to make efficient prints, which means that we want to use all the available surface on the printers. We can usually fit close to 30 parts on a print which means we need a system that can take different sized groups of parts and make similarly sized printable arrangements. After they print, customers put aligners back into their original group.
We have two main goals:
- Get as many parts on a print as we possibly can
- Keep groups of parts together as much as possible
What we have is a serialization/deserialization problem. Though in our case instead of over-the-wire it’s over-the-…printer?
In theory, the packing algorithm looks roughly like this, with orders coming in on a rolling basis:
In practice, life is never so simple.
Rejection stings
People’s teeth are different. Bigger mouths mean fewer parts will fit on a print. We don’t know how many parts will fit on a platform until we try to pack too many. By giving the packer too many parts we ensure it’s always producing totally full prints. This means that, unfortunately, the packer always kicks out a few parts that will need to be packed in the next pass.
Here’s what packing looks like with rejections:
When we reject a part that doesn’t fit, we’re rejecting it based on its shape and not what group it belongs to. What’s wrong with this? Well, now we’re breaking up the groups more than we need to. In the gif above, a red part is rejected in the first pack leading to a print with 3 different groups. This entropy then cascades over 8 hours of printing and we can easily end up with 4+ different groups on the same print. That slows our customers down because they have a bunch of mouths to sort off of a single print. We can do better.
Defrag
What if we only reject parts from the last group? If we do that, it ends up looking a lot better:
Instead of rejecting a random part, we only reject parts from the leftmost group. This keeps fragmentation down in the midst of rejection. Of course, there are always edge cases surrounding customer needs that will throw a wrench in simple optimizations like these, so there are endless opportunities for improvements.
What else?
Running parallel packers with a shared input queue is the next step because we need more throughput. But this brings new challenges. Naively parallelizing leads to fragmentation.
Next, there’s dynamically scaling up and down the number of parallel packers while, you guessed it, keeping fragmentation down.
Both of these problems could be their own blog post, but rest assured that we are working on solving all of them.