Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[4.4.0] Cura produces way to many segements/commands and makes printer stutter #6748

Open
TheAndi opened this issue Dec 3, 2019 · 52 comments
Labels
Status: Needs Info Needs more information before action can be taken. Status: Stale ⌛ This issue is over a year old. It might be obsolete or just needs a fresh set of eyes Type: Bug The code does not produce the intended behavior.

Comments

@TheAndi
Copy link

TheAndi commented Dec 3, 2019

Application version
Cura 4.4.0

Platform
Windows 10 64 bit

Printer
ANET A8, Sidewinder X1

Reproduction steps
Slicing a cylinder like object
grafik

Actual results
The result is in this example a gcode consisting of ~350k lines. This is too much for my ANET running octoprint with a baud of 500k (usually this is not a bottleneck). And it's also too much for the Sidewinder X1 as it also receives its commands via serial (250k baud) from the touch screen.

I noticed that there is a massive stuttering at the outer layer (not the inner one) so I checked the gcode on http://gcode.ws/ :

grafik
grafik

As you can see there are tiny segments in between the "main" segments, leading to about double the gcode lines as Prusa slicer (see below)

I also altered the resolution (and deviation) which didn't shrink the line count significantly
I already used rather coarse values for the example above:
grafik

At some higher values the line count event starts increasing as small bits of infills are generated:
grafik

So these values are not the solution.

Expected results
Because I couldn't get this object to print with Cura. I tried it with Prusa Slicer 2.2 and the print worked smooth right out of the box with similar setting. Gcode was just ~170k of lines.
A look at the gcode (same section) reveals that everything is fine here:
grafik

The segment count (resolution) in this section is the same as in Cura but without these "extra segments"

Additional information
Something I noticed, which might help to find the bug.
It seems like the outer contour copies all the segment nodes from the inner one:
grafik

Is there any option to fix this?

Thanks in advance

@TheAndi TheAndi added the Type: Bug The code does not produce the intended behavior. label Dec 3, 2019
@smartavionics
Copy link
Contributor

