Polygon infill algorithm

Question

I'm working on mesh slicing utility for 3d printing purposes. In general it should slice a 3d mesh model into 2d shapes (a number of polygons, probably with holes) and fill them with paths of determined thickness using a specific pattern. These paths will be used to generate a gcode commands for a 3d printer firmware.

There are various open source tools with same purposes, written on python and perl. But my goal is to understand the workflow of slicer and to write my own tool in C or C++.

So far I am able to get contour of slice and now gonna fill them with paths. The problem is I found no efficient algorithm to do this. A schematic process of infill example:

Can anyone advice how to generate these filling paths? Thanks.

---

Currently I'm using the following algorithm:

1. Find a bounding box of the shape
2. Split bb vertically with lines (number of lines = bb.width/path.thickness)
3. Find intersection points for shape and each line (should be two points per line)
4. Construct a segments from these points with offset from boundary
5. Add a segments which will connect an original segments together forming a line strip
6. We are ready to generate gcode or draw a path

This is simple and fast algorithm, but it does not work for concave polygons and polygons with holes. Also it uses only one specified pattern.

Answer 1

The approach below will produce a fill pattern that consists of a single path (i.e. the fill nozzle will never be turned off, moved, and turned back on), whenever this is possible.

After your step 4 ("Construct a segments from these points with offset from boundary"), turn each vertical line segment into a 2 or more points: the top and bottom endpoints, plus (imagine your diagram is drawn on a transparent slide; put a piece of paper with horizontal lines on it underneath, and mark where the vertical line segments in your diagram intersect the horizontal lines on the paper).

Now form an edge-weighted graph containing a vertex for each point, with an edge connecting two vertices whenever their corresponding points are less than or equal to one grid unit apart. Also add edges between adjacent topmost points of line segments, and between adjacent bottommost points. Use the Euclidean distance between the points for the edge weight. Finally, the magic part: find a minimum-weight Hamiltonian path on this graph. This is a path that visits each vertex exactly once, and has minimum length. The minimum length constraint guarantees that the path will never cross itself, since if any two lines cross, say the line from a to b and the line from c to d, then it would always be possible to create a shorter overall path by deleting these two lines and creating two new lines using a different combination of endpoints (either a---c and b---d, or a---d and b---c). This is the path that you will fill.

Finding a Hamiltonian path (let alone a minimum-weight Hamiltonian path) is an NP-hard problem that is closely related to the more famous Travelling Salesman Problem. Since many good exact TSP solvers already exist (e.g. Concorde), it would be sensible to instead use one of these to find a travelling salesman tour, and then simply delete one of the edges to produce a short Hamiltonian path. (Even if you delete the heaviest edge, this will not necessarily produce a minimum-length Hamiltonian path, since it may be that there exist shorter paths that don't begin and end at adjacent vertices; but we don't really care about the overall length here, we just want a path that visits all vertices and doesn't cross itself.)

Unfortunately, a graph is not guaranteed to contain either a Hamiltonian path, or a travelling salesman tour. (They obviously can't exist if the graph is disconnected, for example, but even connected graphs can fail to have either or both: e.g. a graph with any vertex of degree 1 cannot have a TSP tour.) In this case, if the TSP solver you are using can find tours that don't visit all vertices, you can just repeat this until all vertices are covered. Failing that, I would fall back on your original algorithm.

Answer 2

After some time of research I've ended at the following algorithm: There are a number of optimizations opportunity, though.