Friday, December 15, 2006

California and Cheese

Last week I was in California with Lars. It was a pretty vicious trip. Partially caused by the fact that I abhor flying. I don't have anything against the action of flying itself, but I do have a lot against the airlines. And the fact that Snapple icetea has been taken away from me 3 times on this trip is just atrocious. First they took my Snapple when I was going from New York to San Francisco, then they took 2 more before the San Francisco, Munich flights and finally I was completely stripped when flying from Munich to Oslo. Heartbreaking.

George, Lars and I spent a little bit of time hacking on WebKit. As a result we have our changes merged in the main WebKit repository. Yesterday I've setup a new buildbot and we were able to take down the machine that was heating WildFox's apartment ;) If you're planning to checkout WebKit make sure you look at http://build.webkit.org and see whether in post-commit-linux-qt column the "compiled release" box is green, if it is everything compiles. We're going through some major changes so things break every few hours. If you want to build WebKit just do a svn checkout and follow it with ./WebKitTools/Scripts/build-webkit command, that should be enough to have WebKitQt/QtLauncher compiled and running. There's a lot of things busted at the moment because of the above mentioned changes. We'll fix them once some of the architectural changes that we need will land. Currently I'm serving as the reviewer of all the Qt code which I hope, with time, is going to change as more people gets familiar with it.

Most importantly though, I'd like to thank the person who sent me cheese. Lots of cheese. You absolutely and totally rock. If not the fact that I'm already emotionally involved with Free Software, I'd be all yours. I'm very certain you'd love to see my face when our secretary came to my office and said "your cheese is here". Although it's a perfectly valid sentence, I felt really confused and being certain I never ordered cheese in my life, was seconds away from suing Trolltech over sexual-harassment (I'm not 100% sure why, but I always wanted to do that). Oh, and Norwegian government being definitely anti-me didn't want to deliver the cheese and decided that I have to pay taxes on it. Plus in all their glorious intelligence they decided that something that is marked as "cheese" clearly needs to stay in a warm place while being kept away. Despite Norwegian customs doing their "best" it was one of the coolest gifts ever.

Wednesday, November 22, 2006

Resolution independence for icons

Jakub Steiner wrote an interesting blog about woes of creating resolution independent icons. It's a problem I've been thinking about during the last few days, one that has been solved, at least to some extend, already.

It was solved for fonts. Grid-fitting (aka. "font hinting") is a crucial step on the way to produce legible output at small sizes for any font. Hinting can be manual (e.g TrueType has a stack-based language for it, each glyph in the font contains its own little hint program and as a result of running that program control points for the outlines can be adjusted in any way the creator of the hints desired) or automatic (as used by FreeType). An interesting medium is described in "Example-Based Hinting of TrueType Fonts" paper, in which a method of reusing hints from one font for another are described. All in all it's a very common problem for fonts.

The iSlayer blog that Jakub mentioned makes it very clear we need it fast. His example showing how much worse his logo looks in the vector form than the as bitmap looks almost precisely like the "example of hinting" image that can be found on Wikipedia:
(The upper sample in each case is unhinted)
When talking about fonts we're just dealing with a subset of our exact problem.

In Qt, Gunnar just implemented support for non-scaling stroke, which is great. Now we need to figure out a way of doing automatic hinting for vector shapes and we'll be set.

I've always been all for manual adjustment of icons on a pixel-by-pixel basis, simply because they looked a lot better, but during the last few days I've became convinced that we can, in fact, create resolution independent icons. Or let me rephrase, not "resolution independent icons" but "icons that preserve their good looks across resolutions". We have the former, we need the latter.

I'm taking a week off and that's exactly what I'll work now.

I think manual hinting is too cumbersome and we'd need a new container format for icons to make it really work. A way of specifying a whole icon theme along hints for each icon to make them look good across different resolutions wouldn't necessarily be a bad idea. In fact that would be great, it's the problem of developing the way of storing and producing those hints that would be quite challenging. XML format (with some namespace of course) that can be embedded right in the SVG's would probably work fairly well but I'm afraid wouldn't be enough. Then there's also a question of how would we get artists to create those hints.

No, I think auto-hinting makes a lot more sense here. The research FreeType people did in that area is outstanding.

All in all, I think I can make it work =)

Oh, and if you have a SVG icon that you hand-adjusted to produce a better looking bitmap, I'd appreciate a lot if you could send me both examples via email to <my first name>@kde.org address so that I have some testcases to work with :)

Monday, November 20, 2006

WebKit and new examples

With 4.3 snapshots out I updated the list of my examples with a few new ones:
Animation along a path,

And text on a path that I mentioned in the previous blog.

And two examples showing perspective transformations here and here.

Last week I finally got a new laptop. I bought a Sony Vaio SZ340. Mainly because it came with two gpu's, and for a 13"" laptop that's a very unique feature. In general everything works ok (sleeping, cpu frequency scaling, ethernet, wifi, audio). Battery life for some reason is abysmal at around 1.5 hours even though both cores seem to be scaled correctly. I haven't had the time or motivation to figure out what's causing it though. All in all I'm pretty happy with it so far.

In completely unrelated news I became a WebKit reviewer. To answer all the questions about what does that mean for KDE I have to say that right now it doesn't mean anything. KDE is a community, in which technical decisions emerge in the process of natural selection. If we'll manage to get WebKit Qt/KDE ports working better than KHTML does right now, the transition from our own KHTML repository is going to be fluent and natural. If we won't be able to do that, then we'll still have our own version of KHTML. In my opinion, working on WebKit is, from a purely pragmatic point of view, the right thing to do. Working on new features and maintaining a web engine are very complex tasks that we can make a lot, lot simpler by sharing the burden with WebKit contributors.

Tuesday, November 07, 2006

Text on a path

Yesterday a rather large selection of trolls went to see Borat and while waiting for the movie to start Simon and I started talking about adding support for layouting of text on a path in Qt. I've sat down today, did the necessary math and added some extra members to QPainterPath and QBezier to make it all work. As always I wrote a short demo to illustrate what I'm talking about. I felt a little guilty tough because while I never blog about politics I see more and more people on planetkde feeling obliged to share their opinions on the world of politics. So my hard hitting politically charged statement for today is "i really like cookies". Discuss among yourselves.
With visual aids the results of it all are shown in this short Ogg Theora video file here and the screenshots look like this:


