Zack Rusin

ApiTrace 2.0

2011-09-27T23:14:00.000+01:00

ApiTrace 2.0 is out. ApiTrace is by far the best graphics debugging tool out there.

We have implemented so many new features since 1.0 that we have decided to bump the version number to 2.0.

Some of the new features include:

About 10x faster tracing and 2x faster retracing
Mac OS X support
OpenGL 4.2 support
Support for multi-gigabyte traces in the GUI
Ability to display all of the uniforms
Showing number of calls per frame, marking large frames and ability to indent shaders
Support for `GL_GREMEDY_string_marker` and `GL_GREMEDY_frame_terminator` extensions, so you can mark frames and important pieces of code in your applications.
Incredible amount of bug fixes, making sure that everything we throw at it just works

The huge improvements in the performance of tracing came from both flushing/syncing the trace files only if there's an uncaught signal/exception and switching to Snappy compression from zlib.
We also did some magic to seek and load on demand from a compressed file on the disk which means that we don't load all of the data at once. That allows us to load huge files in the GUI while using very little memory. For example loading a 1GB file takes only ~20MB of RAM.

All of those improvements mean that it's possible to trace and debug huge applications with little to no costs. It's quite amazing. In fact working with graphics and not using ApiTrace starting now is going to be classified as abuse.
Read the instructions and start living the life of a computer graphics superstar, which differs from the life of an average computer graphics hacker by about 10 keyboard headbutts and half a bucket of tears a week! And that's a change we can all believe in!

NV path rendering

2011-09-18T01:27:00.000+01:00

A while ago NVIDIA released drivers with their NV_path_rendering extension. GL_NV_path_rendering is a relatively new OpenGL extension which allows rendering of stroked and filled paths on the GPU.

I've heard about it before but lately I've been too busy with other stuff to look at, well, anything.

I've decided to spend a few seconds looking at the videos NVIDIA posted on their site. They were comparing the NV_path_rendering, Skia, Cairo and Qt. Pretty neat. Some of the demos were using huge paths, clipped by another weird path and using perspective transforms. Qt was very slow. It was time for me to abandon my dream of teaching my imaginary hamster how to drive a stick shift and once again look at path rendering.

You see, I wrote the path rendering code so many times that one of my favorite pastimes was creating ridicules paths that no one would ever think about rendering and seeing how fast I could render them. Qt's OpenGL code was always unbelievably good at rendering paths no one would ever render. Clearly these people were trying to outcrazy me.

Fortunately there's an SDK posted on the NVIDIA site and it's really well done. It even compiles and works on GNU/Linux. Probably the best demo code for a new extension that I've ever seen. The extension itself is very well done as well. It's very robust, ultimately though it's the implementation that I care about. I have just one workstation with an NVIDIA card in it, a measly Quadro 600, running on a dual processor xeon e5405, but it was enough to play with it.

The parts using Qt were using the raster engine though. I've looked at the code and decided to write something that would render the same thing but using just Qt. The results were a little surprising. Qt OpenGL could render tiger.svg scaling and rotating it at about 270fps, while the NV_path_rendering was running at about 72fps. Here's both of them running side by side:

(numbers lower for both on account of them running at the same time of course). As you can see Qt is almost 4x faster. I've figured it might be related to the different SVG implementations and rendering techniques used, so I quickly hacked the demo NVIDIA posted to open a brand new window (you need to click on it to start rendering) and render to QGLPixelBuffer but using the same SVG and rendering code as their NV_path_rendering demo code. The results were basically the same.

I posted the code for the Qt demo and the patch to nvpr_svg on github: https://github.com/zackr/qt_svg

The patch is larger than it should be because it also changed the file encoding on the savedfiles from DOS to Unix but you shouldn't have any issues applying it.

So from a quick glance it doesn't seem like there are any performance benefits to using NV_path_rendering, in fact Qt would likely be quite a bit slower with it. Having said that NVIDIA's implementation looks very robust and a lot more numerically stable. I've spent a little bit of time looking at the individual pixels and came away very impressed.

In general the extension is in a little bit of a weird situation. On one hand, unlike OpenVG which creates a whole new API, it's the proper way of introducing GPU path rendering, on the other hand pretty much every vector graphics toolkit out there already implements GPU based path rendering. Obviously the implementations differ and some might profit from the extension but for Qt the question is whether that quality matters more than the performance. Specifically whether the quality improves enough to justify the performance hit.

I think the extension's success will largely depend on whether it's promoted to, at least an EXT or, ideally an ARB, meaning all the drivers support it. Using it would make the implementations of path rendering in toolkits/vector graphics libs a lot simpler and give driver developer a central place to optimize a pretty crucial part of the modern graphics stack. Unfortunately if you still need to maintain the non NV_path_rendering paths then it doesn't make a whole lot of sense.Mesa3D implementation would be trivial simply because I've already implemented path rendering for OpenVG using the Gallium3D interface, so it'd be a matter of moving that code but I'm just not sure if anyone will be actually using this extension. All in all, it's a very well done extension but it might be a little too late.

ApiTrace

2011-04-25T21:21:00.015+01:00

During the last three weeks I've spent most of my spare time writing a GUI for Jose's amazing ApiTrace project. ApiTrace is a project to trace, analyze and debug graphics api's. Both OpenGL and Direct3D. To some extend inspired by gDEBugger and Windows PIX. We wanted a tool that would let us slice through huge games and CAD apps to the exact call which causes problems and be able to inspect the entire graphics state, including the shaders, textures and all the buffers. We ended up doing that, plus a lot more and we're just getting started. In other words it's the best thing since "Human/Robot Emancipation Act of 3015".

You begin by tracing your target application. You can do that either from the console or from the GUI. A trace file is created and we can do some amazing things with it. You can open it in a GUI and

Inspect the state frame by frame, draw call by draw call:
Replay the trace file:
Check every texture:
Every bound framebuffer:
Every shader:
Every vertex buffer:
You can see if OpenGL threw an error at any point during the replay and if so what was it:
And to go completely nuts, as graphics developers like to do, you get to edit any shader, any uniform and large chunks of the state to immediately see the effects it would have on the rendering:

As a driver developer you no longer have to install all the games just to debug a problem, the report can simply include a short trace which you can use to immediately figure out what's wrong. As an application developer you can inspect every graphics call your app makes, you can analyze your api usage and you could automatically produce standalone testcases which you can send to driver developers.

ApiTrace is hosted on github and it's BSD licensed. It works on Linux and Windows (we're planning to add OSX support as well). Gui is written using Qt and requires the QJson library.

Jose just announced the first release so let us know if there's anything that would make your life a lot easier. Next is support for multiple GL contexts, ability to export just a single frame from a trace (either as a trace file or a standalone C application), ability to start and stop tracing on a hot key and lots of other features soon. So whether you're a driver developer, working on games, CAD apps or 2D scene-graphs this is a tool that should make your life significantly easier and better.

Directing Lemmings

2011-03-18T23:18:00.001Z

Phoronix just posted a link to an interview with Ryan Gordon who says

Also, I find it completely ridiculous that we're shipping open source OpenGL drivers without S3TC support because of patent concerns. Today, that's like shipping a web browser without .jpg support!

Why does so many people think that breaking the law is not only acceptable but mandatory? I don't understand why would you castigate others for following the law. Yes, every single patent is despicable, there's not one of them that's ethically valid but the solution can't be pushing someone else to be breaking the law for you.

Legally there's nothing stopping anyone from licensing s3tc or floating point patents, forking Mesa3D and shipping closed source version of it with code handling both.
It's simply that you can't reconcile Free Software with patents. You just can't add what amounts to arbitrary restrictions to your software and claim freedom. There's absolutely nothing we can do here. There were teams of lawyers looking at this stuff and the conclusion every single time was "you just can't get away with this". Jose and Brian spent a lot of time looking at ways of getting around it as well.

I don't even think we could claim that we're taking a moral stance because it's not us but the distributors who would get sued and would lose. Pushing others under the train just doesn't seem like a moral high ground. Plus all the "I'm not a lawyer but /* bad advice follows */" are just not helpful at all. It's only meaningful if you work for a company that distributes Mesa3D code and your lawyers decided that you'll fight this in court or you'll go around this using some technical quirk. Everything else is back seat driving, without even having the decency to get in the car.

2D musings

2010-11-02T14:56:00.002Z

If you've been following graphics developments in the 2D world over the last few years you've probably seen a number of blogs and articles complaining about performance. In particular about how slow 2D is on GPUs. Have you ever wondered why it's possible to make this completely smooth but your desktop still sometimes feels sluggish?

Bad model

For some weird reason ("neglect" being one of them) 2D rendering model hasn't evolved at all in the last few years. That is if it has evolved at all since the very first "draw line" became a function call. Draw line, draw rectangle, draw image, blit this, were simply joined by fill path, stroke path, few extra composition modes and such. At its very core the model remained the same though, meaning lots of calls to draw an equally large number of small primitives.

This worked well because technically zero, or almost zero, setup code was necessary to start rendering. Then GPUs became prevalent and they could do amazing things but to get them to do anything you had to upload the data and the commands that would tell them what to do. With time more and more data had to be sent to the GPU to describe the increasingly complex and larger scenes. It made sense to optimize the process of uploads (I keep calling them "uploads" but "GPU downloads" is closer to the true meaning) by allowing to upload an entire resource once and then refer to it via a handle. Buffers, shaders, addition of new shading stages (tessellation, geometry) all meant to reduce the size of data that had to be uploaded to the GPU before every rendering.

At least for games and well designed 3D software. 2D stuck to its old model of "make GPU download everything on every draw request". It worked ok because most of the user interface was static and rather boring so the performance was never much of an issue. Plus in many cases the huge setup costs are offset by the fact that the Graphics Processing Units are really good at processing graphics.

Each application is composed of multiple widgets each widget draws itself using multiple primitives (pixmaps, rectangles, lines, paths) and each primitive needs to first upload the data needed by the GPU to render it. It's like that because from the 2D api perspective there's no object persistence. The api has no idea that you keep re-rendering the same button over and over again. All the api sees is another "draw rectangle" or "draw path" call which it will complete.

On each frame the same data is being copied to the GPU over and over again. It's not very efficient, is it? There's a limited number of optimizations you can do in this model. Some of the more obvious ones include:

adding unique identifiers to the pixmaps/surfaces and using those as identifiers as keys in a texture cache which allows you to create a texture for every pixmap/surface only once,

collecting data from each draw call in a temporary buffer and copying it all at once (e.g. in SkOSWindow::afterChildren, QWindowSurface::endPaint or such),

creating a shader cache for different types of fills and composition modes

But the real problem is that you keep making the GPU download the same data every frame and unfortunately that is really hard to fix in this model.

Fixing the model

It all boils down to creating some kind of a store where lifetime of an object/model is known. This way the scene knows exactly what objects are being rendered and before rendering begins it can initialize and upload all the data the items need to be renderer. Then rendering is just that - rendering. Data transfers are limited to object addition/removal or significant changes to their properties and then further limited by the fact that a lot of the state can always be reused. Note that trivial things like changing the texture (e.g. on hover/push) don't require any additional transfers and things like translations can be limited to just two floats (translation in x and y) and they're usually shared for multiple primitives (e.g. in a pushbutton it would be used by the background texture and the label texture/glyphs)

It would seem like the addition of QGraphicsView was a good time to change the 2D model, but that wasn't really possible because people like their QPainter. No one likes when a tool they have been using for a while and are fairly familiar with is suddenly taken away. Completely changing a model required a more drastic move.

QML and scene-graph

QML fundamentally changes the way we create interfaces and it's very neat. From the api perspective it's not much different from JavaFX and one could argue which one is neater/better but QML allows us to almost completely get rid of the old 2D rendering model and that's why I love it! A side-effect of moving to QML is likely the most significant change we've done to accelerated 2D in a long time. The new Qt scene graph is a very important project that can make a huge difference to the performance, look and feel of 2D interfaces.

Give it a try. If you don't have OpenGL working, no worries it will work fine with Mesa3D on top of llvmpipe.

A nice project would be doing the same in web engines. We have all the info there but we decompose it into the draw line, draw path, draw rectangle, draw image calls. Short of the canvas object which needs the old style painters, everything is there to make accelerated web engines a lot better at rendering the content.

Intermediate representation again

2010-10-28T22:12:00.003+01:00

I wrote about intermediate representation a few times already but I've been blogging so rarely that it feels like ions ago. It's an important topic and one that is made a bit more convoluted by Gallium.

The intermediate representation (IR) we use in Gallium is called Tokenized Gallium Shader Instructions or TGSI. In general when you think about IR you think about some middle layer. In other words you have a language (e.g. C, GLSL, Python, whatever) which is being compiled into some IR which then is transformed/optimized and finally compiled into some target language (e.g. X86 assembly).

This is not how Gallium and TGSI work or were meant to work. We realized that people were making that mistake so we tried to back-paddle on the usage of the term IR when referring to TGSI and started calling it a "transport" or "shader interface" which better describes its purpose but is still pretty confusing. TGSI was simply not designed as a transformable representation. It can be done, but it's a lot like a dance-off on a geek conference - painful and embarrassing for everyone involved.

The way it was meant to work was:

Language -> TGSI ->[ GPU specific IR -> transformations -> GPU ]

with the parts in the brackets living in the driver. Why like that? Because GPUs are so different that we thought each of them would require its own transformations and would need its own IR to operate on. Because we're not compiler experts and didn't think we could design something that would work well for everyone. Finally and most importantly because it's how Direct3D does it. Direct3D functional specification is unfortunately not public which makes it a bit hard to explain.

The idea behind it was great in both its simplicity and overabundance of misplaced optimism. All graphics companies had Direct3D drivers, they all had working code that compiled from Direct3D assembly to their respective GPUs. "If TGSI will be a lot like Direct3D assembly then TGSI will work with every GPU that works on Windows, plus wouldn't it be wonderful if all those companies could basically just take that Windows code and end up with a working shader compiler for GNU/Linux?!", we thought. Logically that would be a nice thing. Sadly companies do not like to release part of their Windows driver code as Free Software, sometimes it's not even possible. Sometimes Windows and Linux teams never talk to each other. Sometimes they just don't care. Either way our lofty goal of making the IR so much easier and quicker to adopt took a pretty severe beating. It's especially disappointing since if you look at some of the documentation e.g. for AMD Intermediate Language you'll notice that this stuff is essentially Direct3D assembly which is essentially TGSI (and most of the parts that are in AMD IL and not in TGSI are parts that will be added to TGSI) . So they have this code. In the case of AMD it's even sadder because the crucial code that we need for OpenCL right now is OpenCL C -> TGSI LLVM backend which AMD already does for their IL. Some poor schmuck will have to sit down and write more/less the same code. Of course if it's going to be me it's "poor, insanely handsome and definitely not a schmuck".

So we're left with Free Software developers who don't have access to the Direct3D functional spec and who are being confused by the IR which is unlike anything they've seen (pre-declared registers, typeless...) which on top of it is not easily transformable. TGSI is very readable, simple and pretty easy to debug though so it's not all negative. It's also great if you never have to optimize or transform its structure which unfortunately is rather rare.

If we abandon the hope of having the code from Windows drivers injected in the GNU/Linux drivers it becomes pretty clear that we could do better than TGSI. Personally I just abhor the idea of rolling out our own IR. IR in the true sense of that word. Crazy as it may sound I'd really like my compiler stuff to be written by compiler experts. It's the main reason why I really like the idea of using LLVM IR as our IR.

Ultimately it's all kind of taking the "science" out of "computer science" because it's very speculative. We know AMD and NVIDIA use it to some extend (and there's an open PTX backend for LLVM) , we like it, we use it in some places (llvmpipe), the people behind LLVM are great and know their stuff but how hard is it to use LLVM IR as the main IR in a graphics framework and how hard is it to code-generate directly from it for GPUs - we don't really know. It seems like a really good idea, good enough for folks from LunarG to give it a try which I think is really what we need; a proof that it is possible and doesn't require sacrificing any farm animals. Which, as a vegetarian, I'd be firmly against.

Graphics drivers

2010-07-01T14:42:00.001+01:00

There are only two tasks harder than writing Free Software graphics drivers. One is running a successful crocodile petting zoo, the other is wireless bungee jumping.

In general writing graphics drivers is hard. The number of people who can actually do it is very small and the ones who can do it well are usually doing it full-time already. Unless the company, which those folks are working for, supports open drivers, the earliest someone can start working on open drivers is the day the hardware is officially available. That's already about 2 years too late, maybe a year if the hardware is just an incremental update. Obviously not a lot of programmers have the motivation to do that. Small subset of the already very small subset of programmers who can write drivers. Each of them worth their weight in gold (double, since they're usually pretty skinny).

Vendors who ship hardware with GNU/Linux don't see a lot of value in having open graphics drivers on those platforms. All the Android phones are a good example of that. Then again Android decided to use Skia, which right now is simply the worst of the vector graphics frameworks out there (Qt and Cairo being two other notables). Plus having to wrap every new game port (all that code is always C/C++) with NDK is a pain. So the lack of decent drivers is probably not their biggest problem.

MeeGo has a lot better graphics framework, but we're ways of before we'll see anyone shipping devices running it and Nokia in the past did "awesome" things like release GNU/Linux devices with a GPU but without any drivers for it (n800, n810) and Intel's Poulsbo/Moorestown graphics drivers woes are well-known. On the desktop side it seems that Intel folks are afraid that porting their drivers to Gallium will destabilize them. Which is certainly true, but the benefits of doing so (multiple state trackers, cleaner driver code, being able to use Gallium debugging tools like trace/replay/rbug and nicely abstracting the api code from drivers) would be well worth it and hugely beneficial to everyone.