Yes, please try turning off the wall overlap compensation. That's what's creating those tiny segments in the outer wall. Also, did you try one of my builds (which can be found at https://www.dropbox.com/sh/s43vqzmi4d2bqe2/AAADdYdSu9iwcKa0Knqgurm4a?dl=0). They have a partial fix for this issue. If you want to try one of those, please read the README.md there.

@TheAndi
Copy link
Author

TheAndi commented Dec 3, 2019

Thanks a lot, this setting immediately halved the gcode and should print smooth. Why is this feature used? And do I have drawbacks from disabling it?

Some more thing, while turning of this feature solved all these problems in the wall. There are still "to many" segments in the skirt, making it stutter.

grafik
(First layer with skirt)

Not as important as the walls, but maybe there's a fix too?

@smartavionics
Copy link
Contributor

Thanks a lot, this setting immediately halved the gcode and should print smooth. Why is this feature used? And do I have drawbacks from disabling it?

This feature (overlap compensation) stops overextrusion when 2 walls won't fit in the gap available. e.g. if the gap is 1.5 walls wide, the first wall will be printed full width and the second at 1/2 width. It often works OK and is definitely beneficial for some models. Unfortunately, the implementation is pretty buggy and badly documented. My Cura builds have some of the bugs fixed but not all.

Some more thing, while turning of this feature solved all these problems in the wall. There are still "to many" segments in the skirt, making it stutter.

AFAIK, there are no settings that will reduce the number of segments in the skirt other than the max resolution and max deviation settings that affect the whole model.

@Ghostkeeper
Copy link
Collaborator

Ghostkeeper commented Dec 5, 2019

As far as I know, the overlap compensation should only kick in when the angle between the lines is less than 90 degrees. When checking for the overlap between two lines, the one line is projected on top of the other. If two subsequent lines have an angle of more than 90 degrees the overlap should become 0 and there will be no overlap compensation. There might be a bug in there somewhere then.

I can't reproduce the problem though when I slice a simple 360-segment cylinder. Every line of the wall has pretty much exactly the same length. No overlap compensation seems to be happening. I tried both the outer wall and the inner walls. Perhaps you could share a project file?

@XDA-Bam
Copy link

XDA-Bam commented Apr 10, 2020

I think I have the same problem with Cura 4.5. Wall overlap compensation is disabled. Happens only on certain layers of the object and only on certain parts of the curve. Model and settings see project file.

When I slice it, the problem occurs around layer 125 +-10 and looks like this:
Affected

A couple of layer above or below, it's totally fine again:
NotAffected

Looks like Cura, as mentioned by the OP, somehow duplicates nodes from the inner wall to the outer.

@Ghostkeeper
Copy link
Collaborator

Ghostkeeper commented Apr 21, 2020

This algorithm is mostly rewritten for Cura 4.7. Hopefully that fixes things for you. This is not in Cura 4.6 yet, mind.

One of the things that was fixed was that there could be an extra vertex or two around the seam. Maybe that's what you're seeing.

@chrisdalke
Copy link

chrisdalke commented Jun 23, 2020

I've also experienced this bug, wherever Cura generates a very tiny line segment on curved models it causes the printer to skip. While this is odd slicer behavior, it's also unexpected that a short line segment like that would cause the printer to skip. I've investigated and each "zit" on my print corresponds 1:1 with a short (<1mm) line segment in the gcode.

Some additional context for anyone else who follows on the same path I did -- An explanation why the bug only appears on certain printers could be this Marlin bug (already linked above) which was introduced in more recent firmware:

MarlinFirmware/Marlin#17920
MarlinFirmware/Marlin#17342
MarlinFirmware/Marlin#17146

In those threads, they discuss how the acceleration/jerk algorithm is incorrectly calculating speeds at the vertices for very small line segments in the middle of longer line segments on curved lines (see this comment that has a diagram: MarlinFirmware/Marlin#17920 (comment))

One step to reproduce this may be to test on printers with more recent Marlin firmware (>=1.1.9 seems to be the threshold where this bug appeared). Anecdotally, this happens for me on my printer (Ender 5) ever since I updated from the factory firmware. I am unable to reproduce it on an Ender 3 with 1.1.8 firmware.

@XDA-Bam
Copy link

XDA-Bam commented Jun 23, 2020

An explanation why the bug only appears on certain printers could be this Marlin bug (already linked above) which was introduced in more recent firmware:

There recently (roughly April to Mid June) were problems in Marlin, which caused excessive stuttering on curves when using "Junction Deviation" instead of "Jerk" for speed limiting. Those are now fixed, but the problems with tiny segments still exist when using Junction Deviation - because it's not really a bug in Marlin.

The problem is, that the slicer (Cura in this case) incorrectly distributes the angles between segments along a curve. This is either a slicer bug, or somehow related to the fact that we are slicing already discretized curves (-> STL files). It's not only present in Cura, but very prominent there. Also, vase mode for example does seem to be affected much less or possibly not at all - which supports the idea that this is a slicing problem.

In those threads, they discuss how the acceleration/jerk algorithm is incorrectly calculating speeds at the vertices for very small line segments in the middle of longer line segments on curved lines.

It may seem that way at first, but the calculated speeds are correct in the mathematical sense. The problem is, that Marlin Junction Deviation calculates the curvature for line segment pairs, in case the second segment is small (< 1 mm) and the angle between the two segments is large (> 135°). And on some of those tiny segments, the curvature the slicer has produced is simply incorrect - along a smooth curve, it is mostly consistent and then increases rapidly on that one tiny segment. Then, it's mostly fine again until the next tiny piece comes along.

This slicer inconsistency / bug leads Marlin to believe, that the curvature is extremely high in some locations, causing the print to slow down at the beginning of the affected segments. This is technically the correct behaviour - but the result still sucks. Therefore, I'm eagerly awaiting the new slicing code in Cura 4.7 and also hope that some Marlin devs got the time and motiviation to improve Junction Deviation further.

@chrisdalke
Copy link

Got it, thanks for the detailed explanation!

@brunoosti
Copy link

Had no luck with cura 4.7.
Reverted back to classic jerk and have my prints surface smooth as it should be.

@chendo
Copy link

chendo commented Sep 23, 2020

Having issues with still with 4.7.1 which I've noticed when printing via Octoprint on my Ender 3 v2. However, same gcode when printed via SD card has no issues for the models I'm testing with, which appears to be an issue with USB buffers not big enough. However, same model sliced with PrusaSlicer prints fine over Octoprint.

Octoprint is running on a desktop-class machine, so it appears to be a combination of complex gcode from Cura and Marlin buffers, at least in my scenario.

@fabioglopes
Copy link

I had the same issue printing the benchy hull. I increased the serial buffers on marlin configuration as I am using an external BTT TFT35 and I also increased Maximum resolution and Maximum deviation to 0.25mm on Cura and it solved the problem even with junction deviation enabled.

@XDA-Bam
Copy link

XDA-Bam commented Sep 23, 2020

I had the same issue printing the benchy hull. I increased the serial buffers on marlin configuration as I am using an external BTT TFT35 and I also increased Maximum resolution and Maximum deviation to 0.25mm on Cura and it solved the problem even with junction deviation enabled.

By decreasing the resolution / increasing the max. deviation, I would bet that you are essentially eliminating those tiny segments Cura otherwise squeezes into curves. Thereby, the junction angles are overall increased and Cura is forced to distribute the angles differently between the segments.

I have calculated that the angles between those tiny segments and the preceding/following longer ones found when using the default Cura settings are incorrect. They do not represent the appropriate curvature of the curves or circles (illustrated explanation here, example file which produces problems in Marlin when usding JD here). As JD relies relies on the curvature to calculate the junction speed (for segments below 1 mm in length), printers running Marlin with JD often stutter on curves with Cura GCode. This may also be influenced by how the STL is sliced and how Cura handles the STL.

The Octoprint thing is different from this geometry/angle problem: In that case, there are just too many of these tiny segments, causing the Marlin buffer to run dry, which causes slowdowns during printing.

Reducing the resolution and increasing the allowed deviation is a solid workaround for most people. But the problem in Cura is still present.

@Ghostkeeper
Copy link
Collaborator

I have calculated that the angles between those tiny segments and the preceding/following longer ones found when using the default Cura settings are incorrect. They do not represent the appropriate curvature of the curves or circles (illustrated explanation here, example file which produces problems in Marlin when usding JD here). As JD relies relies on the curvature to calculate the junction speed (for segments below 1 mm in length), printers running Marlin with JD often stutter on curves with Cura GCode. This may also be influenced by how the STL is sliced and how Cura handles the STL.

This could explain why #8321 was not seen with Ultimaker's printers but for many other printers it was. Ultimaker's printers forked off their Marlin version years ago.
We have a fix for #8321 but it turns out that there are still some cases left where it leaves tiny line segments. For the most part it seems to be gone now in our Master branch.

@XDA-Bam
Copy link

XDA-Bam commented Sep 25, 2020

This could explain why #8321 was not seen with Ultimaker's printers but for many other printers it was. Ultimaker's printers forked off their Marlin version years ago.
We have a fix for #8321 but it turns out that there are still some cases left where it leaves tiny line segments. For the most part it seems to be gone now in our Master branch.

Yes, that sounds plausible. The problematic Junction Deviation code path which relies on the curvature was introduced to Marlin in May '18. You can deactivate it in the current version by commenting out #define JD_HANDLE_SMALL_SEGMENTS in the config.

Very nice that most of those tiny segments are gone in master. Just to clarify: It's not the segment length itself that's critical. It's the curvature [length/sin(theta), with theta in Marlin defined as the angle to the preceding element]. The shorter segments just make the calculation more sensitive to errors in the angle.

@chendo
Copy link

chendo commented Sep 26, 2020

The Octoprint thing is different from this geometry/angle problem: In that case, there are just too many of these tiny segments, causing the Marlin buffer to run dry, which causes slowdowns during printing.

Yeah, now that I've read more about it, what I had was more another symptom than the root cause; thought I'd offer what information I've found. I did notice odd segment lengths when I was trying to debug the issue but I'm still very new to 3D printing (3 weeks in) so I wasn't sure what was normal and what wasn't.

I've worked around the issue for the time being by using Klipper, where the gcode that previously had issues now prints correctly, however it looks like the short segments may cause excessive extruder chattering. I've also had good success by enabling arc support and using the Arc Welder Octoprint plugin, which may be a viable workaround for anyone that needs to use 4.7.x for whatever reason still.

I'll be testing with 4.6.2 this weekend as well.

@KimmoHop
Copy link
Contributor

(About JD)

This could explain why #8321 was not seen with Ultimaker's printers but for many other printers it was. Ultimaker's printers forked off their Marlin version years ago.

I'm running Marlin 1.1.9 with jerk, S-curve and linear advance (this is easy to set off for test) and tiny segments cause stutter and blobs. Maybe JD is not only place where small segments are not always treated well?

@qwewer0
Copy link

qwewer0 commented Sep 29, 2020

@KimmoHop Could you try the affected gcode without S-Curve?

@XDA-Bam
Copy link

XDA-Bam commented Sep 29, 2020

(About JD)

This could explain why #8321 was not seen with Ultimaker's printers but for many other printers it was. Ultimaker's printers forked off their Marlin version years ago.

I'm running Marlin 1.1.9 with jerk, S-curve and linear advance (this is easy to set off for test) and tiny segments cause stutter and blobs. Maybe JD is not only place where small segments are not always treated well?

That may be the case, but your Marlin version is quite old (and has a couple of linear advance bugs, IIRC) and running S-curve in combination with linear advance is not recommended and not supported by Marlin. It may work on some gcode, it may fail on others.

You could deactivate LA or S-curve and test again. It may still fail, as you expect. There's also limitations concerning CPU usage, the possibility of the buffer running emtpy and those Octoprint problems mentioned before which could equally be triggered by the tiny segments and cause the artifacts. The problem with JD is the incorrect curvature, the problem in the other cases is likely just too many segments/second to process.

@KimmoHop
Copy link
Contributor

KimmoHop commented Sep 30, 2020

Update - NB! I forgot that I had set maximum resolution and maximum deviation to 0.1mm

This slightly out-of-focus might show it best:
IMG_20200930_084331
From left: S-curve + LA, S-curve, LA, neither. Same file, same day. PS sliced S+LA on right. PS has two simplifications, one that user can set that affects island shape and another fixed one that is applied to all lines (nozzle print paths) if I understood it correctly.

Another side, same order:
IMG_20200930_084459

It's a bit difficult to shoot what you see, but S-curve increases and LA decreases bumps :/

Another reference: PS benchy, S-curve + LA on left, LA on right (I need to clean my bed ;) )
IMG_20200930_084716
Some areas are a bit smoother without S-curve, some worse.

@KimmoHop
Copy link
Contributor

This goes a bit OT, but:

I'm running Marlin 1.1.9 with jerk, S-curve and linear advance (this is easy to set off for test) and tiny segments cause stutter and blobs. Maybe JD is not only place where small segments are not always treated well?

That may be the case, but your Marlin version is quite old (and has a couple of linear advance bugs, IIRC) and running S-curve in combination with linear advance is not recommended and not supported by Marlin. It may work on some gcode, it may fail on others.

How many printers currently in use do have Marlin 2.x? How many will be updated? I think "minority of 8-bitters" to first and "even less" to the second :D
There exists Marlin 2.x branch for AC Mega we have, but I'd have to merge "standard" display handling to it, and I really doubt if print quality would improve (enough or at all) to justify it.

Fortunately issues like #8321 will be (have been) fixed in slicer which is 100x easier to upgrade for majority of printing people.

@brunoosti
Copy link

In my experience a benchy will not show as much defects as some other pieces. Try printing a 1/4 of a big thin sphere (like the back of a 2mm shell helmet). Stuttering movements and blobs all over the place. Tried many things on the slicer with the only solution being disabling JD.
I have an anycubic i3 mega-s (8 bit board), with TMC2208s, updated to marling 2.0.5 with s-curve and LA enabled (k=5.5; yes it works fine with the TMC2208s on the extruder). I had to disable junction deviation in the source code to make it print smooth again. So, with no JD, perfect smooth curves and no stuttering movements on the printer axis.
I have to point out that when testing with LA below k=4 I had problems where the extruder would stop extruding. Anyways, around k=6 seams to be the calibrated value for the Ai3m-s.

@flexgrip
Copy link

So I am experiencing this exact same issue. I kept having these weird bumpy surfaces on curves. Noticeable on the curved portions of the hull on the benchy, especially.

I was scratching my head when I noticed on one of my older SD cards, I had an older gcode for a benchy (sliced in 4.6.2). I hit print and went to bed. Woke up this morning to a beautifully smooth benchy.

I then looked at the old gcode (4.6.2) vs the new one (4.7.1 and 4.8 beta). Both of the newer ones produced gcode that was more than double the file size of the one I sliced with 4.6.2. Immediately I realized it must have been a resolution thing. Looking at the tool paths in cura, I can see the hull of the 4.6.2 benchy is made up up 1-2mm lines. But like the OP observed... in the > 4.6.2 versions of Cura, it is creating an extremely high number of tiny segments.

I tweaked the maximum resolution to 1mm and they are starting to look similar. But then now the smaller circles on the smoke stack aren't super smooth.

I guess I could go back to 4.6.2. But would these numbers me unrealistic?

  • Maximum Resolution: 1mm
  • Maximum Deviation: 0.01mm

Would be nice if we could just disable whatever this new part of the slicing engine is. It's just not worth it if you can't increase your processing power/speed on lower end printers like my Ender 3 Pro. Even with the SKR Mini E3 v1.2, it just can't keep up with all of the tiny segments generated from Cura > 4.6.2 :(

@Ghostkeeper
Copy link
Collaborator

Ghostkeeper commented Oct 27, 2020

Both of the newer ones produced gcode that was more than double the file size of the one I sliced with 4.6.2.

Indeed, in Cura 4.6 there was a bug that caused the model to be sliced at way too coarse resolution if the Maximum Resolution was set to be very low. This was fixed in 4.7, leading to much larger g-codes for printers which had their Maximum Resolution setting tweaked very low (depending on the bug to produce g-code that is more manageable for the firmware). See also the discussion over at #8321. We're duplicating the same discussion here somewhat.

I think a Maximum Resolution of about 0.4mm is good for most printers. Maybe some high-end processors can reduce it somewhat (and no, 32-bit won't help a lot).

@Ghostkeeper
Copy link
Collaborator

This is expected to be fixed in Cura 5.0 (Arachne project) where wall overlap compensation has been removed.

@McNugget6750
Copy link

McNugget6750 commented Feb 16, 2022

The problem is still present in Cura 4.12.1.
image

And turning this off has no positive effect on the issue:
image

@McNugget6750
Copy link

Unfortunately, the feature that causes this is also my favorite feature of Cura.
image

I use this to calibrate my machine to match what I design in CAD as accurately as possible. For example, for my fast print profile I use these settings:
image
These generate lots of really tiny line segments as shown in my previous post. Turning these off to zero eliminates this problem entirely. Unfortunately, it appears to be a combination of both settings. Turning only one off to zero does not solve the problem completely. Turning both off, does.

It would seem that the math behind inset and outset (like in Inkscape) is troubling here. Doing the same thing in InkScape also causes odd shapes. So I assume this is not a trivial thing to implement. However, it is oh so important to get this right or at least remove those tiny little line segments that mess up every printer.

BTW: I had this issue on Marlin 2 and now on Klipper as well. It was actually the reason I transitioned to Klipper in the first place.

@McNugget6750
Copy link

It would seem that the latest Cura Beta 4.13.1 has this issue fixed. I'm going to test this now. https://github.com/Ultimaker/Cura/releases/tag/4.13.1

@McNugget6750
Copy link

McNugget6750 commented Feb 18, 2022

I can also confirm that the bug is still present in the latest Arachne Beta 2 build! DO NOT USE if you need the (Hole) Horizontal Expansion settings of Cura. Go for the 4.13.1 Beta instead.

@smartavionics
Copy link
Contributor

Does this build (equivalent to 4.13.1) work any better?

https://github.com/smartavionics/Cura/releases/tag/20220129

@McNugget6750
Copy link

I'm hesitant to try a fork, to be honest, especially when the config files get updated to be incompatible with other versions.
You could easily test this yourself by taking a very simple model (flat 20x40x4 piece with a 15mm hole in the center) and change the parameters for Horizontal Expansion and Hole Horizontal Expansion.
Then use the Preview view and move the layer slider to half.
Then use the slider that allows you to step through the line segments of that layer until you get to the point where the hole perimeter is being printed.

When you step through each segment using the left/right cursor keys, all segments of the circle should be roughly the same length. If there are a lot of really tiny line segments scattered around the perimeter circle, it's NOT fixed. Alternatively, use https://gcode.ws/ and zoom all the way in.

@smartavionics
Copy link
Contributor

I did what you suggested and couldn't see any little segments...

Screenshot 2022-02-18 20 56 49

Screenshot 2022-02-18 21 00 28

@McNugget6750
Copy link

Yes, that does look pretty clean! Should work!

@McNugget6750
Copy link

Unfortunately, I must correct myself, the bug isn't gone. It appears when a negative value is used for Horizontal Expansion to decrease the size of the outer perimeter. Essentially to make the parts a tad smaller. Unfortunately, this also makes the holes larger - even though there is a separate setting called Hole Horizontal Expansion for that - which destroys the model and creates all these tiny vertices that no printer firmware can deal with.

To test this, enter Horizontal Expansion = -0.05 and test again. It's gonna mess things up. I also have Hole Horizontal Expansion = 0.3 in this test.

@smartavionics
Copy link
Contributor

Well, I did try with similar values. Why don't you post the project file so I can be sure that I am using exactly the same model and settings?

@McNugget6750
Copy link

McNugget6750 commented Feb 21, 2022

Here you go. I hope this is helpful :)
CFFFP_15mm hole calibration_v2.zip

@smartavionics
Copy link
Contributor

Thanks for the project file. When I slice that with no changes to the settings, I cannot see any small line segments. Where exactly are they?

@McNugget6750
Copy link

In this project file you can see them on the inner perimeter of the 15mm hole!
When you click through the line segments making the perimeter of the whole you can see the visualized print head nozzle stop and go in uneven distances. That's not gonna result in a smooth print.
In this example, the exterior perimeter of the print is fine. You can only see it inside the hole. It depends on the number of polygons per mm used during STL export.

@smartavionics
Copy link
Contributor

I still can't see what you're talking about, please provide an image showing some bad points.

@McNugget6750
Copy link

McNugget6750 commented Feb 21, 2022

I just uploaded this to youtube. It's unlisted and only for here. https://youtu.be/qIyQjVGckjg

You can see how the head constantly stops for no reason. Once I get home, I can also upload the exported gCode file.

@smartavionics
Copy link
Contributor

Yes, please upload the gcode file, thanks.

@McNugget6750
Copy link

@smartavionics
Copy link
Contributor

Thanks for the file. That wasn't generated using my build, it was generated using 4.13.1.

I attach the gcode I produced so you can see the difference.

CFFFP_15mm.hole.calibration_v2_gcode-mb.zip

@McNugget6750
Copy link

Alright, convinced. I'll give your build a shot. I just really hope it doesn't break my configs I worked for quite some time on.

@smartavionics
Copy link
Contributor

What I do to survive the trashing of my Cura configs that can happen when developing is to put all of my configuration into a git repo and then simply commit all changes from time to time (especially before running cura having made some major changes). That way, you can roll back all of the configuration files to a previous snapshot very easily.

@McNugget6750
Copy link

Where should I look for them?
I'm googling this right now https://github.com/Ultimaker/Cura/wiki/Cura-Preferences-and-Settings-Locations
I hope that's all of them. Looks like it. As long as they don't store anything important inside of the Windows Registry...

@smartavionics
Copy link
Contributor

My build will put the settings in a folder called "master" and won't modify any files in existing cura setting folders. If you load an existing project file into my cura and then save it, that file could possibly be altered such that it would cause a problem with UM cura but I don't know for sure. So it would be wise to make backups of project files just in case. I'm certainly not aware of any issues related to this.

@McNugget6750
Copy link

A very first test with negative Horizontal Expansion shows your build DOES fix this issue! More testing is needed but if this holds true, I strongly recommend checking where this comes from and then creating a pull request. This bug has been present for such a long time now!

[...]

I tested some more, even changed the export settings in Solidworks to super fine resolution to stress this a little by adding loads more polygons as well as very few polygons. It seems stable! Amazing stuff!

I was trying to get Cura to compile but with no luck so far. I might want to bother you about that at some point.

@smartavionics
Copy link
Contributor

OK, but the bad news is that my Cura diverged quite markedly from UM Cura many moons ago and I haven't a clue at the moment as to what change(s) are making a difference here. I'll investigate and get back...

@smartavionics
Copy link
Contributor

smartavionics commented Feb 23, 2022

Well, that was easy enough. The problem is due to bugs in the UM version of a function called simplify(). The purpose of that function is to reduce the number of points in a polygon without making the simplified polygon too ugly. The history of this is that a few years ago, I proposed alterations (Ultimaker/CuraEngine#1114) to simplify() to fix some existing issues but the UM devs never accepted my offering, as they preferred to go their own way. I didn't have a problem with that because I was happy to use my version of simplify(). Anyway, if I substitute my simplify() into the 4.13.1 source, all those extraneous points and jaggies go away. So, Cura devs, here's my version of simplify() again, I hope it's useful...

void PolygonRef::simplify(const coord_t smallest_line_segment_squared, const coord_t allowed_error_distance_squared)
{
    if (size() < 3)
    {
        clear();
        return;
    }
    if (size() == 3)
    {
        return;
    }

    ClipperLib::Path new_path;
    Point previous = path->at(0);
    Point current = path->at(1);
    /* When removing a vertex, we'll check if the delta area of the polygon
     * remains below allowed_error_distance_squared. However when removing
     * multiple consecutive vertices, each individual vertex may result in a
     * delta area below the threshold, while the total effect of removing all of
     * those vertices results in too much area being removed. So we accumulate
     * the area that is going to be removed by a streak of consecutive vertices
     * and don't allow that to exceed allowed_error_distance_squared. */
    coord_t accumulated_area_removed = previous.X * current.Y - previous.Y * current.X; //Shoelace formula for area of polygon per line segment.

    new_path.push_back(previous);

    // end points of the reference line against which other line segments are compared for co-linearity
    Point ref_line_start;
    Point ref_line_end;

    for (size_t point_idx = 1; point_idx < size(); point_idx++)
    {
        current = path->at(point_idx);

        Point next = path->at((point_idx + 1) % size());

        const coord_t length2 = vSize2(current - previous);
        if (length2 < 25)
        {
            // We're allowed to always delete segments of less than 5 micron.
            continue;
        }

        //Check if the accumulated area doesn't exceed the maximum.
        accumulated_area_removed += current.X * next.Y - current.Y * next.X; //Shoelace formula for area of polygon per line segment.

        const coord_t area_removed_so_far = accumulated_area_removed + next.X * previous.Y - next.Y * previous.X; //Close the polygon.
        const coord_t base_length_2 = vSize2(next - previous);
        if (base_length_2 == 0) //Two line segments form a line back and forth with no area.
        {
            continue; //Remove the vertex.
        }
        //We want to check if the height of the triangle formed by previous, current and next vertices is less than allowed_error_distance_squared.
        //L = b * h           [apply above two and take out the 1/2]
        //h = L / b           [divide by b]
        //h^2 = (L / b)^2     [square it]
        //h^2 = L^2 / b^2     [factor the divisor]
        const coord_t height_2 = area_removed_so_far * area_removed_so_far / base_length_2;
        if (length2 < smallest_line_segment_squared && height_2 <= allowed_error_distance_squared) //Line is small and removing it doesn't introduce too much error.
        {
            continue; //Remove the vertex.
        }
        else if (length2 >= smallest_line_segment_squared && new_path.size() > 2 &&
                LinearAlg2D::getDistFromLine(current, ref_line_start, ref_line_end) <= 2) //Almost exactly straight (barring rounding errors).
        {
            new_path.pop_back(); //Remove the previous vertex but still add the new one.
        }
        else
        {
            // update the reference line
            ref_line_start = previous;
            ref_line_end = current;
        }
        //Don't remove the vertex.

        accumulated_area_removed = current.X * next.Y - current.Y * next.X;
        previous = current; //Note that "previous" is only updated if we don't remove the vertex.
        new_path.push_back(current);
    }

    //For the last/first vertex, we didn't check the connection that closes the polygon yet. Remove it if it's too short.
    if(new_path.size() > 2 && (vSize2(new_path.back() - new_path[0]) < smallest_line_segment_squared || vSize2(new_path.back() - new_path[new_path.size() - 2]) < smallest_line_segment_squared))
    {
        if (LinearAlg2D::getDist2FromLine(new_path.back(), new_path[new_path.size() - 2], new_path[0]) < allowed_error_distance_squared)
        {
            new_path.pop_back();
        }
    }
    //For the first two points we haven't checked yet if they are almost exactly straight.
    if (new_path.size() > 2)
    {
        if (LinearAlg2D::getDistFromLine(new_path[0], new_path.back(), new_path[1]) <= 2)
        {
            // first point is colinear, remove it and check the 2nd point
            new_path.erase(new_path.begin());
            if (new_path.size() > 2 && LinearAlg2D::getDistFromLine(new_path[0], new_path.back(), new_path[1]) <= 2)
            {
                new_path.erase(new_path.begin());
            }
        }
        else if (LinearAlg2D::getDistFromLine(new_path[1], new_path[0], new_path[2]) <= 2)
        {
            new_path.erase(new_path.begin() + 1);
        }
    }

    *path = new_path;
}

@XDA-Bam
Copy link

XDA-Bam commented May 20, 2022

Hi. Has anybody tested if this is fixed in 5.0? Because it looks like there have been significant changes to simplify and also one specific commit a week ago to dress this.

@GregValiant GregValiant added Status: Needs Info Needs more information before action can be taken. Status: Stale ⌛ This issue is over a year old. It might be obsolete or just needs a fresh set of eyes labels Nov 22, 2024
@GregValiant
Copy link
Collaborator

I'm cleaning house.
Is this still an issue in current Cura versions (5.8.0 and up)? Can this be closed?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Status: Needs Info Needs more information before action can be taken. Status: Stale ⌛ This issue is over a year old. It might be obsolete or just needs a fresh set of eyes Type: Bug The code does not produce the intended behavior.
Projects
None yet
Development

No branches or pull requests