It's actually pretty neat (the code, not the fact that I like cookies). It's not yet integrated at all within the QTextDocument (also the code and not the cookies) framework but hopefully we'll be able to figure something out (both the code and the cookies) before Qt 4.3.

Thursday, November 02, 2006

Expressing myself

Simon and I went for a few days to Berlin. It was a lot of fun. Being able to hang out with Ellen, Scott, Espen and Matthias is always great.
Ellen is vegetarian, so thanks to her I've eaten better in Berlin than I think I did the whole last year (granted that my frame of reference is all messed up when it comes to food, but still).
On Tuesday Scott dragged us to a free jazz concert. Simon even contemplated joining and playing along. I was busy being generally freaked out. In the middle of the thing one of the guys playing, walked away from his keyboard, lied down in the middle, on his back, hiked his legs way up in the air and started wiggling his feet. Everyone was clapping and cheering. I've learned that he was not "messed up" as I, personally thought, but was "expressing himself" which is a good thing. I'm not 100% certain how to distinguish between the two but I'm sure I can use this "expressing myself" thing to my advantage. In fact Simon and I kept expressing ourselves throughout our stay in Berlin by getting lost all the time. It's not that we had no clue where we were going - we were simply trying to show that humans, as individuals, are sometimes getting lost in this great world, but no matter how lost one gets, how smelly the subway is that took one the wrong direction or how funny the word "wurst" is, there always is Ellen waiting with some food or maybe even Snapple's... Or something along those lines. I'm still trying to work out this pretentious art thing, but I think I almost got it.
Simon and I even had a few minutes to look at WebKit. I haven't looked at it since we have done the initial port. We fixed most of the serious issues. The rendered pages should all look fine.

I still have 3 patches in WebKit's bugzilla but hopefully they'll get in soon. It feels a little weird to be writing patches, for code that I wrote, fixing my bugs in a project I've been working on for so long and not being able to commit myself. Waiting for others to review and commit my patches to my code is a little, well, silly. But I understand, they changed some style rules and are trying to keep it consistent, while my motivation to read "style guide" documents is basically zero so it's ok to have people look over the patches to make sure they match the style guide.

Right now it mostly sucks for me because I'm forced to keep a few patchsets and since a few of them are not in the main repository, I have to be reverting them to work on fixing something else and wait for them to be committed to the main repository. I think it will take me two or three days of spare-time work to get it to a point where it's more/less usable and once it's there I can comfortably leave it to George and Niko who did amazing job up till now. Plus there seems to be great interest in it from others. Personally, with my todo, I couldn't be bothered to work like I am right now - maintaining local patchsets and reverting and applying them over again, that workflow is just too painful to keep it up. I have this strange perversion where I like to commit my patches to my code myself =) But as I found out in Germany, that's not weird, that's just me expressing myself.

Friday, October 27, 2006

GLOverlay

I uploaded another wonderful Qt example to http://ktown.kde.org/~zrusin/examples. This example has been written by Trond Kjernaasen (one of the Samurai Graphics Assassins, hobbies include death metal and beating Trolltech's QA department at ping-pong). The example shows a wonderful mixing of OpenGL with Qt native rendering. You can type in any phrase, the application will try to look up the images on flicker and then display them in a very eye-candish kind of a way. The application looks like this (but remember it's all nicely animated so you want to see it on your machine).
Trond uses pbuffers to make it all work together so make sure your card supports them. Direct link to the code is here. (some people reported crashes when running on latest NVIDIA driver so watch out ;) )

Tuesday, October 24, 2006

Disappointing

The responses to my latest blog have been hugely disappointing. I thought about ignoring them but since they might be representative to more than just one individual I decided to address them in a whole new blog entry. In no particular order:

Q: Results show that Cairo is bad and slow, is that true?
A: Of course not. That was never what I wanted to show or ever implied. It's so disappointing to see people being so negative and then putting me in the middle of it all. Let me explain using a simple analogy: when two great soccer teams are playing, lets say Brazil and Italy and Brazil wins 3:0, it doesn't mean that Italy is horrible. It means that Brazil was really good at that particular day, a lot better than Italy. Surely before the next game Italy will be better prepared. Graphics is difficult. Trust me I do it every day. One graphics framework being better at something doesn't imply anything negative about the other. All it says is that the framework that was better at something, is really good at that something. Qt is really good at rendering polygons. _Really_ good.

Q: Those tests don't mean anything for most use cases which is rendering images and rectangles!
A: Right... Of course frameworks that focus on those are not vector graphics frameworks. Writing a vector graphics framework that is not good at rendering polygons is a little silly. One might as well stick to pure raster graphics with images/rectangles and it's going to be a lot easier. I'd love to see KDE move towards dynamic, resolution independent interfaces. For the things we're planning, polygon rendering is representative of exactly what we're doing.

Q: Cairo will catchup and it will be better! It's actively developed.
A: That's great. Of course, it's not like the whole graphics team at Trolltech is being fired because Qt is so good there's nothing to be done anymore. We work on graphics every single day so you have to expect Qt to be getting rapidly better.

Q: You will not repeat the benchmarks when Cairo or something else is faster!
A: Right, because that would imply that I have to update and compile every other framework our there every single day and repeat the tests every single day. There's no way I could physically do that (or even be willing to waste my time like that every day). It's up to the framework developers. If you work on a framework, test it after you make some changes and let me know when something changes. If anything will come even close to Qt I'd love to see it. I'd love to stop having to compare Qt to Qt when I do tests. It'd be great if someone would make my life a little bit more challenging.

