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

[{'answer_id': 6833, 'author': 'darth pixel', 'author_id': 1211, 'author_profile': 'https://3dprinting.stackexchange.com/users/1211', 'pm_score': 2, 'selected': False, 'text': '<p>simple answer is math but you know that for sure</p>\n\n<p>more descriptive answer (but still simple and with no math) is more or less as follows</p>\n\n<ul>\n<li>slice an object with a plane to form (calculate) outline perimeter</li>\n<li>create a grid of infill according to your needs (ie: lines, grids or honeycombs)</li>\n<li>calculate where outline cuts your grid of infill</li>\n<li>abandon all what is outside</li>\n<li>sort cut points in some order ("some" is definitely the hardest task)</li>\n<li>join points according to your sort</li>\n</ul>\n\n<p>and voila ;)</p>\n\n<p>of course there is many details not mentioned in such description as distance between perimeter and infill, layer thickness and many others\nthis is just very naive and silly description but it\'s just to direct you where to go further</p>\n\n<p>generally there is great library which you could give a try</p>\n\n<p><a href="https://sourceforge.net/projects/jsclipper/" rel="nofollow noreferrer">https://sourceforge.net/projects/jsclipper/</a></p>\n\n<p><strong>edit</strong></p>\n\n<p>simple sort (counter)clockwise could be like this</p>\n\n<ul>\n<li>set center point of the object (perimeter)</li>\n<li>start from 1200 hour and calculate module and angle of each cut-point</li>\n<li>sort them by angle</li>\n</ul>\n\n<p>it\'s still very simple and it\'s working only for convex set</p>\n'}, {'answer_id': 6836, 'author': 'Trish', 'author_id': 8884, 'author_profile': 'https://3dprinting.stackexchange.com/users/8884', 'pm_score': 4, 'selected': True, 'text': '<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>\n<h1>Basics</h1>\n<h3>Outline Function</h3>\n<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>\n<h3>Infill Functions</h3>\n<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>\nwhere <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>\n<h3>Comparation: Outline=Infill</h3>\n<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>\n<h1>Dealing with the results</h1>\n<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>\n<h2>Modeling starter</h2>\n<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>\n<h1>Enhancing the Modeling</h1>\n<h2>checking for tangents</h2>\n<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>\n<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>\n<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>\n<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>\n<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>\n<h2>Turning Points into vectors</h2>\n<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>\n<p><span class="math-container">$L_1=\\frac{I(x)}{|I(x)|} \\times |\\vec{Q_2}-\\vec{Q_1}|+\\vec{Q1}$</span></p>\n<h1>Optimisation</h1>\n<h2>Sorting properly</h2>\n<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>\n<ul>\n<li>The list of P<sub>i</sub>, which contains all tangential points and end points. Not very helpful.</li>\n<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>\n<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>\n</ul>\n<h3>Shortest movement between prints?</h3>\n<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>\n<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>\n<h3>fewest direction changes?</h3>\n<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>\n<h3>optimizing direction changes &amp; movement paths</h3>\n<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>\n<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>\n<p><span class="math-container">$L_n(x)=-1^n\\times l_n(x)$</span></p>\n<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>\n'}]
['https://3dprinting.stackexchange.com/questions/6832', 'https://3dprinting.stackexchange.com', 'https://3dprinting.stackexchange.com/users/12851/']