As it stands we have an excellent framework in Gallium3D but not a lot of open drivers for it. Ironically it's our new software driver, llvmpipe, or more precisely a mutation of it, which has the potential to fix some of our GPU issues in the future. With the continues generalization of GPUs my hope is that all we'll need is DRM code (memory management, kernel modesetting, command submission) and LLVM->GPU code generator. It's not exactly a trivial amount of code by any stretch of the imagination but smaller than what we'd need right now and once it would be done for one or two GPUs it would certainly become a lot simpler. Plus GPGPU will eventually make the latter part mandatory anyway. Having that would get us a working driver right away and after that we could play with texture sampling and vertex paths (which will likely stay as dedicated units for a while) as optimizations.

Of course it would be even better if a company shipping millions of devices with GNU/Linux wanted a working graphics stack from bottom up (memory management, kernel modesetting, Gallium drivers with multiple state trackers, optimized for whatever 2D framework they use) but that would make sense. "Is that bad?" you ask. Oh, it's terrible because GNU/Linux graphics stack on all those shipped devices is apparently meant to defy logic.

No hands!

2010-06-21T14:46:00.003+01:00

I've spent the last few weeks in London with Keith Whitwell and José Fonseca, the greatest computer graphics experts since the guy who invented the crystal ball in the Lord of the Rings, the one that allowed you to see your future in full immersive 3D. Which begs the question: do you think that there was an intermediate step to those? I mean a crystal ball that showed you your future but 2D, all pixelated and in monochrome. Like Pong. You got 8x8 pixels and then the wizard/witch really needed to get their shit together to figure out what's going on, e.g.

- "This seems to be the quintessential good news/bad news kind of a scenario: good news - you'll be having sex! Bad news - with a hippo.",

- "There's no hippos in Canada...",

- "Right, right, I see how that could be a problem. How about elephants with no trunks?",

- "None of those",

- "Walls maybe?",

- "Yea, got those",

- "Excellent! Well then you'll probably walk into a one.".

Just once I'd like to see a movie where they're figuring this stuff out. If you'll shoot it, I'll write it!

Getting back on track: we've got a lot of stuff done. I've worked mainly on the Gallium interface trying to update it a bit for modern hardware and APIs.

First of all I've finally fixed geometry shaders in our software driver. The interface for geometry shader is quite simple, but the implementation is a bit involved and I've never done it properly. Until now that is. In particular emitting multiple primitives from a single geometry shader never worked properly. Adjacency primitives never worked. Drawing indexed vertex buffer with a geometry shader never worked properly and texture sampling in GS was just never implemented. All of that is fixed and looks very solid.

Second of all stream out, aka transform feedback is in. Both in terms of interface additions and software implementation. Being able to process a set of vertices and stream them out into a buffer is a very useful feature. I still enjoy vector graphics and in there processing a set of data points is a very common operation.

I've also added the concept of resources to our shader representation, TGSI. We needed a way of arbitrarily binding resources to sampler and defining load/sample formats for resources in shaders. The feature comes with a number of new instructions. The most significant in terms of their functionality are the load and gather4 instructions because they represent first GPGPU centric features we've added to Gallium (obviously both very useful in graphics algos as well).

Staying in TGSI land, we have two new register files. I've added immediate constant array and temporary arrays. Up til now we had really no way of declaring a set of temporaries or immediates as an array. We would imitate that functionality by declaring ranges e.g. "DCL TEMP[0..20]", which becomes very nasty when a shader is using multiple indexable arrays, it also makes bounds checking almost impossible.

A while back Keith wrote Graw which is a convenience state tracker that exposes the raw Gallium interface. It's a wonderful framework for testing Gallium. We have added a few tests for all the above mentioned features.

All of those things are more developer features than anything else though. They all need to be implemented in state trackers (e.g. GL) and drivers before they really go public and that's really the next step.

Geometry Processing - A love story

2010-04-27T16:11:00.004+01:00

It's still early in the year but I feel like this is the favorite for the "best computer science related blog title of 2010". I'd include 2009 in that as well, but realistically speaking I probably wrote something equally stupid last year and I don't have the kind of time required to read what I write.

Last week I've merged the new geometry processing pipeline and hooked it into our new software driver, llvmpipe. It actually went smoother than I thought it would, i.e. it just worked. I celebrated by visiting ER, a harsh reminder that my lasting fascination with martial arts will be the end of me (it will pay dividends once llvmpipe becomes self-aware though).

The codepaths are part of the Gallium3D Draw module. It's fairly simple once you get to it. At a draw call we generate the optimal vertex pipeline for the currently set state. LLVM makes this stuff a lot easier. First of all we get the human-readable LLVM IR which is a lot easier than assembly to go over if something goes wrong. Running LLVM optimization passes over a fairly significant amount of code is a lot easier than having to hand-optimize assembly code-generation. Part of it is that geometry processing is composed of a few fairly distinct phases (e.g. fetch, shade, clip, assemble, emit) and given that they all can and will change depending on the currently set state makes it difficult to code-generate optimal code by hand. That is unless you have a compiler framework like LLVM. Then you don't care and hope LLVM will bail you out in cases where you end up doing something stupid for the sake of code-simplicity.

A good example of that is our usage of alloca's for all variables. Initially all variables were in registers but I switched the code to use alloca's for a very simple reason: doing flow control in SOA mode when everything was in registers was tough, it meant keeping track of the PHI nodes. Not to mention that we had no good way of doing indirect addressing in that scheme. Using alloca's makes our code a lot simpler. In the end, thanks to LLVM optimization passes (mem2reg in this case), virtually every usage of allocas is eliminated and replaced with direct register access.

Anyway, with the new geometry paths the improvements are quite substantial. For vertex processing dominated tests (like geartrain which went from 35fps to 110fps) the improvements are between 2x to about 6x, for cases which are dominated by fragment processing it's obviously a lot less (e.g. openarena went from about 25fps to about 32fps). All in all llvmpipe is looking real good.

The software renderer

2010-03-11T15:19:00.005Z

There's a number of great software renderers out there. SwiftShader and DirectX WARP being the two widely known ones. Unfortunately GNU/Linux, and Free Software in general, didn't have a modern software renderer. That's about to change thanks to a project started by José Fonseca. The project is known as the llvmpipe (obviously a development name). José decided that the way forward is writing a driver for Gallium which would code-generate at run-time the rendering paths from the currently set state. LLVM is used to code-generate and optimize the code.

Besides the idea itself, my favorite part of the driver is the software rasterizer. Keith Whitwell, Brian Paul and José implemented a threaded, tiled rasterizer which performs very nicely and scales pretty well with the number of cores. I'm sure one of them will write more about it when they'll have a bit of spare time.

Currently the entire fragment pipeline is code-generated. Over the last two weeks I've been implementing the vertex pipeline, which I'm hoping to merge soon (hence the light smile). Code generating the entire vertex pipeline isn't exactly trivial, but one can divide it into individual pieces and that makes it a bit easier. Start with the vertex shader, then go back and do the fetch and translate, then again move forward and do the emit, then go back and do the viewport transformations and clipping and so on, finally combine all the pieces together.

In between working on the vertex pipeline I've been filling in some missing pieces in the shader compilation. In particular the control-flow. We use the SOA layout which always make control flow a bit tricky. I've just committed support for loops and the only thing left is support for subroutines in shaders so I think we're in a pretty good shape. We can't rock the speedos quite yet, but we're getting there. It's my new measurment for software quality - could it pull off the speedos look? There's few things on this world that can.

Keeping in mind that we haven't even started optimizing it yet, as we're still implementing features, the driver, on my Xeon E5405 runs the anholt.dm_68 OpenArena demo at 25fps (albeit with some artifacts) which is quite frankly pretty impressive, especially if you compare it to the old Mesa3D software renderer that runs the same demo, on the same machine at 3.5 fps.

3D APIs

2010-02-10T16:42:00.002Z

Do you know where babies come from? It's kinda disturbing, isn't it? I blame it on the global warming. Stay with me here and I'll lead you through this. 1) Storks deliver babies (fact), 2) I, not being very careful about how I word things cause global warming (also a fact), 3) global warming kills storks (my theory) 4) evolution takes over and replaces storks with the undignified system that we have right now (conclusion).

Speaking about not being very careful about how I word things, how about me announcing those DirectX state trackers coming to GNU/Linux in my last blog, eh? By the way, now that's a good transition. The announcement was very exciting, albeit a little confusing, in particular to myself. Likely because it's really not what I meant. Mea culpa!

What I was talking about is adding features to the Gallium interfaces that will allow us to support those API's, not about actually releasing any of those API's as state trackers for Gallium. Gallium abstracts communication with the hardware and the support for OpenGL 3.2 + few extensions and Direct3D 10.x requires essentially the same new interfaces in Gallium. So support for Direct3D 10.x means that we can support OpenGL 3.2 + those extra extensions. I don't think that it's a big secret that while we do have and are shipping Direct3D 9 state tracker and are working on a Direct3D 10 state tracker, to my knowledge, we simply don't have any plans to release that code. It's Windows specific anyway, so it wouldn't help the Free Software community in any shape or form.

I know there's that misguided belief that a Direct3D state tracker would all of a sudden mean that all Windows games work on GNU/Linux. That's just not true, there's a lot more to an API than "draw those vertices and shade it like that", windowing system integration, file io, networking, input devices, etc. If software is DirectX specific then it's pretty clear that the authors didn't use X11 and Posix apis to implement all that other functionality. Those windows.h/windowsx.h includes are pretty prominent in all of those titles. So one would have to wrap entire Windows API to be able to play DirectX games. That's what Wine is about and they're better off using OpenGL like they are now.

The issue with gaming on GNU/Linux isn't the lack of any particular API, it's the small gaming market. If an IHV would release a device that 500 million people would buy and the only programming language supported would be COBOL and the only 3D API would be PHIGS then we would see lots of games in COBOL using PHIGS. Sure, the developers wouldn't like it, but the brand new Ferraris that the company could buy, after release of their first title, for everyone, including all the janitors, would make up for that.

The bottom line is that the majority of games could easily be ported to GNU/Linux since the engines usually are cross-platform anyway, at the very least to support different consoles. DirectX, libgcm, OpenGL ES... either they're all already supported or could be easily made to support them. It's simply that it's not cost-effective to do so. A good example is Palm Pre which is running GNU/Linux and even before the official release of their 3D SDK (PDK) which uses SDL they already got EA Mobile to port Need for Speed, The Sims and others to their device.

On the other hand if a title supports only DirectX or only libgcm it's usually because it's exclusive to the given platform and presence of the same API on other platforms will not make the vendor suddenly release the title for the new system.

So yea, Direct3D on GNU/Linux simply means nothing. We won't get more games, won't make it easier to port the already cross platform engines, won't allow porting of the exclusive titles and will not fill any holes in our gaming SDKs. Besides ethically speaking we should support OpenGL, not a closed API from a closed platform.

New features

2010-02-08T14:55:00.003Z

Lately we've been working a lot on Gallium but we haven't been publicly talking about it enough. I, personally, spent a considerable amount of time last week coming up with my strategy for the inevitable monster invasion. In general I always thought that if, sorry, "when" the monsters attack I'd be one of the very first ones to go on account of my "there's a weird noise coming from that pitch black spot over there, I better check it out" tendency. Obviously that's not ideal, especially if the need to repopulate the world arises; I just really feel like I should be present for that. In conclusion I'll quickly go over some things we've been doing with Gallium. Admittedly that wasn't one of my best transitions.

There are three new major APIs that we want to support in Gallium. OpenCL 1.0, DirectX 10.x and DirectX 11. DirectX 10.x was somewhat prioritized of late because it's a good stepping stone for a lot of the features that we wanted.

Two of my favorites were the geometry shaders and new blending functionality. I want to start with the latter which Roland worked on because it has immediate impact on Free Software graphics.

One of the things that drives people bonkers is text rendering. In particular subpixel rendering, or if you're dealing with Xrender component alpha rendering

Historically both GL and D3D provided fixed-function blending that provided means of combining source colors with the content of a render buffer in a number of ways. Unfortunately the inputs to the blending units were constrained to a source color, destination color or constants that could be used in their place. That was unfortunate because the component alpha math required two distinct values: the source color and the blending factor for destination colors (assuming the typical Porter&Duff over rendering). D3D 10 dealt with it by adding functionality called dual-source blending (OpenGL will get an extension for it sometime soon). The idea being that the fragment shader may output two distinct colors which will be treated as two independent inputs to the blending units.

Thanks to this we can support subpixel rendering in a single pass with a plethora of compositing operators. Whether you're a green ooze trying to conquer Earth or a boring human you have to appreciate 2x faster text rendering.

Geometry shaders introduce a new shader type, run after the vertices have been transformed (after the vertex shader), but before color clamping, flat shading and clipping.

Along the support for geometry shaders we have added two major features to TGSI ("Tokenized Gallium Shader Instructions", our low level graphics language).

The first one was support for properties. Geometry shaders in Gallium introduced the notion of state aware compile. This is because compilation of a geometry shader is specific to, at the very least, the input and output primitive they respectively operate on and output. We deal with it by injecting PROPERTY instructions to the program as so:

GEOM
PROPERTY GS_INPUT_PRIMITIVE TRIANGLES
PROPERTY GS_OUTPUT_PRIMITIVE TRIANGLE_STRIP

(rest of geometry shader follows)

The properties are easily extendable and are the perfect framework to support things like work-group size in OpenCL.

The second feature is support for multidimensional inputs in shaders. The syntax looks as follows:

DCL IN[][0], POSITION

DCL IN[][1], COLOR

which declares two input arrays. Note that the size of the arrays is implicit, defined by the GS_INPUT_PRIMITIVE property.

It's nice to see this framework progressing so quickly.

Summing up, this is what yin yang is all about. Do you know what yin yang is? Of course you don't, you know nothing of taoism. Technically neither do I but a) it sounds cool, b) I've been busy coming up with a "monster invasion" contingency plan, so couldn't be bothered with some hippy concepts, c) the previous two points are excellent.

Languages and vGPU

2009-11-30T21:30:00.003Z

Now that, despite all the protein supplements, I've lost weight again and got myself a beard (grew not bought) I feel like I really nailed the homeless pirate look.

In the spirit of camaraderie I spent a few minutes yesterday fixing one of the longest bugs we had in KDE which was the inability to spell check Indic, Middle Eastern, Asian and a few other languages. The issue was that the text segmentation algorithm, due to my uncanny optimism, was defining words as "things that are composed of letters". That isn't even true for English (e.g. "doesn't" is a word that's composed of more than just letters and breaking it up at the non-letter produces two non-words) and it was utterly and completely wrong for pretty much every language that wasn't using a Latin like alphabet. I switched the entire codebase to use the unicode text boundary specification, tr29-11 as implemented in the QTextBoundaryFinder and it's fixed now.

In other knews we've released the Gallium3D driver for VMware's vGPU (right now called svga, but we'll rename it as soon as we'll have some time). It means that we can accelerate all the APIs supported by Gallium in the virtual machine which is fairly impressive.

Accelerating X with Gallium

2009-09-01T20:56:00.004+01:00

Spring is coming. I'm certain of it because I know for a fact that it's not Spring right now and seasons have a tendency to wrap around. Obviously that means I need to work a bit on the acceleration code for X11. It's just like going to a doctor, sure, it sucks, but at the back of your mind you know you need to do it.

So what's different about this code? Well, it's not an acceleration architecture. We're reusing Exa. It's the implementation.

Currently if you want to accelerate X11, or more precisely Xrender, you implement some acceleration architecture in your X11 driver. It may be Exa, Uxa, Xaa or something else (surely also with an X and A in the name because that seems to be a requirement here). Xrender is a bit too complicated for any 2D engine out there, which means that any code which accelerates Xrender will use the same paths OpenGL acceleration does. In turn this means that if we had an interface which exposed how hardware works we could put OpenGL and Xrender acceleration on top of the same driver. One driver, accelerating multiple APIs.

That's exactly what Gallium is all about so it shouldn't be a big surprise that this is what we're doing. We're simply writing an Xorg state tracker for Gallium in which Exa is implemented through the Gallium interface.

So with a Gallium driver, besides OpenGL, OpenGL ES and OpenVG you'll get X11 acceleration. I'm specifically saying here X11 because after implementing Exa we'll move to accelerating Xv, which will give us a nice set of ops which are accelerated in a typical X application.

More 2D in KDE

2009-08-14T19:04:00.003+01:00

An interesting question is: if the raster engine is faster at gross majority of graphics and Qt X11 engine falls back on quite a few features anyway why shouldn't we make raster the default until OpenGL implementations/engine are stable enough.

There are two technical reasons for that. Actually that's not quite true, there's more but these two are the ones that will bother a lot of people.

The first is that we'd kill KDE performance over network. So everyone who uses X/KDE over network would suddenly realize that their setup became unusable. Their sessions would suddenly send images for absolutely everything all the time... As you can imagine institutions/schools/companies who use KDE exactly in this way wouldn't be particularly impressed if suddenly updating their installations would render them unusable.

The second reason is that I kinda like being able to read and sometimes even write text. Text tends to be pretty helpful during the process of reading. Especially things like emails and web browsing get a lot easier with text. I think a lot of people shares that opinion with me. To render text we need fonts, in turn those are composed of glyphs. To make text rendering efficient, we need to cache the glyphs. When running with the X11 engine we render the text using Xrender, which means that there's a central process that can technically manage all the glyphs used by applications running on a desktop. That process is the Xserver. With the raster engine we take Xserver out of the equation and suddenly every single application on the desktop needs to cache the glyphs for all the fonts they're using. This implies that every application suddenly uses megs and megs of extra memory. They all need to individually cache all the glyphs even if all of them use the same font. It tends to work ok for languages with a few glyphs e.g. 40+ for english (26 letters + 10 digits + a few punctuation marks). It doesn't work at all for languages with more. So unless it will be decided that KDE can only be used by people with languages whose alphabets contain about 30 letters or less, then I'd hold off with making raster engine the default.

