<p>simple answer is math but you know that for sure</p>

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

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

<p>and voila ;)</p>

<p>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</p>

<p>generally there is great library which you could give a try</p>

<p><a href="https://sourceforge.net/projects/jsclipper/" rel="nofollow noreferrer">https://sourceforge.net/projects/jsclipper/</a></p>

<p><strong>edit</strong></p>

<p>simple sort (counter)clockwise could be like this</p>

<ul>
<li>set center point of the object (perimeter)</li>
<li>start from 1200 hour and calculate module and angle of each cut-point</li>
<li>sort them by angle</li>
</ul>

<p>it's still very simple and it's working only for convex set</p>

CC BY-SA 4.0
2018-09-05T18:38:11.667Z
Step 5, "sort cut points in some order ("some" is definitely the hardest task)" is where I am stuck.
Chris Uchytil
CC BY-SA 4.0
2018-09-06T05:05:28.227Z
well the simplest way seems to be sort (counter)clockwise ;)
darth pixel
CC BY-SA 4.0
2018-09-05T06:23:28.117Z
2018-09-06T05:10:40.117Z
2018-09-06T05:10:40.117Z
darth pixel
<p>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:</p>
<h1>Basics</h1>
<h3>Outline Function</h3>
<p>Assume the outline of the body is a function <span class="math-container">$O(l)$</span> that has a parameter <span class="math-container">$l$</span> for its length. This function can be calculated into XY coordinates, giving us <span class="math-container">$y\mapsto O^{xy}(x)$</span>, that is parameterized after <span class="math-container">$x$</span>, and should give us the values of <span class="math-container">$y$</span> for a closed function <span class="math-container">$O(l)$</span>.</p>
<h3>Infill Functions</h3>
<p>Now, let's generate a function for infill pattern. Let's make it easy for us and use a diagonals pattern: <span class="math-container">$I_n(x)=x+n\times d$</span>
where <span class="math-container">$d$</span> is a fixed parameter for &quot;distance to last line&quot; and <span class="math-container">$n\in\mathbb Z$</span> is the number of the line with 0 passing the origin.</p>
<h3>Comparation: Outline=Infill</h3>
<p>Now basic algebra! Let the computer solve for each <span class="math-container">$n$</span> the term <span class="math-container">$O(x)=I_n(x)$</span>. The result should be (in the best case) paired points, all on the linear function <span class="math-container">$I_n(x)$</span>. Sort these points by their correlating <span class="math-container">$n$</span> value first, then the <span class="math-container">$x$</span> values.</p>
<h1>Dealing with the results</h1>
<p>Let's assume we have some banana shape and our solutions for n=0 are like this: <span class="math-container">$P_{i=1 \to 4}=\{\{1,1\},\{2,2\},\{3,3\},\{4,4\}\}$</span></p>
<h2>Modeling starter</h2>
<p>On the most simple cases, we hope to only have paired results - the outline is closed and thus each line passing it has to <em>cut</em> it in multiples of two. Because we don't allow geometry to be below <span class="math-container">$\{0,0\}$</span>, 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 <span class="math-container">$\{1,1\} \to \{2,2\}$</span> and <span class="math-container">$\{3,3\} \to \{4,4\}$</span>.</p>
<h1>Enhancing the Modeling</h1>
<h2>checking for tangents</h2>
<p>Now, we might have an odd number of points that solve O(x)=I<sub>n</sub>(x) for a given n. Let's assume <span class="math-container">$P_{i=1 \to 5}=\{1,1\},\{2,2\},\{3,3\},\{4,4\},\{5,5\}$</span>.</p>
<p>Now we need to be careful as one of these points is guaranteed to be a point in which <span class="math-container">$I_n(x)$</span> is a tangent at of <span class="math-container">$O(x)$</span>. So, we need to know the first differential of <span class="math-container">$O(x)$</span> in the points, which is the tangent at <span class="math-container">$O(x)$</span>. But we don't need to solve <em>all</em> 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 <span class="math-container">$P_i$</span> with <span class="math-container">$i=2 \to i_{max-1}$</span>. When <span class="math-container">$O'(x)=I_n(x)$</span>, we got a tangent and remove this point from the list of points to connect with infill lines.</p>
<p>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.</p>
<p>Also, I used the &quot;usually&quot; 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  <span class="math-container">$P_1 \to P_{max}$</span>!</p>
<p>The new, reduced set of points will be a paired list: <span class="math-container">$Q_{i=1 \to 4}=\{1,1\},\{2,2\},\{4,4\},\{5,5\}$</span>. The Infil connects <span class="math-container">$Q_1 \to Q_2$</span> and <span class="math-container">$Q_3\to Q_4$</span>.</p>
<h2>Turning Points into vectors</h2>
<p>Now, we have our points <span class="math-container">$Q_1$</span> and <span class="math-container">$Q_2$</span> (or any other pair of <span class="math-container">$n \land n+1$</span>, where n is an element of the odd numbers), both on <span class="math-container">$I_{n=0}(x)$</span>. How to connect? Easy! <span class="math-container">$I{n=0}$</span> is a function, most likely a linear one. Along this line has to be our connecting line from <span class="math-container">$Q_1\to Q_2$</span>, so the movement we have to plot is the function of our pattern between the points. For a simple, linear pattern this would be:</p>
<p><span class="math-container">$L_1=\frac{I(x)}{|I(x)|} \times |\vec{Q_2}-\vec{Q_1}|+\vec{Q1}$</span></p>
<h1>Optimisation</h1>
<h2>Sorting properly</h2>
<p>Now, we have a set of Lines <span class="math-container">$L_n$</span>, where, as established in the last paragraph, n is an odd number declaring it has the lower-end <span class="math-container">$Q_n$</span>, and the upper-end <span class="math-container">$Q_{n+1}$</span>. How do we sort these lines smartly so we have the least movement? Let's take a look at our lists:</p>
<ul>
<li>The list of P<sub>i</sub>, which contains all tangential points and end points. Not very helpful.</li>
<li>The reduced list of <span class="math-container">$Q_{n}$</span>, which contains all the start and end points; it is <em>sorted</em> in a way that odd numbers are starts, and even ends.</li>
<li>The list of <span class="math-container">$L_n$</span> with i always being an odd number, that contains the movement paths (=lines) from each <span class="math-container">$Q_{n}$</span> to its corresponding <span class="math-container">$Q_{n+1}$</span></li>
</ul>
<h3>Shortest movement between prints?</h3>
<p>Now, let's do some math again: What is the closest <span class="math-container">$Q_{a}$</span> to the <span class="math-container">$Q_{n+1}$</span> we did end at after doing the <span class="math-container">$L_n$</span> 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 <span class="math-container">$R_{i}$</span>, which contains all the <span class="math-container">$Q_{i}$</span> we have not yet moved to.</p>
<p>So what is the closest <span class="math-container">$R_{i}$</span> to the end point of the path <span class="math-container">$L_e$</span> we just moved? Well, easy! Solve <span class="math-container">$min|R_i-L_e|$</span> with i being all the odd numbers in the list of <span class="math-container">$R_{i}$</span> and <span class="math-container">$L_e$</span> the point where the printhead was sent to at the end of the last movement</p>
<h3>fewest direction changes?</h3>
<p>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 <span class="math-container">$l_n(x)$</span> 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.</p>
<h3>optimizing direction changes &amp; movement paths</h3>
<p>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:</p>
<p>Up to now, all our line functions <span class="math-container">$l_n(x)$</span> 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:</p>
<p><span class="math-container">$L_n(x)=-1^n\times l_n(x)$</span></p>
<p>Now, after all the movements with the same <span class="math-container">$n$</span> 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 <span class="math-container">$R_{i}$</span>. Once back on the side we <em>started</em> first at, we look for the closest unused point again, run down that line, rinse and repeat.</p>

