Closed mboerwinkle closed 4 years ago
Looks interesting!
The 3D distance to the boundary would be fairly difficult. Here's the obstacles you're facing:
PolygonUtils::moveInside2
function is only implemented for 2D polygons (like all other functions in that class). Implementing it for 3D polygons would be an order of magnitude more difficult.We currently have an implementation of what's called "Gradual Infill" though, which does something similar but in a different manner. It defines areas in every layer that are close to the ceiling (like it also does for skin) and gives those layer parts a different infill density based on its proximity to the top. The current implementation halves the infill density every 5mm by default. You could try something similar, but it will sort of be the Chebyshev distance to the border rather than Euclidean. Currently, the Gradual Infill implementation is always exponential (always divides the density by half, since that aligns the lines on top of each other nicely) and it only counts from the top.
Basing your implementation off Gradual Infill would sidestep the first obstacle and last obstacle and erase the second obstacle, but computation time and architecture design are still constraints if this were to be included in the main CuraEngine source code.
I wonder, how well does it do overhangs for you right now?
Thanks for your response! Overhangs are currently another problem caused by my current method of determining distance from the shell. As you can see in the attached image, as the wall goes outward, cubes that were subdivided are no longer subdivided midway through. This is especially a problem on walls that slope inwards since the opposite happens: as the border approaches, cubes become close enough to start being subdivided but have no supporting lines. Any sort of rough 3d distance method would solve the problem outlined in my original question as well as the problems with sloping walls: by specifying the argument 3d point as the center of the 3d cube, the same result could be obtained on every layer of a cube, leading to identical subdivision on all layers. In the coming days I will look into the feasibility of doing something similar to Gradual infill from the top and bottom.
Starting subdivision of a cube midway through is not so bad because the new line will bridge between the walls of the cube which is being subdivided. I do understand it if you want to overcome these problems, though.
For the gradual infill feature the lines aren't generated per cell, but globally. While your algorithm generates separate line segments per cube, my algorithm generates single straight lines which are shared among multiple cells.
Yours:
Mine: File: UM2_tetrahedron_gradual_infill.gcode.txt
I am a bit hesitant to merge you infill type into our master, because I don't know how well it would work with the gradual infill feature. Also I think it's a shame that your algorithm only works for cubic infill.
I have fixed the subdivision of the cubes so that there are no overhanging infill line segments. I have also modified it so that it creates denser infill near top, bottom, and slant surfaces in addition to the walls. This is currently done naively by, on each layer that a potentially subdivided cube exists on, checking if the cube intersects the outline or the ceiling of the print. This method has speed problems, and increases computation time from seconds to minutes. I am planning on preprocessing the recursions to bring the speed down to an acceptable level.
@BagelOrb: I ended up not making use of gradual infill. My infill seems to be more of an alternative to gradual infill that gets denser near the bottom and sides as well as top.
I have had no problems with the separate line segments. Preliminary testing seems to suggest that the speed of my infill per filament used is roughly equivalent to grid infill.
You mentioned that it was a shame that it only works for cubes: The use of cubes is tied to them being self-divisible. I do not know of another shape that is self-divisible this nicely necessary way.
Attached is: A photo of a print (overhang) Gcode for a sphere Gcode for a pyramid Gcode for an overhang
Thanks for your time, Martin Boerwinkle
Very cool Martin! It somewhat mimics natural formations like bone.
I'm curious why there is asymmetry in that example print.
On Thu, Sep 8, 2016, 12:03 AM mboerwinkle notifications@github.com wrote:
I have fixed the subdivision of the cubes so that there are no overhanging infill line segments. I have also modified it so that it creates denser infill near top, bottom, and slant surfaces in addition to the walls. This is currently done naively by, on each layer that a potentially subdivided cube exists on, checking if the cube intersects the outline or the ceiling of the print. This method has speed problems, and increases computation time from seconds to minutes. I am planning on preprocessing the recursions to bring the speed down to an acceptable level.
@BagelOrb https://github.com/BagelOrb: I ended up not making use of gradual infill. My infill seems to be more of an alternative to gradual infill that gets denser near the bottom and sides as well as top.
I have had no problems with the separate line segments. Preliminary testing seems to suggest that the speed of my infill per filament used is roughly equivalent to grid infill.
You mentioned that it was a shame that it only works for cubes: The use of cubes is tied to them being self-divisible. I do not know of another shape that is self-divisible this nicely necessary way.
Attached is: A photo of a print (overhang) Gcode for a sphere Gcode for a pyramid Gcode for an overhang
Thanks for your time, Martin Boerwinkle
[image: print] https://cloud.githubusercontent.com/assets/7738815/18337432/20b7bf30-7580-11e6-9370-787aed3b5453.jpg
sphere.gcode.txt https://github.com/Ultimaker/CuraEngine/files/460847/sphere.gcode.txt pyramid.gcode.txt https://github.com/Ultimaker/CuraEngine/files/460863/pyramid.gcode.txt overhang.gcode.txt https://github.com/Ultimaker/CuraEngine/files/460870/overhang.gcode.txt
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/Ultimaker/CuraEngine/issues/381#issuecomment-245494479, or mute the thread https://github.com/notifications/unsubscribe-auth/AL3P996jbGTAORBPuXmXlmvR_N9UOjV5ks5qn5c5gaJpZM4Jk8hm .
I'm not sure exactly what you are asking... If you are asking about the partially completed wall here:
It is not actually a wall at all: it is ooze from a move without extrusion that happened in the same place multiple layers in a row.
If you are asking about why the triangles and hexagons do not line up exactly the same on all sides, then it is because the form of the infill is derived from one large cube that encompasses the entire print that is subdivided and cropped, so the subdivisions do not necessarily line up exactly with whatever you put inside.
I meant more that the two largest triangles are not in the square center.
On Fri, Sep 9, 2016, 12:27 AM mboerwinkle notifications@github.com wrote:
I'm not sure exactly what you are asking... If you are asking about the partially completed wall here: [image: printcircled] https://cloud.githubusercontent.com/assets/7738815/18376133/99eb6ade-764b-11e6-9eee-fa0f4016a8ff.jpg
It is not actually a wall at all: it is ooze from a move without extrusion that happened in the same place multiple layers in a row.
If you are asking about why the triangles and hexagons do not line up exactly the same on all sides, then it is because the form of the infill is derived from one large cube that encompasses the entire print that is subdivided and cropped, so the subdivisions do not necessarily line up exactly with whatever you put inside.
— You are receiving this because you commented.
Reply to this email directly, view it on GitHub https://github.com/Ultimaker/CuraEngine/issues/381#issuecomment-245822675, or mute the thread https://github.com/notifications/unsubscribe-auth/AL3P9_ndLTin9ibxBrwtIs-dw8BE7S58ks5qoO4wgaJpZM4Jk8hm .
Separate line segments will make the gcode larger and will make the path planning slower.
To respond to your earlier post:
I was hoping you would hook in to my gradual infill algorithm, because then there wouldn't have been this duplication of very related features.
Also that would mean that it would work on all infill types, although it would require a totally different algorithm. The most important difference between yours and mine is that mine has infill lines stopping in the middle of a cell. I had hoped you would fix that by extending the lines to the edge of the next cell. I think then gradual infill with cubic infill would be the same as your algorithm.
We would then only have to implement an option to also get denser toward the sides and bottom.
But this is all water under the bridge; the way you've done it works well for cubic infill.
Why is the red triangle subdivided, but not the green one?
@BagelOrb The green one is the bottom part of a new cube. The red one is the top part of a cube. It is subdivided due to the cube's inability to fully fit within the part. (Actually the bounding sphere around the cube can't fit within the part.) Also note that the right side is over a slant overhang.
I animated @mboerwinkle 's sphere to give you an idea of when items get subdivided.
I am curious why you would prefer lines not terminating at cell boundaries. It seems to me that it would lead to stronger parts if you don't have floating wall terminations.
Ah I didn't see the slant overhang.
Nice animation! So pretty!
@NicholasSeward I think you misunderstood. I would like lines terminating at cell boundaries rather than open air, but I don't like lines terminating in another line segment in the same direction. If it can be one line instead of separate segments, then making it a single line makes the path planning stage less time consuming. At every point where 3 or 6 line segments meet, all line segments have to be considered to check which one is the best next line segment. If it were just one line there wouldn't be this computational overhead. It's not that big a deal, though.
How is the speedup coming along?
@BagelOrb I made another animation that highlights situation where there are vertices of degree 3 or more. As you can see, most layers don't have any intersections like this. At layers that cap off the smallest cubes, there are quite a few intersections like this but the degree of these vertices is only 3. Furthermore, I only found these intersections by rounding to 1 decimal place. The number of intersections half if your epsilon for combining vertices is 0.01 and goes to practically zero if epsilon is 0.001. (If cube tips don't land perfectly on a layer, then this will be a complete none issue.) @mboerwinkle was really smart in generating lines to subdivide cubes instead of the actual loop around each cell. Testing will be required but I am pretty sure the planning stage will not stand in the way of this being fast enough.
Note: I was too lazy to eliminate the degree 3+ intersections between the skin and the fill. The dots around the outside won't be a problem when you are only generating the infill.
I would call a * shape a vertex with degree 5. I think that what you call degree 3 I call degree 6. I would call a + shape degree 4. That's because it doesn't consist of 2, but 4 line segments in the way that @mboerwinkle implemented it.
Just to make sure I wasn't looking at it wrong, I made the following graphic. I exaggerated where each line terminates. If lines cross, there are no vertices there. This is a worst case scenario that results in a lot of degree 4 vertices. On most every other layer, the max degree of a vertex is two.
However, this doesn't matter at all. After talking with @mboerwinkle it seems like he is moving to do line merging as a side effect of moving to an efficient octree datastructure.
As it is right now (306 lines)
As it will be (134 lines)
An octtree! That makes so much sense!
The fact that the layer view always looks like triangles is deceptive; I wouldn't have thought of an octtree.
Nice visualisation - again!
Op 15 sep. 2016 06:18 schreef "NicholasSeward" notifications@github.com:
Just to make sure I wasn't looking at it wrong, I made the following graphic. I exaggerated where each line terminates. If lines cross, there are no vertices there. This is a worst case scenario that results in a lot of degree 4 vertices. On most every other layer, the max degree of a vertex is two.
However, this doesn't matter at all. After talking with @mboerwinkle https://github.com/mboerwinkle it seems like he is moving to do line merging as a side effect of moving to an efficient octree datastructure.
[image: lines] https://cloud.githubusercontent.com/assets/5028673/18537516/b2b97702-7acb-11e6-89d4-74a1a0d2baa2.png As it is right now (306 lines)
[image: lines_merged] https://cloud.githubusercontent.com/assets/5028673/18538234/5dd76fea-7ad1-11e6-80f7-58d4214c57e0.png As it will be (134 lines)
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/Ultimaker/CuraEngine/issues/381#issuecomment-247230606, or mute the thread https://github.com/notifications/unsubscribe-auth/AIe9ETJCc7YXgdFXrffoxXKIL8i0mdU3ks5qqMcUgaJpZM4Jk8hm .
I have made significant progress towards speeding up the slicing. Changes made include:
I now batch crop with Clipper (I had been running Clipping tasks one per line segment before :P).
Testing on a sphere (I figure it is a pretty good test subject because it has a fair amount of outline line segments), slicing time has decreased from around 6min15sec to 8.5 sec. (standard grid infill takes 6.1 sec for reference). The time breakdown in the sphere's case is (percentages are in terms of total program running time): Octree precomputation: 8%, Line Segment Generation/Merging: 11%, Cropping: 5% Is this speed acceptable? If you have any further tests you would like me to run, I would be happy to. Any ideas you have for further optimization are welcomed.
EDIT: I forgot to attach example gcode sphere.gcode.txt
Great news! I would like to see a test on a more complex and bigger model, so that slicing will take minutes either way. That way you will get a more accurate estimate.
Try http://www.thingiverse.com/thing:683004/#files for example.
Also I would like to see the impact on the estimated print time and material. Of course that requires you to set some reasonable setting values.
Have you introduced settings for the maximal recursion depth? Is there a setting for the distance from a cube to the edge before it will be subdivided? That would be really nice to tweak the strength of the shell of the print.
Sliced the dragon using grid and my infill (I had to scale it up quite a bit to get calculation times over a minute). Set it up so that Filament used difference was within 1%(EDIT:almost 1%). Print time difference was insignificant. Computation time was about 1.5x higher for mine. Grid SubDivCube Computation time 2m9s 3m24s Filament used 50973mm 50361mm Print time 21h2m3s 21h13m50s
I do have an arbitrary limit on recursion depth based on cube size, but I am planning on using the existing parameters for infill density as the limit. That would make the densest areas of mine identical to the density of your cubic infill. I can change the distance from the cube to the edge before it will be subdivided. Right now I use the radius of a circumscribed sphere as the distance. Thanks, Martin Boerwinkle The gcode files are too big to attach in this comment, so I made a link sharable google drive folder: https://drive.google.com/drive/folders/0B6p5ArFix80vY2JGVWcwTzJPX1U?usp=sharing
Sounds like great progress!
Using the existing infill density is a good idea. It's similar for gradual infill as well.
50% computation time increase is quite a lot. I wonder how the comparison goes when you set it so that the most dense cubes have the same infill density as the normal infill density.
How is the maximum cube size determined? It would be nice if there was a frontend setting for that. Gradual infill also has some settings to tweak that.
Please introduce a setting to change the distance from the cube to the edge before it will be subdivided.
I've thought of a little optimisation which you might not have thought about. When you find a vertex/face close enough to a cube to subdivide it, subdivide it and immediately check the newly introduced cubes for whether they should be subdivided because of the same vertex/face. That way you don't have to iterate over vertices/faces again for the substituting smaller cubes. I don't know for sure whether the above makes sense; I don't really know how you employed the octtree.
Op 17 sep. 2016 03:04 schreef "mboerwinkle" notifications@github.com:
Sliced the dragon using grid and my infill (I had to scale it up quite a bit to get calculation times over a minute). Set it up so that Filament used difference was within 1%. Print time difference was insignificant. Computation time was about 1.5x higher for mine. Grid SubDivCube Computation time 2m9s 3m24s Filament used 50973mm 50361mm Print time 21h2m3s 21h13m50s
I do have an arbitrary limit on recursion depth based on cube size, but I am planning on using the existing parameters for infill density as the limit. That would make the densest areas of mine identical to the density of your cubic infill. I can change the distance from the cube to the edge before it will be subdivided. Right now I use the radius of a circumscribed sphere as the distance. Thanks, Martin Boerwinkle The gcode files are too big to attach in this comment, so I made a link sharable google drive folder: https://drive.google.com/drive/folders/0B6p5ArFix80vY2JGVWcwTzJPX1U? usp=sharing
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/Ultimaker/CuraEngine/issues/381#issuecomment-247739820, or mute the thread https://github.com/notifications/unsubscribe-auth/AIe9ES76buRgetL6YCJFMqeozy-BcSTMks5qqzyagaJpZM4Jk8hm .
Note that no new settings may be accepted in the front-end at this moment, as that would violate the string freeze, and we're officially still on master.
@Ghostkeeper Do you mean this infill can't be added to the front-end (at this moment) or that this infill can't have extra setting fields?
There can't be extra setting fields for it. The reason is that that would introduce text, and we have a string freeze until our boss decides to again go back to the 2.3 branch for the 2.3 release.
Just got word from tha boss that the string changes for this feature are acceptable. It is deemed okay that there are untranslated strings in the release as long as they are well hidden. He does want the setting(s) for this feature to be under "experimental" (and I agree).
So as far as he's concerned, this can be merged once we've reviewed the code and tested it well.
Super cool!
It would be awesome to have settings for the max/min density, and maybe a coefficient that controls the rate of subdivision.
On Mon, Sep 19, 2016, 8:20 AM Ghostkeeper notifications@github.com wrote:
Just got word from tha boss that the string changes for this feature are acceptable. It is deemed okay that there are untranslated strings in the release as long as they are well hidden. He does want the setting(s) for this feature to be under "experimental" (and I agree).
So as far as he's concerned, this can be merged once we've reviewed the code and tested it well.
— You are receiving this because you commented.
Reply to this email directly, view it on GitHub https://github.com/Ultimaker/CuraEngine/issues/381#issuecomment-247990797, or mute the thread https://github.com/notifications/unsubscribe-auth/AL3P95B7cdsdG3-k_6LbTYM5n2z284tPks5qrowTgaJpZM4Jk8hm .
I am working on cleaning up my code and adding the requested settings. However, there is one issue that I am unsure how to resolve: Currently I perform my line segment cropping using Clipper. In order to do this, I had to enable the "use_lines" define in /lib/clipper/clipper.hpp. This option enables what is default behavior for clipper, but there was a note attached saying that it would incur "a very minor cost to performance." As I see it, there are three ways to resolve this problem:
The best thing to do is to quantify it: How much of an actual performance hit does it give? If you are on a Linux system you can get some pretty simple statistics by using the time command to time how long a single run of CuraEngine takes.
I tested the dragon that I previously used with grid infill. The times were identical (2m9s) for with and without the use_lines flag. If there is anything else you would like me to test, I will be happy to.
I actually already have that flag enabled on a branch for exotic infill strategies.
I think the cost is so small that you would need a tremendous amount of testing to even see a significant impact.
Maybe we should do a benchmark test, separately from CuraEngine. Just perform a given set of offsets to some complex polygon a million times.
However, I suspect it's simply a single if-statement somewhere, so with modern architectures with branch prediction there wouldn't even be a performance hit.
Op 28 sep. 2016 18:22 schreef "mboerwinkle" notifications@github.com:
I tested the dragon that I previously used with grid infill. The times were identical (2m9s) for with and without the use_lines flag. If there is anything else you would like me to test, I will be happy to.
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/Ultimaker/CuraEngine/issues/381#issuecomment-250218902, or mute the thread https://github.com/notifications/unsubscribe-auth/AIe9EQiTBZrzICopDawMyzHUgM7e1QZtks5qupRFgaJpZM4Jk8hm .
My code is now visible in my fork at mboerwinkle/CuraEngine. Thanks, Martin Boerwinkle
Does this mean your work on this project is finished?
I will certainly have a look at your code and see how it performs. Can't wait to test this!
These are my initial results on a 2x normal size Ultimaker Robot at infill line distance=1.05: Grid vs CubicSubDiv Slice time: 12s vs 23s = 192% D: Print time (readable): 6h 11m 18s vs 5h 38m 46s = 91% (: Filament: 40231 vs 30646 = 76% (: Gcode file size: 14.8 MB vs 17.8 MB = 120% ):
Overall: worth it!
Would you like your code to be permanently part of CuraEngine? Would you please create a Pull Request?
Your code is not following the standard we have for our colleagues, so I will have to go over your code and fix some naming and spacing etc. I will then also have a look at your code and see whether there is any way to improve the performance.
I find it hard to read your code. Could you maybe add some more documentation to each function you introduced? Also more explicit function names can help. For example dist
could be renamed to distanceFromPointToMesh
. We prefer clarity over brevity ;)
I would love to include my code in CuraEngine. I will go through and comment my code and try to fix unclear names tonight or tomorrow and then create a pull request. Thanks!
We have a document with our code conventions here: https://github.com/Ultimaker/Meta/blob/master/code_conventions.md
@mboerwinkle @NicholasSeward Would you guys be interested in visiting the office here in the Netherlands? The idea came from one of the founders of the company, so it might very well be possible to give you guys a nice tour. ^^
This could be combined with something I worked on during my internship last year. I also had the ideas of more dense infill near the outer walls and tilting the infill-walls, I just didn't get around to combining them. But I had a different purpose in mind, namely creating cups in which material can be extruded, to create a bond between the layers, which I hoped would make prints much stronger. That could be easily added to this idea. Every now and then hover above one of those 'cups', especially those near the edge, and extrude some material. Of course this should be done with the fans off, so the plastic doesn't solidify too quickly. It takes several seconds for them to come to a full stop if they are spinning at full speed (speeding up again goes a lot faster). So doing this too often might increase printing time too much. That would be a trade-off. And it would be more effective near the edge, because that's where the stresses will likely be greater. And the cups are smaller there, which is probably also a good thing (although I can imagine they shouldn't be too small). But a possible problem is that the walls of the cups might melt because of the pool of hot material. So it might be better not to do this too close to the outer walls. That would be something to experiment with. Controlling how the material flows may also be a problem, so it would probably also take some experimenting to see if the nozzle should remain stationary or move (maybe along the edge of the cup). For example, you wouldn't want the material to rise up and engulf the nozzle, which I have seen happen during some experiments.
@BagelOrb: Happy to see the merge! @NicholasSeward and I would love to visit, but it will be a bit difficult as we are in the United States... I can be contacted at mboerwinkle@gmail.com.
@DDDirk: Sounds like an interesting idea... You mentioned experimenting you have done? It does sound like there are a significant number of challenges to overcome, though.
Thanks, Martin Boerwinkle
I haven't experimented specifically with this, but with a simpler version (between vertical walls) because I had limited time for that internship-assignment. But now that this exists, adding extrusion in the 'cups' could be an interresting addition. I would love to experiment with this, but I already have too many other things to work on (but then who hasn't? :) ). I just wanted to mention it, in case someone else would like to give it a try.
I think one major issue would be to prevent the extruded material to solidify before it bonds with the layers, especially if you extrude in the middle of an already deep cup. If it bonds at all. It did when I extruded between two walls, but in these cups the heat has more room to escape. One possible solution would be to increase the temperature, but then you may have to wait for the nozzle to cool down again before continuing. And doing it less often would mean extruding in deeper cups, which would again present the problem of the material cooling down before it bonds. Maybe you could lower the nozzle into the cup (although it depends on the printer how much that is possible) and move up during extrusion. Just a thought. Lots of room to experiment. :)
Interesting ideas, though the lack of time on my part is disconcerting ;)
Yeah the US is kind of the other side of the world, so I think my managers won't be too thrilled to fly you guys over :slightly_frowning_face:
Closing this since it's been merged.
I am working on an infill similar to the Cubic infill but which recursively subdivides each cube based on its distance from the shell. The reasoning behind this infill is that by having a higher infill density near the shell and a lower density in the core, a higher strength to weight/print time/cost ratio can be obtained. Currently, the infill uses the distance from the center of the cube to the current layer's bounding polygon as its method of determining if a cube should be subdivided (by using PolygonUtils::moveInside2 and finding the distance to the resulting point). What would be optimal is if it could find the distance from the center of the cube to the shell of the 3d model so that floors and ceilings would also be reinforced.
In short: I am looking to write a function that takes as an argument a 3d point, and returns its distance from the model's shell.
Any guidance in how to cleanly implement this would be greatly appreciated.
Thanks, Martin Boerwinkle
Attached is a screenshot of the current version of the infill in repetier and the gcode file that the screenshot is taken from (cube.txt).
cube.txt