While the latter problem could be solved with some clever shared memory usage or forcing Xrender on top of raster engine (actually I shouldn't state that as a fact, I haven't looked at font rendering in raster engine in a while and maybe that was implemented lately), it's worth noting that X11 engine is simply fast enough to not bother over a few frames in this way or another. Those few frames that you'd gain would mean unusable KDE for others.

And if you think that neither of the above two points bothers you and you'd still want to use raster engine by default you'll have to understand that I just won't post instructions on how to do that here. If you're a developer, you already know how to do it and if not there are trivial ways of finding that out from the Qt sources. If you're not a developer then you really should stick globally to the defaults and can simply test the applications with the -graphicssystem switches.

2D in KDE

2009-08-14T01:21:00.007+01:00

So it seems a lot of people is wondering about this. By this I mean why dwarfs always have beards. Underground big ears would be probably a better evolutionary trait, but elfs got dibs on those.

Qt, and therefore KDE, deals with 3 predominant ways of rendering graphics. I don't feel like bothering with transitions today, so find your own way from beards and dwarfs to Qt/KDE graphics. Those three ways are:

On the CPU with no help from the GPU using the raster engine
Using X11/Xrender with the X11 engine
Using OpenGL with the OpenGL engine

There's a couple of ways in which the decision about which one of those engines is being used is made.

First there's the default global engine. This is what you get when you open a QPainter on a QWidget and its derivatives. So whenever you have code like


void MyWidget::paintEvent(QPaintEvent *)
{
 QPainter p(this);
 ...
}

you know the default engine is being used. The rules for that are as follows:

GNU/Linux : X11 engine is being used
Windows : Raster engine is being used
Application has been started with -graphicssystem= option :
- -graphicssystem=native the rules above apply
- -graphicssystem=raster the raster engine is being used by default
- -graphicssystem=opengl the OpenGL engine is being used by default

Furthermore depending on which QPaintDevice is being used, different engines will be selected. The rules for that are as follows:

