A story of binary search and bezier curves
For my GSoC project, I wanted to find the intersecting point of two arbitrary bezier curves. There are some existing algorithms for this purpose, but since it can be interesting, I decided to try to find one algorithm myself. I did some
not successful research on finding it, here’s the story and what I learned.
The bezier curves in Krita are 2 variable cubic equations, so naturally, I thought of finding the intersecting point by solving the equations of the two curves. I wrote down the equation, type them into Wolfram Mathematica and hoped MMA to give me a result. There must be some performance regression between MMA 11 and MMA 13. The MMA 13 I’m using stuck there and never gave any result. I had to ask my friend who’s still on MMA 11 to calculate it.
Yes, though I have more or less thought that the general solution of the equation would be complicated, however, when I saw my friend sending me a 1.1M picture of the result, I knew the actual result was way wilder than I expected. (You may view this picture on a new page to see how big it is.)
Any conscious person won’t try to even take a look at this pile of math. It’s definitely impossible to brute force find out some working formula for the intersecting point.
So I searched techniques for solving the equations, and one method just popped out, it’s named “Gröbner bases”. I took a look at it and it’s related to something named “Ring theory”, and every explanation was an alien language to me. Anyway, I ended up finding a set of instructions (Section 8 in this article) which I can no-brainer follow in MMA.
I just followed the article, except for replacing the equation with the bezier curve’s. I hit enter and MMA started calculating, the memory consumed is growing and MMA didn’t stop for an hour. After an hour, MMA ate 50 gigs out of my 80 gigs memory and windows BSODed.
I don’t want to rerun another hour and I doubt if it can give me a reasonable solution after I got the 1.1M MMA output. And even if it worked, I don’t think I will be allowed to embed a whole CAS into Krita, so I gave up on that.
It’s so hard to get the algebraic solution for the intersecting point! So it’s finally time to look at the existing methods. I can see that there’s a reason for people to invent the binary-search-based method that’s currently being used. And there’s no reason to search for an algebraic solution, binary search can also give a high precision solution in a few iterations, and for Krita, a numerical solution is enough.
So in the end, a brief introduction to the binary search way is here: The intersecting point is always in the intersection of the bounding box of two curves, it’s possible to break a curve into two halves, and detect for intersection again. When the bounding box is small enough, the algorithm can return. For further detail, you can view the 7th chapter of this book.