garyhodgson.com/reprap

Whenever I’m watching a print (because it can be hypnotising after all) I usually become acutely aware of any superfluous aspects of the design and how inefficient the fill patterns can sometimes be.  The fact that the model is sliced into layers leads quite naturally to filling each of these layers with a 2D pattern. The line and grid patterns from Skeinforge produce stable, solid objects from as little as 30% infill, and for the most part this is sufficient. I wonder though if we can find a better filling strategy? One that utilises the 3D nature of the model.

If the fill is to provide internal strength to an object and support any internal overhangs (ceilings), but also use minimal material, then I guess the ideal algorithm would analyze the model and identify where best to position struts, columns, butresses and such.  Taking into account the printers ability to bridge gaps and so on.

Mockup of model with "ideal" fill of struts, etc.

Even if such an intelligent algorithm is possible it would no doubt be so computationally intensive as to break another constraint we should define: that the fill pattern should be determined in a reasonable amount of time.

This is why the line algorithm works very well – it fits almost any organic or non-organic form, and can be computed relatively quickly. This is also demonstrated by the alternative fill patterns that Alessandro Ranellucci has implemented in Slic3r: hilbertcurve, archimedeanchords and the octagramspiral patterns are marked as “slow” and indeed can take a long time to generate for non-trivial models.

X-end-motor.gcode, Slic3r, Line Algorithm, @32s

X-end-motor.gcode, Slic3r, Hilbertcurve Algorithm, @7m 20s

As a sidenote, this highlights another observation I have made: that the current delineation between 3D model (usually STL format) and Gcode seems skewed, and some information that should belong in the model (e.g. fill structure) is delegated to the runtime process. I’ll hopefully expand on this in another post, but it’s worth mentioning here because perhaps our view of what a reasonable computation time is, would change if it is moved back along the workflow to model generation.

So the question: Is there a fill pattern, that provides the same strength and can be computed in the same order of magnitude as the line approach, but which uses less material?

Some Ideas

Some initial thoughts involve ways of packing other, simpler, 3D forms within the model, which leads to such things as the sphere packing problem.  In this case we would ideally find a solution that has a dense, irregular packing of unequal spheres, where each sphere is the largest possible size for the containing form. Here is where my woeful lack of mathematics causes a real problem. I suspect, but can’t be sure, that there is no way of determining such an ideal packing arrangement within the timescale constraints we have set (i.e. minutes, if not quicker).

This also highlights another aspect of the problem: the 3D model we are attempting to fill can be any arbitrary form. If the target model was always a cube, or even always a regular solid, we could potentially pull some tricks (lookup precalculated values perhaps?) in order to use a sphere packing approach. With the prospect of packing non-regular, and potentially very organic, models the problem becomes ever more difficult!

Sphere-Packed Model Example

Sphere-Packed Model, Slice Through

Another avenue of investigation is whether an arbitrary model can be divided into simpler shapes?  The assumption being that working on several simple solids would be easier and quicker than working on a simple complex shape.

Another idea involves using the vertices of the target model as a basis for generating internal edges, perhaps utilising Delaunay triangulation or something similar, but in three dimensions. This would have the benefit of being tailored for each model, but would it guarantee structural strength? How would such an algorithm work in three dimensions?

Mockup of slice with example triangulation between nearest vertices

Mockup of slice with example Delaunay triangulation (but not actually correct, only to give an indication)

Then something dawned on me: do we have to constrain the fill pattern to the boundaries of the target model? What if we had a pre-defined 3D fill pattern, say a honeycomb, which we intersect with the model to produce the fill pattern?

The pattern could potentially derive from a 3D Tessellation.

3D tessellation with truncated octahedron (via Wikipedia)

Further browsing online leads to Hyperbolic Planar Tesselations. I have no idea whether something like this could be utilised, but the fractal nature of how the pattern interacts with the boundary could yield ideas for resolving how to give strength to irregular, organic shapes.

Hyperbolic Planar Tesselations (via www.plunk.org/~hatch/HyperbolicTesselations)

Mock Print

In order to get a feel for the problem I decided to mock up such a pattern to print. This led to an interesting realisation, that the various tools available will each work with this solution to varying extents. I played with OpenSCAD, Google Sketchup, Skeinforge and Slic3r whilst trying to manually generate an example structure. I found that concept of internal structure in these tools is rather foreign, and I had to hack a bit to get some results. Most 3D modelling tools I have tried concern themselves with solids, the skin of the model, and not the skeleton. Perhaps there exist CAD programs geared towards engineering which use a skeleton + skin paradigm? Perhaps this is also worth investigating further?

In the end I used OpenSCAD to generate a cube filled with a set of sphere-spaces, and used Skeinforge to slice two models, one with zero infill and one with 30% infill.

It is worth mentioning that I attempted creating a similar structure in Sketchup, but using a real model (Mendel X Motor Mount) and a lattice of spheres (as shown a few paragraphs earlier).  Attempting to intersect the spheres with the model caused Sketchup to hang (or rather take an unacceptable amount of time to respond). This perhaps hints at the potential performance problems such a solution may have?

The printed model shows that, for a very basic target shape, the packed sphere approach yields a reasonably rigid object. It is certainly not comparable to a cube filled with 30% line pattern infill, but printing the mock gave me confidence that it is at least worth continuing to research such techniques.

Where Next?

The goal of writing this post was to collect some thoughts on the subject which I could refer people to for discussion.  It would be cool if someone more mathematically-minded could comment on the feasibility of such 3D space filling algorithms. Or if others have had similar ideas on the subject at all!

To summarise:

1.  I think it is worthwhile looking for more efficient fill patterns that take advantage of the 3D nature of the model it is filling.
2. The main obstacles are computational intensity and ensuring the resulting model has sufficient strength, regardless of its form.
3. It is worth reviewing whether current 3D modelling tools are suitable for defining such things as internal structure.  There is potentially an opportunity to develop something interesting here.

I’m going to try and find time to play further and try and throw together perhaps a script to preprocess a model, or perhaps implement a fill algorithm directly.  I will also look a bit more at existing tools to see if there is already something out there which allows the definition of internal support structures.

Any feedback would be very welcome!