Friday, January 26, 2007

Generating SVG's with Qt

I've been working on a lot of things at once over the last week but I just remembered that I never mentioned something that I should have. In the beginning of the Qt 4.3 development phase I added a class called QSvgGenerator to QtSvg. QSvgGenerator is a paint device, meaning you can open QPainter on it and yes, that's right, you'll get an SVG XML stream back that you can save to a file or manipulate.

So now you can redirect your widget/window and have a snapshot of your application dumped to SVG format... Come on that's pretty cool. The generator still needs a lot of work, especially when it comes to complex text. But here's a weird, example. I made Qt render a simple animating bezier curve, then loaded html with Qt documentation and rendered that with opacity of .75 (which is why it looks very blend) and finally redirected to a painter opened on a QSvgGenerator. As a result I get a SVG (viewed, of course with, svgviewer) looking like this:

And the full output is here. So yeah, the concept of being able to load simple html and then save it as SVG is pretty neat.

Also boolean ops on paths are now in Qt. You'll find them in QPainterPath's. Since I already had the code and Andreas asked me for it, I added QPainterPath::intersects(const QPainterPath &other) and QPainterPath::contains(const QPainterPath &other) that can be used to check whether two paths intersect or whether one path fully contains the other. I still want to do some heavy optimisations on it, but I'd like to implement "Snap Rounding of Bezier Curves" instead of trying to find the right shortcuts to use reduced-predicates for the intersection finding algorithm.

Monday, January 22, 2007

The magic of animation

Creating a decent animation, albeit a lot of fun, is quite complex. Besides being able to create the content (and therefore exhibiting basic artistic skills) one has to go through the mundane process of trying to figure out what exactly should be on every frame.

SVG, as a format, is absolutely atrocious at expressing animations. KDE 4 is moving more towards dynamic metaphors, where animations will be used to convey a lot more information. Now the question is how do we let people who inherently have no artistic skills create animations that look and behave correctly. While "look correctly" is pretty simply defined as: it's visually appealing. Then "behave correctly" has a more complex definition that will depend on many factors. We'll define a "well behaved animation" as one which simply doesn't irritate or inhibit the work flow of the users.

While the latter is mostly a challenge for usability engineers I'd like to help people create animations - quickly, with minimal amount of artistic skills and no mundane tasks. So ideally I'd like to be able to say "this is what I'm starting with" and "this is what I'd like to end up with" and see computer animate this process. The technique is known under "shape interpolation", "shape blending", "image morphing" and many other names. There was a lot of research done on this topic but so far no one used this technique to do real-time animations on desktop.

The most popular research papers related to this problem include "As-Rigid-As-Possible Shape Interpolation", "A physically based approach to 2-D shape blending" and finally "As-Rigid-As-Possible Shape Manipulation". If you haven't seen it, you definitely want to look at the last one, there's a short movie on that site showcasing some of the things one can do utilising their algorithm. Some of the examples from the above research follows:

I think that shape interpolation together with as-rigid-as-possible shape manipulation done on QPainterPath's, or whole SVG's in fact, could potentially be the answer to our animation woes. The pain, once again, is that people always work on polygons in those papers so I'd need to spend a bit of time to figure out how to mix it in with paths and inject curves into the algorithm.

Oh, and yesterday was the "World Hug Day" so if you haven't hugged anyone yet, go right ahead.

Thursday, January 18, 2007

More on WebKit Qt

Two days ago Lars and I sat down and did the initial implementation of classes which will represent the public API for the Qt/KDE version of WebKit. In KHTML almost everything has been handled by KHTMLPart. We'd like to avoid having one huge object that does everything this time so we went with similar abstraction to the one present in WebCore - meaning Page/Frame distinction. The top level classes are now: QWebPage which represents (surprise - a web page) and QWebFrame which is (another shocking discovery) a frame (remember that a page can have multiple frames).

