Offset bug?

[timoria21]

Hello,

I'm sure I hit an offset bug already resolved in this library.

Can you please confirm that these missing nested offsets were fixed in this or in the Rust version of this library?

Removing some nesting levels, everything works fine.

Just in case, do you remember the changeset?

Thank you.

[jbuckmccready]

Looks like the bug is between the rectangle and inner most circle that surrounds it - if you just run those two does that form a minimum reproducing example? Can you share the polyline inputs?

I have not implemented the multiple/simultaneous polyline offsetting yet in the Rust version but I was actually just gearing up to get to that real soon. I think it is fixed in the Rust version because it looks like it has to do with intersect detection/resolution which has had a lot of small fixes done.

[timoria21]

Here you go:

Polyline p1 = new Polyline();
Polyline p2 = new Polyline();
Polyline p3 = new Polyline();
Polyline p4 = new Polyline();
Polyline p5 = new Polyline();

p1.addVertex(10, -80, 0);
p1.addVertex(90, -80, 0);
p1.addVertex(90, 0, 0);
p1.addVertex(10, 0, 0);
p1.iSClosed = true;

p2.addVertex(80, -40, -1);
p2.addVertex(20, -40, -1);
p2.iSClosed = true;

p3.addVertex(77, -40, 1);
p3.addVertex(23, -40, 1);
p3.iSClosed = true;

p4.addVertex(50, -61.2132, 0);
p4.addVertex(71.2132, -40, 0);
p4.addVertex(50, -18.7868, 0);
p4.addVertex(28.7868, -40, 0);
p4.iSClosed = true;

p5.addVertex(50, -64.3952, 0);
p5.addVertex(25.6048, -40, 0);
p5.addVertex(50, -15.6048, 0);
p5.addVertex(74.3952, -40, 0);
p5.iSClosed = true;

double offsetDelta = -0.6;

OffsetLoopSet loopSet = new cavc.OffsetLoopSet();

loopSet.cwLoops.Add(new OffsetLoop(0, p2, Polyline.createApproxSpatialIndex(p2)));
loopSet.cwLoops.Add(new OffsetLoop(0, p5, Polyline.createApproxSpatialIndex(p2)));

loopSet.ccwLoops.Add(new OffsetLoop(0, p1, Polyline.createApproxSpatialIndex(p1)));
loopSet.ccwLoops.Add(new OffsetLoop(0, p3, Polyline.createApproxSpatialIndex(p3)));
loopSet.ccwLoops.Add(new OffsetLoop(0, p4, Polyline.createApproxSpatialIndex(p4)));

ParallelOffsetIslands alg = new cavc.ParallelOffsetIslands();
StringBuilder sB = new StringBuilder();

sB.AppendLine(p1.ToString());
sB.AppendLine(p2.ToString());
sB.AppendLine(p3.ToString());
sB.AppendLine(p4.ToString());
sB.AppendLine(p5.ToString());

string input = sB.ToString();
sB.Clear();

for (int iter=0; iter<100; iter++)
{
    sB.AppendLine($"# Iter: {iter}");

    OffsetLoopSet offsetResult = alg.compute(loopSet, offsetDelta * iter);

    if (offsetResult.ccwLoops.Count == 0 && offsetResult.cwLoops.Count == 0)
        break;

    foreach (OffsetLoop offsetResultCcwLoop in offsetResult.ccwLoops)
    {
        sB.AppendLine(offsetResultCcwLoop.polyline.ToString());
    }

    foreach (OffsetLoop offsetResultCwLoop in offsetResult.cwLoops)
    {
        sB.AppendLine(offsetResultCwLoop.polyline.ToString());
    }
}

string output = sB.ToString();

[timoria21]

Hello, did you have a chance to run the code I provided? Thanks.

[jbuckmccready]

I did start implementing the island offsetting algorithm in Rust to test it, I am not sure when I'll be done as I have been busy with work.

[timoria21]

I thought that the C++ version was able to do this offset, isn't it? Do you mean that C++ version could but has bugs in this respect?

[jbuckmccready]

Yes the C++ can do it, I thought you already tried it and determined it's bugged in C++. Not sure about the Rust code, that's what I was going to test to determine if the bug is due to issues I've fixed in the Rust that are still in the C++.

[timoria21]

Ah ok, with my C++ version the result is the one in the picture. I'm curious to see what you'll get with the Rust version. All the open-source boolean libraries (Clipper & co.) treat these cases in the same way. I was surprised to see CC fail on it.

[timoria21]

Is there any place in the code where I can debug this? Did you remember the specific function that determines these blind regions? Thanks.

[jbuckmccready]

I would debug around where slice points are found, slices are formed, and slices are stitched together:

• Top level compute function for algorithm: https://github.com/jbuckmccready/CavalierContours/blob/master/include/cavc/polylineoffsetislands.hpp#L360
• Where slice points are created: https://github.com/jbuckmccready/CavalierContours/blob/master/include/cavc/polylineoffsetislands.hpp#L371
• Where slices are formed: https://github.com/jbuckmccready/CavalierContours/blob/master/include/cavc/polylineoffsetislands.hpp#L393
• Where slices are stitched together: https://github.com/jbuckmccready/CavalierContours/blob/master/include/cavc/polylineoffsetislands.hpp#L400

You can step into each of those function calls and see what it's doing. There should be a slice point at each intersect between the polyline loops, slices are formed from the intersects, then slices which are determined invalid by offset distance are discarded, then the remaining slices (ones not discarded) are stitched together into closed loops, and finally those closed loops are determined to be clockwise or counter clockwise by their area.

The example shapes you posted are pretty simple so hopefully it's easy to see what's missing/not handled right at a given step in the algorithm.

[timoria21]

Ok, I will start to analyze/debug the code. As I mentioned, I was surprised to see a problem in this area of the library. What I cannot understand is if I am after a small bug or a more large CC missing logic module.

Thank you.

[timoria21]

I was wrong again. Trying to support the following case, I broke the original library. Can you confirm that offset for intersecting curves is not supported as in the Clipper library?

Clipper Offset

[jbuckmccready]

Yeah, I don't think the island offsetting algorithm as currently implemented will work in general for intersecting loops, was not needed for my use case, and I did not attempt to make it work so. Because of that there may be an easy change to make it work, or not... devils in the details.