Undergraduate Research Thesis
This project is on github: Link
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:
- The 12d Printer was a somewhat outlandish concept of using multiple print heads one printer concurrently
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:
- Using existing GCode from some other slicing software
- Operating on a single layer at a time
- Take the chains of coincident segments and see which chains can be printed concurrently
- For chain pairs using a greedy algorithm
- Link the chain pairs together using free non-print moves
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:
- For the sake of computing time, segments were assumed to be the same small length which may cause time estimates to be off (I overestimated where possible)
- The segments, when paired are assumes to take the same amount of time to print (which may not be true in the case of the gantry style and items with different angles relative to the gantry)
- There is an inherent need for synchronization between the print heads (which is complicated by motion controllers doing look-ahead planning for acceleration/deceleration; it may be hard to give a guarantee for a segment pair without simulating many other pairs)
- Acceleration, Deceleration, Stopping in one spot, temperature, extrusion speed, extrusion amount are all parameters that are manipulated to affect the quality of the resulting part (and things like synchronization may inadvertently influence these parameters)
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