Q: Tests have to be unfair!
A: What are you basing this on? You either trust me as an Open Source developer or you don't. And if you don't then don't waste mine and yours time by reading my blog. The code for Cairo benchmark is at http://ktown.kde.org/~zrusin/examples/cairorender.tar.bz2 if you think it's unfair, feel free to send me fixes (and don't be silly by trying to render polygons to a cached surface and then repeatedly composing the surface, like I said the tests measure polygon rendering, not image blitting).

Q: Ha! Qt is not Open Source, Cairo is the standard!
A: Not even mentioning that both of those are wrong, how does that relate at all? I am first and foremost an Open Source developer. Yes, I do prefer to write desktop code in C++ than C which was the basis for me joining KDE in the first place, but that's all. If I'll decide to quit Trolltech at some point and will get an offer from company supporting GNOME, I'll start contributing to GNOME the next day. It's all Free Software, that's what's really important to me. Qt is Free Software, that's why I work on it. I'm an Open Source developer, I just happen to work on KDE. I moved half way across the globe, to a country where I knew I'm going to be hungry all the time, just to be able to work on Free Software full time so please skip my blog if you want to bring something as ignorant as that here.

Q: Give me the code?
A: Why? I gave you the dataset and I told you what to test. If you question my results, go write an application rendering polygons and see for yourself. It's an absolutely trivial operation. If you can't do that then what's the point of you fetching my code? The bottom line is that if you don't believe me already, you won't either way and the whole discussion is moot. The people who cared knew where the code was and if you'll look at the date you'll notice the code was there from before I posted the blog (the link to the code is two paragraphs above).

Q: The test is not representative of anything!
A: Of course it is. What would be the point of me writing a test not representative to anything? Like I said in the second paragraph the test is completely representative to the things we want to do in Plasma. If your application renders SVG's, Flash, fonts as paths, complex shapes or actual vector shapes, the test is fully representative of the results you'll see. But again, it doesn't imply anything negative - so it's not that Cairo will be very slow in those cases, it's that Qt will simply rock them.

Q: But what if something else would be faster than Qt? Would you post results then?
A: Well, I don't exhibit self-destructive behaviour so no, of course not. I'd fix my code to make sure it's faster and then I'd post them. This is how this works. If there's anything, and I do mean anything that Qt is slower at than any other vector graphics framework, be it Microsoft's WPF, Java2D or Cairo we'll fix Qt and make sure it's either faster or at least at the same level. Like I said, I'd love to be able to test Qt against something else, rather than Qt itself. If you can provide me a benchmark that shows Qt slower at anything in comparison to any other vector graphics framework, I'll make sure that it's not the case for long.

Monday, October 23, 2006

Benchmarks

A lot of people has been asking me about some performance comparison for the vector graphics framework we have. Rendering polygons, especially when we're dealing with stroke, tends to be the most expensive rendering operation performed in vector graphics. I constructed a little test, which tests raw polygon rendering power of Qt and Cairo.

For the test I used the latest Qt main branch, and the master branch from Cairo's Git repository.

The test is composed of rendering three complex polygons. The first one is a text path, the second is a small polygon with a large amount of vertices that fall on the same scanline and the third one is a huge polygon with about 100000 vertices.

The results measure frames per seconds at which each framework was capable of rendering the given testcase. Therefore the larger the better.

I tried being as objective as possible. All tests go through the whole pipeline, meaning I tried to make sure that the framework doesn't cache too much and actually renders what's being asked. I used latest version control code for all frameworks. The data used in the tests is available here: http://ktown.kde.org/~zrusin/complex.data (newline separated polygons whose coordinates are comma separated). All tests were written to utilize antialiasing.

Oh and all tests have been done on a machine with Pentium(R) 4, 3.20GHz processor, 1 GB RAM and NVIDIA 6600 with 1.0-9625 drivers.

Having said that the results were (charts follow):
First just pure Cairo vs Qt native performance:

Qt was respectively 7, 5 and 6 times faster. Than Cairo in those plain tests. This is a direct result of Qt's new wicked tessellator in 4.3.

But all the frameworks have many backends, the most interesting one being the OpenGL backend. For 4.3 I devised a new method of rendering polygons for the OpenGL, based on stencil clipping. So lets see how Qt's OpenGL engine compares to Qt's native XRender engine:

The difference is huge. Qt OpenGL rendered the first polygon at 487 frames per second vs 76 in Qt XRender engine. Note though, that in XRender we tessellate which is of NlogN complexity, in OpenGL I'm able to render polygons in a completely linear fashion. The method does deteriorate for polygons with 80000+ vertices due to large amount of triangles that has to be processed - it's a GPU bottleneck though which means that with a more powerful graphics card those results would skyrocket.

Finally, lets combine the results of all the frameworks and see how they match-up:

The reason for Cairo with Glitz backend yielding the same results as Cairo with XRender backend is that polygon rendering in both of those goes through the same client-side steps all the way until the final blit and it's not the blit but the tessellation and rasterization that are the bottlenecks. I added Amanith to the results because some people mentioned it in my blog before. Both Amanith and Cairo (Cairo only with native XRender backend) crash on the last polygon. In Amanith the tessellator seems to fall apart. In the Cairo case application crashes in the XRender code, so most likely rasterization code is not keen on one the trapezoids that Cairo sends it. Cairo with Glitz backend render the last polygon at about 0.2 frames per second (but doesn't crash which again shows that it's likely XRender's trapezoid rasterization code, especially that Carl couldn't reproduce the given crash on his laptop). Interesting fact right now is that Qt with XRender is way faster at rendering polygons than Amanith and Cairo with Glitz, both of which are OpenGL accelerated.

Notes: I know Carl is working on a new tessellator for Cairo which should exhibit the same logarithmic behaviour as the current Qt one. Carl was kind enough to even send me a tarball of the branch in which he's working on it. Unfortunately, although the results for the first polygon were at about 13 FPS (2 frames per second better than the current Cairo tessellator) they were degenerating for other two polygons. This is most likely due to large precision of the new tessellator (in both #2 and #3 testcases you get vertices close enough to consider them coinciding without any visual artifacts). Once Carl will get the precision down and integrate the new tessellator I'm going to run the tests again.

Conclusion from all those tests is that right now Qt is leaps ahead of any other vector graphics framework in terms of raw performance. Nothing comes even close. Qt's OpenGL engine is so fast it's basically unfair to compare anything else to it.

Objectivity aside, Qt rocks. It really does. And if you're using Qt and not using Qt's rendering architecture, everyone should point at you and make fun of you for not having complete and utter trust in me, as the only true graphics ninja and the team of Trolltech's Samurai Graphics Assassins.

Thursday, October 19, 2006

ARGB windows

I've been getting a lot of questions about writing semi transparent applications with Qt. So I've put up an example showing once again how to use ARGB visuals with Qt. The example, just like the old one I showed a while ago looks like this:



The code is available at http://ktown.kde.org/~zrusin/examples/argb.tar.bz2.

By the way of this example I would like to ask some KDE people to stop abusing the fact that I work for Trolltech. What has been happening a lot lately is that people send me emails asking and in some cases actually telling me to do X or Y for their application or send them code to show them how to do Z, which would not be a problem if not the fact that if I won't respond within a few hours they email qt-bugs referencing me by name and writing that this is a "bug" for me. That's ridicules, please don't do that. My motivation to help you is not proportional to the amount of emails you manage to get in my inbox. And if I tell you on IRC that I can't reproduce a bug and I'll need more informations, for example what version of X.Org and on what drivers you're running it, then sending the same bug you told me about on IRC to qt-bugs will not magically make me fix it, I'll still need the same extra informations to get anywhere. So please have mercy on me and be reasonable I am physically not capable of addressing everyones graphics related issues and questions.

Saturday, October 07, 2006

Bands

I've been browsing youtube today and I was pretty suprised to find some hardcore music videos on it. I've spent a little time just looking for bands that I enjoy listening to. So, in no particular order, here's what I am listening to:
Shelter - Here We Go
Throwdown - Forever
Hoods - The King Is Dead
H2O - One Life, One Chance
Madball - Pride
Earth Crisis - Nemesis
Do or Die - Bella Famiglia
Sick Of It All - District
Ramallah - The Horror
E-Town Concrete - Mandibles
Warzone - The Sound of Revolution
Hatebreed - Perseverance
Terror - Overcome
The ending of Throwdown's Forever when he says:
"For myself,
For my friends,
For my family,
Straight fucking Edge!" is just such a great breakdown.

Friday, October 06, 2006

Perspective transformations in main

Today I merged qt-perspective branch into qt-main. Yesterday I fixed some issues with bilinear filters and some minor stroking artifacts and decided that perspective transformations are ready for main stream. We're hoping to switch snapshots to 4.3 very soon which will allow everyone who considers 4.2 way too stable something pretty unstable to play with =) Of course the main purpose of perspective transformations is to make things like the 3D album selection in iTunes. That's trivially doable in Qt now :)
I switched QGraphicsView to use QTransform which means that items on QGraphicsView can have perspective transformations. As always a bunch of screenshots follows (I know that some planets don't play nicely with blogspot so you might have to just come to blogspot.com and refresh to see them)
All of those are trivially doable in Qt without any OpenGL calls. It's really extremely nice and I must admit I spent most of today playing with it and writing demos. (Oh, and because it happens over and over again, please pay no attention to the fps field, when I'm implementing new features I always test corner cases and the fps on my examples are always skewed because they test something very different than what the the screenshots would imply. Whenever I post screenshots I keep forgetting to mention that and there's always someone who gets bogged down by it so now you've been warned :) You'll have to get 4.3 snapshots if you'll want to see how well it works).

