Bridging direction calculation

[Huwyler]

I have looked at the way the bridging direction works and I think this should be done differently:

Imagine a hollow cube (or a rectangular tube) with a rectangual cut-out on one of its sides.

A layer within this cut-out would look like somwhat like a (ectangular)"C". The first layer on top of the cut-out would then be a (rectangular) "O".

Now, as far as I understand it, the bridging direction algo looks at the last layer being a "C" and finds that it's only one "part". So, the bridging direction is set to -1, leading to "normal" alternating infill directions. If you have the cut-out on both sides, the bridging direction is correct. because the algo sees two parts below and finds that their centers of gravity are in the direction of each other that I would expect to be the bridging direction.

Generally, I think having the bridging direction as member of a layer "part" is not so good. Imagine having a cut out on the right side and another one on the top side. Which direction should be used on that "O" shaped "part"?

I have looked into the code only shortly, but Looking at the output, I see (and indeed it's clear) that the engine is able to detect the area where there has to be a solid infill. So what about this idea: Remove this "bridge direction" member of the whole layer part. Instead, after having calculated the bottom infill area, make an intersection of this area with the whole layer below. In the example above (with one cut-out on the right side) the result would be two rectangular polygons (because of the overlap of the bridging area). Now take the centers of gravity of them, and you have your direction. On the same part, there may be the above mentioned cut-out on the top side. Here you do the same, and you have again the correct angle.

As I said, I havent looked very closely at the code. Maybe there is something that I am missing which makes this impossible. Starting somewhere in February (this month I am very busy) I would be happy to take a closer look at it and maybe try to implement this (it doesn't seem to be very complicated to me). But I just wanted to ask you what you think about it first.

[daid]

You are right that this definitely needs some re-work. I currently did it per "layerPart" because that was already slightly better then the Skeinforge "per layer" bridge direction. So doing it per infill area would already be an improvement over the current implementation.

However, I do not think the "intersect full infill area with layer below" would work correctly for C shaped parts. As you would still get a C shaped intersection going around the whole edge.

What Skeinforge did was looking at all the places where the infill crossed the layer below. On every crossing it calculated the angle, and the infill angle was then the average of all those angles. Which gave it's own share of problems, but might give you more ideas.

Finally, I would love it if someone could take a look at this. I'm busy enough as it is. And improving bridges is something I want, but not something I haven't found time to do yet.

[Huwyler]

Thank you for your response! I'd be glad if I could help! :-)

I still think that with the part I have in mind, my strategy would work, as the intersection is not C-shaped, but consisting of two tiny rectangles. But probably you have another part in your mind. I should have added a picture. :-)

But anyway, there are other situations (maybe the one you thought I was thinking of) where my strategy wouldn't work. Namely where the intersection really IS C-shaped.

I'll think about it. But as I said, no sooner as in February.

[daid]

Ah, yes, I was thinking of the 2nd one. That's the one I'm really hoping to solve one day. It's quite common to have shapes like that which are not printer properly right now, while the skeinforge implementation sort-of did those correct.

[richardjm]

I've been thinking about this issue too. Would some kind of longest straight unsupported length calculation work. So you look at all the edges that aren't supported and then find the longest edge and bridge parallel to that.

Just a thought.

[BagelOrb]

Note that a full solution will encounter the following problem: Consider an overhang area shaped like the area below the 'M'.

Where the left side, right side and bottom are supported, but the top sides are not. In such a case any bridging strategy can cover only subareas of the total - three examples below

Therefore any complete solution must contain a heuristic for choosing between alternative bridgings.

[richardjm]

I think the idea of using longest unsupported edge still works as no strategy will actually work in this example it would choose either the first or last case. On 21 Dec 2014 16:40, "Tim Kuipers" notifications@github.com wrote:

Note that a full solution will encounter the following problem: Consider an overhang area shaped like the area below the 'M'.

Where the left side, right side and bottom are supported, but the top sides are not. In such a case any bridging strategy can cover only subareas of the total

• three examples below

[image: bridging problem] https://cloud.githubusercontent.com/assets/8895761/5518119/47af153c-8916-11e4-9c38-fd0fa6d1e008.png

Therefore any complete solution must contain a heuristic for choosing between alternative bridgings.

— Reply to this email directly or view it on GitHub https://github.com/Ultimaker/CuraEngine/issues/50#issuecomment-67775977.

[BagelOrb]

It will be suboptimal in some situations, but it certainly is a good approximation and quite simple to implement.

I have no idea of how the bridging direction is currently implemented. Does anyone have the prerequisites to implement this modification? I don't think Daid has time for it.

[richardjm]

I did have a look at the code it currently picks the two largest areas and bridges based on centre mass of those. I could dig into the code and work on creating a pull request for it but it'll take me a little while to get up to speed on the engine.

On 22 December 2014 at 10:02, Tim Kuipers notifications@github.com wrote:

It will be suboptimal in some situations, but it certainly is a good approximation and quite simple to implement.

I have no idea of how the bridging direction is currently implemented. Does anyone have the prerequisites to implement this modification? I don't think Daid has time for it.

— Reply to this email directly or view it on GitHub https://github.com/Ultimaker/CuraEngine/issues/50#issuecomment-67820300.

Richard

[Mowi]

My bridges also fail although they have a supported edge. The bridges ends do not always attach properly to the edge underneath. At the moment Cura attaches the bridges only on the perimeters of the previous layer. You could get better attachment if you use a bigger area to attach the ends on. So also attach it on the infill off the previous layer and maybe even make that area a solid infill. You could combine the "better layer before bridging?" and the "slic3r bridge" from the image below. To decide on the direction of the bridge you could then also look on the sides that offer best chances for a good attachment.

[BagelOrb]

@Mowl your comment is not on the direction of the bridges, but on the area which they cover. Please make a separate issue.

[NicholasSeward]

It is often that I need to provide a countersink for a hole on the bottom of my part. I either add a chamfer or I remove the hole for 1 layer to allow bridging and will drill the hole afterwards. However, I think it is possible to solve this for more than just circular holes.

The gray is the previous layer. The blue lines are what I call skeleton lines and you add as many as you need to define the unsupported edge. (I realize that the bottom layer quality will suffer [or look super sweet in my opinion] with this approach but would be more than acceptable in any mechanical part that needs this.) Once the skeleton is in place, pick the largest exposed skeleton line and add parallel lines (green) until you can't. Repeat with the next largest exposed section of a skeleton line.

I am going to have one of my students prototype this to see how it will actually work and look. Would this be something that you guys would be interested in?

[nallath]

We're always interested in experiments :)

[BagelOrb]

Note that your example on the right is rather suboptimal; you can simply bridge horizontally!

Also note that you shouldn't print all skeleton lines fully. The left bottom half of the / angled line in your right example doesn't need to be printed (and is overextruding).

Things will get a lot more complicated when

• The hole in your left example isn't convex
• The previous layer in your left example doesn't fully surround the hole in the next layer.
• The previous layer in the right example consists of several polygons around the area of the next layer.

I advise not to try and fix all these problems, but handle them as limitations of the bridging algorithm - areas which simply aren't bridged. It's too much to try and solve all these problems at once. You do need to handle avoiding such cases, though.

[NicholasSeward]

I am just brainstorming here. The example below is extreme but could work on a very well calibrated machine doing super slow bridging. I would love feedback and tweaks while I am in the brainstorming stage.

The algorithm is as follows: (The example doesn't follow the algorithm exactly but it should get the idea across.)

1. Find the shortest line* that runs along an unsupported edge. If found go to 4.
2. Find the shortest line* that runs along an unsupported vertex. If found go to 4.
3. Find the shortest line* that runs over an unsupported region. If found go to 4 else end.
4. Get max printable band that contains the found line.
5. Subtract band from region to be printed. Treat edges created from the subtraction as a supported edge. Go to 1.

*anchored on both ends

[nickthetait]

Your algorithm seems pretty sensible Nicholas, but I don't understand the picture. Could you provide some explanation on the colors, picture ordering, and algorithm phase. Additionally it would help by having more than one example or an actual simplified test case model to view in 3D.

[NicholasSeward]

The left image has the layer to be printed in gray with the previous layer in black.

The sequence of 15 images (ordered from left to right on each row) uses... gray=unprinted blue=current band of bridge material (I didn't draw the lines but each one can be filled in with a series of parallel lines.) black=edges you can tie a bridge to

I generated an image in the sequence for every time step 5 is hit.

[BagelOrb]

The pictures are left to right and then to to bottom. Each blue area is the next area bridged.

I think your description of your algorithm is a bit too simplified, though. "Shortest unsupported edge"? You start in the pictures with an unsupported edge which is supported at both ends.

It's quite a big algorithm and might be computationally expensive, while bridging like this would result in ugly overhangs because the sagginess of one line carries over to the lines you attach to it. I have to think about this for a bit. I'm not yet sure whether this is a good idea to implement.

[NicholasSeward]

@BagelOrb Yeah, I messed up at the beginning. However, the algo should probably remove unprintable regions to start with which would result in the image sequence I have shown. (For instance, star holes would be turned into pentagons. The edges of the pentagon could be used for step 1. It should be a simple matter to do some convex hulling.)

I would argue that this would be a horrible default option. This really requires that someone really know there machine and get the speed, extrusion rate, and ration very well tuned. However, for less extreme examples it could make sense by default. Either way, it will be fun to see if I can prototype this. Actual prints will speak louder.

[BagelOrb]

If you could make a proof of concept implementation, I would be very interested to see how well it works.

[NicholasSeward]

Here is my first go at a proof of concept. This proof of concept contains some 3rd order bridges. (Bridging between bridges that also bridge between bridges.) Now that I have my tool chain figured, I would love some challenges that could push the algorithm.

[BagelOrb]

Looks pretty darn good!

Did you do this via CuraEngine or did you make a gcode yourself?

It's mostly the implementation in CuraEngine which I'm afraid of...

[NicholasSeward]

@BagelOrb I did this outside of CuraEngine.

As far as efficiency is concerned, even with a simple naive non-R-tree approach I think it should be quick enough. Would you mind listing the implementation hurdles you are afraid of?

Here is an extreme torture test. 12th order bridging! It has the expected droop and a few stitching misses.

[darconeous]

Impressive!

[BagelOrb]

I don't know what you mean by a non-R-tree approach, but it sounds like you know a bit about programming ;)

What I'm afraid of is that figuring out which parts of a polygon are supported would take quadratic time. Of course you could get that down, but anything more than linear is already quite costly for high poly polygons. Then taking the difference between the bridgeable area and the newly bridged area is another polygon operation which is quite costly.

I must admit that the bridging code is the only code in the engine which i haven't really looked at.

For me there are bigger problems which are easier to fix, but you are free to make a pull request. I'd gladly see people contributing to Cura!

[NicholasSeward]

@BagelOrb Of course I don't expect you to implement this for me. I just want to make sure that effort spent in this direction will not be for naught.

Here is what I know. Bridging currently takes the difference of the current layer with the previous layer. It would be an easy modification to classify where the lines in this difference polygon came from. (previous=supported, current=unsupported) That is done with Clipper and is O(n * log(n)) I believe. From here you need to make infinite lines out of all the unsupported lines and clip them using the difference polygon. [I think another O(n * log(n)) operation] You pick the smallest one...do some offsetting...do some clipping...get new difference polygon...yada...yada.

Bottomline: I think it can be done in O(k * n * log(n)) time where n is the number of lines in the difference polygon and k is the highest order bridging that is required. The current solution being O(n * log(n)). There are also a ton of speedups available: convexhull to kill unprintable sections, simplify polygon because a bridging operation can only be so good in the first place, etc.

Question: At the end of the day for normal situations, I think it will take 3 times as long. (citation needed) For exotic bridging, it could take 3n times as long where n is the highest order bridge. I am having a hard time thinking of a part that would cause this increase in time to be noticeable. (Usually, there are only a few layers with a bridge.) If I can hit this theoretical performance, is this something that could live in the CuraEngine?

[nallath]

As far as I'm concerned; Yes.

[BagelOrb]

You don't even need to hit the theoretical performance for it to be included in CuraEngine. As long as it's an option to switch between fast bridging and good bridging I am willing to merge a PR. There is of course a balance where a bit slower algorithm, but way better bridging wouldn't lead to a new option, but would lead to the old bridging algorithm being replaced by the new one. We'll see...

I do think an option to decide the maximum depth of bridging would be nice.

I think you could speed some things up to expected O(n) by using a SparseGrid (see src/utils). Please take that into consideration.

I also think it would be nice if it's possible to only generate support for unbridgeable areas, but that's a whole different story.