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.
