Use sweep-and-prune algorithm for overlap detection

waruyama commented 4 years ago

Currently if overlaps between several curves or paths have to be found, we compare the bounds of each element to the bounds of all other elements. This works, but since it it a classic O(n2) algorithm, it becomes slow if many elements are involved.

A much better algorithm is Sweep and Prune, which sorts the elements along one axis and then sweeps along the axis finding potential overlaps. This is a O(n) algorithm, which means it has much better performance for many elements. Here is a great explanation on how it works:

https://gamedev.stackexchange.com/questions/57470/are-collision-detection-always-on2

Instance where Sweep and Prune could be used are:

I had implemented this in an older version of Paper.js, but porting it to a current version should not be a problem.

For complex cases the performance improvement should be dramatic.

lehni commented 4 years ago

This sounds really good. I can't wait for this to land! BTW, you mean Curve.getIntersections(), right?

waruyama commented 4 years ago

Thanks, corrected. This will only consist of two static functions:

getItemBoundsOverlaps(items1, items2, tolerance)

and

getBoundsOverlaps(bounds1, bounds2, tolerance)

The first is only a utilty function that takes the bounds of all items can calls the second function. The return value will be an array. Each entry contains the indexes of overlapping items2/bounds2 entries for the entry at this index in items1/bounds1.

Any suggestions where to put these two functions?

lehni commented 4 years ago

Do they both use the same algorithm internally? Could the algorithm itself be in Numerical? And then maybe two static methods that make use of it: Rectangle.getBoundsOverlaps() and Items.getBoundsOverlaps()?

lehni commented 4 years ago

If only Rectangle.getBoundsOverlaps() uses the algorithm then it can be inlined there.

waruyama commented 4 years ago

They both use the same algorithm. Basically getItemBoundsOverlaps() calls getBoundsOverlaps(), where the real work takes place. I like your suggestion of Rectangle.getBoundsOverlaps() and Item.getBoundsOverlaps() a lot and will start with this.

waruyama commented 4 years ago

Quick update: I have implemented the algorithms, but there is still a problem with using it in Curve.getIntersections(), because it seems that when I wrote the initial code that function behaved in a slightly different way (no separate collection of locations per path). This causes 13 tests to fail, but I am confident that I will make it work within the next few days.

waruyama commented 4 years ago

Created pull request #1739 for this.

(Oh dear, just noticed it contains my changes package.json etc., even to .gitignore)

lehni commented 4 years ago

You don't need to close the PR. You can add a fixing commit, even squash these commits to one, and then force-push the updated branch to the one that you created the PR against, and it will update.

waruyama commented 4 years ago

Some profiling shows that PathItem.Boolean.reorientPaths() in my test case has become about 20x faster. Curve.getIntersections() is about twice as fast, probably because a lot of time is spent on fat line clipping, which is not affected by the change. PathItem.compare() is not in my chart, is does not seem to be used much.

The elephant in the room now is getWinding(), which takes about 90% of the time in my test case. It would be great to find a better algorithm for this, too.

Here is my test case:

<html>
  <head>
    <title>Performance test for sweep and prune</title>
    <script src="paper.js"></script>
    <script type="text/paperscript" canvas="myCanvas">
      var path1 = new CompoundPath();
      for (var i = 0; i < 40; i++) {
          for (var j = 0; j < 40; j++) {
              path1.addChild(new Path.Circle({center: [i * 25, j * 25], radius: 10}))
          }
      }
      var path2 = path1.clone().rotate(15).translate(5, 5);

      var starttime = Date.now();    
      var result = path1.intersect(path2);
      console.log(Date.now() - starttime);

      result.fillColor = "red"
    </script>
  </head>
  <body>
    <canvas id="myCanvas" width=1024 height=1024></canvas>    
  </body>
</html>

waruyama commented 4 years ago

propagateWinding()/getWinding() are great candidates for using the sweep-and-prune algorithm. Before propagation we could determine the vertical and horizontal overlaps between all curves using sweep-and-prune. Then, if getWinding() for a point on a curve is called, we only have to check the curves that overlap with the point's curve horizontally or vertically (depending on the angle of the curve in the point). This would save us a lot of comparisons and I am sure that cases like the one in the example above would benefit tremendously.