It's pretty interesting what one can do with it. Me being me (aka. weird) had to try to do something visually funky so I made our test browser have a transparent overlay progress loader that is hidden when nothing is being loaded and made the pages render in grayscale until they are fully loaded, so a loading page looks like:And before someone complains - no this won't be a default and won't even be included in WebKit by default, it's just to give people a rough idea what one can do with this framework (and yes, the filter that I did for it messes up fonts but I just didn't even bother to make it flawless) Or more precisely I wanted to make sure one can do anything. Here's another example with webpage rotated a little bit (this time without grayscale filter on it) :
So, yeah, I think you'll be able to do a lot of new and pretty exciting things with WebKit once KDE 4 hits the streets.

Wednesday, January 17, 2007

OpenVG

OpenVG is a royalty-free, cross-platform API that provides a low-level hardware acceleration interface for vector graphics libraries such as Flash and SVG. Or at least that's how http://www.khronos.org/openvg defines it.

The problem is that there is no Open Source implementation. And the implementation that claims to be the reference implementation is closed. It'ss a rather silly situation, especially given how important vector graphics is becoming on our desktops/mobile devices nowadays.

After this introduction I'm sure you already know that I went ahead and started an Open Source implementation of OpenVG. I did it on top of QtOpenGL. The main reason for it is that QtOpenGL, quality and speed wise (in Qt 4.3) beats everything out there - every vector graphics framework.

So, there's a git repository at:
http://gitweb.freedesktop.org/?p=users/zack/openvg.git;a=summary
there's an example included, that animates and looks like this:Gears demos are mandatory for any kinds of hardware accelerated API it seems ;) Oh, and due of all the extra features that went in Qt 4.3, Qt snapshots are currently required to compile it.

I'm not sure where this is going to go. It will largely depend on whether there's real interest in it. In general I think it'd be interesting to see KDE have a library that would allow running of OpenVG based content right on KDE. It could be potentially an incredibly powerful feature of KDE as a platform, to support the hardware accelerated vector graphics api.

Sunday, January 14, 2007

More boolean ops

I've spent most of the day just playing around with different degenerate cases of boolean operations. I've recorded a short movie showing some live path merging - the one case that should be interesting to application developer is combining two simple rounded rectangles to produce a frame with, what one can easily imagine to be, a highlighted selection on the left. Note that in this case two simple rectangles are enough to produce animation of the selection rectangle on the left going up and down between the "imagined" items :)

And also I forgot a very important thing, which is that Gunnar and Eskil hooked me up with a very cool QtJambi mug. They're doing an amazing job (working on QtJambi, not giving out cups). And here's the mug (and the last I checked, the thing holding it, was me).

Set operations on paths

I'm virtually never excited about the things I have implemented. Partially because I've been working on computer graphics for quite a while and a lot of what I do comes down to doing things that I've done before for different software, or in a different scenario. Writing code while knowing exactly what problems you'll end up facing and how to solve each one of them is very mundane and it makes it hard to get excited about it once you're done. So whenever I have a little bit of time I try to sit down and implement something that hasn't been done before.

So, here's problem #1: one of my embarrassments in the Qt X11 engine is that fact that we don't do anti-aliased clipping there. So if you'll clip out a rounded rectangle in your viewport/widget it will leave out nasty jaggies on the sides. We do it correctly on Windows but not on X.

Main reason for why we haven't done it, is that Qt has this nice concept of combining clip-regions which requires basically a full fledged implementation of boolean set operations on polygons to work correctly.

And here's problem #2: in Qt we have this class called QPainterPath which is a resolution independent, geometrical representation of some rendering. We got reports from people saying it would be really great if people could use boolean set operations with QPainterPath's. And I agree. Set operations on QPainterPath's would be an incredibly powerful feature, especially for animations.

Requirements for a state of the art algorithm here would be: fast, works with all kinds of degeneracies and operates directly on paths without intermediate conversion to polygons. The issue is that none of those things is usually associated with set operations on polygons.

In 1998 a paper entitled "Efficient clipping of arbitrary polygons" was published by G√ľnther Greiner and Kai Hormann. It's a great paper, unfortunately the algorithm doesn't handle degenerate cases at all. This November Dae Hyun Kim and Myoung-Jun Kim published a paper entitled "An Extension of Polygon Clipping To Resolve Degenerate Cases" which addressed the shortcoming of the algorithm described by Greiner. The paper was a little short on details though so I've emailed Dae Hyun Kim who was kind enough to send me the full, original version of their papers. It's a tremendous paper and I'm very grateful to Dae Hyun Kim for sending me it.