Thursday, September 21, 2006

Perspective transformations

A really neat feature that Arthur in Qt4 was lacking was support for perspective transformations. QMatrix is an affine transformation class. Even though our docs advertise it as a 3x3 matrix it's actually 2x3. I've been wanting to do perspective transformations in Qt for a while. With Qt 4.2 frozen I had a chance to sit down and work in the main branch for the last two days. As a result I have a very basic support for perspective transformations in Qt. I added a QTransform class which is a true 3x3 matrix and gutted most of Qt where I replaced QMatrix with QTransform. Now it's possible to do projections of any kind of Qt element. That includes images like Konqy here:



but also all other Qt elements, like here a button with a label and icon:

All of which allows one to create a really nice looking 3D like looking effects in all Qt apps.

Tuesday, August 15, 2006

Glucose and graphics

Today I pushed a new acceleration architecture for Xorg. Called Glucose, it uses OpenGL to accelerate X. What happens there is that Glucose hooks into the initialisation code during the graphics card setup and dispatches the X rendering calls through the same codepaths that XGL uses. The email describing it and the some reasons for it is here: http://lists.freedesktop.org/archives/xorg/2006-August/017527.html. One step closer to the Open Source graphical utopia.

Besides that I've spent the last few days working on optimising various parts of Qt's rendering architecture. From OpenGL painter, through X11 to the raster code. Just beating down graphics into submission at this point really. At first a few code paths held me in a headlock that required some repetitive "banging head on the keyboard" action on my part but now it's ok. Now, Qt just rocks at rendering vector graphics. No screenshots today though :) I started writing a real-time vector graphics cartoon fully in Qt but it's not yet finished. By the way one thing I find missing in all Open Source vector editors is that you can't just scan your sketches and put them as background to trace over, Flash does it pretty ok. Instead of complaining I probably should just go ahead and implement it in Inkscape.

Finally Paul and I sat down today to figure out semantics of OpenGL support in Qtopia Core and we got it down. I'd like to have a fair dosage of 3D support on the Greenphone.

Oh, and US Airways stole my luggage. If you ever met me you know I have (had) a great collection of shirts. Now they belong to US Airways. Oh, and my US cell was in it, so if you've been wondering why I haven't been picking up your calls lately, it's because US Airways stole my phone.

Tuesday, August 08, 2006

Magic

So lets say you're writing an application. It's a pretty good looking application too. Lets say your gui is completely vector based. It's so nice because an artist designed it! But there's a problem, a large portion of your users doesn't really like the artist's style. Furthermore accessibility wise your application is a nightmare. To add insult to injury your application doesn't match at all the color scheme of any desktop environment. What do you do?