The problem is that implementing this needs a lot of refactoring, but it should be possible to implement.

lehni commented 4 years ago

I will soon look into merging this. Busy traveling this week. Adding it to propagateWinding()/getWinding() could be a decent next step! 👍

waruyama commented 4 years ago

Maybe we should wait a little with integrating this into the development branch. I just finished a rough implementation of sweep-and-prune for propagateWinding() and the new version is now 10x faster than the current development build on the example above. Actually the sweep-and-prune function is now the part where most of the time is spent.

There are still 9 tests failing, but this should not be a problem to fix. I am not quite happy with the implementation, which feels a bit too hacky to be integrated into the paper.js codebase. Give me some time and we will have a nice performance update for the new year.

lehni commented 4 years ago

Wowzie, that sounds amazing! I am happy to wait for that goodness :)

waruyama commented 4 years ago

Little update: All tests pass now, performance is 5 to 10 times better on my test cases. I also made some refactoring, but there is more to do. But you can expect to see a clean version before Christmas.

waruyama commented 4 years ago

I have pushed a newer version of this on my own sweep-and-prune branch at https://github.com/waruyama/paper.js/tree/sweep-and-prune

Now the sweep-and-prune algorithm is also used in propagateWinding(), at least a partial sweep-and-prune algorithm.

It passes all tests. I need to add a few more comments and do some code formatting, but that should be all that is left to do. The pull request will be updated when this is finished.

One important change was to replace "overlaps" with "collisions", because we are already using "overlaps" for paths in a totally different context.

lehni commented 4 years ago

wowzie! I'll check it out soon! I just saw that your commits include the build libraries in dist. This should not be included…

waruyama commented 4 years ago

Yeah, I noticed this. And I even added them by hand with git, no idea why I did this. Will sort this out.

waruyama commented 4 years ago

Here is the performance difference between the current brute force algorithm and sweep-and-prune on my machine for the test case above depending on the number of paths:

I would say this is a very nice example to change a O(n^2) to nearly O(n) algorithm.

lehni commented 4 years ago

Wow, that's impressive indeed! Let's merge ASAP :)

waruyama commented 4 years ago

Amazingly most of the time in the algorithm seems to be used for sorting the collision indices at the end, exactly here:

    for (var i = 0; i < allCollisions.length; i++) {
        var collisions = allCollisions[i];
        if (collisions) {
            collisions.sort(function(i1, i2) { return i1 - i2; });
        }
    }

So if we want to make it even faster, we should either check if we can live without sorting or make sorting somehow faster.

lehni commented 4 years ago

Haha, wow. I guess that just means it's fast enough ;) BTW, can't we just call sort() without the callback if it's just integer sorting?

lehni commented 4 years ago

@waruyama what do you think of 3cc7fa35917f173334be3666d3d22d9d6c7b9921 ?

waruyama commented 4 years ago

Does using only one curveCollisionsMap work? The idea was this: (1) We find for each curve all curves that overlap the curve in horizontal and in vertical direction. (2) When casting a ray through a point on the curve to determine its winding we do this either in horizontal or vertical direction, depending on the dir variable. Therefore we only have to check the curves from (1) to find the winding, which makes it much faster, which saves a lot of work because we do not have to check all curves for each point.

waruyama commented 4 years ago

Simply calling sort() does not seem to work. As I understand it this does string sorting, which means that if you have [355, 200, 1, 4] the result will be [1, 200, 355, 4]. Sorting in Javascript is really awful.

lehni commented 4 years ago

Yes the code above works, it passes all tests. It still handles hor / ver separately, it just stores the data differently, resulting in some simplifications:

https://github.com/paperjs/paper.js/commit/3cc7fa35917f173334be3666d3d22d9d6c7b9921#diff-83b0f841b43dce90324008de0d976e25R180

https://github.com/paperjs/paper.js/commit/3cc7fa35917f173334be3666d3d22d9d6c7b9921#diff-a905b52ce1034e624e255c2f684e6af7R102

https://github.com/paperjs/paper.js/commit/3cc7fa35917f173334be3666d3d22d9d6c7b9921#diff-83b0f841b43dce90324008de0d976e25R538

waruyama commented 4 years ago

Alright, I will have to take a closer look, I am sure there still is room for improvement on my code.

