Avoid crossing perimeters is slow (was: 1.0.0RC1 hangs exporting gcode)

[Jerrill]

When trying to export gcode for this model using these setting, Slic3r hangs "Exporting G-code to..."

Here are the files required to reproduce the issue:

https://github.com/Jerrill/files-for-issues/tree/master/slic3r-1.0.0RC1/01

I'm running the Max OSX version of Slic3r.

[Jerrill]

It appears to be related to the thickness of the tower walls. I increased the wall thickness to 0.5 mm and it successfully exported.

[alranel]

Thank you, I will verify that issue.

[Jerrill]

Here's another one that seems to hang Slic3r: https://github.com/Jerrill/files-for-issues/tree/master/slic3r-1.0.0RC1/02

[alranel]

avoid_crossing_perimeters is the culprit. It's slow… for now. :-)

[RetireeJay46]

I just compared Slic3r 0.9.9 against 1.0.0rc1, and the older versions is MUCH faster to finish the step of Exporting G-Code. Same model, same settings.

[frankjoke]

Ye, Exporting G-Code in new version takes endless, I have no clue wha the difference is. Even small parts which slice in seconds with KIss or Cura and old Slic3r can take now minutes, some more complex an hour, but all other process before is finished in seconds, just export is slow.

And by the bay, it seems it does not use multiprocessing in this part as well because CPU utilization is onloy for one CPU. would be cool to do multiple layers in different CPU's... Maybe somebody working on changing export code tells us what was added or changed and which options influence it.

[alranel]

@ledvinap, I have a couple ideas here:

• generate configuration space on-demand (i.e. no need to build the graph when we have a single, convex, island, or no need to build the external parts if we have a single island anyway etc.)
• use Voronoi diagram as graph in most complex cases (complexity seems way lower)

[ledvinap]

The current graphs have few thousand edges. With decent algorithm to generate configuration space (visibility testing is probably main culprit, all polygons needs to be passed to clipper space for each tested line. Also discarding long edges could help a lot) and O(n log n) Dijkstra implementation it should be so fast that time spent is not a problem.

The path-finding does not need to be perfect - it is OK to find good path, there is no need for it to be shortest. This allows lot of simplifications.

BTW: What do you think about Boost.Geometry.Index for point handling? It should allow fast interval search and enable using point set (simplifying configuration space generation)

[alranel]

While I wouldn't like to reintroduce dependency on Boost.Geometry, your idea about Boost.Geometry.Index sounds interesting. Do you have any idea about a possible algorithm using it?

[alranel]

Idea: http://www.visilibity.org/ :-)

[taraba]

I'm also having issue with the gears.stl file from http://www.thingiverse.com/thing:264769/#files on 1.0.1. It's a 12 MB stl so that doesn't help any. The weird thing is that it's only eating 13% of the CPU on my i7 processor with 4 threads. The HDD doesn't look to be limiting it so I'm wondering why it's not using more CPU.

I'll test it out on the latest development version as see if there's still an issue.

[ledvinap]

I have some very preliminary but promising results with path planning.

The idea is to use grid combined with equally spaced points around slices for path planning and improve results with variant of Theta* http://en.wikipedia.org/wiki/Any-angle_path_planning.

Visibility checking could be reduced only to nearby points. Clipper seems fast enough to check visibility if test is done in batches (clipper is using linear linked lists with insertion sort for some operations internally. This gets too slow quite quickly).

Event without optimization it's speed seems to be acceptable and search complexity could probably stay within O(nlog(n)) of graph area.

Work-in-progress (in terrible state) is in local branch of my Slic3r clone

[alranel]

I have been working on that too using a very different approach, maybe I'll have it finished later. And this is probably a good thing since we can benchmark our approaches and compare who did better :)

[alranel]

Hi again @ledvinap, my implementation using VisiLibity is published in the visilibity branch. I'm curious to see how yours is going to perform compared to this one. :) (And if we could avoid an additional dependency I'd be very happy!)

[ledvinap]

Very poorly, probably ;-) Visilibity or some similar algorithm could perform very well. The problem is - how to choose perimeter crossing if necessary? If I understand visilibity, it uses hard boundaries. But is perimeter crossing optimization important at all? In my opinion it would be nice to choose carefully (make crossing short, avoid multiple crossings, don't use too long path to avoid crossing, maybe prefer some easy-to-clean spots). It could be be quite easily expressed in connectivity graph, but is harder with polygon approach..

[alranel]

I completely agree with you...

[alranel]

Actually, I agree on your thoughts about visibility approach vs. connectivity graph. Regarding the need for a fast algorithm I'd say this is a priority and we might need more than one mode, letting user choose his desired compromise between accuracy vs speed.

How's your work going on this?

[ledvinap]

Well, it's slow, too many other things to do ... I am testing new approach with delaunay triangulation, basically simplifying detour from https://github.com/memononen/recastnavigation/. Now working on constrained dalaunay - poly2tri should be usable, but something like poly2tri-c or Triangle would be better ...

[alranel]

Triangle is not usable because of licensing issues. What advantes does poly2tri-c have over the original poly2tri?

[ledvinap]

Poly2tri-c does implement delaunay refinement method. I'am afraid that CDT alone will result in lots of skinny triangles (curved boundary area means lot's of short constrained segments), possibly causing problems for path planner. I'll know more when it is at least partially working ...