CC BY-SA 4.0
2018-09-05T18:48:06.257Z
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
CC BY-SA 4.0
2018-09-05T20:50:13.857Z
yes, the banana in exampe 1 is bent in such a way that it bends around the middle of the "gap".
Trish
CC BY-SA 4.0
2018-09-06T11:09:01.420Z
@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
CC BY-SA 4.0
2018-09-05T10:16:32.663Z
2018-09-14T10:49:17.817Z
2020-06-18T08:29:41.667Z
Trish
<p>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?</p>

<p>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?</p>

<p>EDIT:</p>

<p>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? </p>

CC BY-SA 4.0
2018-09-05T09:09:59.390Z
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
CC BY-SA 4.0
2018-09-05T12:30:13.313Z
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
CC BY-SA 4.0
2018-09-05T18:41:37.853Z
@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
CC BY-SA 4.0
2018-09-05T21:51:59.837Z
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
<slicing><infill>
How are infill paths connect to form an efficient path that respect the object's geometry?
Chris Uchytil
# How are infill paths connect to form an efficient path that respect the object's geometry?

(Asked by: username_0 on 2018-09-05)

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?

**Tags:** slicing, infill
> **Comments:**
> **username_1**: 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)  
> **username_2**: 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?  
> **username_0**: @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.  
> **username_3**: 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.  

---

## 2 answers

### Answer by username_5 on 2018-09-05. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_5**: yes, the banana in exampe 1 is bent in such a way that it bends around the middle of the "gap".  
> **username_5**: @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.  

---

### Answer by username_4 on 2018-09-05. Score: 3

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

> **Comments:**
> **username_0**: Step 5, "sort cut points in some order ("some" is definitely the hardest task)" is where I am stuck.  
> **username_4**: well the simplest way seems to be sort (counter)clockwise ;)  

---