QWidget the default engine is being used (picked as described above)
QPixmap the default engine is being used (picked as described above)
QImage the raster engine is being used (always, it doesn't matter what engine has been selected as the default)
QGLWidget, QGLFramebufferObject, QGLPixelBuffer the OpenGL engine is being used (always, it doesn't matter what engine has been selected as the default)

Now here's where things get tricky: if the engine doesn't support certain features it will have to fallback to one engine that is sure to work on all platforms and have all the features required by the QPainter api - that is the raster engine. This was done to assure that all engines have the same feature set.

While OpenGL engine should in general never fallback, that is not the case for X11 and there are fallbacks. One of the biggest immediate optimizations you can do to make your application run faster is to assure that you don't have fallbacks. A good way to check for that is to export QT_PAINT_FALLBACK_OVERLAY and run your application against a debug build of Qt, this way the region which caused a fallback will be highlighted (the other method is to gdb break in QPainter::draw_helper). Unfortunately this will only detect fallbacks in Qt.

All of those engines also use drastically different methods of rendering primitives.
The raster engine rasterizes primitives directly.
The X11 engine tessellates primitives into trapezoids, that's because Xrender composites trapezoids.
The GL engine either uses the stencil method (described in this blog a long time ago) or shaders to decompose the primitives and the rest is handled by the normal GL rasterization rules.

Tessellation is a fairly complicated process (also described a long ago in this blog). To handle degenerate cases the first step of this algorithm is to find intersections of the primitive. In the simplest form think about rendering figure 8. There's no way of testing whether the given primitive is self-intersecting without actually running the algorithm.
To render with anti-aliasing on the X11 engine we have to tessellate. We have to tessellate because Xrender requires trapezoids to render anti-aliased primitives. So if the X11 engine is being used and the rendering is anti-aliased whether you're rendering a line, heart or a moose we have to tessellate.

Someone was worried that it's a O(n^2) process which is of course completely incorrect. We're not using a brute force algorithm here. The process is obviously O(nlogn). O(nlogn) complexity on the cpu side is something that both the raster and X11 engines need to deal with. The question is what happens next and what happens in the subsequent calls.

While the raster engine can deal with all of it while rasterizing, the X11 engine can't. It has to tessellate, send the results to the server and hope for the best. If the X11 driver doesn't implement composition of trapezoids (which realistically speaking most of them doesn't) this operation is done by Pixman. In the raster engine the sheer spatial locality almost forces better cache utilization than what could be realistically achieved by the "application tessellate->server rasterization" process that the X11 engine has to deal with. So without all out acceleration in this case X11 engine can't compete with the raster engine. While simplifying a lot it's worth remembering that in terms of cycles register access is most likely smaller or equal to 1 cycle, access to L1 data cache is likely about 3 cycles, L2 is probably about 14 cycles, while the main memory is about 240 cycles. So for CPU based graphics efficient memory utilization is one of the most crucial undertakings.

With that in mind, this is also the reason why a heavily optimized purely software based OpenGL implementation would be a lot faster than raster engine is at 2D graphics. In terms of memory usage OpenGL pipeline is simply a lot better at handling memory than the API QPainter provides.

So what you should take away from this is that if you're living in the perfect world, the GL engine is so much better than absolutely anything else Qt/KDE have it's not even funny, X11 follows it and the raster engine trails far behind.

The reality with which you're dealing with is that when using the X11 engine, due to the fallback you will be also using the raster engine (either on the application side with Qt raster engine or the server side with Pixman) and unfortunately in this case "the more the better" doesn't apply and you will suffer tremendously. Our X11 drivers don't accelerate chunks of Xrender, the applications don't have good means of testing what is accelerated, so what Qt does is simply doesn't use many of its features. So even if the driver would accelerate for example gradient fills and source picture transformations it wouldn't help you because Qt simply doesn't use them and always falls back to the raster engine. It's a bit of a chicken and an egg problem - Qt doesn't use it because it's slow, it's slow because no one uses it.

The best solution to that conundrum is to try running your applications with -graphicssystem=opengl and report any problems you see to both Qt software and the Mesa3D/DRI bugzillas because the only way out is to make sure that both our OpenGL implementations and OpenGL usage in the rendering code on the applications side are working efficiently and correctly. The quicker we get the rendering stack to work on top of OpenGL the better off we'll be.

OpenGL ES

2009-05-15T23:10:00.003+01:00

Two facts, one you didn't need to know, other that you should know. I'm the World Champion in being Vegetarian. Did you know that? Of course not, you probably didn't even know it's a competition. But it is. And I won it. My favorite vegetable? Nachos.
Technically they're a fourth of a fifth generation vegetable. But vegetables are like software, you never want to work with them on the first iteration. Like you wouldn't want to eat corn, but mash it, broil/fry it and you got something magical going on in the form of tortilla chips.

The other fact: OpenGL ES state trackers for Gallium just went public. That includes both OpenGL ES 1.x and 2.x. Brian just pushed them into opengl-es branch. Together with OpenVG they should be part of the Mesa3D 7.6 release.

At this point Mesa3D almost becomes the Khronos SDK and hopefully soon we'll add an OpenCL state tracker and start working on bumping the OpenGL code to version 3.1.

OpenVG Release

2009-05-10T02:10:00.004+01:00

I've been procrastinating lately. Where I define procrastination as: doing actual work, instead of writing blog entries. "Can you do that? Redefine words because you feel like it?", oh, sure you can. As long as you don't care about anyone understanding what you're saying, then it's perfectly fine. In fact it's good for you, the less people understands you, the more likely it is that they'll classify you as a genius. Life is awesome like that. That's right, you come here for technical stuff and get blessed with some serious soul searching stuff, enjoy.

We have released the OpenVG state tracker for Gallium.

It's a complete implementation of OpenVG 1.0. While my opinion on 2D graphics and long term usefulness of OpenVG changed drastically during the last year I'm very happy we were able to release the code. After the Mesa3D 7.5 we're going to merge it into master and 7.6 will be the first release that includes both OpenGL and OpenVG.

[You're exuberant about that]. I figured I'll start including stage directions for the blog so that you know how you feel about reading this.

I don't have much to write about the implementation itself. If you have a Gallium driver, then you're good to go and have accelerated 2d and 3d. It's great to see more state trackers being released for Gallium and this whole concept of "accelerating multiple APIs" on top of one driver architecture becoming a reality. [You love it and with a smile, wave bye]

Intermediate representation

2009-03-23T02:01:00.002Z

I've spent the last two weeks working from our office in London. The office is right behind Tate Modern with a great view of London which is really nice. While there I was mainly trying to get the compilation of shaders rock solid for one of our drivers.

In Gallium3D currently we're using TGSI intermediate representation. It's a fairly neat representation with instruction semantics matching those from relevant GL extensions/specs. If you're familiar with D3D you know that there are subtle differences between seemingly similar instructions in both APIs. Modern hardware tends to follow the D3D semantics more closely than the GL ones.

Some of the differences include:

Indirect addressing offsets, in GL offsets are between -64 to +63, while D3D wants them >= 0.
Output to temporaries. In D3D certain instructions can only output to temporary registers while TGSI doesn't have that requirement.
Branching. D3D has both if_comp and setp instructions which can perform essentially any of the comparisons, while we immitate them with a SLT (set on less than) or similar with a IF instruction with semantics of the one in GL_NV_fragment_program2.
Looping.

None of this is particularly difficult but we had to implement almost exactly the same code in another driver of ours and that makes me a little uneasy. There's a number of ways to fix this. We could change the semantics of TGSI to match D3D, or we could implement transformation passes that operate on TGSI and do this transformation directly on the IR before it gets to the driver, or we could radically change the IR. Strangely enough it's the solution number #3, which while appearing the most bizzare, is the one I like the most. It's because it goes hand in hand with the usage of LLVM inside Gallium.

Especially because there's a lot generic transformations that really should be done on the IR itself. A good example of that includes code injections due to missing pieces of the API state on a given GPU, e.g. shadow texturing, including the compare mode, compare function and the shadow ambient value, which if the samplers on the given piece of hardware don't support need to be emulated with code injections after each sampling operation which utilizes the sampler that had the above mentioned state set on it.

Unfortunately right now the LLVM code in Gallium is far from finished. Due to looming deadlines on various projects I never got to spend the amount of time that is required to get in shape.
I'll be able to piggy back some of the LLVM work on top of the OpenCL state tracker code which is exciting.

Also, has anyone noticed that the last two blogs had no asides or any humor in them? I'm experimenting with "just what I want to say and nothing more" style of writing, wondering if it indeed, will be easier to read.

KDE graphics benchmarks

2009-03-12T14:14:00.002Z

This is really a public service announcement. KDE folks please stop writing "graphics benchmarks". It's especially pointless if you quantify your blog/article with "I'm not a graphics person but...".

What you're doing is:


   timer start
   issue some draw calls
   timer stop

This is completely and utterly wrong.
I'll give you an analogy that should make it a lot easier to understand. Lets say you have a 1MB and a 100MB lan and you want to write a benchmark to compare how fast you can download a 1GB file on both of those, so you do:


   timer start
   start download of a huge file
   timer stop

Do you see the problem? Obviously the file hasn't been downloaded by the time you stopped the timer. What you effectively measured is the speed at which you can execute function calls.
And yes, while your original suspicion that the 100MB line is a lot faster is still likely true, your test in no way proves that. In fact it does nothing short of making some poor individuals very sad due to the state of computer science. Also "So what that the test is wrong, it still feels faster" is not a valid excuse, because the whole point is that the test is wrong.

To give your tests some substance always make your applications run for at least a few seconds reporting the frames per second.

Or even better don't write them. Somewhere out there, some people, who actually know what's going on, have those tests written. And those people, who just happen to be "graphics people" have reasons for making certain things default. So while you may think you've made this incredible discovery, you really haven't. There's a kde-graphics mailing list where you can pose graphics question.
So to the next person who wants to write a KDE graphics related blog/article please, please go through kde-graphics mailing list first.

Video and other APIs

2009-02-09T01:31:00.002Z

I read today a short article about video acceleration in X. First of all I was already unhappy because I had to read. Personally I think all the news sites should come in a comic form. With as few captions as possible. Just like Perl I'm a write-only entity. Then I read that Gallium isn't an option when it comes to video acceleration because it exposes programmable pipeline and I got dizzy.

So I got off the carousel and I thought to myself: "Well, that's wrong", and apparently no one else got that. Clearly the whole "we're connected" thing is a lie because it doesn't matter how vividly I think about stuff, others still don't see what's in my head (although to the person who sent me cheese when I was in Norway - that was extremely well done). So cumbersome as it might be I'm doing the whole "writing my thoughts down" thing. Look at me! I'm writing! No hands! sdsdfewwwfr vnjbnhm nhn. Hands back on.

I think the confusion stems from the fact that the main interface in Gallium is the context interface, which does in fact model the programmable pipeline. Because of the incredibly flexible nature of the programmable pipeline a huge set of APIs is covered just by reusing the context interface. But in modern GPUs there are still some fixed function parts that are not easily addressable by the programmable pipeline interface. Video is a great example of that. To a lesser degree so is basic 2D acceleration (lesser because some of the modern GPUs don't have 2D engines at all anymore).

But, and it's a big but ("and I can not lie" <- song reference, pointing out to let everyone know that I'm all about music) nothing stops us from adding interfaces which deal exclusively with the fixed function parts of modern GPUs. In fact it has already been done as the work on a simple 2D interface has already started.

Basic idea is that the state trackers which need some specific functionality use the given interface. For example the Exa state tracker would use the Gallium 2d interface, instead of the main context interface. In this case the Gallium hardware driver will have a choice: it can either implement the given interface directly in hardware, or it can use the default implementation.

The default implementation is something Gallium will provide as part of the auxiliary libraries. The default implementation will use the main context interface to emulate the entire functionality of the other interface.

Video decoding framework would use the same semantics. So it would be an additional interface(s) with default implementation on top of the 3D pipeline. Obviously some parts of the video support are quite difficult to implement on top of the 3D pipeline but the whole point of this is that: for hardware that supports it you get the whole shabangabang, for hardware that doesn't you get a reasonable fallback. Plus in the latter case the driver authors don't have to write a single line of hardware specific code.

So a very nice project for someone would be to take VDPAU, VA-API or any video framework of your choice and implement a state tracker for that API on top of Gallium and design an interface(s) that could be added to Gallium to implement the API in a way that makes full usage of the fixed functionality video units found in the GPUs. I think this is the way our XvMC state tracker is heading.
This is the moment where we break into a song.

Latest changes

2009-02-04T06:06:00.001Z

I actually went through all my blog entries and removed spam. That means that you won't be able to find anymore links to stuff that can enlarge your penis. I hope this action will not shatter your lives and you'll find consolation in all the spam that you're getting via email anyway. And if not I saved some of the links. You never know, I say.
I also changed the template, I'd slap something ninja related on it, but I don't have anything that fits. Besides nowadays everyone is a graphics ninja. I'm counting hours until the term will be added to the dictionary. So my new nickname will be "The Lost Son of Norway, Duke of Poland and King of England". Aim high is my motto.

As a proud owner of exactly zero babies I got lots of time to think about stuff. Mostly about squirrels, goats and the letter q. So I wanted to talk about some of the things I've been thinking about lately.

Our friend ("our" as in the KDE communities, if you're not a part of it, then obviously not your friend, in fact he told me he doesn't like you at all) Ignacio Castaño has a very nice blog entry about 10 things one might do with tessellation.
The graphics pipeline continues evolving and while reading Ignacio's entry I realized that we haven't been that good about communicating the evolution of Gallium3D.
So here we go.

I've been slowly working towards support for geometry shaders in Gallium3D. Interface wise the changes are quite trivial, but a little bigger issue is that some (quite modern) hardware, while perfectly capable of emitting geometry in the pipeline is not quite capable of actually supporting all of the features of geometry shader extension. The question of how to handle that is an interesting one, because just simple emission of geometry via a shader is a very desirable feature (for example path rendering in OpenVG would profit from that).

I've been doing some small API cleanups lately. Jose made some great changes to the concept of surfaces, which became pure views on textures. As a follow up, over the last few days we have disassociated buffers from them, to make it really explicit. It gives drivers the opportunity to optimize a few things and with some changes Michel is working on avoid some redundant copies.

A lot of work went into winsys. Winsys, which is a little misnomer, was a part of Gallium that did too much. It was supposed to be a resource manager, handle command submission and handle integration with windowing systems and OS'es. We've been slowly chopping parts of it away. Making it a lot smaller and over the weekend managed to hide it completely from the state tracker side.

Keith extracted the Xlib and DRI code from winsys and put it into separate state trackers. Meaning that just like WGL state tracker, the code is actually sharable between all the drivers. That is great news.

Brian has been fixing and implementing so many bugs/features that people should start writing folk songs about him. Just the fact that we now support GL_ARB_framebuffer_object deserves at least a poem (not a big one, but certainly none of that white, non-rhyming stuff, we're talking full fledged rhymes and everything... You can tell that I know a lot about poetry can't you)

One thing that never got a lot of attention is that Thomas (who did get one of them baby thingies lately) released his window systems buffer manager code.

Another thing that didn't get a lot of attention is Alan's xf86-video-modesetting driver. It's a dummy X11 driver that uses DRM for modesetting and Gallium3D for graphics acceleration. Because of that it's hardware independent, meaning that all hardware that has a DRM driver and Gallium3D driver automatically works and is accelerated under X11. Very neat stuff.

Alright, I feel like I'm cutting into your youtube/facebook time and like all "Lost Sons of Norway, Dukes of Poland and Kings of England" I know my place, so that's it.

OpenCL

2009-02-01T22:45:00.001Z

I missed you so much. Yes, you. No, not you. You. I couldn't blog for a while and I ask you (no, not you) what's the point of living if one can't blog? Sure, there's the world outside of computers, but it's a scary place filled with people that, god forbid, might try interacting with you. Who needs that? It turns out that I do. I've spent the last week in Portland on the OpenCL working group meeting which was a part of the Khronos F2F.

For those who don't know (oh, you poor souls) OpenCL is what could be described as "the shit". That's the official spelling but substituting the word "the" for "da" is considered perfectly legal. Longer description includes the expansion of the term OpenCL to "Open Computing Language" with an accompanying wikipedia entry. OpenCL has all the ingredients, including the word "Open" right in the name, to make it one of the most important technologies of the coming years.

OpenCL allows us to tap into the tremendous power of modern GPUs. Not only that but also one can use OpenCL with accelerators (like the physics chips or Cell SPU's) and CPUs. On top of that hardware OpenCL provides both task-based and data-based parallelism making it a fascinating options for those who want to accelerate their code. For example if you have a canvas (Qt graphicsview) and you spend a lot of time doing collision detection, or if you have image manipulation application (Krita) and you spend a lot of time in effects and general image manipulation, or if you have a scientific chemistry application with an equation solver (Kalzium) and want to make it all faster, or if you have wonky hair and like to dance polka... OK, the last one is a little a fuzzy but you get the point.

Make no mistake, OpenCL is little bit more complicated than just "write your algorithm in C". Albeit well hidden, the graphics pipeline is still at the forefront of the design, so there are some limitations (remember that for a number of really good and few inconvenient reasons GPUs do their own memory management so you can not just move data structures between main and graphics memory). It's one of the reasons that you won't see a GCC based OpenCL implementation any time soon. OpenCL requires run time execution, it allows sharing of buffers with OpenGL (e.g. OpenCL image data type can be constructed from GL textures or renderbuffers) and it forces code generation to a number of different targets (GPUs, CPUs, accelerators). All those things need to be integrated. For sharing of buffers between OpenGL and OpenCL the two APIs need to go through some kind of a common framework - be it a real library or some utility code that exposes addresses and their meaning to both OpenGL and OpenCL implementations.

Fortunately we already have that layer. Gallium3D maps perfectly to the buffer and command management in OpenCL. Which shouldn't be surprising given that they both care about the graphics pipeline. So all we need is a new state tracker with some compiler framework integrated to parse and code generate from the OpenCL C language. LLVM is the obvious choice here because unlike GCC, LLVM has libraries that we can use for both (to be more specific it's Clang and LLVM). So yes, we started on an OpenCL state tracker, but of course we are far, far away from actual conformance. Being part of a large company means that we have to go through extensive legal reviews before releasing something in the open so right now we're patiently waiting.
My hope is that once the state tracker is public the work will continue at a lot faster pace. I'd love to see our implementation pass conformance with at least one GPU driver by summer (which is /hard/ but definitely not impossible).

SVG in KDE

2008-08-28T18:28:00.002+01:00

"Commitment" is one of the words that have never been used in this blog. Which is pretty impressive given that I've managed to use such words as sheep, llamas, raspberries, ninjas, donkeys, crack or woodchuck quite extensively (especially impressive in a technology centric blog).

That's because commitment implies that whatever it is one is committed to plays an important role in their life. It's a word that goes beyond the paper or the medium on which it was written. It enters the cold reality that surrounds us.

But today is all about commitment. It's about commitment that KDE made to a technology broadly refereed to as Scalable Vector Graphics. I took some time off this week and came to Germany where I talked about usage of SVG in KDE.

The paper about, what I like to call, the Freedom of Beauty, is available here:

https://www.svgopen.org/2008/papers/104-SVG_in_KDE/

It talks about the history of SVG in KDE, the rendering model used by KDE, it lists ways in which we use SVG and finally shows some problems which have been exposed by such diverse usage of SVG in a desktop environment. Please read it if you're interested in KDE or SVG.

Hopefully this paper marks a start of a more proactive role KDE is going to be playing in shaping of the SVG standard.

Fixes in Sonnet

2008-08-26T05:33:00.002+01:00

As we all know inner beauty is the most important kind of beauty. Especially if you're ugly. Not ugly, don't sue me, I meant to say "easy on the eyes challenged". That's one of the reasons I like working on frameworks and libraries. It's the appeal of improving the inner beauty of certain things. I gave up on trying to improve the inner beauty of myself (when I was about 1) so this is the most I can do.

You can do it too. It's real easy. I took this week off because I'm going to Germany for SVG Open where I'll talk about SVG in KDE and today fixed a few irritating bugs in Sonnet.

One of the things that bugged me for a while was the fact that we kept marking misspelled text as red instead of using the God given red squiggly underline. Well, I say no more!
Our spelling dialog lists available dictionaries now and one can change them on the fly. That's good. Raspberries good. And raspberries are pretty darn good. Even sheep like raspberries. Or so I think, the only sheep I've ever seen was from a window of a car and it looked like an animal who enjoys raspberries. Who doesn't? The only problem was that it liked listing things like "en_GB-ise" or "en_GB-ize-w_accents" as language names which is really like a nasty bug in the raspberry. And what do you with bugs? I'm not quite certain myself but given the way this blog is heading it's surely something disturbing... Anywho. that's also fixed. Now we list proper and readable names. As in:

Working on Sonnet is a lot of fun. A small change in a pretty small library affects the entire KDE which is rather rewarding. So if you wanted to get into KDE development in an easy and fun way go to https://bugs.kde.org search for "kspell" or "sonnet" pick an entry and simply fix it!

Fast graphics

2008-08-20T16:39:00.007+01:00

Instead of highly popular pictures of llamas today I'll post a few numbers. Not related to llamas at all. Zero llamas. These will be Qt/KDE related numbers. And there's no llamas in KDE. There's a dragon, but he doesn't hang around with llamas at all. I know what you're thinking: KDE is a multi-coltural project surely someone must be chilling with llamas. I said it before and I'll say it again, what an avarage KDE developer, two llamas, one hamster and five chickens do in a privacy of their own home is none of your business.

Lets take a simple application, called qgears2, based on David Reveman cairogears and see how it performs with different rendering backends. Pay attention to zero relation to llamas or any other animals. The application takes a few options, -image: to render using a CPU based raster engine, -render: to render using X11's Xrender and -gl to render using OpenGL (-llama option is not accepted). It has three basic tests, "GEARSFANCY" which renders a few basic paths with a linear gradient alpha blended on top, TEXT that tests some very simple text rendering and COMPO which is just compostion and scaling of images.

The numbers come from two different machines. One is my laptop which is running Xorg server version 1.4.2. Exa is 2.2.0. Intel driver 2.3.2. GPU is 965GM, CPU is T8300 at 2.4GHz running on Debian Unstable's kernel 2.6.26-1.
The second machine is running GeForce 6600 (NV43 rev a2), NVIDIA proprietary driver version G01-173.14.09, Xorg version 7.3, kernel 2.6.25.11, CPU is Q6600 @ 2.40GHz (thanks to Kevin Ottens for those numbers, as I don't have NVIDIA machine at the moment).

The results for each test are as follows:

GEARSFANCY
	I965	NVIDIA
Xrender	35.37	44.743
Raster	63.41	41.999
OpenGL	131.41	156.250

TEXT
	I965	NVIDIA
Xrender	13.389	40.683
Raster	(incorrect results)	(incorrect results)
OpenGL	36.496	202.840

COMPO
	I965	NVIDIA
Xrender	67.751	66.313
Raster	81.833	70.472
OpenGL	411.523	436.681

COMPO test isn't really fair because as I mentioned Qt doesn't use server side picture transformations with Xrender but it shows that OpenGL is certainly not slow at it.

So what these results show is that GL backend, which hasn't been optimized at all, is between 2 to 6 times faster than anything out there and that pure CPU based Raster engine is faster than the Xrender engine.

So if you're on an Intel GPU, or NVIDIA GPU rendering using GL will immediately make your application a number times faster. If you're running on a system with no capable GPU then using raster engine will make your application faster as well.
Switching Qt to use GL backend by default would result in all applications running a magnitude times faster. The quality would suffer though (unless HighQualityAntialiasing mode would be used in Qt in which case it would be the same). This certainly would fix our graphics performance woes and as a side-effect allow using GL shaders right on the widgets for some nifty effects.
On systems with no GPU raster engine is a great choice, on everything else GL is clearly the best option.

Accelerating desktops

2008-06-27T17:44:00.002+01:00

In general I'm extremely good at ignoring emails and blog posts. Next to head-butting it is one of the primary skills I've developed while working on Free Software. Today I will respond to a few recent posts (all at once, I'm a mass-market responder) about accelerating graphics.

Some kernel developers released a statement saying that binary blobs are simply not a good idea. I don't think anyone can argue that. But this statement prompted a discussion about graphics acceleration, or more specifically a certain vendor who is, allegedly, doing a terrible job at it.

First of all the whole discussion is based on a fallacy rendering even the most elaborate conclusions void. It's assumed that in our graphics stack there's a straight forward way between accelerating an api and fast graphics. That's simply not the case.

I don't think it's a secret that I'm not a fan of XRender. Actually "not a fan" is an understatement I flat out don't like it. You'd think that the fact that 8 years after its introduction we still don't have any driver that is actually real good at accelerating that "simple API" would be a sign of something... anything. When we were making Qt use more of the XRender api the only way we could do that is by having Lars and I go and rewrite the parts of XRender that we were using. So what happened was that instead of depending on XRender being reasonably fast we rewrote the parts that we really needed (which is realistically just the SourceOver blending) and did everything else client side (meaning not using XRender)

Now going back to benchmarking XRender. Some people pointed out an application I wrote a while back to benchmark XRender: please do not use it to test a performance of anything. It will not respond to any real workloads. (also if you're taking something I wrote to prove some arbitrary point, it'd be likely a good idea to ping me and ask about it. You know on account of writing it, I just might have some insight into it). The thing about XRender is that there's a large amount of permutations for every operation. Each graphics framework which uses XRender uses specific, defined paths. For example Qt doesn't use server-side transformations (they were just pathetically slow and we didn't feel it would be in the best interest of our users to make Qt a lot slower), Cairo does. Accelerating server side transformations would make Cairo a lot faster, and would have absolutely no effect on Qt. So whether those tests pass with 20ms or 20hours has 0 (zero) effect on Qt performance.

What I wanted to do with the XRender performance benchmarking application is basically have a list of operations that need to be implemented in driver to make Qt, Cairo or anything else using XRender fast. "To make KDE fast look at the following results:" type of thing. So the bottom line is that if one driver has for example result of 20ms for Source and SourceOver and 26 hours for everything else and there's second driver that has 100ms for all operations, it doesn't mean that on average driver two is a lot better for running KDE, in fact it likely means that running KDE will be five times faster on driver one.

Closed sourced drivers are a terrible thing and there's a lot of reasons why vendors would profit immensely from having open drivers (which is possibly a topic for another post). Unfortunately I don't think that blaming driver writers for not accelerating graphics stack which we went out of our way to make as difficult to accelerate as possible is just a good way of bringing that point forward.

Animated interfaces

2008-06-02T18:50:00.003+01:00

Lately I've been writing a lot about frameworks, today I want to take a step back and talk about a "technique". "Drunken master"/"Praying Mantis" kind of foo pertaining to animations.

Over the years of writing animated user interfaces I've developed a set of rules that I follow when writing animations. It's been a checklist that I've been following almost religiously. Much like my morning list of "1) Open eyes, 2) Check for dead bodies in the bed, 3) Around the bed, 4) if 2 and 3 are negative brush teeth and take a shower, otherwise prepare for a very bad day", which is the main reason why I never had a bad day in my life. Which is another good lesson to learn - very low expectations make for a very fulfilling life.

I've realized that those rules might be useful to others so I'll write a bit about them today. I guarantee you that if you'll follow them the animations that you'll add to any user interface will not make any of your users want to stab you, which again, following the low expectations lesson from the above, is a making of a great day. In fact following these rules will make your UI rock, which even if you have high expectations is a desirable quality.

So without further ado, here are my rules:

Anger rule:
Creating animations is a lot of fun. Which in turn makes the act of adding animations to a user interface a happy activity. When we're happy we're willing to endure a lot more abuse. In particular ignore or not even notice something that is very irritating. Unfortunately computer UIs are usually used by people who are not happy at all (e.g. they're at work) and their perception of what seemed like a neat animation to you when you were in a great mood will be vastly different. So always, always make sure you've experienced all of your animations when being angry. If they haven't irritated the hell out of you, congratulations you are on to something.

Blind interpolator rule
Find someone who has never seen the animation you're designing, tell them to close their eyes as soon as the animation starts. Ask them how they think it ended. If their brain isn't able to fill in the blanks and figure out how the animation ends then the animation does something unexpected that will force your users to learn it. For a user interface to be intuitive you have to avoid forcing users to learn its behavior. It has to come naturally.

The timing rule
This one is tricky. Timing your animation correctly is one of the hardest things to do. I use a two step approach to figure this one out:
- follow physics - so follow timings from a real world, e.g. if something is falling let it lasts as long as it would if you had dropped something in real world,
- make it fast - if animation lasts too long people try to stop it by hitting any random key on the keyboard. From user-interface perspective what you definitely want to avoid is having your users hitting random keys while the application is running.
Animations in user-interfaces need to be very, very short. The point of them is to give subtle hints as to where things are coming from. They're an aid in understanding computers, not a graphical effect that is meant to impress. I tend to violate this rule because if I spend 2 hours writing a really neat animation I'll be damned if everyone won't be forced to look at it. But that is wrong! Very wrong. Subtlety is the key here. If the animation is running on a desktop a good rule of thumb is the "escape key rule" - if your animation is longer than the time required to move a hand from the mouse and hit the escape key, the animation is too long.

No sci-fi rule.
Also known as the 'avoid goofy and crazy things rule'. Effects grounded in reality will make sure your interface is easier to learn and more intuitive. For user interfaces wacky and cool don't imply "good", in fact it's usually just the opposite. These are not games where "wacky" and "cool" are desirable qualities.

The refresh rule

Make your animation run at the number of frames per second equal to the refresh rate of the output device and synchronize the updates with vertical retrace.

Lately I got obsessed with trying to automatically figure out what is an optimal number of frames per second for animations in user interfaces. I can obsess with the craziest of them so last week I added this rule.

What do you think, how many frames per second should an animation be running at? 15? 24? 30? 40? 60? Coincidentally those are also this weeks winning lottery numbers. The answer is "it depends". It is highly dependent on the refresh rate of the output device. The "you need 24fps (or 30fps or even 60fps) to achieve smoothness" is a myth. No one knows how many frames per second humans can actually perceive but pilots were able to decipher kinds of planes shown for 1/220th of a second. So it seems that we could actually recognize objects at 220fps. How many would we require to not notice any frames is a question without an answer right now but it's likely that you'd need more than 400fps to do it. None of the commercially available display devices can refresh at that speed. So ideally what you want to do is synchronize the number of frames per second to a refresh rate of your output device. Here's an example you can play with: http://byte.kde.org/~zrusin/animsync.tar.bz2. You'll see a square moving back and forth in a window like this:

You can specify the number of frames per second on the command line and passing "-s" option will sync the animation to the vertical retrace of your output device (assuming your GL driver supports it, which, unless you're running DRM head or the closed NVIDIA driver is unlikely). Experiment with it a bit.

So, these are my rules. They're not laws so in certain situations you might need to break one of them but if you do, you better have a very good explanation that you can back up with some facts for why you're doing so.

No black here

2008-03-03T00:04:00.003Z

Sup, y'all. I realized that Free Software is a lot like the wild west used to be. So, partner, I'll be spreading some "west" and a lot of "wild" over this post.
"What?", you say (oh I'll have a conversation with you whether you want it or not). Well, the connection is obvious once you think about it: during the wild west days people used to ride horses, kill each other for no apparent reason and raise cattle, while in Free Software we write software. I rest my case.

I've spent the last week with Aaron. I absolutely love hanging out with him. It's platonic. Or so I think, with all the heavy drinking that I do, it all gets a little blurry. Also, Peyton (Aaron's son) is a wickedly cool kid.

Anyway, I have a lot of Gallium3D things to do which are a priority, but at nights Aaron and I hacked on Plasma and KDE. I think I speak on behalf of Aaron when I say that we became computer programmers for the women. Which might seem a little confusing to, well all of you (especially if you're a woman) until you realize that it came down to being either a computer programmer or a crackhead. Computer programmer job pays, like, way better and if I had to pick second reason why I do what I do it's money.
We got the Dashboard widgets working. It's been something that I wanted to do for the longest time. Obviously not all of them work because some of them use OS X specific apis (like Core Image magic).
I also added interfaces to use Plasma's DataEngine's from JavaScript in web applets. So you would do something like


var engine = window.plasma.loadDataEngine("time");
var data = engine.query("Local");
document.getElementById('time').innerHTML = "Time is " + data.value("Time");

to use Plasma's time data engine to display the current time. One could use Plasma's Solid data engine to get the list of all the devices attached to the computer and display it in the web applet which would be a little more useful than another a time widget but you ain't enterprise ready unless you have 23 clock applets and we're almost there. There's also a small bug somewhere, that apparently doesn't exist in Qt and is, in fact, a figment of my own imagination due to which the background looks black. On Chuck Norris widget (that like a lot of other dashboard widgets just works. You download it, click on it, run it, show it to all your friends, and remove it once they're gone because it's pretty damn useless) it looks like this:

Do you see black? No, you don't! It's simply that Chuck Norris is a black hole that consumes everything around it, including all the color. Deal with it. Chuck Norris has.

OpenVG and accelerating 2D

2008-02-07T13:39:00.001Z

I tend to break a lot of keyboards. Not because I release all the aggression that I hold deep within me on them, but because I drool a lot. It's not my fault, I really do love graphical bling. Since I'm one of the people who flourishes not when he's doing well, but when others are doing just as badly I've thought about getting other people on the "excessive drooling" bandwagon.

I've tried it in the past. First with my "you ain't cool, unless you drool" campaign, which was not as successful as I've seen it be in my head. It made me realize that marketing is unlikely one of my superpowers. That was a real blow especially since it came a day after I've established that there's like a 95% chance that I can't fly and if I can, then my neighbor will be seriously pissed if I keep landing on his car. You'd think they'd build them stronger, but I digress. After that I went with my strengths and had two technical efforts. The first one led to Exa the second to Glucose. Both are acceleration architectures that try to accelerate Xrender - the API which we use for 2D on X. What Xrender is very good at is text. What Xrender is not so good at is everything else.

Furthermore what one really wants to do nowadays is use the results of a 2D rendering in a 3D environment as a texture or simply implement effects on top of the 2D rendering with shaders. Wouldn't it be nice to have a standard and simple API for all of that? You bet your ass it would. In this particular case "you bet your head" would be a more suitable expression, since by a simple act of reading this blog it's clear you already gave up on your ass and stake your future on your head. I endorse that (both the head more important than ass theory and better api idea). Currently, through the magic of DRM TTM and GLX_texture_from_pixmap one could achieve partially that (we'd need GLX_pixmap_from_texture to finish it), but if you've seen Japanese horror movies you know they got nothing on the code one ends up with, when doing that.

I already mentioned in my previous post that we can lay any number of API's on top of Gallium3D. In fact in the last diagram I already put the two graphics API's that interest me on top of it. OpenVG and OpenGL. In my spare time I've started implementing OpenVG on top of Gallium3D. I'm implementing 1.1 which hasn't been officially released yet. While OpenVG 1.0 is essentially useless for our drool-causing desktops because it doesn't even touch the subject of text handling, 1.1 does and that in itself makes it a great low-level 2D vector graphics api.

We already have OpenVG engines for Qt and Cairo which should make the switch fairly painless. "Hey", you say and I swiftly ignore you, because I have a name you know. "Sunshine", you correct yourself and I smile and say "Huh?". "I want my KDE 4 fast and smooth! Gallium3D has this 3D thing in the name and I have hardware that only does 2D, what about me?". Nothing. You need to use other great solutions. "But my hardware can accelerate blits and lines!". Awesome, then this will likely rock your world. As long as you won't try to run any new applications of course. Even embedded GPU's are now programmable and putting the future of our eye-candy on a technology that predates 2 year old embedded GPU's is an exercise in silly which my chiseled pecs refuse to engage in.

OpenVG standard says "It is possible to provide OpenVG on a platform without supporting EGL. In this case, the host operating system must provide some alternative means of creating a context and binding it to a drawing surface and a rendering thread." which is exactly what we want. That's because we already have that layer, it's GLX. GLX will do the context creation for us. This also means that we'll be able to seemingly combine 2D vector graphics and 3D and manipulate the results of vector rendering the same way we would normal 3D.

Finally 2D graphics will be accelerated the same way 3D is and those hours which you've spent playing 3D games thinking "how the hell is it possible that putting a clock on my desktop makes it choppy when this runs at 400fps?" will be just a story you'll get to tell your grand-kids (while they stare at you with the "please god, let me be adopted" look). As a bonus we get two extremely well documented API's (OpenGL and OpenVG) as our foundation and instead of having two drivers to accelerate 2D and 3D we'll have a single driver.

So what happens with Glucose? Alan and José are still working on it a bit and in a short-term it does provide a pretty enticing solution but long term OpenVG/OpenGL combo is the only thing that really makes sense.

With much love,
Drool Coordinator

GPGPU

2008-02-06T09:57:00.001Z

Would you like to buy a vowel? Pick "j", it's a good one. So what if it's not a vowel. My blog, my rules. Lately I had a major crash on all things "J". Which is why I moved to Japan.

It's part of my "Most expensive places in the world" tour, unlikely coming to a city near you. I lived in New York City, Oslo, London and now Tokyo. I'm going to write a book about all of that entitled "How to see the world while having no money whatsoever". It's really more of a pamphlet. I have one sentence so far "Find good friends" and the rest are just pictures of black (and they capture the very essence of it).

José Fonseca helped me immensely with the move to Japan, which was great. Japan is amazing, even though finding vegetarian food is almost like a puzzle game and trying to read Japanese makes me feel very violated. So if you live in Tokyo your prayers have been answered, I'm here for your pleasure. Depending on your definition of pleasure of course.

Short of that I've been working on this "graphics" thing. You might have heard of it. Apparently it's real popular in some circles. I've been asked about GPGPU a few times and since I'm here to answer all questions (usually in the most sarcastic way possible... don't judge me, bible says not to, I was born this way) I'm going to talk about GPGPU.

To do GPGPU there's ATI's CTM, NVIDIA's Cuda, Brooke and a number of others. One of the issues is that there is no standard API for doing GPGPU across GPU's from different vendors so people end up using e.g. OpenGL. So the question is whether Gallium3D could make such things as scatter reads accessible, without falling back to using vertex shaders or vertex shaders/fragment shaders combination to achieve them.

Core purpose of Gallium3D is to model the way graphics hardware actually works. So if the ability to do scatter reads is available in modern hardware then Gallium3D will have support for it in the API. Now having said that, it looks like scatter reads are usually done in a few steps, meaning that while some of the GPGPU specific api's expose it as one call, internally number of cycles passes as few instructions are actually being executed to satisfy the request. As such this functionality is obviously not the best to expose in a piece of code which models the way hardware works. That functionality one would implement on top of that api.
I do not have docs for the latest GPU's from ATI and AMD so I can't say what it is that they definitely support. If you have that info let me know. As I said the idea being that if we'll see hardware supporting something natively then it will be exposed in Gallium3D.

Also you wouldn't want to use Gallium3D as the GPGPU api. It is too low level for that and exposes vasts parts of the graphics pipeline. What you (or "I" with vast amount of convincing and promises of eternal love) would do is write a "state tracker". State trackers are pieces of code layered on top of Gallium3D which are used to do state handling for the public API of your choice. Any api layered like this will execute directly on the GPU. I'm not 100% certain whether this will cure all sickness and stop world hunger but it should do, what even viagra never could, for all GPGPU fanatics. The way this looks is a little like this:

This also shows an important aspect of Gallium3D - to accelerate any number of graphical API's or to create a GPU based non-graphics API, one doesn't need N number of drivers (with N being the number of API's), as we currently do. Gallium3D driver (that's singular!) is enough to accelerate 2D, 3D, GPGPU and my blog writing skills. What's even better is that of the aforementioned only the last one is wishful thinking.

So one would create some nice dedicated GPGPU api and put it on top of Gallium3D. Also since Gallium3D started using LLVM for shaders, with minimal effort it's perfectly possible to put any language on top of GPU.

And they lived happily ever after... "Who" did is a detail, since it's obvious they lived happily ever after thanks to Gallium3D.

Constant state objects

2007-12-27T22:18:00.000Z

I know you wither away, like a leaf in the darkness of the chilly, Autumn night, without my posts. I've been depriving you for too long of the sunshine that is me. Writing an interesting post explaining the new way one is doing register allocation or how the code generation has changed to benefit the drivers is a little difficult and I didn't feel like it would interest anyone. Especially that I know that if I write a blog about a little demo app I wrote in half an hour to showcase some technology I get 50 comments but when I blog about the process of creating that new technology I get two comments with one of them being "What?". On top of that I was lacking those new nude photos (it's art you pig!) of myself that I've promised you and which you yearn for so much.

Lately I've been working on the Gallium3D i965 driver. I had to read up some documentation because, as it turned out, being a "graphics ninja" did not give me intrinsic knowledge of all graphics hardware ever built. I know! I was as shocked as you are right now.

It started with the fact that I wanted to experiment with the layout of vectors in shaders for the code generation using LLVM facilities.

To experiment with different layouts I've decided to write i965 driver for Gallium3D and experiment with LLVM code generation for i965 in that driver. Keith Whitwell and I have been hacking on it and it's going pretty well. It's amazing how much code we've removed from the old i965 driver while porting it to Gallium3D. It was a rather nice feeling to see so much of the complexity of the driver disappear.

The great thing about writing a Gallium3D driver is that a lot of the complexity of the high level API goes away, as it's being moved to "state tracker". State tracker is responsible for all API specific state handling and tricky conversions. The driver never sees the state tracker, it implements a very thin interface, which corresponds rather closely to the way modern hardware works.

One of my favorite changes is the new way we handle state changes. It used to be that the driver had to check whether any of its state changed and if it did upload it before drawing anything. It turned out to be a rather serious bottleneck and it made reading our driver a little painful.

In Gallium3D we went away from that. Now we use similar semantics to what Direct3D10 and OpenGL3 (will) use. Which is that states are largely immutable objects. Their usage follows the

create from a template
bind the state to make it active for subsequent rendering calls
delete when not needed anymore

pattern. This way the driver can do all of its conversion on creation (which ideally happens only once) and then on bind calls (which we have multiple off) it can just reference the id of this state to have it used instead of having to do a full conversion from the Mesa state and upload of the converted state.
When I wrote the constant state objects code I ported our simple i915 driver and, even though on i915 we don't have hardware state caching just doing the state conversions in create calls improved the performance in simple examples by about 15fps. For more complicated examples where the state changes are more frequent it will be a lot more. Not even mentioning drivers which will do full state caching in the hardware where this is going to fly like Superman with diarrhea.

Less complexity in the driver and faster code, is what I think love is all about. Granted that my idea of love might be a smidge skewed on account of me being crazy and all but no one can argue with the "simpler/faster" being 'awesome'.

And to really top this graphics talk off, a picture of me naked:

In retrospect not my best day. The lighting was all wrong...

Gallium3D LLVM

2007-11-02T17:16:00.000Z

I've seen the future. The blurry outlines sketched by such briliant audio-visual feasts as Terminator came to fruition as in the future the world is ruled by self-aware software.
That's the bad news. The good news is that we haven't noticed.
We're too busy due to the fact that we're all playing the visually stunning "The Good Guy Kills the Bad Guys 2" on Playstation 22. It really captured the essence of the first. The theaters are ruled by "Animals - Did they exist?" documentary with some stunning CG of a horse, although I could have sworn that horses had 4, not 3 legs but then again I'm no nature expert.
What everyone was wrong about though is which program became self-aware and exerted its iron-fist like dominance upon the unsuspecting humans and the last few, very suspicious cockroaches. It wasn't a military mistake. It was a 3D framework that evolved.

But lets start from the beginning. First there was Mesa, the Open Source implementation of the OpenGL specification. Then there came Gallium3D, a new architecture for building 3D graphics drivers. Gallium3D modeled what modern graphics hardware was doing. Which meant that the framework was fully programmable and was actually code-generating its own pipeline. Every operation in Gallium3D was a combination of a vertex and a fragment shader. Internally Gallium3D was using a language called TGSI - a graphics dedicated intermediate representation.

Gallium3D was generating vertex and fragment shaders at run-time to describe what it was about to do. After that system was working, some engineers decided that it would make sense to teach Gallium3D to self-optimize the vertex/fragment programs that it, itself, was creating. LLVM was used for that purpose. It was used because it was an incredible compiler framework with a wonderful community. The decision proved to be the right one as Gallium3D with LLVM proved to be a match made in heaven. It was pure love. I'm not talking about the "roll over onto your stomach, take a deep breath, relax and lets experiment" kind of love, just pure and beautiful love.

So lets take a simple example to see what was happening. Lets deal with triangles, because they're magical.
Now to produce this example Gallium3D was creating two small programs. One that was run for every vertex in the triangle and calculated its position - it was really just multiplying the vertex by the current modelview matrix - that was the vertex shader. The other program was run on every fragment in this figure to produce the resulting pixels - that was the fragment shader. To execute these two programs they were being compiled into LLVM IR, LLVM optimization passes were run on them and LLVM code generators were used to produce executable code. People working on Gallium3D quickly noticed that, even though, their code wasn't optimized at all and it was doing terribly expensive conversions all the time, it was up to 10x faster with LLVM on some demos. They knew it was good.

So Gallium3D was in essence, at run-time, creating and optimizing itself. Which lead many Free Software enthusiast to create, wear and rarely even wash shirts with a slogan "We might not have a billion dollar budget but our graphics framework is smarter than all the people in your company together".

Then in the year 2113 Gallium3D got bored with just creating graphics and took control of the entire world. Which realistically speaking wasn't hard to do because we were willingly immersing ourselves in the worlds it was creating for us anyway.

But that's still many, many years away from our boring present. So for now, while you wait for sex robots, dinners in a tube and world without insects (or for that matter absolutely any animals at all) you can just go, get and play with Gallium3D where LLVM is used. At the moment only in the software cases, but the fifth of November is going to mark the first day in which work on code-generating directly for GPU's using LLVM is going to start.

Remember, remember the fifth of November... (oh, come on that's one heck of an ending)

KHTML future

2007-10-23T23:57:00.000+01:00

I've read Harri's blog about WebKit and I figured it makes sense for someone to respond. First of all I liked the blog, It was full of drama, action, despair, marketing and bad and good characters. Which is really what I'm looking for when reading fiction.

Especially the part that mentioned QtWebKit as an irrelevant fork of KHTML sources. That was awesome. It's the kind of imagination we need more of in the blogosphere. For the purposes of the point Harri was trying to make, which I think was "no matter what's the reality, our ego is bigger than yours", it was a well suited argument.

Describing the WebKit project as a fork of KHTML sources is like calling GCC a fork of EGCS, or to use a more popular analogy it's like calling chicken a fork of an egg. If you want to talk about forks then technically nowadays KHTML is a fork of WebKit. Not a terribly good one at that. It's real easy to back that statement up by comparing the number of submits to KHTML to the number of submits to WebKit. In fact that comparison is just embarrassing for KHTML.

I also found it funny that people like Lars Knoll, Simon Hausmann, George Staikos or myself are not part of the KHTML team. "We are the 'KHTML team' (except KHTML's author and ex-main developer Lars who's one of the biggest supporters of WebKit now and other people who used to work on KHTML but now work on WebKit as well... but they were all ugly... honestly!)" you can go make shirts with that.
We're working on WebKit now hence we're not KHTML team members. Any KDE developer who works on WebKit (hey, Niko, Rob, Adam, Enrico...) is automatically dissociated from the KHTML team.

The fact is that there is more KDE developers contributing to WebKit than there is KDE developers contributing to KHTML.

So since there's more of us, I think technically that means that we are the official KDE web engine team. KHTML team, we would love to work with you, the fork, but you're kind of a pain in the butt to deal with.

Which is ok, because like I mentioned a number of times KDE community lives of the "who does the work decides" dogma. And ultimately the Apple guys, the Trolltech guys, people from George's company who work on this stuff full-time and tons of Free Software contributors working on WebKit do much, much more work than people do on KHTML.

On a more serious note, let me explain a very important point: bug for bug compatibility with the latest Safari would be worth much, much more to KDE than any patches that are in KHTML and haven't been yet merged to WebKit could ever be worth.
Web works on the principle of percentages - web-designers test their sites with engines that have X% of market reach. Konqueror with stock KHTML isn't even on their radar. WebKit is. Having web designers cater towards their engine is worth more than gold to KDE users.

And if you care more about some personal grudges than the good of KDE, that's also OK, because we, the official KDE web rendering team will do what's right for KDE and use WebKit.

Gallium3D, Shaders and LLVM

2007-09-29T22:14:00.000+01:00

Today we're going to talk about shaders. Well, I'll talk, or to be more specific write, or to be blunt I'll pretend like I'm actually capable of putting my thoughts into readable excerpts that other human beings (hopefully you) and some of my imaginary friends (they're not all winners) can understand.

The question I've been asked a few times during the last week was "who are you and what are you doing in the bushes outside my house", which isn't related to computer graphics at all and what I do in my spare time is none of your business so I won't be talking about that. Now the other question that I've heard a few times during the last week was "will Gallium3D use LLVM?", the short answer is "yes, it will".

First of all a little about graphics hardware. A common thing to do in modern graphics hardware is to have very wide registers and allow stuffing arbitrary vectors inside those registers. For example one register might very well store 8 2 component vectors. Or 16 components of 16 different vectors with other components being stored in subsequent registers. To support writing to those wide registers, usually there's another register, often a stack of them, which is used as a write mask for all operations. Cool, eh? So now when your language supports, god forbid, branches or loops and you want to code generate something for graphics hardware, you're left with two options. Option one is to give up and go ride donkeys in a circus and option two which is to do something crazy to make it work. To be honest I've never even seen a real life donkey. I've seen a cow but we just didn't hit it off. So I knew that option one is just not right for me.

So one of the big worries that we had was whether we'll be able to code generate from LLVM for graphics hardware. After some discussions about pattern matching in code generators and opcode lowering it finally looks like the answer is "yes, we will be able to generate something usable". So the way it will work in Gallium3D is largely similar to the I wanted to do it in the LLVM GLSL code that Roberto and I have been working on for Mesa a few months back. The difference is that the IR in Gallium3D is completely language agnostic.

You can run OpenGL examples already, granted that some of them will not produce correct results,but if it all would just work then I'd have nothing to blog about. I'll start integrating LLVM parts within the next two weeks which is when the performance should get a major boost and flowers should bloom everywhere. You might think that the latter is not, technically, related to our work on Gallium3D and the fact that Autumn is here makes that last statement even more dubious, but you're wrong. Who would you rather trust, you or me? I bet you thought "me" and so I rest my case.

And all of that is brought to you without any sheep sacrifice and hardly any virgin sacrifice ("hardly any" because I, as a representative virgin, am making a small sacrifice, but from what I understand it doesn't count as a full fledged "virgin sacrifice").
How do you like them apples? (or oranges... or strawberries... I like raspberries... They're all good is I guess my point).

Gallium3D

2007-09-21T14:53:00.000+01:00

Critics are raving: "Gallium 3D is the best thing that ever happened to Free Software graphics", "It's breathtaking!", "Never before has nudity been so tasteful!"... Alright, maybe not the last one. Actually none of them, since it's a brand new project. In fact that's the point of this entry. To introduce you two.

You, a brilliant (as derived from the fact that you're reading this blog) Free Software enthusiast or simply my very own stalker (both options very satisfying to me personally). And Gallium3D, the foundation of Free Software graphics for years to come.

Gallium3D is a redesign of Mesa's device driver model. It's a new approach to the problem of accelerating graphics. Given tremendous investment that free desktops make in OpenGL nowadays I'm very excited to be working on it.

At Tungsten Graphics we've decided that we need a device driver model that would:

make drivers smaller and simpler
model modern graphics hardware
support multiple graphics API's

The basic model, as presented by Keith Whitwell on XDS2007, looks as follows:

You can follow the development of Gallium as it happens in Mesas gallium-0.1 branch.

Also you can read a detailed explanation of what it is on our wiki .

Now why should you be excited (besides the fact that, like I already pointed out, there's no developer nudity in it and that being excited about the stuff I'm excited about is in general a good idea).

Faster graphics
Better and more stable drivers
OpenGL 3
Ability to properly accelerate other graphics APIs through the same framework. Did someone say OpenVG?

This is a huge step on our road to tame the "accelerated graphics" demon in Free Software. We've been talking about it for a long time and now and we're finally doing it. There's something zen like about working on free software graphics for years and finally seeing all the pieces falling into place.

Git cheat sheet

2007-09-10T09:06:00.000+01:00

Due to the fact that I've been moving I forgot to point out that about three weeks ago I created a small Git cheet sheet. Quoting my email to the Git mailing list: I took a short break from being insanely handsome (which takes a lot of my time - gorgeous doesn't just happen) and based on similar work for Mercurial created a little SVG cheat sheet for Git. I'm not sure if it's going to be useful for anyone else (the target audience was composed of engineers who agreed to move to and work from Norway so you know right of the bat that historically they already made some bad decisions), but the times when I do art are so rare that I feel the need to share.

The thing that I took from the Mercurial sheet, besides the idea, is the flow-chart (people dig icecream and flow-charts, the first one is really hard to get into a SVG rendering so I went with the second) so the license is the same as of the Mercurial sheet which was Creative Commons. There's likely a few errors in it and if you have any suggestions or if you sport latex pants and a fancy green hairdo that goes with those pants (which equals the fact that you're an artist) and would like to pimp the sheet out, it would be my pleasure to help you.

The SVG is at:
http://byte.kde.org/~zrusin/git/git-cheat-sheet.svg
Sample png's are here:
http://byte.kde.org/~zrusin/git/git-cheat-sheet-medium.png
http://byte.kde.org/~zrusin/git/git-cheat-sheet-large.png

I also got up to speed on all the latest announcements. I thought that the Novell's Spotlight collaboration announcement was disappointing. I'm referring to the "Microsoft will provide Novell the specifications for Silverlight".

Richard Leakey once said "We are human because our ancestors learned to share their food and their skills in an honored network of obligation". I love that quote because it so beautifuly describes what we, so heavly, rely on in the Open Source community. For a company to take from the great ocean of free knowledge, led by an open standard of SVG and end up with a closed specification is just disgusting. Seeing an Open Source company strike a deal to cooperate on that closed technology is just sad to me. I understand why they did it but understanding something doesn't make it morally right.

I really hope, pointlessly as it might be, that the work on the Silverlight specification and the specification itself will be open. You obviously thought that SVG isn't good enough for your purposes and you built on top the experiences and ideas taken from SVG. Let us improve SVG based on your experiences and ideas. Once we've done that, you'll be able to repeat that process again. That's the way it works and that's the way our society has always worked.

Despite what you might think, you don't own ideas, they belong to us all.

Quasar

2007-09-06T09:18:00.000+01:00

Does working on the 3D stack make me look fat? Give it to me straight. I promised myself I won't cry no matter what the answer is. As I mentioned in my last blog I'll be getting awfully kinky with our 3D stack and people wondered whether my work on it affects Quasar. Well, just as me moving didn't affect my habits with regards to taking showers (which I do frequently, i.e. every christmas or so), smoking (never ever), being awake (at least once per day) it also didn't affect my spare time habits (except the "starving" thing which was one of my favorite past-times in Norway). Since Quasar was always my spare time project, my move affected it as much as me buying new sneakers affects temperature in Japan (which it doesn't, assuming of course that the folks in Japan won't find the vision of me in the new sneakers so insanely hot to increase the temperature of the whole country).

Aaaanyway, so what is Quasar? Besides being a word that starts with a Q, has some other letters in the middle and sounds funky. It's a dynamic rendering framework, which in turn begs the question "what the hell is that?" ("the hell" being an optional part of this sentence).

Let me lead you through the evolution of Quasar and hopefully at end of this trip we'll be on the same page with regards to what we really need in terms of a graphical framework on the desktop.

Quasar started as a pretty basic image manipulation framework. I wanted to make sure that people can chain filters e.g. read-image->scale image->blur image->render image. It was a linear pipeline. The thing that made it important to me was that it was focused on hardware acceleration. This is a very important point which I want to underline.

I'm not interested in software based effects. This is not to say that the software versions of all of them shouldn't work, I just refuse to bother. It's 2007, even phones come out with some kind of gpu in them, worrying about software based graphical effects does to your time what listening to financial advises from blogs of Open Source engineers does to your money - wastes it (which reminds me, I also have some financial tips for you. Well, tip, just one. It's not the quantity but quality as they say. Invest money in winning lottery tickets. Note that I said "winning", buying any other kind would be silly. You're welcome). With the work we're doing right now at Tungsten Graphics our graphics stack will be extremely good at it.

When I was a kid we didn't have fancy graphics. We had crackheads, alcoholics, pimps, thugs and plenty of other shady characters none of which, I'm fairly certain, did computer graphics (childhood memories warm your heart, don't they?). If my years of working on a vector graphics framework taught me anything (besides how to write a vector graphics framework) it's that the most fundamental part of a high level graphics framework isn't the framework at all. It's the way in which you let people design their applications, their interfaces. What use are blurred perspective transformations if two people know how to use them? What's the point of 20 composition modes if people can't be bothered to understand the basic 2.

So I started seeing effects as a step, a very crucial one, on the way to very appealing interfaces, but not my ultimate goal. In a desktop world we're dealing with graphics on a fairly abstract level, because we're doing graphics for non-graphics people. Good effects framework is not one that has every possible effect ever invented but one that makes it possible to quickly add those effects to ones application/interface and end up with something usable and pretty.

Finally inherent complexity of graphics bothered me. Maybe not even the complexity itself (especially since it's where my job security stems from), but the fact that it takes a lot of knowledge to understand and know the fast paths. The knowledge necessary to extract that logic can be easily abstracted in a graph like structure. That's what I started doing in Quasar.

Quasar is a dynamic graph. One that can rearrange itself to produce the output in the fastest possible way.
Those are the three basic tenants of Quasar, to rehash, they are:
- hardware accelerated,
- easy to incorporate and produce good looking results,
- smart enough to produce the results in the quickest possible way, no matter how little knowledge its users posses.

The way it works is that one creates the rendering in a graphical builder (which at the moment looks very much like Quartz Composer), loads it up in application and, well, that's it.

Of course, the graph can be created or modified at run-time just well. It follows the "tell me what you'd like and I'll give you that in the best way possible" principle.
Having said that Quasar is still far from complete but I just posted where to get it from on the relevant KDE list (if you don't know which one, trust me you want to wait a little bit longer before trying it out). Oh, and of course Quasar will support full effects pipelines on top of movies (integrated with Phonon).

In London

2007-08-31T16:09:00.000+01:00

Today was my last at Trolltech. Some of you already knew that, the others are likely getting mouth to mouth reciprocation right now while a heavy set man is charging defibrillator paddles next to them (breath, breath!).

Technically Qt is years ahead of all of its competition and with Trolltech's amazing engineering team it will continue doing great. I felt that other parts of the Open Source graphics stack could use my work a little more at the moment.

We (Open Source community) move at an astounding pace but the lower parts of our graphics framework are lagging a little bit behind. I wanted to go back to working on those parts of the graphics stack and it made sense for me to join a company that would directly profit from my work on Mesa, DRI, drivers and X.

This Monday will mark my first day at Tungsten Graphics. The engineering team at TG includes the likes of Brian Paul, Keith Whitwell, Michel Dänzer, Alan Hourihane and others, which reads almost like "Who's who in Open Source graphics". Clearly the only thing that was missing there was someone who looks really good naked. That's me. I also know a thing or two about this whole "graphics" thing which tends to help.

I'll be living in London for the next ~2 months or so. In England, while mainly working on Mesa, I'll be filling the void left by the departure of Victoria and David Beckham.

Small steps

2007-08-20T10:20:00.000+01:00

I was on vacations last week but I'm being all jealous of my luggage. It got a free trip around the world. During my last 8 flights my luggage has been lost 5 times. Is that a record? Confetti anyone? It's a celebration. If you're going to meet me during any of the upcoming conferences I'll be the outgoing and highly sarcastic naked guy with a sign on my chest saying "for my face look this way" and an arrow pointing up.

I neglected to mention that, as Simon said, QtWebKit is working on Windows. Simon did an amazing job of porting all the quirks of the build system but "amazing" is the default state for all of his code so it's not a surprise at all. While he was doing that I've sat down and ported XML tokenizer to QXmlStream from LibXML. If you never wrote a web rendering tokenizer (and unless you're crazy, the chances of that are pretty high, and if you did you're crazy and won't remember doing it anyway) you know that "fragile" is a term that nicely describes it. After it was ported Lars and I sat down to fix the regressions and they didn't even know what hit them (ha! ninja reference).

In other news I've merged in FreeType2 rasterization algorithm patches in Qt. Our raster engine, uses the beauty that is FreeType's rasterizer, with a few patches on top. Because they break BC in FreeType's public interfaces we can't merge them back at the moment. In any case the patches improve rendering speed in general antialiased paths of the raster engine (meaning on Windows, Qtopia Core and in general whenever rendering to a QImage) by about 10% which is gangsta awesome ("gangsta awesome" is a very high level of awesomeness, at least judging from MTV).

I've also optimized the path clipping code. Andreas uses the path clipping code in GraphicsView for collision detection, so when I say "path clipping code" you should read "path clipping and GraphicsView collision detection". A lot of the time in that algorithm has been spent on vertex allocation for tested paths. I've used a few tricks to speed it up by about 15%. The code for that algorithm is the number two reason why baby seals die (the first is still undisputed). It's not even the algorithm itself but the inherent complexity of the problem. I'm a big fan of computational geometry in computer graphics because it makes grown man cry, except me and I like feeling like the lean, mean, killing machine that I am. My favorite part of the path clipping problem is that there are two ways of solving the precision problems and neither of them really works. The trick is that paths operate in double coordinate system, efficient snap-rounding implementations that I've seen operate in fixed-point coordinate system which falls apart in this case because of absolutely random distribution of vertices across the full double spectrum. Tessellation and clipping itself can be done in a screen coordinate system, which makes it possible to consistently represent your coordinates with fixed-point representation. That doesn't work for paths because, e.g. boolean operations on paths need to be done in native path coordinates not screen coordinates. So the algorithm forces an absolutely crazy mix of dynamic fixed-point size, reduced-predicates, magic and good-will to work. Aren't you happy that I'm doing it for you? You better be.

Yours(1) Latino(2) Lover(3)

1) Not really "yours", more "community". I love "you" but "you" need to realize that I need to be seeing other people.
2) Not really "Latino". Unless of course my Spanish or Brazilian friends would like to name me an "honorary Latino" or "Latino by association". I'd be definitely down with that. The only food I can make that is eatable and doesn't force the fire department to evacuate the building before are nachos. I'm a definition of grace in the kitchen. "Whatever you have in the kitchen I will make it burn" is my motto. Plus I'm sporting quite an attitude to boot. "Make Zack a Latino" campaign. We can make it work!
3) Not really "lover". More "no feelings haver". Though technically I've worked on software for so long that hate is, next to sarcasm, my primary export.

Web on canvas and Dashboard widgets

2007-07-22T14:35:00.001+01:00

There are days when I do something quite interesting and in my mind I can almost see myself on a stage in tight, tight spandex pants, long hair, perm, cowboy boots yelling angrily "are you ready to roock?!". People cheering, babies laughing, women throwing their bra's on the stage. It's poetic. Then I remember that I'm a computer scientist and I snap right out of it. I go back to the life filled with math equations on napkins, sleepless nights in front of buzzing computers, stacks of books in corners and no spandex pants (although I can deal with the last one just fine). The fact that I hate rock lessens the blow, but it doesn't make it any less disappointing. So in those moments of sadness I blog, yearning attention and approval, so readily available on the internet. Cough, cough...

I was wondering how hard would it be to create a QGraphicsItem that uses QtWebKit to render pages on a canvas. The idea being that combining full blown canvas like QGraphicsView framework with web rendering engine would give us quite a killer combination. So I've sat down today and done it. At first I had to redo some of the rendering code in QtWebKit and once I was finished I had a QWebGraphicsItem that beautifully renders pages. It being a QGraphicsItem all the effects available to graphics items in Qt are available for free to it. So you can animate, scale, rotate, perspective-transform and do a whole bunch of neat effects on it for free. Once I've done that I figured that it's obvious that this is the best way of getting Apple's Dashboard widgets to work. So I've done that too. I quickly hacked up a class that reads-in Apple Dashboard widget bundles and can render them on a QWebGraphicsItem. The compatibility is not 1:1 quite yet, because some of the Dashboard widgets use JavaScript objects that I haven't implemented yet, like AddressBook object. To be honest I'm not 100% sure whether I want to implement them, I think we can get those things done a lot nicer, it's just a question of whether 1:1 compatibility with Apple Dashboard is worth the extra effort needed to make all those JavaScript objects work on KDE.
First a screenshot of one Apple Dashboard widget rendered and on top a scaled to half its size KDE homepage:

Now a Dashboard widget with a perspective-transformed dot.kde.org page. Since this is QGraphicsView I can interact with the item while it's transformed so I've selected some text on it.

Crackalicious. (no drugs were used while hacking on this, but I did touch myself a little after getting it to work). Furthermore (yes, there's more... what can I say, I'm a giver...) in QtWebKit we have this neat interface that allows you to inject QObject's into the framework as JavaScript objects at run-time, so adding new JavaScript objects is trivial and getting Opera widgets to work would be very, very simple. No spandex pants included though.

Scripter

2007-07-14T15:59:00.000+01:00

Before boarding a flight I'm eagerly awaiting the security presentation that is about to ensue. I figure that these people spent their valuable time learning how to point to the ground, back, forward and to the side and someone needs to appreciate that effort. During my last flight I even went ahead and tried to inspect my life jacket. "Tried" because as it turned out my seat was missing it. As the security announcement advised, I "calmly" informed the fellow sitting next to me that "in the unlikely event of a water landing" he's screwed because as a stronger man I'm taking his life jacket. This also prompted me to think about tools that make our life easier (just to clarify, when I say "our" I mean "my"). I've spent a little time yesterday creating a tool that will make my (when I say "my" I mean "our") life a lot easier. So today I wanted to tell him (when I say "him" I mean "you") about us (when I say "us" I mean "it").

I've spent a lot of time writing simple C++ applications to test out some kind of rendering algorithm. Internally we had a tool that automated a lot of it. The tool uses a very simplistic, reg-exp based language to specify commands. I wanted something more powerful. This is how scripter came to be. Scripter is a very simple application that uses QtScript's bindings to Arthur to do its rendering. It allows for rapid prototyping of algorithms and most importantly for me, quick testing of Qt's rendering framework. At first it was a whole IDE with its own code editor, very quickly though I decided to remove the editor and just make it a content widget that monitors the file it was opened with for changes. The reason for that is that I wanted to keep working in my own editor and just have a dynamic, visual preview of everything I was doing. So with Scripter one can be writing rendering code while the visuals effects of the editing are immediately visible. Here are two screenshots of examples included with it:

But the whole beauty of this application is ability to create animations, while seeing the changes done in real-time. I recorded two demos:

The first one shows me just playing around with an example. In this case it's a freedesktop.org clock.
The second shows me writing a simple animation from scratch. This one has an added benefit of seeing me hack in real-time, no copy&pasting, a little bit of chaos (next time I should probably figure out what kind of animation I want to do before start recording, but oh, well, live and learn). Fun. This one is 12mb though.

Scripter requires Qt 4.4. If you don't have Qt 4.4's snapshot it won't work. Get it from the SVN at labs.trolltech.com with :

 svn co svn://labs.trolltech.com/svn/graphics/scripter

Revelations

2007-07-08T15:34:00.000+01:00

Like many other geeky people I've spent the last week in Scotland. The insane abundance of overgrown egos caused wrinkles at the very fabric of weather conditions in Glasgow and it rained the whole week. It happened to be my second birthday in a row that I've spent on a KDE hackfest. If things continue like this Aaron will have to adopt me, because I refuse to marry him and we're spending way too many "family holidays" together to be "just friends".
I've been always highly supportive of the "Earth is the center of the universe" theory. I considered this to be a side-effect of the fact that I'm the very center of the creation. By association this small piece of rock has got to be in the smack-middle of the universe.
That is until I find a way of developing a dust-powered interstellar spacecraft (dust being the only material possession that I have at my disposal in numbers even remotely close enough to those necessary for intergalactic travel) and I leave this place in pursuit of happiness/aliens. Unlike all other people I don't really want to meet aliens or exchange knowledge/ideas with them, I just want to punch a foreign life form in whatever is their equivalent of a face. Stay with me here, because there's an elaborate reason for that: I'm spending a lot of my time talking to people and for the purposes of a story "I've seen aliens, met them and we chatted a bit about the meaning of life, technology, universe and then I got anal probed" makes a boring story. One that is so prevalent in Alabama. Now if I've met someone who has seen an alien, met an alien and punched it in the face - that person has got my full attention. A way better story.
But for now I'm stuck here, so I used this week to look over some of the graphics code that was written for KDE4. It looks pretty good. Clearly a lot of it has been influenced by heavy drugs and some people have got to be shooting it straight down their aortas for them to have that severe effects. I'm trying to figure out whether to write a FAQ or some scripts to clean some of the mess up. I've also done a little fun hacking. I added sample 3D plasmoids looking like this:

They work very nicely and taking that code allows you to write 3D plasmoids. The examples animate (pretty nicely I might add, but everything I do is at least "pretty nice" so that's a redundant statement). The code is in KDE SVN playground/base/plasma/applets/samplegl* module.

Since for some cards we still don't have terribly good 3D drivers I created a sample plasmoid that shows how to rotate it and have something shown on the back. The code is in the playground/base/plasma/applets/rotator. A movie with the rotating widget is here. And statically it looks like this:

With much love
Yours Truly: militant interstellar dominator (by day), graphics voodoo practitioner (by night)

Ghetto Trolls

2007-06-28T18:36:00.000+01:00

I'm trying to get my presentations for Saturday's Akademy conference ready, which is going really well. Let me rephrase - it's not going well, but I tremendously enjoy pressure and cookies. The latter having, unfortunately nothing to do with any of this blog. I'll be talking about graphics and linguistics and want to show some neat things I've been working on lately. Assuming I'll finally get those things to work the way I want them to. Which would be really good for the purposes of demos. Otherwise we'll enjoy some quiet time or start exchanging childhood stories. I've got a few good ones.
Speaking of horrifying experiences today was a sad day. If I had any feelings I'd be very sad. There could be serious tearing. Donald Carr, who's been one of the coolest people here at Trolltech, resigned and is leaving to the USA tomorrow. Together with Donald we formed the "Ghetto Trolls" interest group, in which we spent our time arguing over who's living in worse conditions. I slept on the floor and couldn't eat anything, he didn't have electricity. Tough call. Hopefully I taught him a little bit about graphics and he made me realize that buying two bottles of orange juice and milk in Norway is equivalent to half a sheep in South Africa and sheeps are a rare and precious commodity. Now, why would anyone want half a sheep, I don't know. I'm assuming it must be because I'm not South African. I guess it depends which half of the sheep we're talking about.

Anyway, here's a picture of the "Ghetto Trolls" and if you're coming to Akademy hopefully I will make it worth your time.

Mirroring widgets

2007-06-04T11:43:00.001+01:00

"The life of man is divided between waking, dreaming and dreamless sleep." or so it's written in "The Upanishads"... I wouldn't know because the cartoon version still hasn't been released and I refuse to spend even a second of my life pumping a stream of information into my brain that hasn't been properly sprinkled with commercials and product placement. Which reminds me: use Qt...

I can almost see you sitting at your desk with the same expression the great Plato had when he said: "What?" (not one of his greatest quotes, but I'm sure he said it at one point or the other). In my last blog I described how the engineering department at Trolltech spent the last few months fixing bugs in, what could be described as, a constant "waking" state. By natural progression the next Qt release is putting us in the "dreaming" state.

It's been a while since the last time that I've posted an example on how to do something funky so today I'll partially make up for it. I get a lot of questions asking me how to do something windowing system specific. People at the office can approximate the exact time of delivery of each one of the emails relating to that topic as the seismographic vibrations, originating in the vicinity of the area where the table meets with my head (in a repeated and aggressive fashion), cause ripples to appear in coffee mugs around the office. Hopefully today's example will satisfy the most vicious desires for X11 wackiness.

6'2" (height by association - as measured by the height of the author), weighting at about 139 lines of code (while wearing the license header), the undisputed (mainly because the only one) champion (questionably) of... well, nothing: QX11Mirror. QX11Mirror is a class that can monitor and return the contents of any X11 window in real time. So you could start your favorite media player, pass its window id to QX11Mirror and then render the contents half-the-size with perspective transformation. It would look like this:
One thing that you can't see is that the contents of the movie is updated while the movie is playing and the perspective transformation is animating. All of which is done in real-time. It's really cool.

The original reason for writing this, seemingly, silly example was not "making something pretty". Even though the inability to make applications look gorgeous is the number one cause of hair loss (as shown in a study by doctor "me". Note: "me" is not really a doctor. In fact "me" doesn't even fulfill grammatical requirements of the previous sentences.), which is number one reason for you not looking gorgeous and I'm a big proponent of having KDE developers look beautiful. "KDE - we got hair... In all the right places...". (I know... I'm as shocked as you are that I'm not being paid a zillion dollars to do marketing.) No, the original reason for all of this was to make web plugins behave a lot nicer. Currently the problem is that they don't compose correctly within the web rendering tree. So what I wanted to do is correctly fetch the offscreen contents of those windows, render them in correct stacking order and propagate the events back to them. This goes along the "make stuff work" ideology which I consider myself to be a big fan off. Oh, and here's Flash plugin rendering inside of a Qt applications (as always in my example, things are animating inside):
Oh, and the code is available at Graphics Dojo.

Keyhole

2007-05-30T18:05:00.000+01:00

Today's blog might sound a little muffled, that's because it's coming straight from the heart. Which is in direct opposition to all of the "What's Open Source community missing" blogs/articles, which are coming straight from a vastly less prominent body part. To not dwell to much on human anatomy, I'm going to move on to the main topic today which is peace, love and Qt 4.3. The first two are overrated and got their fair share of treatment in all kinds of literary works, therefore the only reasonable conclusion is that my perky-self focuses on Qt today.

A number of people surely have already pointed out in their blogs that Qt 4.3.0 has been released. The first thing you'll notice about this release is the version number. Rightfully so because 4.3.0 is the highest Qt version we've ever released. 4.2.0 was already taken and we felt very strongly about reusing a ".0". Although "13.13.0" was available we really came together as a team/body/unit/crew (pick one) to release 4.3.0.

Now, I'm not going to be doing marketing for 4.3.0 (mainly because others are being paid better to do that) or listing the "like totally awesome new features", what I wanted to do is present the perspective of people who actually spent days and nights working to make this piece of software the best they could. Whether from the loins of those geeks came something exceptional is a judgement call that I leave to you. This is your keyhole into our world.

The main focus of this release was for us the general increase in quality of Qt. In the darkness of our meeting rooms we were moving tons of paper, while from time to time lonely tears danced on our cheeks (due the fact that the light smoke coming from our pens and pencils was irritating our eyes). Immersed in this mysterious darkness, we sat and watched. The cracking of the projector, seemed to be the only noise that dared to challenge the insanable silence. We knew that we wanted to make people smile a little more with this new release. Very early in the release process we also agreed that shipping drugs with Qt was not an option. We turned for help to the happiness champions - Care Bears and Popples. We watched and analyzed. In the very end we decided that while we agree that Gi-Joe's are like totally cooler (the engineering department is unfortunately male dominated) we know what we have to do. We came to the conclusion that people seem to be a lot happier if things work the way they planned and there's no unpleasant surprises. That's what we focused on. Fixing bugs, making sure that things work the way they are expected to, all in all improving the quality of Qt. If you have ever spent extended periods of time just staring at the code and rerunning tests in order to fix bugs, you know it's a mundane process that takes a lot of concentration. This is what we've been doing for the last few months. Fixing bugs and running around screaming (a lot of screaming, not a whole lot of running) if someone broke one of the tests. Have you ever seen engineers play ping-pong after fixing bugs for weeks? Oh, it's quite a sight. A lot of raw energy (very raw, one could say that energy hardly touched by any kind of skill). Flying balls, paddles and often engineers were a common sight late in the evening (low flying engineers bring bad luck - especially if the flight schedule predicts a landing at "you").

No one is more critical of us than we are but we work together to improve all the things we don't like. While I was thinking about this today I couldn't stop thinking about Pythagoreans who despite achieving many great things, were often described as a group who cherished authority beyond anything else. That approach is completely different from any discussion we have here. Every argument is judged solely based on its soundness no matter who's making it. I think that what I'm trying to say in this, severely not hysterical, paragraph is that one thing you can be sure off is that every decision we have reached and every change we have made in Qt was not due to any kind of hidden agenda, religious beliefs or beauty of people pushing for it. It was done because 20+ engineers decided that the arguments for it are stronger than against it. I realize that due to the fact that we have those discussions at the office and in person, a lot of the transparency of them remains hidden behinds clouds for people outside Trolltech. We're working to improve the flow of the information from the heart of Qt's home to the outside and while we do that please remain assured that behind the clouds there's a world adhering to the strictest physical and logical rules and not an ocean of strings with muppets drowning underneath.

Having said that, we're very happy with Qt 4.3.0 so hopefully you'll enjoy it too.

If you want pure Qt release goodness with pictures of the chosen few who get to stare at Qt code until their eyes bleed make sure you read Girish's blog.

Browser plugins

2007-05-27T15:53:00.000+01:00

One of the perks of being a software engineer is that during the day you get to use such phrases as "oh, what the hell", "that's pure crack" and a large number of "expletive-deleted" without it seeming weird in any way. I can only feel sorry for doctors who rarely get the opportunity to scream "oh, what the hell" while looking at new patients. It's quite therapeutic.

I've spent a little time this week implementing support for plugins in WebKit Qt and the general situation of cross-browser plugins is the reason for the above, spot-on, observations. My blog is, of course, famous for hard-hitting political satire but not today. Today I'll talk technology. No politics, hardly any environmentalism, virtually no vegan propaganda - just straight to the point geek talk (well, "write" but "talk" sounds a lot better).

Given how important browsers are in our day-to-day computer usage it would seem that cross-browser plugins should be a well understood and in fact solved problem. Nope, that's definitely not the case here.

So while tapping your fingers on the messy desk, you roll your eyes and ask "so zack, what is wrong with browser plugins?".
The role of zack - young, careless and wild wacko is played by critically acclaimed me. The role of "you" is played by "you" and "you" really need to step up because you're not convincing anyone right now.

Currently cross-browser plugins use a very sexy (assuming of course that you're heavily into s&m) mix of Xt and another toolkit of their choice. The usage of Xt is just an utter disaster. In fact mixing event loops in any application is a cause of many subtle problems. George had the best idea when he implemented netscape plugins in an out of process application for Konqueror. It's really the only thing that makes sense.

In the Konqueror when a page has a plugin, an external application, the plugin viewer, is started. That process in turn loads and initializes the actual plugin and via DCOP informs the browser what is its window id. Once the hosting browser knows the window id of the plugin, it can XEmbed it. The neat side-effect of this approach is that if a plugin misbehaves one can kill it without any damages to the current browser session (besides the fact that the plugin doesn't render anymore).

The new plugin standard tries to use XEmbed all way. Unfortunately it assumes in-process communication between the browser and the plugin which again is a bad idea. It's a bad idea because it removes this neat concept of an "event loop" from the equation and assumes that whatever event-loop the plugin uses is the same as the one hosting browser is running. Which in turn doesn't do wonders for the whole "cross-browser" aspect of plugins (as long as the definition of "browsers" includes at least two entries and at least one of them is not Firefox).

So lets say you'd like go nuts (like young people tend to do) and display a slider in your plugin which, of course, good, god-fearing people never do. But lets push forward with this highly dubious example and say that maybe you wouldn't want to go all out and display, maybe not right away a slider but some kind of an animating widget. Well, you're pretty screwed because you need the event-loop native to the toolkit in which the widget is implemented to receive the timing events.. Just ask SwfDec guys. They wrote this awesome piece of software, then wrote a browser plugin using, what claims to be, a cross-browser standard just to find out that in that particular standard "cross-browser" meant that it works in Firefox and Firefox. So SwfDec guys found out that Konqueror is not part of that set (unfortunately they also found out a few other things).

So how could we fix it, without having a large groups of grownups sharing some quiet time in a corner, while the sound of weeping fills the room. Hosting plugins in an external process has clear advantages. To the list that I mentioned above we can add another point - by running a plugin in an external process plugins could easily specify what kind of an event loop they need. If your plugin needs Glib's event loop, GTK+ container would be started, if your plugin uses Qt, Qt container would be started (which might or might not use Glib's event loop in Qt 4) if your plugin needs Xt then you should be punched in the face and it all would just work. Containers would announce their window id's through DBUS so that hosting applications could XEmbed them and the world would be a better place (because clearly "browser plugin woes" are occupying one of the top spots on the list of "what's wrong with the world", right between "dust" and "rich people").

At the moment I'm trying to see how feasible it is to lay npruntime implementation, which serves as a bridge between the plugin and the hosting browser on top of DBUS. If that works then we can move to running all plugins as external processes. Which means:

plugins taking a lot of CPU can be stopped/killed without affecting the browser
when a plugin crashes the browser keeps running without any problems
external event loops don't pollute the browser
a lot of code for plugin viewers could be shared (besides networking interface) between browsers on systems running X11. Which means that for a change plugin working in one browser would run in all of the others using those containers.

This is basically what we're doing in WebKit Qt. I just really want a simply working plugin infrastructure for browsers. I'm not a man who holds grudges, but last year I didn't get what I wanted, even though I've been exceptionally good, so this better work (last year I wanted to win the lottery. Sure, some might point out that I made it exceedingly difficult by not playing (did you see the odds?) but lets not get bogged down by minor details).

Oh, and a mandatory screenshot of the Diamond plugin in QtWebKit.

Mesa and LLVM

2007-05-24T13:46:00.000+01:00

I've been toying for a while with the idea of rewriting programmable pipeline in Mesa. The most obvious reason is the fact that fragment shaders are absolutely crucial when it comes to modern graphics. We use them extensively in Qt and I'm using it all over the place in my special effects library. As those small (mostly GLSL based) programs become more and more complicated a need for an extensive compiler framework with especially good optimization support becomes apparent. We already have such a framework in LLVM.

I managed to convince the person I consider an absolutely genius when it comes to compiler technology, Roberto Raggi to donate some of his time and together with me rewrite the programmable pipeline in Mesa. The day after I told Roberto that we need to lay Mesa on top of LLVM I got an email from him with GLSL parser he wrote (and holly crap, it's so good...). After picking up what was left of my chin from the floor I removed the current GLSL implementation from Mesa, integrated the code Roberto sent me, did some ninja magic (which is part of my job description) and pushed the newly created git repository to freedesktop.org.

So between layers of pure and utter black magic (of course not "voodoo", voodoo and graphics just don't mix) what does this mean, you ask (at least for the purpose of this post). As I pointed out in the email to the Mesa list last week:

it means that Mesa gets an insanely comprehensive shading framework
it means that we get insane optimization passes for free (strong emphasis on "insane". They're so cool I drool about being able to execute shading languages with this framework and I drool very rarely nowadays... And largely in a fairly controllable fashion.)
it means we get well documented and understood IR,
it means we get maintenance of parts of the code for free, (the parts especially difficult for graphics people)
it means that there's less code in Mesa,
it means that we can basically for free add execution of C/C++, soon Python, Java and likely other languages, code on GPU's because frontend's for those are already available/"in work" for LLVM. (and even though I'm not a big fan of Python the idea of executing it on GPU is giving me goose-bumps the way only some of Japanese horror movies can)

I think it has all the potential to be by far the best shading framework in any of the OpenGL implementations out there. Now having said that there's a lot of tricky parts that we haven't even begin solving. Most of them are due to the fact that a lot of modern graphics hardware is, well, to put it literary "freaking wacky" (it's a technical term). We'll need to add pretty extensive lowering pass and most likely some kind of transformation pass that does something sensible with branch instructions for hardware that doesn't have support for them. We'll cross that bridge once we get to it. Plus we'll need to port drivers... But for now we'll bask in the sheer greatness of this project.

Ah, the git repository is at http://gitweb.freedesktop.org/?p=users/zack/mesa.git;a=shortlog;h=llvm , Roberto and I have tons of unpushed changes though . Of course this is an ongoing research project that both Roberto and I work on in our very limited spare time (in fact Roberto seems to now have almost what you'd call a "life". Apparently those take time. Personally I still enjoy sleepless nights and diet by starvation patched by highly suspicious activities in between. Which by the way does wonders to my figure and if this is not going to work I'll try my luck as a male super-model) so we can only hope that it will all end up as smoothly as we think it should. And in KDE 4 most graphics code will be able to utilize eye-popping effects with virtually no CPU price.

Folding

2007-04-08T12:40:00.000+01:00

One of the more frequent questions that I see is how to do interesting transition effects for applications. So here's how, first of all prototype your algorithm. Here we're going to use a page folding to visualize transitions as turning of pages. So that it looks like this:

Then we figure out how to adopt it to application. The trick is how to get contents of an application without extra repaints. In Qt the contents of top-level's is buffered and there is a private but exported way of fetching that contents (not fully platform independent at the moment). The example #2 shows how to grab the contents of the window without extra repaints and copies and use it to implement the effect, so it looks like this:

The forms were taken from Kate config dialogs so they're real config pages (hence also why they're, well, not too pretty). The effect is fully animated so to get a better idea of how it looks you'll have to look at the ogg file provided here. It's also worth noting that this effect is very efficient and works smoothly with virtually 0 cpu usage.

As mentioned in the last blog, to see more examples and code for this one visit Graphics Dojo. The above mentioned examples are at the examples 2 page.

Graphics Dojo

2007-04-03T15:56:00.000+01:00

I have been traveling and working a lot lately. I was attending Bossa Conference, which was the best organized Open Source conference I had the pleasure of attending. I got to hang out with people I normally spend very little time with like Rasterman. Raster and I had some time to sit down and talk about graphics, Qt, Evas, chickens (don't ask), him being a crab killer (again, don't ask) and just have a lot of fun. Chris explained a few things about LLVM to me. It's always fun to hang out with Marcelo as well. All around it was a great time.

I went to spend a little time with my "family" in England last week which was also just amazing.

The most important news though is that thanks to amazing work that Marius did on labs.trolltech.com I've got a Qt focused graphics corner. Being a Graphics Ninja, I've decided to call it the Graphics Dojo. The first action point was the release of some of the examples that I wrote in my spare time. You can take a look at an overview here or go directly to page 1 or page 2. There's a few ones I've never shown before, like Mario Klingemann influenced Ring of Fire.

I hope that the "Graphics Dojo" and the articles which I'll be posting on it will help everyone write better looking interfaces.

Reflections

2007-03-09T10:13:00.000Z

In the spirit of my never ending "pimp your Qt application" series comes another example. This time, "how to make iTunes-like album selector". It's funny how much attention this widget got. I looked at it yesterday on one of the Macs at the office and just implemented it. I probably should make it a view for a list model but for now it's just a simple widget. It runs at perfectly smooth 60 frames per second while utilizing ~7% cpu on my 3GHz Pentium4 with NVIDIA GeForce 6600, so by no means a monster of a machine. Oh, and of course this is all done with pure Qt. Reflections are actually a vector effect, so they would work equally well for any vector based graphics (by using the same code as this example, you can reflect your svg's or even whole widgets with no problem). Mandatory screenshot:
And as with every animated example a movie (again, framerate of the screencapture does not come close to the real world performance) is available here . Finally the code is available here.

Gradient bounds

2007-03-07T12:02:00.000Z

The most unfriendly thing about rendering gradients with Qt has been the fact that you had to specify gradients in coordinates of the shape they were to be rendered on. It wasn't ideal especially for all applications which included any kind of animations or were rendering large number of items because it meant that the gradient had to be individually created for each and every one of items/frames. I've fixed that two days ago by adding a coordinate-mode property to QGradient, which now accepts ObjectBoundingMode. Object bounding mode, just like in SVG, means that the gradient coordinates are percentages of bounding box of the shape that the gradient is about to fill. So all the coordinates are between 0 and 1 and Qt automatically adjusts the bounds for gradient when it's being rendered. This makes it possible to easily use QGradient's with QPalette. An example where I'm drawing a bunch of rectangles and animate them along while the gradient is set only once with (0,0, 1, 1) coordinate box (meaning starting at the topleft and ending at the bottom right corner of each rectangle).
And since it's an animation (including a widget show/hide effect) here's a movie showing it in action.

Browsers, performance and interventions

2007-02-25T21:29:00.000Z

This week I beat WebKit Qt's rendering into shape. I rewrote the theming and canvas code.
It works so nicely that I'm actually pretty happy with it. The rewrite helped me fix issues with statically positioned elements (which just didn't work on a scrollview/canvas combination I did before). Due to which my blog finally looks and behaves correctly as seen on the screenshot above. That plus scrolling is about 10x faster and you never see gray areas on scrolling as you did before.
This week George Staikos has been here in Oslo to work with us on the networking code. George and I have been friends for five or six years and he has this nasty habit that forces me to start an intervention and try to get him off it. What I'm referring to is the fact that George has been Canadian for, well his entire life, and it is my professional opinion (but I'm not a doctor) that he needs to move on. I'm not sure in which culture it is customary to bring Snapple ice-tea to your friends when you come to see them but we need to change him to that because he definitely didn't bring me any this time and that's just rude.
Going back to work, I'm sure Lars will blog about the networking magic they did so I'll keep my mouth shut. Once the code they were working on will be ready (which should happen within next week or two) and we'll start using in WebKit, we'll make the transition and start using WebKit Qt based browser on a daily basis. So we're close which is pretty exciting.

We have also started optimization run for Qt 4.3. My grand plan is to make sure Qt 4.3 is 2x faster in general rendering code than Qt 4.2 was. I have a list of algorithms to shave and rewrite over the next few weeks which will be rather challenging.
By the way of performance some people noticed that Qt OpenGL in recent snapshots with Antialiasing turned on is actually slower than it was in Qt 4.2. It's because of an experiment that we're trying on. We're now using GLSL to antialias primitives. Of course it's a lot slower than the old code but produces very high quality results. I don't really like it though because the performance hit is just too big.

Core dump

2007-02-09T21:13:00.000Z

Today I'm joining the rapid fire blogging squad.

Roberto is moving back to Italy and last Wednesday was his last day at the office. Roberto is one of my best friends at Trolltech so I was incredibly bummed out by his departure. The office won't be the same place without him. Plus who will help me hack on a prototype GLSL jit engine that I wanted to do some research on? (rhetorical question, I'd only trust him with that anyway)
Roberto is also, by far, one of the best hackers who ever worked on KDE so I'm very excited to say that Roberto and Trolltech came to an agreement by which Trolltech will sponsor Roberto for two days of the week to work on KDE.

This has been a bug fixing week so I didn't have any time to work on WebKit. Last week I did manage to finish off integrating SVG into WebKit Qt
I also played a little bit with combining native Qt application rendering from within WebKit. One can embed a whole native Qt window inside an html frame and then control the Qt application from javascript (signals, slots and properties of the window and its children are dynamically exposed). Here's a native Qt application (my transform example) rendered inside the advertisment frame on cnn.com (sorry for the depressing image).

For the last two days I've been thinking about adding basic high dynamic range color support to Qt. QColor is already suitable for it and extending it wouldn't be a big issue. QColor's internal representation is a union of unsigned shorts. Basic HDR support requires 64bit, where every channel is a so-called, "half". Half values have 1-bit sign bit, 5 exponent bits, and 10 mantissa bits. It's a format used, among others, in OpenEXR and Cg. In fact OpenEXR project provides a C++ half implementation under a BSD-like license. Along a CIELAB colorspace support that I wanted to add to Qt for a while now, support for HDR would open a slew of new possibilities. On a silly, desktop level - imagine a desktop background the is light proportionally to the sun-light that you'd see for your currently configured timezone. On a more basic level HDR is pretty much essential for any kind of image processing/editing nowadays. I'll most likely write another blog dedicated to color-theory and things I'd like to fix/implemented in Qt that are related to it. Google returns hundred thousands of HDR images so if you'd like to see what people do with it, you won't have to look for long. One of my favorite examples is New York at night by Paulo Barcellos Jr that can be seen on fickr here.

During lunch at Trolltech there's only one kind of yellow cheese available. Climbing to the highest-levels of good-faith and stupidity I assumed the cheese would absolutely have to be vegetarian (many cheeses is still made with natural rennet, which is taken out of lining of young cattle's stomachs). Yesterday one of the people pointed out that it most likely isn't. Today morning I called Tine, which is the biggest dairy producer in Norway (and one whose cheese Trolltech buys) to ask them about the situation. The result was, that of course, the cheese is not vegetarian. If you're a vegetarian, do not eat cheese or any products containing it while in Norway. For me the bottom line is that for the last few months I've been having non-vegetarian cheese for lunch putting me right now in levels of pissed off/disappointed that I've never been at (you know that silly questions about graphics you wanted to ask me? you might want to wait with that a few days).

Generating SVG's with Qt

2007-01-26T13:56:00.000Z

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.

The magic of animation

2007-01-22T16:23:00.000Z

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.

More on WebKit Qt

2007-01-18T11:16:00.000Z

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.

OpenVG

2007-01-17T01:16:00.004Z

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.

More boolean ops

2007-01-14T22:39:00.000Z

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

2007-01-14T01:23:00.000Z

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.

Blend modes and dash offsets

2007-01-09T22:09:00.000Z

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

Rotations

2007-01-05T18:21:00.000Z

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:

California and Cheese

2006-12-15T17:50:00.000Z

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.

Resolution independence for icons

2006-11-22T13:50:00.000Z

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

WebKit and new examples

2006-11-20T12:50:00.000Z

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.

Text on a path

2006-11-07T16:28:00.000Z

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.

Expressing myself

2006-11-02T13:10:00.000Z

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.

GLOverlay

2006-10-27T14:34:00.000+01:00

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

Disappointing

2006-10-24T10:09:00.000+01:00

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.

Benchmarks

2006-10-23T09:38:00.000+01:00

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.

ARGB windows

2006-10-19T11:33:00.000+01:00

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.

Bands

2006-10-07T15:52:00.000+01:00

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.

Perspective transformations in main

2006-10-06T18:52:00.000+01:00

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

Perspective transformations

2006-09-21T13:48:00.000+01:00

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.

Glucose and graphics

2006-08-15T19:15:00.000+01:00

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.

Magic

2006-08-08T17:01:00.000+01:00

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:

Artist creates a gui in SVG
Developer does logic in his/hers favorite language
Application loads the SVG and does selective rendering (as described in the last blog)
----- magic -----
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.

Shadows

2006-08-04T17:59:00.000+01:00

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

2006-08-04T16:44:00.000+01:00

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.

SVG on graphicsview

2006-08-03T10:23:00.000+01:00

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.

Compiling SVG to C++

2006-07-31T20:11:00.000+01:00

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

2006-07-31T15:20:00.000+01:00

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.

Effects and Qt Jambi

2006-07-28T14:55:00.000+01:00

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.

Hardware accelerated polygon rendering

2006-07-27T00:56:00.000+01:00

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!

Animation and layout on paths

2006-07-25T13:49:00.000+01:00

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.

Tessellation again

2006-07-24T14:40:00.000+01:00

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.

Project Unity and eye-candy

2006-07-12T20:39:00.000+01:00

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

Fun with curves

2006-07-01T09:10:00.000+01:00

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

In Norway

2006-06-13T16:34:00.000+01:00

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.

Toronto

2006-05-25T02:32:00.000+01:00

The last two days were a lot of fun. Yesterday I went to Toronto for a meeting with ATI mobile team. The trip itself was pretty entertaining. I have a lot of things on my schedule so just five days ago I managed to give a definite answer to the question of whether I can come to Toronto. US Airways likes to overbook their flights, so after getting to the airport at 9am yesterday I found out that I can't get on my flight to Buffalo because it was full. I was supposed to meet up with David in Buffalo so we had to quickly change our plans and I took a flight directly to Toronto. Once I got there David and I ate lunch at a very nice Indian place and went to meet ATI guys. We talked about OpenVG, OpenGL ES and their mobile lineup. Getting to meet those guys was a lot of fun and the discussion was just great. Very productive for me. At the end we all went to grab dinner at a place called 'Spicy Momma'. That's one hell of a name for a restaurant! They're definitely not false advertising too (referring to the "spicy" not "momma" part). Two of the guys from the ATI team was vegetarian so we were able to team up and get lots of vegie food.
Since we haven't booked a hotel, after dinner we had to go and look for a place to stay. We found a hotel fairly quickly. We also got some cookies from the girl working at the reception desk (she baked them herself and in this case that was a good thing) and my "happy life" receipt has 'free cookies' very high up on the list, so that made me pretty happy =)
Today the weather was wonderful so we stopped on our way back at the Niagara falls and decided to eat lunch at a place with a great view. It's one of those places that just makes you feel better (even being a city boy myself). Fun.

Improving reality

2006-05-22T05:41:00.000+01:00

Historically there has been a big gap between real world and computer interfaces. Things behave one way in real world and our desktop applications behave another. I'd like to see us moving to some extend away from that. I've been talking about physics simulations becoming more widespread on the desktop last summer and ever since I went through a lot of them. Over the weekend I started looking into moving to a real physics engine. Open Dynamics Engine is, as far as I know, the best one. Problem there is that for desktop apps cloth, rope and water simulations are way more useful and currently it, still, takes too much effort to mimic them.

I'd just like to have a model, where moving from reality to the computer interface doesn't involve much of a mental switch. Or at least it's very natural. I'm not saying that it should behave exactly like something out there but it needs to be a lot more dynamic than what we have right now. Which is really, what we refer to when we talk about "organic interfaces".

There are some things that are spot on, that improve on what you normally get in real life and make computers act as what they really are, tools. Yesterday I was writing something by hand, thinking "man, this would be so much easier with a spell checker". You know you got something right, if you really miss it while performing a similar activity outside the computer world.

Talking about spell checking I played a bit with Sonnet over the weekend. I've been handling KSpell, then KSpell2 for a while and then I just grew tired of it last summer (for various reasons not really related to the code itself). I've been toying with the idea of full linguistic framework for a while. Besides spell checking we're talking about grammar checker, dictionary, thesaurus and translator. Sonnet is just that - full linguistic framework. I'd like to have all those functions available to all KDE applications. Being able to take a step back, look at all the problems I've seen and complains I got over the years from both users and developers and just sit down and rework the whole framework to fix them is great. Linguistics is fascinating and for some reasons there's not a whole lot of people who'd want to deal with it, at least not as far as its desktop usage goes.

Random thoughts

2006-05-17T00:12:00.000+01:00

I just remembered that I never mentioned how great Brazil was. And I definitely have to mention the fact that I've been taught how to play "Svn Trunk" which is the best card game I've ever seen. I believe the game is known as "Trucu" in Brazil, but since I've learned it, it's now internationalized and it's been renamed ;) For KDE 4 I'd like to have a common card canvas that things like KPat and in future "KDE SVN Trunk" can share (with some really great winning animations because unless there's a neat animation at the end, winning is pointless).
I'd like to make card decks stylable via SVG as well.
See this?
If that's not the proof that I'm the greatest international Trucu player I don't know what is...

Oh, and today my softrucks arrived. It's been raining a bit lately and I have too many skateboards around to not be able to break something daily on one of them. I'll sit down later tonight to install them on a board and will give it a spin. So if you won't see anything interesting happening graphics wise in Qt/KDE/X in the near future it's because Softrucks don't work that well and I'm most likely in a hospital =)

On a sidenote, a new version of Jahshaka (repeat quickly four times for an additional point bonus) has been released. That application is very impressive.

Precision

2006-05-15T19:48:00.000+01:00

One of the most difficult problems of computer graphics today is producing truly robust algorithms. Working in floating point coordinate system introduces a lot of subtle problems. Computational geometry approaches the problem from two directions:
1) Implementing algorithms on top of rational numbers.
2) Introducing rounding phases to algorithm, usually in a post processing stage.

For example lets look at a pretty popular example, based on the one from Hobby's paper. In this example we have three line segments with one intersection between them. Now if we round up the intersection to integer coordinates two new intersections are introduced - ones that are completely incorrect. Although we don't round up that heavily the following example scales into infinity as you uniformly divide coordinates by the same number.

There are two main reasons why this behavior is so undesirable for graphics.
1) It produces obviously incorrect results.
2) Optimized algorithms often break down due to those inconsistencies.

The first one is actually less important - on this scale the degeneration of our results is likely to produce errors that won't have too significant effects on what you see on the screen. Two is a lot more severe. For example a lot of the more popular geometrical algorithms includes a step of finding segments containing a point. Assuming that a segment has floating point coordinates and the point is, as well, in floating point coordinates - the containment test will very quickly break down as the limited precision will hit the computations. So there's no way to reliable perform that test, due to which all those algorithms will simple fail. As a result, an incredibly small rounding error will likely cause a complete failure of an algorithm and because of that small error you won't see any results on the screen. That's a serious problem.

Going back to the solutions to this problem. John Hobby wrote a paper entitled "Practical Segment Intersection with Finite Precision Output". Algorithm which he introduced in that paper has since been named "snap rounding". Numerous papers have been written since about this algorithm, some of the better ones include "Iterated Snap Rounding" by Halperin and Packer and "Snap Rounding Line Segments Efficiently in Two and Three Dimensions" by Goodrich and Guibas. The basic principle of this algorithm is very simple; every event point is computed within some tolerance square. Every tolerance square has its middle computed and all events that we encounter, whose coordinates fall withing already existing tolerance square are "bent" in a way that changes their coordinate to be equal to the middle of the tolerance square. This technique works surprisingly well.

The second method, often employed by professional grade geometrical software, involves replacing float/double by a custom "rational" number class. They produce mathematically correct results, which is ideal. The reason why we can't really even consider them is that they're about 30+ times slower than doubles.

Now the reason I went on this rant is that I've been testing results of my new algorithm for rasterizing polygons, which involves decomposition, and even though on paper the algorithm was always correct and the unit tests were all passing, the algorithm was falling apart in some cases. I've spent a while going through my intersection detection code, snap rounding implementation and couldn't find anything. Then I looked at some of the data files I had and they were only in limited precision of .001 which is not even close enough to being precise enough for floating point intersections/coordinate systems. Feel my pain =)

The basics

2006-05-11T04:14:00.000+01:00

If you look at the frameworks we have and the way 2D graphics is heading, it's obvious everything we render is really a polygon. Rendering any other primitives is more an optimization than anything else. There's a few reasons for that. One of the more important ones is the complexity that is introduced with stroking (I'd crack a joke about difficulties of stroking here but lets skip that). For example lets look at the rectangle underneath. We're using a linear gradient stroke on it:

What should be obvious is that it's actually two shapes. We have the fill but we also have the stroke . Here be dragons, because the stroke is not a rectangle anymore! It's a polygon with hole! So rendering this seemingly simple shape suddenly becomes rather complex. Now a lot of people will notice that a simple hack could be to draw two rectangles
as in : first and then with the ending result being . Then of course you need to special case because if the fill has an alpha you will end up with which is cleary incorrect as now the fill seems to have a gradient... Further more if we're overlaying shapes that optimization is right out. So on this extremely simple example we can see that special cases are accumulating very quickly and the code gets really convoluted very quickly. The question becomes whether making the code so ugly and error prone (especially as the number of conditions which affect what kind of rendering path the code takes, accumulates) is a good trade of for small optimizations.

Without the support for stroking and alpha-blending, things tend to be easy. Unfortunately the reality of the fact is that both are hard requirements for any decent rendering framework. So for all of you who've been wondering why the new rendering frameworks are slower than the code you were using so far to draw rectangles and lines, now you know. In Qt we try to make people happy by having all those special cases, by reverting back to using Xlib whenever possible and, of course, by improving the frameworks but it's just a lot of work. I'll try to go over some of the things I'm doing with graphics in Qt, KDE and X.