Random words at the end of GSoC
This week is the last week of my GSoC period. Other participants may have ended earlier, but I got an extension of the deadline to one month later. Here’s some random words for my summer.
My whole GSoC period was very hurried and busy. Most of my contributions were not done during the summer, because I got a one-month training for ICPC during my summer holiday. Before the training started, I was thinking that I might be able to do both training and GSoC at the same time, but I was completely wrong. The eight-hour training left me with almost no spare time. Trying to do some contribution in the tiny gaps in my schedule, I was very stressed that month, and in the end, I did not make too much progress also. If there’s not an extension of the deadline, I would be facing a huge pile of unfinished work at the end of August, when training ends. So this is a lesson for me, and also a piece of advice for any GSoC contributors who come after me, that a GSoC project needs some time to finish, and having a well-planned schedule in advance is important.
The thing I’m working on has little documentation for me to follow. Unfortunately, at the end of August, I found The algorithm I used in my previous blog turned out to not meet Krita’s needs. The thing is, having a bunch of pixels that form an ellipse is not sufficient, because Krita draws an ellipse by moving the brush along it, so it’s necessary to know the order of pixels to form a trace. So now is the time to delete all my previous hard work and start refactoring. That’s almost starting from the ground up.
There are already algorithms that can generate an elliptical trajectory, namely the midpoint algorithm. The general idea is to start from one point and trace along the ellipse. For example, if we start from the leftmost point on the ellipse, we should go in a left-upper-ish direction. Obviously, starting from the leftmost point and going up, the slope decreases from infinity to negative infinity. At the first, the slope we follow is larger than 45 degrees, so we can always take a step up, and occasionally, we take a step upper-right to follow the ellipse. When we traced to the point where the slope on it is 45 degrees, the ellipse then now going faster in the right direction, so we should change the stepping rule to “always take a step right, occasionally step upper-right”. When reached the rightmost point, the upper half of the ellipse trace is done, and the lower half is centrosymmetric to the upper half.
But the actual midpoint algorithm doesn’t handle rotation. The only way I found on SO is to apply transforms to an unrotated ellipse, which makes the result inaccurate. It took me some time to get the formulas for rotation and to extend the original midpoint algorithm. The result pixel vector can be considered as a polygon so actual drawing can be easily done with a call to the existing paintPolygon method.
With all the above done, I’m close to finishing this project now. For this specific project, not much of Krita’s codebase is involved, I didn’t have too much trouble trying to figure out the structure of the codebase. But the hard part is trying to invent a new algorithm which is pixel-perfect and handles rotation. My bad time management skills and conflicts with my schedules also made me suffer a lot. In the end, I’m glad to participate in this project and learnt a lot!