How comfortable are yyou with Typed Arrays in Paper.js? Because if I change the arrays holding the collision indices to Int32Array objects before sorting, this gives another considerable performance improvement. Something like this:

        for (var i = 0; i < allCollisions.length; i++) {
            if (allCollisions[i]) {
                allCollisions[i] = new Int32Array(allCollisions[i]).sort();
            }
        }

sort() for Typed Arrays does not seem to be supported by all browsers: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/TypedArray/sort

lehni commented 4 years ago

Alright, I will have to take a closer look, I am sure there still is room for improvement on my code.

The main reason why I changed it was that I saw potential to reduce the amount of code, and also reduce memory consumption by only creating the bounds arrays once, and use the same list for both passes (hor and ver).

waruyama commented 4 years ago

I think your changes make a lot of sense. Here are some small remarks:

In Curve.js Line 2126 you should be aware that there is a difference between calling findCurveBoundsCollisions() with twice the same bounds array and the bounds array and null. In the first case the results for each bounds will contain the bounds' index itself, in the second case it will not contain that index.
Very nitpicking, but maybe bothAxes is better than bothAxis in `findCurveBoundsCollisions``

lehni commented 4 years ago

In Curve.js Line 2126 you should be aware that there is a difference between calling findCurveBoundsCollisions() with twice the same bounds array and the bounds array and null. In the first case the results for each bounds will contain the bounds' index itself, in the second case it will not contain that index.

@waruyama are you sure? There's this code here in findCurveBoundsCollisions():

        var bounds1 = getBounds(curves1),
            bounds2 = !curves2 || curves2 === curves1
                ? bounds1
                : getBounds(curves2);

Very nitpicking, but maybe bothAxes is better than bothAxis in `findCurveBoundsCollisions``

Yes, you're right :)

lehni commented 4 years ago

Oh, and I'm not sure about using Int32Array yet… For one, I think it would break our deprecated test:phantom unit test-runner :(

waruyama commented 4 years ago

Later in the code there is this:

    if (boundsA === boundsB) {
        // if both arrays are the same, add self collision
       currentCollisions.push(currentIndex);
   }

So there is a differnce. Maybe a bit difficult to see I admit.

Regarding the Int32Array, this is about 20% faster, so it is not really a game changer. We have documented it here and it someone needs another few percent of performance increase, they can implement it in their own fork.

lehni commented 4 years ago

Oh damn… I just published v0.12.4 with this in. And publishing is a lot of pain right now, because the automatic scripts don't fully work anymore due to some gulp changes :/

But how is it passing all unit tests then?

lehni commented 4 years ago

Hmm but if you look at my code, wether I pass curves2 === curves1, or curves2 === null, bounds2 will end up being === bounds1, so I really think we're good, see here:

bounds2 = (!curves2 || curves2 === curves1) ? bounds1 : getBounds(curves2)

waruyama commented 4 years ago

Sorry, I did not mean to say that your code is wrong. Just wanted to point out a difference in the two ways of calling that function, since you changed it. I may take another close look later, but for now I think we are good, too.

lehni commented 4 years ago

Now I remember. I changed it from this:

var boundsCollisions = CollisionDetection.findCurveBoundsCollisions(
                values1, self ? null : values2, epsilon);

to that:

var boundsCollisions = CollisionDetection.findCurveBoundsCollisions(
                values1, values2, epsilon);

because when self is true, values2 equals values1 already, and findCurveBoundsCollisions() will set bounds2 to bounds1 if null is passed for values2 or if values1 equals values2, so the result is the same, and I decided the extra check wasn't actually doing anything.

lehni commented 4 years ago

Thanks again for your great work @waruyama! Do you feel like working on some other features too? Perhaps we could take a stab together at finishing the offsetting code for release?

And there's a question for you here, btw:

https://github.com/paperjs/paper.js/blob/9206135a1f9fed1241ee8c9964c8b13bb0e57743/src/path/Curve.js#L1848-L1850

And shall we close this issue, now that the algorithm is implemented?

waruyama commented 4 years ago

Yep, issue can be closed. Implementation works, is quite clean and according to Paper.js coding standards, and achieved performance improvement goal. What else can you expect?

paperjs / paper.js

Use sweep-and-prune algorithm for overlap detection #1737