GSOC 2012: Pencils down

Hi all!

Today we have the final pencils down for the Google Summer of Code 2012. It was a wonderful experience do this work along with an awesome team such as the Krita developers. So much learning, and yet so much to be learned, that only a summertime it's not enough.

Along the course of this project, I made some changes in many things, like the integrator, the particle implementation, mouse dynamics calculation and other features, which appeared while the job was advancing in its results. However, the initial functions related with the sand painting style were always the final purpose, so they endured.

I described some of the implementations we made so far and what is yet to be done. I put a few links to past blog posts that described some of the features developed in more detail.

What we have

The problems concerning the Pouring operation was made in this post. There are some things to do, but for now, I believe that the current state will do. The Pouring set some properties related to the grains, such as size, mass and friction, which modifies the way the spread operation work

The brush settings widget: we have the brush settings and the grains settings. Most of them have a diference in the Pouring operation mode.

Once we add grains in the canvas, we can Spread them like a regular sand painting technique. Initially we had some numerical errors related with the grains positions and velocities. To fix this problem was really hard but we accomplish good results without compromising performance.

Some errors were due to mouse velocity calculation. In some situations, mostly when we move the mouse very fast, the time interval becames very small, close to zero, resulting in ugly results in the mouse velocity estimative. Fortunately, Krita already had some code with a solution for this, so I just had to understand what was done and adapt in my situation.

I made a video of an experiment :

Note that the particles are not erased while spreading. Taking a closer look we see that the particles are painted in new positions, although some of them act a little out of the expected behaviour.

From the videos and images some of you could think that the brush works only in grayscale, but it does work in other color models :

We made strokes of the Pouring operation with different colors in each one.
After that, we did some Spread (the well defined white spaces) to show it working in the color grains. The main drawback in this Spread operation is the grain color handling. When we update the grains positions we repaint them using the current color (when putting a grain in a new position) and background color (when "erasing" the particle previous position). We can improve that by holding the color used in the Pouring operation inside the Particle class and deleting the previous position using a alpha channel painting.

 What is missing


There are a few more things that were planed to be done, but I didn't have time to do it. Again, to the Spread operation work properly it took a very good effort so it could emulate the sand behaviour while the user painted using it.

As explained in this post, we divided the canvas in a number of grid cells so it could apply the Spread only in those which are under the mouse position.
However, the grains which are under the  brush radius should have been spread as well. So one of the things to be done is the to extend the grid cell selection under the mouse radius, not only to the mouse position. There is also the posibility of customizing the grid size for user convenience: larger cells for faster computers, smaller cells for slower computers.

A missing feature is the mouse "particle" customization. The spreading is made by emulating a particle in the mouse position with the same size as the brush radius. However, the mass and friction for the brush are the same as the current configuration of the grain particles, so it's not a very user friendly setting scheme, since the grains settings is only, obviously, for the grains.

Another problem is when you save a document where you used the sand brush. When you load it, the particle positions are not retrieved, although we can use the created KisAnnotation to do so.

And now?

Well, now we wait for the evaluation. I tried to put a good documentation in the code so anyone can understand what is happening in each part of it. Although some things are missing, most of what was proposed was made
and the main features are working well. I need to do some more tweaks to make the brush more user friendly, but for now, the visual results are satisfying.

I really hope I can continue working in this brush in the next years so it can have a behaviour even more beffiting with the actual behaviour of sand painting. But we will make more plans when we are sure that everything went okay in the evaluation.

Until next time!


Performance improvements :)

Hi all!

For the first time, I accomplished good performance improvement in a code after refactoring and commenting the code. This kind of practice really helps to clarify an implementation.

My code was very "dirty", almost unreadable, so I rewrote all the comments, hoping that it could help anyone to understand what's going on in the scene. While rewriting, some major errors in the link cell algorithm was corrected. For instance, I had the grid cell operation retrieving the upper-right neighborhood of a cell, instead of the lower-right:  this was driving me crazy.