Crying is certainly an option. One used extensively by a lot of ISV as well (with limited success). What would be really cool is if you could have an external stylesheets that the desktop environment can affect, that your users can style with accessibility features, color schemes and basically whatever people want. So one would need a highly extensive support for external CSS stylesheets in SVG. One that goes a little beyond what SVG standard offers because SVG doesn't allow styling of things like "transform" element which would be very useful for number of things.

At this point it's probably very clear that is exactly what I did today.

QtSvg in 4.2 will have full support for external CSS stylesheets. That support includes all svg properties and attributes that we use.

So lets create a very simple application that loads its UI from a SVG file and lets one style it by editing an external CSS file. The SVG file that we come up is here. We add a style, that looks like this and we're well on our way. Now we add logic to our application. In this case we'll render gears as in the ever famous GLX example, but we'll do it 2D vector style. So our application looks like this: . Neat.

K, but it's pretty gray, so lets change it. First of all we'll add
#viewport {
fill:white;
}
to make sure our background is white. Then we'll change gradient on our controls by adjusting stop-color and stop-opacity properties. Then we'll change the font on our "Gears" sign. Add a wider stroke to the control container and change the stroke on our view. Final stylesheet is here. Suddenly our application looks completely different and we haven't changed one line of code. In fact we haven't really touched the application at all but it looks like this:

Magic. Let me create a bullet points with exact description of how this works:
  1. Artist creates a gui in SVG
  2. Developer does logic in his/hers favorite language
  3. Application loads the SVG and does selective rendering (as described in the last blog)
  4. ----- magic -----
  5. Flexible, good looking, accessible, scalable application.
I take full responsibility for point #4.

But lets continue. Now lets say this application has rather small controls and some of our friends have problems clicking on some elements and reading the text. So changing colors is not what we want, we would like to make it easier to read and click on elements. It's all vector graphics, so could be zoom the whole interface? Yes! We'll add
#wholeapp {
transform: scale(2,2);
}
to our stylesheet to zoom whole application and make it look like this:


Notice that because it's vector graphics you don't get artifacts you'd normally get when zooming. One can (as in the example before) extend the borders, zoom only certain elements... Well, basically rearrange everything.

The things we can do with this are pretty amazing and I've been playing with it for the last two hours and it's a little scarry how much fun it is to change the complete look and feel of an application this way. Especially the amount of things that can be changed while keeping the application still behaving more-less like the initial version, is amazing. I hope people will have a lot of fun with this.

Friday, August 04, 2006

Shadows

Some of the questions that I get quite a lot lately are: how do I make good looking shadows with Qt4? How do I make them from SVG's? Can you show me the code?

So to answer those question in general I wrote a small application that shows how to do shadows. There's couple of ways of getting the shadows look decently. The first step is getting a black rendering of whatever it is that you want to shadow. In this example we open a QPainter on the svg rendering that we want to shadow and we fill the entire area with black color. The trick is to set the composition operation to SourceAtop, which basically makes rendered area from the SVG black - exactly what we wanted. Once we have our rendering in black we can blur it. The code for the application along a couple of SVG's is here: http://ktown.kde.org/~zrusin/examples/shadows.tar.bz2. Finally images showing the results of our demo application follow:




Fun with SVG

On top of the selective rendering of SVG's another feature that I promised to implement was the ability of rendering a SVG file/element into an arbitrary rectangle on the surface.
So one can have a SVG with some viewbox, that SVG can in turn have some element defined and one can have a surface with a whole different coordinate system and in that system have a rectangle on which the SVG element should be rendered. So in the picture it would look like this - SVG with an element mapped to another viewport with a custom bounding box.

Implementing it on top of selective rendering turned out to be rather simple. All we have to do is translate and scale (but we translate by the difference between the destination and mapped scaled coordinates of the source).

As always, I wrote a demo application to test it. In the application I have 4 SVG elements renderer at different locations within the same viewport and a circle with a radial gradient rendered on top of them. Here's how it looks:


What's pretty nice about all of this is that it makes styling applications using SVG's pretty simple. For example I wrote a simple application that renders a clock, clock is stylable via SVG. SVG contains five elements with four predefined id's "face", "minutes", "hours" and "seconds". The application loads those element into respective spots and renders them. I couldn't help myself so besides rendering them I'm dynamically generating correct shadows for SVG shapes defined in the style files. It really is pretty cool. Here are the screenshots (yeah, yeah, I didn't have any time to create really good looking SVG clocks so you'll have to live with one's I slapped together :) ).


Ideally I'd love to see applications that do custom rendering stylable in the same way. For example KOrganizer for the calendar view could easily load SVG file that defines the look of that view. This way before new KDE releases we wouldn't have to be manually changing the look of applications to match the style or make them seem more modern - we would just add a new SVG file and that's it.

Thursday, August 03, 2006

SVG on graphicsview

A lot of people has been asking for a simple way of rendering SVG files on top of qgraphicsview. The only catch was that most of them wanted it along a way of doing selective rendering of SVG files. For example people create huge SVG files and use them as collection of items. Individual elements are nested inside a group element that has a predefined xml:id. I've spent most of yesterday just fixing things in QtSvg to make it possible. The thing that makes it tricky is the following: lets say that we have a SVG fragment with the following structure:
<g transform="scale(0.5,0.5)">
  <g id="myElem" transform="scale(2,2)">
    <rect x="0" y="0" width="2" height="2"       transform="translate(20,20)" />
  </g>
</g>
So we have a group that defines a transformation matrix and inside that group we have our predefined element with id="myElem". The question is what is the bounding box of our rectangle and how do we make sure it fills out the complete area of the rendering viewport. To do that we need to find the rendered element and traverse starting from that element down through its children propagating the transformation matrix correctly. So when we're in rect out transformation matrix is defined by the rect transformation (one translating by 20 in each direction) matrix muliplied by the parent transformation matrix (scaling by 2 in each direction). So the actual bounding box of the rectangle is x=40, y=40, width=4, height=4. Having that all we need to do is set our window to those dimensions and render the element. The code to traverse the SVG tree and QGraphicsSvgItem are already in Qt so once we'll update the snapshots you'll have it.

