JUL
20
2010

GSoC: Transformation Tool for Krita

It's been two weeks since my last blog entry, so I thought it was time I gave an update about my work.

The next step was to add perspective transformation to the tool, and the least I can say is it wasn't easy.
First thing is it took me some time to find the formulas and good values to create a good perspective effect, and then to obtain the same one with Qt.
There are different reasons why I had to know the formulas and couldn't just rely on Qt, one of them is that the perspective transformation is not invertible, unless you know the equation of the plane in which were all the points before the perspective projection.

For those interested, here is the formula I used for the perspective projection :

where (cx, cy, cz) is the position of the camera and (ex, ey, ez) is the eye position. I took respectively (0, 0, 1024) for the camera and (0, 0, -1024) for the eye.

To invert the perspective transformation, I had to solve the following 3x3 system of equations :

The last equation is the equation of the plane your points were before perspective projection. The parameters (a, b, c) can be found by calculating the cross product of two (non colinear) vectors of the plane.

For those who are interested, here is the solution :

But don't think that the work is done once I have the formulas !
The thing is each time I implement a new transformation, I have to take it into account when the user manipulates the selected pixels. Let's take an example, it will be easier : when the user grabs a handle at the middle of a side of the selection, and moves the cursor, he or she expects the middle of this side to match the mouse position. That means I have to find the scale factor value for which after applying all the transformations (scaling, shearing, rotations and perspective projection), the middle of this side matches the mouse position.
While the task was quite easy before, it has become much harder now that there is perspective (to keep it simple, it is because it breaks the symetry of the selection).

I managed to make translation, rotations, shearing and rotation center movement work correctly with perspective, but not scaling.
When scaling from a side of the selection, there is only one scale factor to adjust (horizontal or vertical), so I could make it work using a dichotomic search, but when there is two scale factors to adjust (when scaling from a corner), I cannot use dichotomy anymore.
I imagined different methods to tend to or approximate the two desired scale factors, but none was successful.

I even tried to find the exact solution with Maple, but as I expected, it couldn't solve a 4-4 nonlinear system of equations (the unknowns are the two scale factors, and the translation along X and Y axis, because the opposite corner of the one grabbed must stay at its position at click)..
I think I could come up with new ideas and I would eventually find a solution, but time flies, so I decided it wasn't that bad if the corners didn't follow the mouse position, and I would go back to it later if I had some time.

After that, I still had to make the tool able to apply perspective transformations to the paint device. I just added a new constructor to the already existing perspective transform worker.
I also added a checkbox to hide the tool decoration, a progress bar, and corrected some bugs.

I have already begun investigating warp transformation methods, but I am not yet ready to begin implementation. This is certainly the most exciting part of my project, but also the scariest ! ;)
I'll try to give updates more often.