Anyway, most of the particles retrivement algorithm was slow due to unnecessary I/O operations in the annotations. So, to make things faster, one class is working as a particles manager (KisSandPaintOp), where it takes care of the interaction between the image properties and the particle architeture (grids, neighborhoods and the particles themselves).
The KisSandPaintOp reads and writes all the particles from the annotation ans save them as the SandBrush add new particles.

There are some other things that is missing, but is easy to be done:
  • brush widget update: have to add the "mouse particle" settings, mostly the physical properties like mass, friction and dissipation. The grid customization had to be done again, since I removed while fixing the grid retrieve in the neighboorhood.
  • brush default settings: the brush is begins with all its values set to zero, so I need to initialize them in a default value

This was the good news of this week. Along with that, I made a list of the main flaws in the brush behaviour. I have some ideas how to fixing each one,
but, like most of the previous ideas, I'm taking sometime to study the best ones:

  • dynamic pouring fix: the mouse velocity and acceleration are taken as parameters to modify the added particles position. However, when the movement is in one direction only (X or Y) the grains form a line, yielding an undesirable result (see the picture below). I'm applying the mouse velocity and acceleration directly in the particle pixel position, and update them at each call of the paintAt() method of the SandBrush.
Note the lines drawn in the X/Y directions. The mouse movement in this type of situation has to act in a more "random" way.
  • sand depletion operation: the sand depletion (amount of sand for each brush stroke) is decreasing too fast. I need to find a more reasonable asymptotic function to do the depletion, with the brush radius as parameter. As bigger the radius is, more fast the sand should This is not a high priority feature, but it's nice to have a more real feeling of the painting.
  • particle positions update in the spread operation: I implemented the main step of the spread operation (the final  step of the brush function). As the following video shows, the correct grid position is retrieved allong with its particles to do the spread operation.

    However, for a reason I can't identify, the positions are not updated: I'm not deleting the previous positions yet, just trying to paint the new ones, which does not happen. And to make things worse, the selected particles have their color modified to blue, something that I'm not doing.

Anyway, just a few more steps and the spread operation will be done. The main properties of the brush is in this spread operation so  accomplish the desired behaviour depends on this step. Fortunately, most of the necessary functions for this operations are working properly so I'm with good expectations of the results. Let's see how it will go!

Till next time!


Particle persistence with Krita Annotations

Hello there!

Since we can add grains with physical properties, we can start to work on the hard part: particle selection, collision and animation. However, to do that, we need a way to make the objects created in a stroke to be persistent, since after the paintop is done all objects created during the operation are destroyed.

To do that, we had to find a way to hold a collection of particles and then spread it after the pouring. Thus, I'm using Krita's Annotations, a feature that make possible to add aditional information to an image, like a comment, or, in my case, the collection of particles.

With that, we can save the image state after the creation/pouring of the grains and load them in a way that make it possible to start the usual painting operations.

However, since the number of particles grows really fast, the pouring mode of the brush will just add the particles and save them in a collection that will be converted in an annotation. This annotation will be reloaded when the user start the spread mode, where we only modify the particles positions and don't add any new particle on the canvas.

Another feature that we made these days is a private grid partition of the image. This is necessary since the number of particles grows really fast (in a common pouring painting we add from 5000 to 100000 grains), so to speed up particle selection and neighborhood detection, we are using two data structures that holds the particle indices associated with a grid and create a neighborhood relation between them, so we have to retrieve only those inside and near that grid cell.

For instance, given a image, its associated grid is created by taking the canvas width and height and dividing each by the number of rows/columns disired. If the mouse is in the position (gx,gy), we will search the grid index
by taking its position, multiplying by the number of grids and dividing it by the image size:

grid_x_position = number_of_horizontal_grids * gx / image_width

doing the same for the grid vertical position. With that, we initialize a neighborhood relation structure where we will seach for particles to select and do collision, if need to be.

We could search for these particles in the eight neighbors of the cell where the mouse is, but in practice we can reduce it by half, based on commutativity relation between neighbors. Suppose that (gx, gy) are not boundary cells. Them, since a particle i is neighbor of particle j, we only need to search for neighbors in one way only, in our case, the lower-right half of the neighborhood.

Neighborhood search space restriction.

