I completed my Undergraduate Research Thesis on developing a solution to the planning problem for the 12d Printer Problem. This discussion builds on that so let me summarize the key points first:
For my research I tackled the project of two print heads in two configurations: the unbounded configuration where items can move freely and the gantry (most current IDEX printers) model. At a high level the algorithm is as follows:
For a more detailed discussion of the algorithm, I refer you to my paper on the topic. (TODO: Link)
What I want to discuss more is the software development process. A solution was developed first in Python and then transitioned to C/C++ as performance became an increasing focus.
Where I want to start is testing. The biggest problem that I ran into was a refusal to write good test cases (coupled with reinventing the wheel in many places). For example, rather than using a tested, public library such as Boost Geometry, I instead decided to re-implement the function that I needed: distance between two lines. This is a function built into Boost Geometry (Link). I knew Boost Geometry existed; I have no idea why I didn't use it. My guess: I had trouble with boost geometry and thought How hard can it be to reimplement myself? Turns out, it can be quite difficult, especially when there are no test cases. I lost alot of time to computational geometry problems that could be trivially solved with a library.
Once I had a working solution, it was relatively smooth sailing. A lot of tinkering and trying different algorithms and approaches. For this I used a public dataset of GCode files and could run my algorithms across the inputs. I used ideas from the 313 Wikipedia Indexer to make this enjoyable (namely multi-threading and having an in-flight progress readout). There were about 13,500 different files considered in total.
Results were somewhat promising. I showed that this simple algorithm could produce speedups on average 54% (unbounded config) and 13% (IDEX / Gantry config). These results should be taken with a grain of salt though.
The reason that this project never advanced was the controls theory side. A couple key assumptions were made that, I believe, have significance in the real world:
These problems are discussed more in the 12d Printer page.
For a more detailed discussion of the algorithm, results, and samples I recommend reading the paper. (TODO: Link)
In summary, an interesting problem with potential real world applications. The controls side probably needs more work (currently, April 2022) than the planning side. The biggest conclusion: this was another project which got squeezed against a deadline; I needed results to write the paper to graduate. Some day I may revisit it, but after the late nights it took to get it "done", the motivation hasn't been there.
Perhaps the most interesting future direction is to explore GPU acceleration of the collision detection. It should be possible to generate a 2D (bit) grid of which segments can be printed concurrently. This would provide a significant speed up; the calculations of collisions is the majority of the time. Some initial tests were run and results were promising. However, once the deadline pressure kicked in, it got quickly sidelined. It would be interesting to revisit with my new GPU programming experience from my CSCE 645 - Polygon Packing project
Various Models considered in the paper