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.

Sign up for GitHub

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

Jump to bottom

A large fractal pyramid takes ages to slice. #117

Closed
bubnikv opened this issue Feb 10, 2017 · 3 comments
Closed

A large fractal pyramid takes ages to slice. #117

bubnikv opened this issue Feb 10, 2017 · 3 comments

Comments

@bubnikv
Copy link
Collaborator

bubnikv commented Feb 10, 2017

A large fractal pyramid takes ages to slice.
http://www.thingiverse.com/thing:1356547

Likely the reason is the plethora of islands.
The smaller fractal pyramids are processed relatively quickly.
@bubnikv
Copy link
Collaborator Author

bubnikv commented Feb 28, 2017

The underlying Clipper library does not handle long overlapping contours well. It handles them, but it takes ages to process. A single call of a clipper diff call takes 10 minutes in a debug build at the base of the pyramid.

Here are the contours in SVG format.
exactly-overlapping-contours.zip

@bubnikv
Copy link
Collaborator Author

bubnikv commented Mar 1, 2017

The Clipper::JoinCommonEdges method has a terrible time complexity for complex partially overlapping polygons.

call tree                                                                          calls       self time      total time
<unprofiled>                                                                         1.0     44 ms    0%    247 s   100%
  ClipperLib::ClipperBase::Clear                                                     3.0      2 ms    0%      2 ms    0%
  ClipperLib::ClipperBase::AddPaths                                                  2.0    423 us    0%     33 ms    0%
    ClipperLib::ClipperBase::AddPath                                              5461.0     33 ms    0%     33 ms    0%
  ClipperLib::Clipper::Execute                                                       1.0      6 ms    0%    246 s   100%
    ClipperLib::Clipper::ExecuteInternal                                             1.0     83 us    0%    246 s   100%
      Clipper_ExecuteInternal_Process                                                1.0     14 ms    0%    170 ms    0%
        ClipperLib::Clipper::Reset                                                   1.0      2 ms    0%      8 ms    0%
          ClipperLib::ClipperBase::Reset                                             1.0      6 ms    0%      6 ms    0%
        ClipperLib::Clipper::InsertLocalMinimaIntoAEL                              863.0     21 ms    0%     33 ms    0%
          ClipperLib::Clipper::AddLocalMinPoly                                    10098.0     11 ms    0%     11 ms    0
        ClipperLib::Clipper::ProcessHorizontals                                    863.0     19 ms    0%     20 ms    0%
          ClipperLib::Clipper::AddLocalMinPoly                                     555.0    573 us    0%    573 us    0%
        ClipperLib::Clipper::ProcessIntersections                                  863.0      6 ms    0%      6 ms    0%
          ClipperLib::Clipper::AddLocalMinPoly                                      35.0     53 us    0%     53 us    0%
        ClipperLib::Clipper::ProcessEdgesAtTopOfScanbeam                           863.0     13 ms    0%     90 ms    0%
          ClipperLib::Clipper::ProcessHorizontals                                  863.0     76 ms    0%     77 ms    0%
            ClipperLib::Clipper::AddLocalMinPoly                                   497.0    825 us    0%    825 us    0%
          ClipperLib::Clipper::AddLocalMinPoly                                      50.0     45 us    0%     45 us    0%
      Clipper_ExecuteInternal_Fix                                                    1.0      2 us    0%    246 s   100%
        Clipper_ExecuteInternal_Fix_orientations                                     1.0      3 ms    0%      3 ms    0%
        ClipperLib::Clipper::JoinCommonEdges                                         1.0      2 s     1%    246 s   100%
          ClipperLib::Poly2ContainsPoly1                                          2423486.0    243 s    98%    243 s
          ClipperLib::Clipper::FixupFirstLefts1                                   1967.0    648 ms    0%      2 s     1%
            ClipperLib::Poly2ContainsPoly1                                        1578337.0      1 s     1%      1 s
        Clipper_ExecuteInternal_Fix_fixup                                            1.0      5 ms    0%      5 ms    0%

bubnikv added a commit that referenced this issue Mar 2, 2017
@bubnikv
Fix of #117: A large fractal pyramid takes ages to slice
73f603d 
The Clipper library has difficulties processing overlapping polygons.
Namely, the function Clipper::JoinCommonEdges() has potentially a terrible time complexity if the output
of the operation is of the PolyTree type.
This function implmenets a following workaround:
1) Peform the Clipper operation with the output to Paths. This method handles overlaps in a reasonable time.
2) Run Clipper Union once again to extract the PolyTree from the result of 1).
@bubnikv
Copy link
Collaborator Author

bubnikv commented Mar 6, 2017

Fixed by
73f603d

The Clipper library has difficulties processing overlapping polygons.
Namely, the function Clipper::JoinCommonEdges() has potentially a terrible time complexity if the output
of the operation is of the PolyTree type.
This function implmenets a following workaround:

  1. Peform the Clipper operation with the output to Paths. This method handles overlaps in a reasonable time.
  2. Run Clipper Union once again to extract the PolyTree from the result of 1).

@bubnikv bubnikv closed this as completed Mar 6, 2017
CReimer pushed a commit to CReimer/Slic3r that referenced this issue Jul 28, 2017
@bubnikv @alranel
Fix of prusa3d#117: A large fractal pyramid takes ages to slice
c4929c3 
The Clipper library has difficulties processing overlapping polygons.
Namely, the function Clipper::JoinCommonEdges() has potentially a terrible time complexity if the output
of the operation is of the PolyTree type.
This function implmenets a following workaround:
1) Peform the Clipper operation with the output to Paths. This method handles overlaps in a reasonable time.
2) Run Clipper Union once again to extract the PolyTree from the result of 1).

Conflicts:

	xs/src/libslic3r/ClipperUtils.cpp
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@bubnikv