Equipped with the paper I've sat down to modify the algorithm to handle paths, which was the last of my requirements for it. The research done in both papers was dedicated to polygons, while I wanted to apply it to paths, where curves are first class citizens. The main difference between polygons and paths. for the purposes of our new algorithm. is that with polygons any two segments can intersect in at most one point, with paths two arbitrary segments can intersect each other in at most 9 points. Furthermore with paths one segment can intersect itself. That plus a few smaller issues are causes of serious woes when working with paths in computational geometry - reason why basically no one does it.

Qt does now though. And yeah, I'm very excited about it. The new algorithm deserves a research paper of its own and if I'll have some spare time I'll definitely write a little bit about it.

I really needed this. I needed to do something that was very unique from a purely mathematical/computer science perspective rather than "oh, hey i fixed this bug/implemented this feature" type of stuff to keep me motivated. A screenshot showing a path (in dark gray fill and black outline) created from an intersection (boolean "And" operation) of two paths (the dashed blue and red objects) is shown below.

The number of effects and things that can be done with boolean set operations on paths is tremendous (not even mentioning the clipping :) ). You can be sure I'll write at least a few demos to show how to do very neat effects by differently combining few very simple paths.

Tuesday, January 09, 2007

Blend modes and dash offsets

Draft of SVG 1.2 Full adds composition modes to SVG. Besides the typical Porter&Duff operators some additional blend modes are defined in it. Those modes are also very commonly seen in many Adobe Photoshop tutorials and people frequently asked for them in Qt. They include "screen", "multiply", "overlay", "plus", "difference", "hard and soft light" and a few less prominent ones.

We decided to implement them for 4.3. Unfortunately Gunnar said that he simply won't have time to implement them and since I consider them to be very important I sat down after work today and implemted those blend modes in Qt. So if you checkout tonight's snapshot of Qt you'll nice that QPainter has new CompositionMode's. If you looked at some of the Photoshop tutorials on the net on how to do lightning effects, now you'll be able to do them all in Qt which is rather nice.

Once I did that I decided that I'll go ahead and implement the other feature that was missing in Qt and is required by SVG which is: dash offsets for stroke. API wise to QPen and QPainterPathStroker I just added setDashOffset(qreal offset) methods which respectively set the dash offset for the rendering operations in Qt.

To play around with blend modes I took two input images - CD cover image from a band called H2O and a flare generated with Gimp, they looked as follows:

And I wrote a simple application that blends those in real time, and the results of two of the modes look as follows:

One can do a lot of really interesting things with the new blend modes.
Oh, and since I'm weird like that I just went ahead and added support for composition modes (and dash offsets of course) to QtSvg and from what I see QtSvg is currently the only open source SVG renderer supporting the extended blend modes which is a nice bonus :)

Friday, January 05, 2007

Rotations

I didn't have time or motivation lately to talk about the things I am doing but today I wanted to mention something because I think it will make your life a little more exciting (that's assuming you like adding eye-candy to your applications).

Andreas and I were talking yesterday and to my great surprise he mentioned that not everyone can do 3D math in their heads. Furthermore he insisted that some people might have a problem with using QTransform::quadToQuad method which I added as a convenience method to the QTransform class. He went as far as to say that some people might not know how to transform one quad into another in 3D space. Of course in no way do I believe him, but after a short discussions we decided that adding QTransform::rotate(qreal angle, Qt::Axis axis) method to QTransform which lets one rotate an object about any arbitrary axis (X, Y and Z) would help some people.
I'm swamped with work so Samuel took this task of me and implemented that method today.

Anyway, if you quickly need to add some nice effects to your application without feeling like doing any work just use QTransform::rotate and blow people's mind ;) A short Ogg movie showing qtransform2 (you'll of course need the latest Qt snapshot to compile it) in action is here and it looks like this: