## Nightmare on constant scallop street

Tuesday, July 17th, 2012 at 11:06 am

About 3 weeks ago I got sent a big part to have a look at which took about 5 hours to process. This wasn’t too disruptive as I was at Europython and could keep popping back to the hotel room to read the output, change the print statements and set it running again.

The problem traced down to this image where a 6-way cell was connecting up wrongly.

The black lines are going up a wall, and the contours are in this vertical wall. We are getting a sharp internal corner of offset from a contour that runs to the left and then to the right around that tip. And the tip is almost coincident with another corner at the bottom of the wall in XY. The rectangle with the 6-way cell is actually a square in XY space of about 0.02mm on each side and has reached its limit of subdivision.

When I originally designed the scallop routine (even back in NC Graphics days) my assumption was that I could always subdivide any complex areas in X and Y all the way down until the contents of the cell became simple, because nothing was actually coliniear. In mathematics this is known as In General Position. The problem is that alignments do happen in the real world.

Anyways, I managed to sort this case out and get it resolved after a lot of reruns.

Then this one came up:

Uh oh.

Zoom out and you can see that the subdivision is causing the problem, and not the 8-way cell.

This is what seems to be happening:

The line along the top happily goes along z=200 between the two corner points of this tiny cell. When the midpoint is inserted it just glances the edge of a wall which bumps it up to above the side of four boundaries on each half-side (two boundaries for each red segment). The red segments are not detected because we don’t subdivide the line when we insert a new point. If we did subdivide the line then it would alter the joining up of boundaries within the adjacent cell to the north, and I have no means of rolling back the algorithm to reconsider those cells — which then may require more subdivisions, potentially kicking off an endless chain reaction and so forth.

Once the new fibre down the middle is inserted (without the boundaries to the red segments included), then it is impossible for the boundaries to the black segments to join up, and nothing can be done to save the situation. The contour will always break through and go for this wander around the outer area of where it belong.

An easier option would be to detect that this case has happened and reject this subdivision as not possible and hope it tries again somewhere else where we can fit in. The sample rates along the top fibre is in tolerance — which does not mean you capture all the wall clipping points (where the clipping may be less than one micron).

Still tricky to do. Should I attempt it?

Coincidentally, a week ago I revisited some of the NCG code in Waterbeach (where they too have problems with the scallop routine) and noticed how I overcame the unreliability of the scallop algorithm there in relation to hitting edge cases and not General Position situations. In that code when the stepover step fails, it tries again with a slightly different stepover (eg 10% larger). This hits an alternative set of configurations and often misses the bad positioning. The difference is imperceptible.

I guess that solution is a bit like the Z-avoid inflexions I have in the constant z-slicing. This is where the slicing routine perturbs the level up or down to avoid horizontal planes in the model — on the basis that if you slice exactly on a flat area it is undecidable as to whether it should be included in the cross section or not. And anyway close to these planes you encounter all the irregularities of not quite horizontal geometry resulting in extremely glancing calculation-unstable triangle and edge intersections.

Hmmm. Maybe I should reimport that trick — even though it feels kind of like cheating. I may be able to convince myself that it is not.

The options are either to get all these horrible obscure cases right (and there may be an endless number of them), or enable retries at slightly different offsets so as to avoid these obscure cases.

Also, by trying different offsets I could step back a smaller offset if a very wide collapse is detected. That’s always been a request for a long time. I once made some experiments with my scallop bisectors feature, and have mulled this over for some time. The one thing that has prevented me from going full-on with it has been the fact that the scallop algorithm is way to complex already, and doesn’t need to be made worse.

### 1 Comment

• 1. Freesteel&hellip replies at 2nd August 2012, 8:50 pm :

[…] getting let down by them. But when a bug showed up on a genuine customer part that mattered, I spent a week working through it, which was long enough for the flood-gates to be opened. The random part […]