Shape union produces wrong results if points of overlapping shapes touch on horizontal lines.

[lehni]

I'm sorry @hkrish to report more bugs with the boolean code! Check this example, derived from #449:

var path1 = new Path.Rectangle({
    point: [60, 50],
    size: [50, 50],
    fillColor: 'red',
    selected: true
});

var path2 = new Path.Rectangle({
    point: [100, 50],
    size: [50, 50],
    fillColor: 'blue',
    selected: true
});

// project.activeLayer.rotate(15);

var path3 = path1.unite(path2);
path3.fillColor = 'yellow';
path3.selected = true;
path3.position += [0, 100];

Resulting in:

Now if you uncomment that rotate(15)command, you get:

Note that there are still extra points that we could get rid off, but that I guess is fine?

http://sketch.paperjs.org/#S/lZAxT8MwEIX/yslLiojcBBSGoE5dGRCMTQeTXKnBvYvcS6tS9b9zCUqkToAn+31Pfu/ubMjt0JTm9ROl3prU1Nz074OL0DrZ5rAAwiM8692+YC2O3gPOzhWBnpY9SQmrhyyFIlunP+ref6GKxZW48SEsOXAsIYnYJKMXg36KTQkSO6zocvNYUUVj/N2f4vPsf/lvocNfCszn0Eb+UGRdLf6AT+6E0UYWJzjLi+ua91pz2JbtyCsfqveWAdopW23JCUPgYzLBsYCyvsGkt7z34pngdgErHUWHXCs0l28=

[hkrish]

At the moment, we have no way to handle overlapping paths I am afraid. That is the reason for the paths merely touching each other as well. This is the main limitation of Boolean ops in paperjs right now.

I briefly looked at some research the skia guys did, they seem to be handling it separately from normal intersections. I have to look into this problem in detail.

Again. Sorry for the delay. I am quite busy at job right now, and will be, probably until Easter.

@lehni I will keep you posted.

/hari

On 07-Apr-2014, at 12:22 pm, Jürg Lehni [email protected] wrote:

I'm sorry @hkrish to report more bugs with the boolean code! Check this example, derived from #449:

var path1 = new Path.Rectangle({
point: [60, 50],
size: [50, 50],
fillColor: 'red'
});

var path2 = new Path.Rectangle({
point: [100, 50],
size: [50, 50],
fillColor: 'blue'
});

// project.activeLayer.rotate(15);

var path3 = path1.unite(path2);
path3.fillColor = 'yellow';
path3.selected = true;
path3.position += [0, 100];
Resulting in:

Now if you uncomment that one line, you get:

Note that there are still extra points that we could get rid off, but that I guess is fine?

http://sketch.paperjs.org/#S/lZCxbsIwEIZf5eQlVI1M0iodgphYGap2JAxuci0Gcxc5FxBFvHuPVE3F1nqy/+/k77fPhtweTWledyj1xqSm5uZ6PrgIrZNNDnMgPMKz7u0L1uLoI+DkXBHoatmTlLB6ylIosnX6nXb+EzUsbsJ3H8KCA8cSkohNUtHlblZRRT+mhz+Z8ux/qrfQ469rOoU28lYvt64Wf8ClO2G0kcUJTvLittGjNhr+wPbklQ8tryMDtKNGx5IThsDHZIQdBrVgo0xij2PecufFM8H9HFbaWt+zVmguXw==

—
Reply to this email directly or view it on GitHub.

[lehni]

You mean situations, where the curves cover each other and don't result in one intersection, but theoretically in an infinite amount of solutions, right? Because if we can't handle any overlapping paths, then what would the point of boolean ops be? :)

I'm guessing that with the infinite solutions, we would need a way to pick one as a valid intersection location. Wouldn't we have to choose between the start and end points of both curves, simply?

[hkrish]

Yes, I meant when two bezier curves overlap at least a portion of their span.
The intersection calculation is actually not that difficult. Since two cubic bezier curves can only intersect a maximum of 9 times, we can stop bezier-clipping, at the 10th intersection and declare the curves are overlapping. Now we need to isolate the overlapping regions (start and end points of the overlapping regions) and cut them out of the main curve.

The part after that looks a bit hard though. i.e. when we traverse the graph later. The reason, is that, we have to conditionally process the overlapping regions according to the operator and the location of the next and previous curves. For a quick example, consider the Union operator, two paths below are overlapping by some amount,

In this case, when we trace the path, after calculating intersections, we are to discard the overlapping part of, one of the curves and we get the union.

Now here are two other paths, overlapping about the same region,

In this case, we have to mark overlapping regions on both operands as invalid and trace paths while avoiding them, so that we get this:

This is only for one operator. And for others several of these edge cases exist. This is why for now I just opted for the easy solution. To be exact, overlapping (osculating is the technical term) curves are a degenerate case for boolean ops.

However, I agree with you guys that we absolutely need this. I am just trying to explain that, this is not a bug, but a limitation at the moment. I will look into this once we have the offset paths sorted out.
And @lehni thanks for creating the other issue regarding osculating paths, I will probably start updating my progress there instead.

/Hari

[lehni]

@hkrish isn't it strange though that the rotated paths produce the correct result? Isn't this perhaps simply an issue of horizontal paths not handled correctly?

[hkrish]

I did look at it in detail. The issue is with overlapping paths. The transformation may nudge the points just enough that the paths may not be precisely on top of one another anymore.

Try changing the rotate(15) to rotate(90). Now the intersecting parts are not horizontal, but the issue will reappear, since the lines are aligned again. 180 and 270 degrees does not seem to show the issue, but again we can't debug like this, the IEEE floating points have a major say in this. If you step through the code in the debugger, the boolean code makes no attempts to resolve when it reaches an overlapping section, and because of that it occationaly takes the wrong path.

It might seem arbitrary, but a subtle difference in the slope of these curves determine which path is being taken, when we sort and choose a path to traverse at an intersection.

What we need is a conscious design choice of how the algorithm should behave. Also might need some code to identify the parts that are overlapping. This may not be the only issue when we deal with overlapping paths. So may be it is a good idea to keep this issue open for now?

[lehni]

Yes that makes a lot of sense. Do you think this is something we can address in the current implementation, as opposed to the new approach that you once mentioned?

[lehni]

Who would have thought! I managed to address these issues in the current code base, and the work in the boolean-fix branch has landed on develop! Time to test thoroughly, but I'm closing these bugs. Feel free to reopen if similar problems arise.