Witha that, when the mouse moves, we can apply the forces on each particle based on the mouse speed and acceleration and after that, we animate them to have the dynamic feel. For now, the grid creation is based on the image size, but I'm doing the grid customization widget so the user can indicate the number of grids that suits his/hers needs better.

Along with that, I have more few things to fix yet, but I'm enumerating them and soon we will have more details of the situation. Until next time!


A more dynamic pouring

Hi again!

I modified the brush so we can apply velocity and acceleration on the particles based on the mouse movements. In the brush settings, we can set how much sand can drop while pouring it on the canvas, with the sand depletion marked. I will make a better way to control this behaviour in the widget since the values are pretty low for the real amount of sand (when you select the value "50" in the "amount" spinbox, you can add 5000 particles per stroke). The solution I'm thinking is to add a multiplier button, like in the Pixel brush, so the user can add more with low values of the "amount".

Another news is that we can't use the QGraphics Framework due to performance issues. The framework make the selection and collision more easy to handle, but it's really slow for what we had in mind, so I will work on my own code for that.

For now, I'm thinking in the way to divide the canvas in a grid. Using this division, I can use a faster data structure to retrieve particles close to the mouse position and do some processing on then. I already made something similar in the Granular Particles Simulation and I think it won't be a problem to adapt it to the brush.



Some news of the sand brush

Hi all!

It's been a long time since my last post. Lots of things happened since then: I got sick, start a chapter in my university project, finished my short experience as teacher, saw family and friends... and kept working on the sand brush (just forgot to blog about it :P).

The project changed a few things for the sake of simplicity. Since the brush have some similar aspects with games, I'll use the Qt4 Graphics Framework in Krita. Since collision detection, shape modification and object (particle) transformations will be features that the brush has to have, instead of reinventing the wheel, I saw that the Graphics Framework already have these functions.

I did some tutorials about the QGraphicsView to better understand how the QGraphicsItem, QGraphicsScene and QGraphicsView interact and how I can modify Krita's nodes and layers to work with it. I modified my previous Particle class to work in a more simple way and now I'm putting some inheritance from QGraphicsItem to proper use the Graphics Framework advantages. For instance, the updated() method of the class will work using the RK4 integration algorithm to redraw the particle new position in a animation step.

Meanwhile, I created a new paintop plugin on Krita repository and did some hacking on it so we can have some visual stuff to look at it:

I have just loaded and put some filled circles on the canvas with a (slow) depletion. When working with the brush, imagine that you have limited sand on your hand, so every stroke has a sand limit. I'm searching a better assymptotic function than the one I'm using now to do a more smooth depletion. One of the next features to do it's a more dynamic way of spreading these circles, based on the mouse movement properties (velocity, position and acceleration).

I'm studying the layers and nodes of Krita archtecture in a way that I can add a more interactive canvas to manage these circle grains. Perhaps managing these grains in this architecture will yield a behaviour closer to the expected.

Till next time!


Granular particles at sight

Hi all! This week was a little rough, since I had some health issues, but nothing that could stop my coding. :)

The simulation had a huge improvement when I changed the integrator. I was using the fifth order Gear's predictor and corrector integrator. Since most of the people in real-time applications says that the fourth order Runge Kutta integrator is the most effective, I implemented and saw what they where talking about: it's really fast! From a few minutes using Gear's algorithm with collision detection, it dropped to a few seconds with collision detection. A lot better. :)

In the first time I was calculating the collisions between particles. To another improvement, I followed the hint given by Bugsbane in a comment of the last post and decided to remove the particles collisions.Indeed, for our purposes, these collisions must happen only in two specific situations: (1) when the mouse does the spreading of sand already in the canvas and (2) when one particle tries to pass the canvas boundaries.


Granular particles update!

Hello again!

I've been fooling around with my granular particles repository these past days before do a real coding into Krita. I'm trying to optimize my simulation through a series of modifications in the code I wrote last week.

My first attempt to run this granular particles simulation was quite a big failure, since it was really slow and full of errors. I correct some small things this past weekend and during this week I implemented a neighborhood restriction to the collision detection between particles.