# How are infill paths connect to form an efficient path that respect the object's geometry?

I am attempting to write a basic slicer for some objects I am working with. I need to write a custom slicer as the objects are not polygonal based (they are implicit objects) and therefore cannot be plugged into slic3r. I can easily obtain the perimeter/shell of the objects I am working with and have a few successful prints. What I am having trouble with is how to add infill. I think the biggest hurdle is simply my inability to frame the question properly. How do current software tackle this problem?

I don't know of my current approach is feasible but if I have a collection of vectors that represent the path around the outside of the object and a collection of vectors that represent an arbitrarily large infill pattern is there a way to union the two paths together to from an outer path (the object shell) and an inner path that is the infill pattern cut out in the shape of the object?

EDIT:

Sorry for the lack of clarification. So lets say I cut out the infill pattern to match the inside of the object. How do I then intelligently connect all the broken infill segments together to form an efficient path that doesn't cross gaps or mess the object up in any way?

• Based on the answers you have already, it may make sense to edit your question to clarify how the answers don't really address the problem for you (assuming we missed something critical) – Sean Houlihane Sep 5 '18 at 9:09
• You sure it wouldn't be faster and easier to take your objects and run them thru one of the apps that creates a mesh? What is the exact format and content of your objects -- i.e. how were they generated, are they in any industry-standard format, etc? – Carl Witthoft Sep 5 '18 at 12:30
• @CarlWitthoft Unfortunately the objects are not industry standard and converting them back to a mesh would defeat the purpose of working with the implicit objects. – Chris Uchytil Sep 5 '18 at 18:41
• In my implementation (in c#) I iterated through the list of lines to check if the start point or end point are the same as the start or end point of the current line. If found then I removed it from the list and that new line become the current. All lines found would be added to a queue of points that I then turned into and array of points to make a path. – user77232 Sep 5 '18 at 21:51

The answer to this is pretty much basic algebra: The software tackles the problem by using a set of functions that generate the infill pattern for ALL the build volume, then discard anything outside the shells. Which is determined by algebra:

# Basics

### Outline Function

Assume the outline of the body is a function $$O(l)$$ that has a parameter $$l$$ for its length. This function can be calculated into XY coordinates, giving us $$y\mapsto O^{xy}(x)$$, that is parameterized after $$x$$, and should give us the values of $$y$$ for a closed function $$O(l)$$.

### Infill Functions

Now, let's generate a function for infill pattern. Let's make it easy for us and use a diagonals pattern: $$I_n(x)=x+n\times d$$ where $$d$$ is a fixed parameter for "distance to last line" and $$n\in\mathbb Z$$ is the number of the line with 0 passing the origin.

### Comparation: Outline=Infill

Now basic algebra! Let the computer solve for each $$n$$ the term $$O(x)=I_n(x)$$. The result should be (in the best case) paired points, all on the linear function $$I_n(x)$$. Sort these points by their correlating $$n$$ value first, then the $$x$$ values.

# Dealing with the results

Let's assume we have some banana shape and our solutions for n=0 are like this: $$P_{i=1 \to 4}=\{\{1,1\},\{2,2\},\{3,3\},\{4,4\}\}$$

## Modeling starter

On the most simple cases, we hope to only have paired results - the outline is closed and thus each line passing it has to cut it in multiples of two. Because we don't allow geometry to be below $$\{0,0\}$$, the line in this example will pass into the body at the first solution of these points and pass out of it at the second and so on. Generally: It moves in at odd and exits at even i. So our infill lines in the example need to connect $$\{1,1\} \to \{2,2\}$$ and $$\{3,3\} \to \{4,4\}$$.

# Enhancing the Modeling

## checking for tangents

Now, we might have an odd number of points that solve O(x)=In(x) for a given n. Let's assume $$P_{i=1 \to 5}=\{1,1\},\{2,2\},\{3,3\},\{4,4\},\{5,5\}$$.

Now we need to be careful as one of these points is guaranteed to be a point in which $$I_n(x)$$ is a tangent at of $$O(x)$$. So, we need to know the first differential of $$O(x)$$ in the points, which is the tangent at $$O(x)$$. But we don't need to solve all the points: We know the first should enter and the last exit the body, so we need (for most cases) to only solve this for the points $$P_i$$ with $$i=2 \to i_{max-1}$$. When $$O'(x)=I_n(x)$$, we got a tangent and remove this point from the list of points to connect with infill lines.

Because we could have several tangents in a set of points, this check has to be done for all sets of points to eliminate these points.

Also, I used the "usually" there by intent: there are cases where the first or last point is a tangent, and because it is easier to cose, we should run the elimination process over all $$P_1 \to P_{max}$$!

The new, reduced set of points will be a paired list: $$Q_{i=1 \to 4}=\{1,1\},\{2,2\},\{4,4\},\{5,5\}$$. The Infil connects $$Q_1 \to Q_2$$ and $$Q_3\to Q_4$$.

## Turning Points into vectors

Now, we have our points $$Q_1$$ and $$Q_2$$ (or any other pair of $$n \land n+1$$, where n is an element of the odd numbers), both on $$I_{n=0}(x)$$. How to connect? Easy! $$I{n=0}$$ is a function, most likely a linear one. Along this line has to be our connecting line from $$Q_1\to Q_2$$, so the movement we have to plot is the function of our pattern between the points. For a simple, linear pattern this would be:

$$L_1=\frac{I(x)}{|I(x)|} \times |\vec{Q_2}-\vec{Q_1}|+\vec{Q1}$$

# Optimisation

## Sorting properly

Now, we have a set of Lines $$L_n$$, where, as established in the last paragraph, n is an odd number declaring it has the lower-end $$Q_n$$, and the upper-end $$Q_{n+1}$$. How do we sort these lines smartly so we have the least movement? Let's take a look at our lists:

• The list of Pi, which contains all tangential points and end points. Not very helpful.
• The reduced list of $$Q_{n}$$, which contains all the start and end points; it is sorted in a way that odd numbers are starts, and even ends.
• The list of $$L_n$$ with i always being an odd number, that contains the movement paths (=lines) from each $$Q_{n}$$ to its corresponding $$Q_{n+1}$$

### Shortest movement between prints?

Now, let's do some math again: What is the closest $$Q_{a}$$ to the $$Q_{n+1}$$ we did end at after doing the $$L_n$$ movement? Well, first of all, we need to make sure we don't get back to already moved paths so let's make a new list $$R_{i}$$, which contains all the $$Q_{i}$$ we have not yet moved to.

So what is the closest $$R_{i}$$ to the end point of the path $$L_e$$ we just moved? Well, easy! Solve $$min|R_i-L_e|$$ with i being all the odd numbers in the list of $$R_{i}$$ and $$L_e$$ the point where the printhead was sent to at the end of the last movement

### fewest direction changes?

Always moving just the shortest distance might create a large number of direction changes. So it might be a good idea to keep the point-lists sorted by the parameter n of the function $$l_n(x)$$ that created the points in the first place, and run down that list from minimum n that generated points (which can be below 0) to the maximum n that generated points.

### optimizing direction changes & movement paths

Now, we have 2 approaches that pretty much only follow the pattern. However, we might make our average movement paths more efficient by using a simple trick:

Up to now, all our line functions $$l_n(x)$$ had the same vector and just a different starting point to one another. So all the starts were on one side of the body, all the ends on the opposite. With a very simple trick on the infill function we can generate a group of functions that alternate the sides of the end-points between each line, jsut by adding an inverse element:

$$L_n(x)=-1^n\times l_n(x)$$

Now, after all the movements with the same $$n$$ are done, check for the closest starting point (which should be on the same side, but is not necessary the neighboring line), and go down that line fully, eradicating these points from the list of remaining points $$R_{i}$$. Once back on the side we started first at, we look for the closest unused point again, run down that line, rinse and repeat.

• Just a quick clarification. Is this banana oriented so the line at n=0 cuts into it twice with a gap in the middle? The tangent makes sense. I've working with implicit torus/ray intersections and it works the same way. Odd means grazing (tangent ray) and even means penetrating ray. My question now is, how do you connect the end of this first line to the next line? That is where I'm stuck. Forming a path between all the cut infill lines to form a path. – Chris Uchytil Sep 5 '18 at 18:48
• yes, the banana in exampe 1 is bent in such a way that it bends around the middle of the "gap". – Trish Sep 5 '18 at 20:50
• @ChrisUchytil I did work out a few optimizations you could try: for a minimum number of movement changes and then the closest line to print. Mind it is not an optimization of calculation length but of the movement path. – Trish Sep 6 '18 at 11:09

simple answer is math but you know that for sure

more descriptive answer (but still simple and with no math) is more or less as follows

• slice an object with a plane to form (calculate) outline perimeter
• create a grid of infill according to your needs (ie: lines, grids or honeycombs)
• calculate where outline cuts your grid of infill
• abandon all what is outside
• sort cut points in some order ("some" is definitely the hardest task)
• join points according to your sort

and voila ;)

of course there is many details not mentioned in such description as distance between perimeter and infill, layer thickness and many others this is just very naive and silly description but it's just to direct you where to go further

generally there is great library which you could give a try

https://sourceforge.net/projects/jsclipper/

edit

simple sort (counter)clockwise could be like this

• set center point of the object (perimeter)
• start from 1200 hour and calculate module and angle of each cut-point
• sort them by angle

it's still very simple and it's working only for convex set

• Step 5, "sort cut points in some order ("some" is definitely the hardest task)" is where I am stuck. – Chris Uchytil Sep 5 '18 at 18:38
• well the simplest way seems to be sort (counter)clockwise ;) – darth pixel Sep 6 '18 at 5:05