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:

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:

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 ;)