One of the things that are possible with it is for example having an entire card deck in an SVG file and putting individual cards into predefined groups. I wrote a quick example that takes such constructed SVG files, fetches the cards from the SVG and renders them with some arbitrary transformations on QGraphicsView. A pretty nice feature of it is that I made sure the SVG file has to be loaded only once. QGraphicsSvgItem's can share the context and are capable of picking the right parts of the SVG that actually constitute their whole visual appearance. Thanks to that no unecessary parsing or processing of the SVG tree takes place. A screenshot follows :)

So now it's possible to use QGraphicsView along SVG elements. And since QGraphicsItem's handle all input events one can do pretty nice things by using SVG to define look of the items and handle the logic in the code.

Monday, July 31, 2006

Compiling SVG to C++

The problem is that creating visually appealing widgets is rather difficult. The number of developers who can draw is about equal to the number of artists who know math ;) (and that's an extremely small number). Sometimes people ask me to do, what seems to be, absolutely trivial things, like giving them some code to do rounded rectangles. Having mockups doesn't help here because there's a long way from going from a semi-transparent gray rounded rectangle without an outline to : QPen pen(Qt::NoPen); QBrush brush(QColor(193,193,193,127)); painter.setPen(pen); painter.setBrush(brush); painter.drawRoundRect(10, 20, 80, 60, 25, 25);.

I was trying to figure out how can we make it easier. Using SVG is a very obvious solution. Sometimes though you want to make it a little bit more custom and using SVG might not seem like the best idea. I sat down after work today and created a SVG to C++ compiler. It's pretty interesting. You can do a mockup in your favourite SVG editor and then compile it to C++ and you have a widget. Or an artist could do a mockup and send the compiled widget and the svg to a developer who can then go nuts. Given that I've spent on it about 2 hours so far it's very basic. I'll try to see about releasing that code sometime soon. Right now it's based on an internal research implementation of SVG (yeah, I wrote of a few) I did a while back for Trolltech, so we'll have to figure out what to do with it. It's an interesting route that I'm not 100% convinced makes all that much sense. Maybe it would be better to just be able to say widget->fromSvg("svgfile.svg"); and have some api to figure out the shape/look of the widget directly from an SVG.

Anyway, sample generated output and the svgfile used to generate it, is at: http://ktown.kde.org/~zrusin/examples/svgtocpp.tar.bz2.

More blurring

Jani Huhtanen was kind enough to let me know that he's got another blurring algorithm that works even faster than Mario Klingemann Stack Blur algorithm. It seems to produce results that are a little further from gaussian blur than Stuck Blur but it works about 3-4 times faster which makes it a fantastic algorithm for people who just want to blur :) Thanks go to Jani for sending me his code.
I figured the code deserves a demo of its own so I quickly whipped out another sample app. Now we have a lens that does selective blur on our image (the code is not optimized because I wanted to see how it performs before optimizations - like for example for a real app you wouldn't blur the whole image as I am right now but only the part obscured by the lens). To show in screenshots:
Roberto with a unblurring lens on top:

Roberto blurred a little:

And blurred a little more:


The code is available at: http://ktown.kde.org/~zrusin/examples/expblur.tar.bz2

Today I also worked on Qt's OpenGL engine a bit, just cleaning things up. It would be so simple to do OpenVG implementation on top of our OpenGL engine that I'm tempted to just do it.
We got a new demo device from ATI as well today. It's very nice. Now to get Qtopia core running on it... First of all we need to get rid of all the glBegin/glEnd calls and switch things to vertex arrays and buffer objects which is something we should have had done a lot sooner but now it's really important as we want to be running on OpenGL ES natively.

Friday, July 28, 2006

Effects and Qt Jambi

Yesterday for fun I implemented a new blurring method. Blurring is a very common effect that opens quite a lot of possibilities. For example one can use it for shadows and it works very nicely when one is trying to deemphasise something visually. The algorithms that we had for it in KDE were not impressive at all. I went ahead and implemented Mario Klingemann's "Stack Blur" algorithm. I changed his algorithm a bit, mainly added support for handling alpha channel correctly and I was very impressed. It gives really nice results and is blindingly fast.
On a 385px by 385px image i was getting around 200fps with it. This is all software mind you and it should prove that software algorithms are good enough to still do a lot of visually appealing 2D things.

I'm not certain where I'm going to put the algorithm itself though. Qt will get an api for filters but that will happen for 4.3 most likely. I think it would make sense for people to start using this algorithm right now. Like I mentioned a few times I don't like KImageEffects class at all, because it's a mess. So for now I decided to release the algorithm itself as part of a small demo app. Roberto who saw my last demo app where I was using South Park head character asked me to use his character next time. So, first of all the application is available here. And now a few screenshots:
First this is plain Roberto:

Now Roberto blurred:

And finally Roberto with ghost-traces:

It all works incredibly fast so you should be happy with the results.

Gunnar blogged about Qt Jambi and if you have java running I suggest you give it a spin. When I showed some of the demo apps to people on KDE Four Core meeting they were very impressed (rightfully so I might add ;) ). I love the fact that with Qt Jambi I don't have to work with listeners. I just could never get myself to like or even tolerate the syntax for using listeners in Swing. Being able to automatically connect slots by name with QtJavaUtils.connectSlotsByName is just neat.

Thursday, July 27, 2006

Hardware accelerated polygon rendering

So in the spirit of writing down about the things I'm working on on a daily basis today comes hardware accelerated rendering of complex polygons. Ignacio CastaƱo finally convinced me to this ingenious method so all credit for it should go to him. I've spent last few moments at the office today looking into this method and it's just gorgeous so I'll give a brief overview of it.

In general all (at least Open Source) hardware accelerated vector graphics frameworks break up complex polygons in the process of tessellation. Like I mentioned in a few blogs before this process turns out to be quite complicated when trying to make it robust and fast. Ignacio's method beautifully avoids both problems.

So now to the method - the core idea is that we render to the stencil buffer and use it to correctly render the final polygon. So to use the Odd-Even fill rule we enable stencil writes and set up the stencil mask with glStencilMask(0x01) call. Next we make sure that the on passing the pixels are inverted with glStencilOp(GL_KEEP, GL_KEEP, GL_INVERT);. Then we can set the function and reference value for stencil testing by calling glStencilFunc(GL_ALWAYS, 0, ~0). Now we just render the vertices of our complex polygons as, for example triangles (fans would be just as suitable). Finally, we can enable color writes, disable stencil writes and enable stencil test and render a quad with the min/max coordinates of our polygon.

The method is awesome, as it (in theory) doesn't involve any kind of client side computations (besides a trivial min/max test) and (again in theory) operates in whole on the hardware. A wonderful sideeffect of all of this is that we avoid robustness issues that tessellation introduces.

To test this method I wrote today an application to compare different methods of rendering complex polygons (full client side rasterization, trapezoidation on X11 with Xrender, triangulation with OpenGL and finally stencil tests with OpenGL). So far Ignacios stencil method is by far the best. A sample result showing rendering of a rather complex (1000+ vertices) polygon follows, first client side rasterization:

And now Ignacio's method:


Finally an insane polygon I created for testing robustness (intersections at distances smaller than the resolution of doubles) and speed (it has segments with 100+ vertical vertices falling on a scanline). The new method can actually handle it correctly and with 100000+ vertices we still get usable performance. Pretty amazing, so thanks Ignacio for letting me know about this!

Tuesday, July 25, 2006

Animation and layout on paths

I finished the code to correctly map transformations along arbitrary paths (that includes bezier curves). It's extremely nice. The list of features that can be implemented on top of it is quite extensive. A two very obvious examples are animations along a path (as defined in SVG) and text layouting on arbitrary curves.

For example take a look at the following screencast (of course it's really smooth in reality but our screencasting software still has a long way to go, although I've been pretty nicely surprised this time). In this demo you can see a South Park character head (in this case it's mine) animated along a bezier curve with me manipulating the curve in real time.



So now to the math because it's rather neat. Moving along a path would be trivial if not that we have bezier curves in our paths. So the only tricky part is figuring out the transformation necessary to transform coordinate system suitably for arbitrary points on a bezier curve (that plus we need to find the length of the curve itself for which algorithm I could describe in a separate blog).

The parametric form of cubic bezier curve has the following form:
. In this case we need two algorithms to solve all our problems:

  • Nearest point on a curve - to correctly compute t on arbitrary positions within the curve

  • Tangent (or normal) vector to a point on the bezier curve - to compute our transformation given that the curve will be our attachment surface


The first one is described in detail in Graphics Gems 1. For the second all you have to do is take the derivative of the parametric equation. After simplification you should end up with:

Now we can compute the change in t by substituting the variables with the components of our control points. The vector that we get can be used to compute the slope of a line tangent to the curve at a given point. The last thing we need to do is compute the transformation matrix needed to transform our object. We do that by first translating the object to the point at the given t (we already have t and we get the point by substituting in the original equation) and then rotating the object by atan(slope of a tangent line) (this is assuming that we're transforming with regards to the horizontal axis). Extra points for doing all that with absolute minimal number of operations ;)

Or.. you could use Qt and we'll do all that for you.

Monday, July 24, 2006

Tessellation again

I've spent a little bit of time on our tessellator again. It seems that every time I do that another problem pops up. It's such a trivial algorithm that it's starting to become irritating. I'm getting more and more motivated to write a paper about it. There's a number of very fundamental issues here.
In the basic case, meaning simple polygons, tessellation is trivial and there are papers describing techniques to do in linear time like this or this. The problem is that most polygons that we currently decompose are not simple. Self-intersecting polygons with holes are very common and that's where most of our algorithms falls apart.

There are two papers describing handling such complex polygons: An implementation of a Near-Linear Polygon Triangulation Algorithm for General Polygons and
FIST: Fast Industrial-Strength Triangulation of Polygons. The detail that is usually not mentioned is that handling self-intersecting polygons in those algorithms has severe effects on their complexity (from nearly-linear to n^2*log*n).

Which leads to trivial conclusion #1: if tessellation of simple polygons is almost linear then would it be faster to unwind complex polygons and tessellate created this way simple polygons rather than tessellate directly one complex polygon. The only challenging aspect of unwinding polygons is finding the points where the polygon self-intersects. As a side-effect we venture into a lot better researched part of computational geometry - segment intersections. We can apply Bentley&Ottmann algorithm between the edges of a polygon and mix it with any of the snap-rounding techniques to try to handle precision problems.

Now this operates in nlogn but the catch is that when rendering large number of simple non-self-intersecting shapes we do a whole lot of work for absolutely nothing.

That in turn leads to conclusion #2: when rendering large amounts of simple primitives our fancy tessellation algorithm falls apart because it does a lot of work for absolutely nothing. Algorithmically there's nothing one can do here, you have to have a little bit of higher-level knowledge that can help you figure out whether the following primitive to be rendered is simple or not.
And now my latest thorn: when rendering complex polygons we generate a lot of trapezoids (due to the fact that almost every vertex forces generation) which after rasterization all fit within one scanline (happens very often when rendering on a big viewport mapped to a small window). So when the server is rasterizing those trapezoids it does a lot of work for nothing. The horizontal red spans in the following image show trapezoids which visually won't add anything to the rendering (after rasterization of them that is).

I'm still a little bit torn as to at which step should merging of those trapezoids actually happen.

Wednesday, July 12, 2006

Project Unity and eye-candy

I'm very happy that we got to do the WebKit integration during the KDE Four Core meeting and release it in the form of the Unity project. I think it's an interesting situation. We need an actively maintained web engine for KDE4, there's no question about that. In the past, due to the problematic situation we were in with Apple, I was leaning towards bringing Gecko into KDE. The reasoning was that if we're supposed to depend on an externally developed web engine it makes way more sense to depend on one that has been developed in the open. But Apple did tremendous amount of work to improve the situation and we now have an open WebKit (although the name could use a lot more work ;) ). I think it makes sense for us to join that effort, especially since most KDE developers understands that codebase a lot better than they do Gecko. Apple is using WebKit in a more desktop-aware fashion (e.g. dashboard) and it would be real nice if we could share those parts between OS X and KDE as well. There is tremendous amount of things that can be done with a well developed web engine on the desktop. Bridging in network connectivity/internet services and the desktop is one of the most visible trends in computing right now and KDE has to make sure it's ready for it. SVG, XSLT, XPath and CSS create one hell of framework with which a lot can be accomplished and we have a lot of ideas about some of the new things we could do with it. I guess we'll see what happens next.

Lubos writes that KDE needs someone to work on composition manager for KDE 4 because I don't have time. Which is only partially true. It reminds me of a conversation I had with George and Dirk during the KDE Four Meeting right before we started working on project Unity.
Dirk: What rendering framework is WebKit using on Windows?
George: Cairo.
Dirk: And on OS X?
George: CoreGraphics.
Dirk: What are we going to use?
George: Zack...
And to tell the truth, before we even had working CMake files to compile Unity, the graphics layer has been already ported (the only thing I haven't done was support for shadows, but that's not really crucial.. yet). And as to my lack of time to work on KWin, it's really not that simple. Almost everyone wants me to work on something for them and with Lubos using the goofiest indention ever (KWin's workspace.cpp :) ) KWin is not even close to being near the top of my todo (not to say that I'd suddenly start working 24/7 on it if it used Qt indention, but with long todo's and lack of sleep things like being comfortable while working on a codebase are hugely important).

I'm back in the US because today I've started my week long vacations. I don't have a laptop (and haven't had a working one for almost a year since I broke the last one while working on Exa, which is btw, a great testament for those who think that people working on Open Source make a lot of money) so this is going to be the first week in about 8 years when I won't do any programming. I'll spend the week compensating for my European starvation diet. By the way of my diet, for the KDE Four Meeting Aaron brought a whole box of vegan food that Tracy and him assembled for me in Calgary. It was really cool and it meant a lot to me, so yeah, thank you guys :)

Saturday, July 01, 2006

Fun with curves

During the last few days I've decided that besides some serious bug fixing for Qt 4.2 tech preview I'll work a little on bezier curves. I started looking at interpolation with bezier curves in order to improve the quality of some of the polygons that we're rendering.
For example in 4.2 we actually construct paths from bitmap fonts. The algorithm that we use is basically following the edges doing lineto's between individual elements. The problem is that once you zoom it quite a bit you can see the edges. It's a problem that most SVG's is suffering from as well (blockiness due to extensive usage of lines instead of curves). My algorithm is largely similar to what Maxim Shemanarev did in AGG. The results are really good, so I'm very happy and I hope to get it in soon.
While working on that I used the math in few more places. I finished up the code to do object positioning along a custom path. Which we need in two places: animation support for objects moving along a path and text layout on a path. Both are extremely nice features.
The work Simon is doing on text layouting is just awesome. I'm extremely happy we now have the ability to add application private fonts by working with a truetype file directly. The last time I looked at Poppler it was one of those outstanding things that have been missing. One more missing feature there is the ability to create custom fonts directly from paths and getting Scribe to use them. For example in SVG I've been hacking around it by falling back to a very primitive custom layouting strategy (instead of using Scribe) every time the font that's being specified is a custom font constructed from paths.

Last week, Donald, one of the support engineers from Trolltech, got me to try out his snakeboard. (btw, if you never heard the South African accent i strongly recommend you meet someone from there right away because it's quite an experience). I'll stick to skateboards. Boy, was this sucker hard to control. And Donald figured that the best way to learn how to ride is to try it downtown right next to the harbor. Oh, yeah, because when I'm eating dirt I like as many people as possible to see me. Fortunately after about three fours we've been asked to leave after Donald, in a very crude way, tried to measure the vertical distance between his back and the pavement.

Oh, if I haven't responded to any of your emails it's most likely because I lost them last week.
Today we're kicking off the KDE Four meeting. My birthday is tomorrow and I'll spend it working locked in a cabin, neato ;)

Tuesday, June 13, 2006

In Norway

I've been in Norway for almost a week now. The weather has been real nice for the last few days so I think I even might have been complaining a little less than I usually am when in Norway =)

So for the last few days I've been working on making sure that svg works nicely on top of QGraphicsView. And boy does it rock. I went ahead and implement a lot more of SVG (the more dynamic stuff) and because it's all on graphicsview I can edit SVG's on the fly. Here's a screenshot:


One thing that I've been lacking in Arthur and I hacked around it in QtSvg is the ability to set explicit transforms on brushes (meaning transformations on fills and strokes that don't affect the rendering shape). It's a pretty trivial feature (assuming you know your linear algebra ;) ) so I went ahead and added support for transformed brushes today. So now QBrush has a setTransform method that applies to both textures and gradients and is independent of the main painter transformation matrix. You can do some cool stuff with it like:

Now finally I added some api to make sure that things like the Office 12 Ribbon widget are possible in Qt. I don't think that I'll have the time to finish a full blow ribbon like widget for 4.2 but at least we made sure it's possible to implement it in applications using Qt. Obligatory screenshot:

Now I do a lot of things but one thing I'm really bad at is cooking (for definitions of cooking that include the phrase "eatable meal" because I'm really good at burning "things" - referred to here as "things" because in most cases once I'm done cooking, it's impossible to identify what was it that I was cooking... could be a shoe, you'll never know and the difference is miniscule anyway). My lack of skill there is not a problem in US but makes for a one hell of a diet plan in Norway (i believe the technical term for it is "death by starvation"). Last week I had a real nice conversation with a certain lady. I asked whether she has any vegetarian sandwiches to which she replied "yes! of course" and proceeded to hand me a ham-sandwich. I politely declined and mentioned that one must stretch the definition of "vegetarian" real far before it includes the subpoint saying that eating ham is ok. To which she (visibly excited by the brilliance of the following idea) said: "but if you take out the ham it's vegetarian!". It's really hard to argue with that logic, but no, despite the popular belief "meat-meal minus meat does not equal vegetarian meal". In fact it doesn't even equal a meal. It qualifies as "a something on a plate" (given there's a plate in that equation at all) but not much more. Now a nice thing about all of this is that every morning I get to count all my ribs in a mirror and so far so good, they're all there.