prusa3d / PrusaSlicer

G-code generator for 3D printers (RepRap, Makerbot, Ultimaker etc.)
https://www.prusa3d.com/prusaslicer/
GNU Affero General Public License v3.0
7.8k stars 1.94k forks source link

Rewrite perimeter fuzzification functions to properly follow perimeter shape #13593

Open Jarno-de-Wit opened 2 weeks ago

Jarno-de-Wit commented 2 weeks ago

The previous implementation of the fuzzy_polygon (classic perimeter generator) and fuzzy_extrusion_line (Arachne perimeter generator) did not work well at larger values for Fuzzy skin point distance. At higher values, the generator would start cutting corners, and overshooting at corners leading to incorrect overhangs being generated. The latter of these issues was reported in #7744.

This PR is a complete rewrite of the fuzzification algorithm to work well with both small and large values for Fuzzy skin point distance. The table below shows a comparison between the old and new fuzzy skin generation algorithm between the old fuzzification algorithm (left), and the new fuzzification algorithm (right) at various Fuzzy skin point distance values. (Note: the top infill has been hidden to better show the difference between the algorithms.)

Fuzzy skin point distance Old fuzzification algorithm New fuzzification algorithm
0.8 mm Old_0 8 New_0 8
2.0 mm Old_2 0 New_2 0
5.0 mm Old_5 0 New_5 0
50.0 mm Old_50 0 New_50 0
5.0 mm (Top down view) Old_5 0_top New_5 0_top

A brief summary of how the new algorithm works:

while not at the end:
    choose new segment length
    for each original corner point on this segment:
        place this corner point at the appropriate offset (magnitude determined using linear interpolation over current segment)
    place the end point of the segment

Since a new point is placed at x-locations where a corner point existed in the original line, the corner cutting that was visible in the original algorithm is avoided. By cleverly picking the lengths of each of the segments (i.e. taking into account the remaining perimeter length), the outline can be closed with every segment length being in the acceptable range, thus not suffering from the overshoot present in the original algorithm

Jarno-de-Wit commented 1 week ago

While the 2.9 update fixed the overshoot issue in the Fuzzy Skin generator, in doing so a new problem was introduced where the external fuzzy perimeter would be stopped too early. This leads to the perimeter not always being properly closed, and in extreme cases even being completely missing in case the Fuzzy skin point distance is set larger than the perimeter's length. Additionally, the corner cutting behaviour that existed in 2.8.1 (and is visible in the screenshots above) still exists in 2.9.0-alpha1. Both of these issues are fixed in the new fuzzification functions implemented in this PR.

As the fuzzy skin generation code was moved to a different file in 2.9.0-alpha1, I have updated the linked branch of this PR (fuzzy-skin-fix) to be up to date with the public master branch again.

Jarno-de-Wit commented 1 week ago

Another side by side to highlight the improvements of the new / fixed algorithm over the one currently in 2.9.0-alpha1. The shape is the same as the one used above. In the first two rows, a cylindrical modifier is added at one of the corners which has a different point distance from the main shape. This causes the perimeter to no longer consist of closed loops for the bottom half of the shape, triggering some of the issues mentioned above (i.e. too short perimeter extrusion).

Notes:

Scenario 2.9.0-alpha1 algorithm New fuzzification algorithm
Point distance: 10 mm - Modifier point distance: 1 mm V2 9-Seams New-Seams
Point distance: 10 mm - Modifier point distance: 15 mm V2 9-Short New-Short
Point distance: 75 mm - No modifier V2 9-75 0 New-75 0