[alranel]

Bad news. The visilibity branch works correctly, but it's still too slow. The model provided by @Jerrill is a torture test for visibility algorithms because it's got may little holes/obstacles.

[ledvinap]

Hmm ...does visilibity really check visibility of all other points for each search node? That won't scale well ...

[ledvinap]

I have barely working version that uses poly2tri to triangulate layer with 1mm equally spaced on both sides of slicer boundary and then finds shortest path connecting midpoints of triangles. It does not handle boundary weight now and contains bugs (the path is strange .. but connected). G-code generation for first test file is around 5 seconds (22 total), so it seems quite promising ... Triangle refinement will be very helpful, but maybe simple funnel mechanism will be enough ...

[alranel]

I just pushed one more implementation to the acp-voronoi branch. This one builds a graph by generating the Voronoi diagram of the ExPolygon. The Voronoi diagram basically provides a central skeleton and connections between it and each vertex. My implementation still contains some mistake, but performance looks very promising even with the torture test. It's completely implemented in C++, so we have a port of the Dijkstra search.

[alranel]

Also your approach is interesting; why did you use poly2tri instead of polypartition which is already in our codebase?

[ledvinap]

Voronoi skeleton is great for avoiding walls as much as possible, but will be slightly suboptimal for FDM. Maybe funnel algorithm can fix that ... How do you handle crossing of object boundary? I'll expect quite strange paths being selected ..

poly2tri is included in master. From polypartition home page, only Hertel-Mehlhorn seems usable, others have low quality or high complexity.

[alranel]

Oh, you're right. We have both polypartition and poly2tri. I don't remember which one we're using right now :)

The idea behind this Voronoi-based implementation is:

• inset island and build a graph using Voronoi (boundaries + skeleton + links between them)
• outset islands, use them as holes and build a contour using bounding box of the entire object, and build a graph using Voronoi
• if travel endpoints are both within the same graph (i.e. both in the same island or neither in islands), use it for motion, otherwise do a straight move to the closest point in the outer graph, then move there towards destination

So, there's no graph between the inner and the outer boundaries. Crossing penalty can be applied to the resulting path, i.e.: if the final path is much longer than any straight path, do the straight path anyway.

[alranel]

That funnel algorithm sounds promising...

[ledvinap]

My motion planner algorithm is actually able to find path ;-) I pushed last version to my local branch. Please ignore code quality ...

triangles: green - normal cost ; red - penalized circles - Dijkstra: white - not visited; gray - visited; black - closed; yellow - part of path blue line points to triangle parent green circles, red line - path

Speed is excelent - even with optimization disabled (-O0) and writing lot's of stl's first file is 34s .. 5s from previous test seems reasonable (and it could be improved further)

[ledvinap]

Triangle refinement will probably help a lot .. poly2tri-c seems to be best candidate now ...

[ledvinap]

Implemented string pulling from recast/detour, seems to work well.

Also using constrained delaunay triangle is nearly equivalent to using voronoi skeleton - only path vertices are on triangle side instead of triangle center ...

[ledvinap]

I have problem with penalized area outline overlap - union after equally_spaced_points will probably help. But it would be nice to to be able to ensure that there is some safety distance after offset - offsetting by this distance should not cause any intersection (including self-intersection) of polygon. For example with polygon in shape of letter C, I want to ensure than ends are farther than specified distance, clipping them if necessary, or that they overlap, creating O shape. Is there some Clipper operation sequence to do this?

[ledvinap]

Just a progress update - the algorithm seems to work quite well. There are many possible improvements, but is usable.

with CROSSING_PENALTY => 1000, inner_margin .3, outer_margin 1 :

[ledvinap]

Got poly2tri-c mostly working. It does help in cases when path through big triangle is too long to be considered. It is reasonably fast. String pulling algorithm fails sometimes to produce straight path - portals through triangles are shifted a bit from straight line, resulting path is 'almost straight' and in many cased shorter than simple CDT result. Poly2tri-c refinement sometimes fails - it is probably caused with degenerate input geometry, I'll need to investigate that further.

Using poly2tri-c will bring in glib (https://developer.gnome.org/glib/stable/).

Is poly2tri-c inclusion acceptable? Maybe it could be used as optional part (any algorithm that converts PSLG to convex polygons should do, but resulting path quality will vary)...

[ledvinap]

Sample of refined CDT - the result is not bad, speed seems to be aproximately linear with model area (it goes as n^3 with --scale n for maze)

[idzuwan]

I know this is old but seem this problem still exist on 1.0.0RC3, it will take forever to generate gcode with avoid_crossing_perimeters enabled

[harlequin-tech]

The problem is still present in 1.1.5 on OSX 10.9.3. Takes forever to complete the slice and output gcode with avoid_crossing_perimeters enabled, very fast with it disabled.

[lordofhyphens]

Is this still a problem in 1.3.0-dev or https://github.com/alexrj/Slic3r/files/336282/slic3r-most_prs.zip ? Please reopen if it is.

avoid_crossing_perimeters is a much more complex problem as well, so it is going to be slower in general than not doing so.