Michael Dominic K.

The great demise of the file

2009-07-30T16:51:32+02:00

I recently had an HDD failure and had to dig deep into the filesystem to recover some data. Pain in the ass. While navigating the crummy, hidden folders to recover weirdly-sounding filenames… an epiphany hit me — The File is dying. The metaphorical role of a file is dying. The file used to be the beginning and the end — it contained an essay, a book, a photo, a song, a todo list, a business card… to give you a document I would put the file containing it on a disk. Or on a usb stick. Or I would send it via email.

The piece of information was the file and vice versa: the file was the piece of information.

But not so much anymore. The email program does not operate on files. Neither does the twitter client nor the todo-tracking application. They store data in well-hidden databases in the internal directories that we’re not supposed to look at. And quite rightly — because there is nothing to see there. Looking at the huge photos.db one might only wonder where his dog photos are.

Sure, the applications still give you a way to share things and take them out of the storage. You can export a contact out of your address book as a vcard file. But the role of The File here is slowly being reduced to a role of an intermediate storage medium. The business card is temporarily put in the .vcf file before it gets injected into somebody else’s database (another address book?).

As more and more applications operate on databases, the computer is becoming a monolithic black-box that “has things”. How exactly (and where) the data is stored is becoming less clear. The application and the interface becomes united with the user data. It becomes one.

And if I own your user interface, I own your data.

Not so good

Databases as storage mediums solve problems by creating new ones.

I've got a directory on my disk that contains stuff related to my company – documents, invoices and some other content which is still mostly file-based. But I also have a todo list related to my work things and some notes about current projects. These are stored in two separate applications that operate on their own storage. So now: if I copy the whole company directory to another medium I'm not effectively copying everything. This trivial issue is extremely confusing for most users who are not familiar with the application internals.

There are other technical issues as well. Apple’s Time Machine is a good example here. It’s a great backup service but it was designed to operate on files. When a file is modified locally Time Machine copies it to a backup storage. This way it’s fast and incremental – the changes are small and isolated. You can even browse various versions of the file from the past. But if your “file” is a monolithic 1GB notes & pictures database (it’s “everything”) the whole concept is blown away (ie. Yojimbo example).

Meet the service

Not surprisingly, we stopped talking “files” long time ago. We’re talking “services” now. In some cases it works great: in example, I don’t exactly care how my Linux, Mac or iPhone email client store the mail data. I don’t care because the central storage (my IMAP server) is out there and it has a clear, well-defined service API. It’s transparent.

Too bad that email is a lonely exception here. Quite a significant portion of the data generated by us today is put in totally black-boxed, closed services that are very open to take our data but not very keen on giving it back in a sane way. This is often a deliberate business practice but sometimes – a lack of thought. Social services like Facebook come to mind. Google does not score better either.

The great escape

Should we stop defending the lost trenches of The File? Should we fight for more open services? Should we get concerned about freedom of data storage? Should we acknowledge that open code is not enough? Should I buy a new guitar?

Could be. Remembering the hard lesson from the web: convenience always wins over integrity.

Midgard ObjectiveC bindings

2009-03-26T08:48:32+01:00

I'm glad to announce the first (experimental) release of a project I've been working on recently — Midgard bindings for the ObjectiveC language. Those bindings are for the upcoming Midgard2 — the brand new fresh version of the library.

Midgard2 is an Open Source Content Repository and it provides an objectified view to the data and services surrounding it. At the basic level it abstracts the database access (SQLite, MySql, PostgreSQL) but this is only where it all starts. Serialization & replication, managing own storage objects, multi-process access to data are all covered. The fully object-oriented (GObject-oriented) API allows you to focus on the data, not the database syntax.

For many desktop software developers, database technologies belong to where they belong — the web alone. This is not necessarily true. As the software & services en masse move to the web, the need to integrate the cloud with the desktop becomes indispensable.

Midgard is quite ready for that — it based & engineered fully on the top of the desktop (Gnome) software stack. Being highly modular and having very little dependencies it scales from a note taking application to a full-blown CMS system.

ObjectiveC bindings

The Midgard objc bindings come in a shape of a standard Mac installer. The package (which requires a Leopard+ system) installs a Midgard private framework which allows to develop Midgard applications using XCode. The applications built this way have Midgard embedded dynamically into them — they don’t require any extra libraries/components on the target machine.

3G in Orange - now with less fat

2009-03-12T15:41:34+01:00

Note: As many people have reported to me, the practices described below seem to be pretty common among mobile operators in Europe. To some extent the proxy can be bypassed — at least on the desktop.

Alternate Internet

Over the past couple of years a lot of effort and resources were invested into selling various variants of the ‘alternate Internet’. ‘Alternate’ meaning here — ‘Almost like the real thing, but…’

A prime example here is WAP. WAP was supposed to be this ‘Internet for mobile phones’ thing where providers would create an alternate WAP content of their websites. It ended up just being a synonym of Internet banking for geeks (at least in Poland).

Another example of an alternate Internet is what most mobile phones present when you type a url of a modern web page. You are supposed to believe that the crappy-formatted, layout-broken Frankenstein on the screen is the Internet.

It’s not.

In the context of the two examples above it’s not surprising the understand the sudden interest in mobile browsing when devices (ie. the iPhone or the Nokia tablets) started providing real, first-class Internet experience. People like the real thing, not the cheap imitation.

3G in Orange.pl

The worst kind of alternate Internet is the kind that’s advertised & sold as “the real thing” but it’s actually not. I'm talking here about what Orange does in Poland on it’s 3G network.

And what it does is: all images (jpg, png, gif) downloaded via the http protocol are being dynamically recompressed to their lower-quality representations. In other words: all images are being accessed through a proxy which serves them in a significantly reduced quality.

Here’s a more concrete example to illustrate how a Dilbert strip looks like on the iPhone. The left image is what you see when accessing it through the Orange 3G network. The right image is the original picture — as you can see it when accessed via wifi.

It’s not hard to see the differences. The gif image on the left has a reduced color palette and the gradients look pretty cheap.

There is no way to avoid the recompression on Orange 3G in Poland. It seems to be happening on a binary basis (the proxy detects headers?). Sadly — it also affects all other applications accessing image data via http — not only the browser.

Below is an example of the Twitteriffic application on the iPhone. Again — left is 3G, right is wifi. Observing the avatars one can easily see that the pictures (jpg’s) on 3G (left) are quite blurry (compressed) when compared to the originals (right).

Unfortunately, this is not all. Additionally to recompressing the images, Orange is injecting a 12kb piece of javascript code into all html documents. This code (which looks like originating from Sprint) is adding a right click option to images to “improve their quality” (meaning: load the original image). Obviously, this only works if you’re in a web browser and if the web browser is a supported one (sorry, no iPhone support).

Mind boggles

The whole idea is so broken that it’s even hard to start explaining all the problems with it. I could go on enumerating all the issues but I’ll just focus on two fundamental ones.

Firstly — the idea is not fair because customers are not being told the whole truth. They think they’re buying Internet access while in fact they’re getting lower-quality Internet access. It’s obvious why the recompression process has been put in place — lowering the image quality/size gives a fake impression of faster download speeds (this is by far one of the primary factors of the connection).

Secondly, I see a significant security/privacy infringement in those actions. Owning the pipe does not mean you can alter the content passing through it. In the corner cases there might be digital rights embedded in the pictures. But even in the standard case — silently injecting a piece of runnable code that gets executed on the user’s machine is, as far as my logic goes, highly illegal. Or at least — very evil.

The ability to recompress the traffic implies the ability to monitor it in the first place. What else is Orange in Poland doing with the traffic data?

I'm not sure if I want to know.

New Wild

2009-03-04T09:55:46+01:00

I've been spreading the news here and there for few days now but it’s time to make it official.

After quitting Novell I decided to take the plunge and try something I've been long waiting for… – go self-employed and start own company. New Wild is just that — a young company offering services related to mobile software, web and unix(ish) engineering. Additionally (and that’s new) it’s also about cocoa — both mobile (iPhone) and desktop.

One part of what I'm planning to do at New Wild is pushing my own software projects — first of which I hope to be announcing quite soon. Another part is helping others to make their ideas happen. That’s more commonly known as contracting & consulting.

The decision to start New Wild is not something that came out of a profound business analysis and huge preparations. Quite the contrary — like every important decision it came out of an impulse. The very basic promise behind New Wild is that after spending the last several years working at big companies I know how to provide some real value to people who want to make their software ideas happen.

I'm open for business!

Quicklook for markdown

2009-02-10T18:20:00+01:00

Update: My changes were merged into the original code.

As services such as DropBox become more mature, it makes again sense to store simple textual content (ie. notes) as files — instead of going for Everything Buckets. For simple text files DropBox provides an actually working synchronization, offline access to the data and a pretty good integration with the native platform (be it GNOME or OSX).

I usually store my notes and other simple text snippets as markdown-formatted plain-text files. The simple markdown format is exactly the amount of syntactic sugar I need to get along. Additionally, the markdown format is supported by all popular editors (gEdit, TextMate, vi…) and many web-writing platforms.

On OSX by default the markdown files (.markdown) have two limitations when compared to standard (.txt) files:

Can’t be Quicklook'ed
Contents are not indexed by Spotlight (can’t be searched)

Installing an editor such as TextMate gives support for the .markdown extension but does not solve either of the above problems.

Phil Toland did a great work and created a markdown quicklook plugin. I took his code and improved a bit on it. In particular, my version does 3 things more:

Uses discount C library to render markdown (instead of calling-in Perl)
Styles the output a little bit (Helvetica vs. Times)
Adds spotlight indexing

To get going you need to install the compiled binary plugin in ~/Library/Quicklook/ (create if it doesn’t exist).

Strategies for tagging content

2009-01-15T19:50:25+01:00

Damn. I was trying to find this website I knew I bookmarked in my delicious bookmarks months ago. I even remembered why I got it bookmarked in the first place — it had unique design & colors, something inspiring for future. So I tried searching for design, colors, pretty, cool… lots of results, no luck with the site I was looking for. Made me think.

Now, I'm not actually browsing my delicious library that often. I'm mostly dumping stuff there and forgetting about it. So I started thinking — if I'm using it that scarcely and I can’t find what I'm looking for anyways, what’s the point of doing it in the first place?

Or maybe I'm just tagging the information wrongly? Let’s have a bird’s eye view at various strategies for tagging stuff.

Tagging for contents

Perhaps the most obvious way to tag is to describe the contents of the tagged object. In example, I'm applying tags julia to photos where my girlfriend is present. Similarly I'm tagging photos that contain me with mdk tag. The use case here is obvious: having this tags in place I can easily create a view (search) containing photos with both julia and mdk — the set of photos where we’re together in one picture.

It’s quite easy to overdo it. I've got some photos with tags such as winter, summer… what I was thinking? Photos in general have information about the time when they were taken — adding those tags is just duplication. Another example of over-commitment is ultra-fine-grained tagging. Some people on Flickr do it all the time describing with tags everything present on the photo.

If the picture is about a dog, the dog tag most likely makes sense. And if the picture is about a city street and the dog is just happening to be in the frame…

Tagging for content is not a universal solution to every data description problem. Sometimes it doesn’t work too good. Consider an example of a todo managing application where you can tag individual items that you need to get done. You might have an item there saying: “pay the phone bill”. Tagging it with bill, phone or even money is not that useful. It’s very unlikely you’ll use any of those keywords to look up this item in future.

Tagging for context

Instead, you should tag for context. If you’re using internet banking, your context in the above case is: banking. Next time you will be doing the internet banking chores you can list all the items with the banking tag and handle them in one go. That might include an item called “change the mailing address for the credit card statement” which also belongs to banking but is not directly about bills and money. Except for the context.

There is a creational difference between tagging for content and tagging for context. In the first case (tagging for content) we’re applying the tag to name (describe) something already existing in the tagged object. Ie. a person, following the photo example I've given earlier. When tagging for context, we’re adding new information to the target.

Another example: an “order new window blinds” todo item. When tagged with phone it gets a new meaning: the blinds need to be ordered via phone. Holding the phone in our hand is the context to get this thing done.

Tagging for feeling

Tagging data with information about the contents (tagging for content) creates fairly objective (universal) meanings. A cat tag on a photo has a quite obvious (and familiar) meaning to everybody. Adding contextual information using tags (tagging for context) still remains fairly objective, however the tag describes the tagger in relation to the tagged object. Ie. a phone tag on a todo item describes my relation to the object. So, we could say: the tag becomes a carrier of a personalized information.

Now, moving to the most subjective way of tagging — tagging for feelings. In this case we “stamp” the content with our feeling towards that content. An obvious example: putting a cool tag on a photo. Or on a file.

In this variant it’s sometimes useful to invent new categories and custom words which have a personalized meaning. An example: I might use a tag whichcraft to tag all the stuff related to my past girlfriends. This obviously has a meaning only to me (and maybe to others when explained).

Data tagged with feelings becomes more concrete and full — but only for the original tag author. Therefore, it makes most sense in cases where personal use and personal organization are involved.

The original problem

Coming back to the original problem of tagging a bookmark (an interesting site) for future reference — this use case requires me to use a mix & match of all of the above three tagging methods.

Firstly, I want to apply content tags: I want to use ruby and webdev if the website is about ruby and web development. Secondly, I want to apply some contextual information: ie. toread tag if I want to read the website later. Thirdly and lastly: I want to tag it with awesome if the website has great design and colors.

Since the context and feeling tags are “private” tags (they have meaning in relation to me) it makes sense to prefix them with a special character.

In the end, I might end up with a list of tags like this:

ruby
webdev
@toread
@awesome
@rainbow

This way I can search for @awesome meaning specifically things I marked as awesome, not random content which just happens to have the word. And that — in most cases — does the trick.

Hell in Wrocław

2008-05-07T23:35:15+02:00

I’ll be attending and giving a presentation at Libre Graphics Meeting this year in Wrocław.

Title: “Programmer’s hell: working with a UI designer”.

Time: Friday, 14:25.

Lot’s of fun guaranteed, come to feel some hot flames.

Nordea sucks

2008-04-18T17:13:43+02:00

I rarely feel like blogging about personal stuff but today my patience finally went off. Since I switched from Finnish Nordea (which provides excellent service BTW) to a Polish one I'm having only problems. Not the only one being that for two months now they’re unable to send me a banking card for my account.

Today, however, something much more scary happened. When trying to send them email (using their own banking account messaging system) I got this nice failure:

Warning: pg_exec() [function.pg-exec]: Query failed: ERROR: syntax error at or near 
"u" at character 2101 in /www/pglib/libs/c_db_postgres.php on line 106
error: query(): ERROR: syntax error at or near "u" at character 2101 
INSERT INTO cms.tabmail ( sto, ssubject, scontent, sheaders ) VALUES 
( 'solopl@nordea.com', 'produkty i usługi bankowe', 
'Temat: produkty i usługi bankowe...

As garrett pointed out — of all the places you want to see this kind of error, your bank is not one. For those unfamiliar with the problem — it’s esentially an Sql injection bug which, in short, means that your system security is a piece of shit.

Moonlight flicks

2008-03-04T20:46:00+01:00

Miguel has a good status update on Moonlight. Complementing that I recorded a few simple demos presenting current state of our Moonlight trunk.

While talking to friends at FOSDEM I noticed that while everybody pretty much heard about Moonlight/Silverlight, not so many people have actually seen it in action. This is understandable — at the moment building Moon from source is not trivial. Hopefully those little videos will help a little.

Microsoft showcase — a website collecting links to various Silverlight-enabled pages and web apps. Users can browse sites and rate them. Built with Xaml and Javascript. Watch demo / Download high-res avi.

Podium — A dynamic mashup of various news related to US election candidates. Shows some more advanced text-flowing and formatting capabilities. Again — Xaml and Javascript. Watch demo / Download high-res avi.

Surfaces — A very simple surface manipulation/D&D example. Clutter has a similiar demo. Watch demo / Download high-res avi.

This is only a small selection of Silverlight-enabled sites which was easier to record (ie. not using media playback). A bigger list we use for testing is available at Moonlight 1.0 test sites.

Changes of "N"

2008-01-31T23:27:47+01:00

Just a small status update: I recently quit Nokia and joined the new old faces at Novell for a brighter future. Cheers guys! Helsinki folks — don’t despair, you still have Meritahti.

Also, like last year, I’ll be coming to Brussels for FOSDEM this year. Let’s meet!

On GNOME mobile

2007-11-27T00:37:10+01:00

Murray writes about GNOME mobile:

The is currently most obvious in the GMAE (or GNOME Mobile) group, which Jeff insists on controlling, which the board allowed despite knowing what would happen. After almost two years it has produced nothing more than a press release announcing its existence, and that happened six months later than the members wanted.

I don’t think Jeff is to be blamed here first. I don’t know about other players involved but I personally feel that we at nokia simply didn’t put enough effort into GNOME mobile.

This is to be read carefully. We did put a lot of serious work (directly and indirectly) into GNOME and various GNOME mobile components. A lot of those efforts are invisible. Where we so far failed is to make this work standardized, reusable and transparent — what (if I understand correctly) was the original goal of the GNOME mobile.

Hopefully this can be changed. But I don’t think it’s fair to blame Jeff for this particular issue.

GL colorspace conversions

2007-11-17T14:38:05+01:00

A fellow sushi-lover MacSlow was blogging some time ago about various cool things that can be done with OpenGL and video. Mirco writes:

“The remaining things to implement are: using fragment-shaders for the colorspace-conversion too, hooking up some implicit-animation love for switching between different videos.”

I'd like to pick a little bit on the first part of his todo (using hardware-accelerated colorspace conversions).

RGB vs. YUV

Computer graphics is an RGB-world. Every point/pixel on the screen is represented by an intensity of red, green and blue. Any visible color can be coded with a combination of those three values. RGB is the way to specify colors in various drawing API’s, HTML color coding, etc. However — RGB gamut is not modeling well the way human eye works. Our perception has certain characteristics that are not well expressed in the RGB universe. For example — a human eye is very sensitive to changes in lightness (intensity) but is not very keen on noticing differences between dark shades of blue. This is where YUV colorspace kicks in. YUV (just like RGB) can be used to represent any color but the representation is more interesting from the video compression point of view — which is mostly about benefiting from the imperfections in our sight.

In YUV colors are represented by luminance (Y) and two chrominance components (U and V). For example, in RGB the white color is represented with [1.0; 1.0; 1.0] triple while in YUV it would be a [1.0; 0.0; 0.0] set. In a way YUV predates RGB and computers as it’s the format used in the analog TV (the cable essentially contains YUV signals at different bands).

Conversion

The reason why YUV is important is that it’s used as the native format in video compression. The raw (fast) output we get from a modern video decoder is a (some kind of) YUV buffer. YUV can be fairly easily converted to RGB (and vice versa) but it comes at a price. Since it’s a per-pixel operation the processing time gets steep fast. With high-resolution DVD-quality video we’re talking about ~10 million points per second. With numbers like that any operation becomes a bottleneck. Since in the end we somehow need to get the RGB representation, the only thing we can do is delegate the conversion from the CPU to the graphical hardware.

Overlays to the rescue

The traditional way of dealing with this problem was to use overlay capabilities of the graphics board. Overlays are around since long time (way longer than 3d acceleration) and are fairly well established. Overlays, being a hardware capability, allow us to “take over” a certain (more or less rectangular) area of the screen and dump there some pixel data — bypassing the traditional drawing pipeline. The data pushed can be in YUV format. Modern graphics hardware supports all popular YUV formats and the conversion is handled by the hardware.

The limitation of this approach is that the video (overlay) is not really a first-class citizen in the UI pipeline. It’s something that is (simplification here) “burnt over” other elements of the UI. We can’t transform it, we can’t use it in the 3d/2d effects pipeline and it’s problematic (slow) to draw over it (think transparent playback controls drawn over playing video). Overlays are more than enough for implementing standard desktop players but are useless when we want to do more fancy stuff.

For the fancy effects we want to use video as a native texture/source image while still delegating the colorspace conversion to the hardware. OpenGL API/pipeline does not support YUV formats but we can easily fix that with custom GPU code.

YUV formats

One problem with YUV is that it comes in different flavors (formats) and there are quite many of them. FourCC website has a good overview. The good thing is that there are just a couple of popular formats used in practice and the huge rest is mostly exotic or legacy.

Let’s take a quick look at the popular IYUV/I420 format we get from a DivX decoder. It’s a planar format which means that (unlike most RGB formats) the components are not interleaved. We can graphically represent an I420 buffer:

The buffer contains the full Y plane followed by two U and V planes. And here comes the rub — the U and V planes are sub-sampled at half the resolution. So, assuming we’re dealing with a 400x240 video we first get the luminance (Y) plane at full resolution (400x240) followed by U/V planes at half the resolution (200x120). Again, this is because the information about the lightness of the picture (Y) is more important than the information about the chrominance (“colors”) of the video. In other YUV formats it’s common to assign less bits for the U and V.

GL implementation

In the GL implementation we particularly want to:

Avoid any data processing on the software side
Avoid extra mem copies/unpacking of the data
Benefit from the hw-accelerated scaling/filtering (linear, cubic, etc.)
Get a high-quality image

To achieve this we need to use three GL elements which are not part of the GL 1.x standard but are commonly available as extensions — multitexturing, fragment programs and rectangular texture.

Multi-texturing allows us to use three different textures (Y, U and V plane respectively) as the source for the output image. A custom fragment shader executes the proper blending function to create the RGB data out of the YUV source. Rectangular texture is necessary to be able to use non-power-of-two resolution source as the texture.

For the textures/planes we use a GL_LUMINANCE 1-byte texture format. We also need to use a separate set of texture coordinates for each plane due to the resolution differences. The texture-filtering step (ie. during scaling) happens before the shading step so in the shader we automatically get properly filtered data (each texture separately).

For other YUV formats (ie. the interleaved ones) we need to do a bit more work. As the UV components are usually scattered across many triples automatic GL scaling/filtering will destroy our data before it reaches the shader. To counter that we need to first draw (with hw-accelerated conversion) to an off-screen FBO/texture and reuse that data as a native RGB texture for further rendering in the UI/scene. Alternatively one can use pbuffers (less optimal performance-wise).

Source code

Here is an example program + source which renders a sample video (Nokia n810 ad) using GStreamer + hardware-accelerated colorspace conversion and some effects. The example uses a rather primitive way of syncing video using timers. The proper way would be to write a decent GStreamer video sink or extend the existing GL-sink to use fragment programs. This approach would prolly be the right way to handle video in ie. clutter.

A rendering of the program output just for reference (might not show up in RSS, full resolution video can be downloaded here):

Curvy blues

2007-10-27T18:40:45+02:00

I was looking in the past (and some more) at various solutions for efficient hardware-aided curve rasterization methods. Those ideas mostly focused on using the graphical hardware for accelerating the geometry generation process. But what happens, when we completely skip the geometry generation step? Even more blazing performance and totally resolution-independent rendering. Thanks to some tips by Jon and interesting math discussions I had in the past weeks, I'm glad to present my current thinking.

Quadratic curves

Quadratic curves (second-degree polynomials) consist of a starting point, an end point and one control point. Such curves cannot self-intersect nor inflect. The representation of a quadratic curve is a parabola, a straight line or (a degenerate case) — a point. Quadratic curves are not the most popular ones in modern graphical packages. Cubic types (more about them later) are the basic unit of notation. In example, cairo doesn’t provide direct quadratic API. It’s understandable as any quadratic can be trivially represented in a cubic form. However, since (due to their limited properties) quadratics are usually much faster to process it makes sense to look at them separately. Quadratics are part of the SVG standard and have some interesting uses — including TrueType fonts (which are represented only with 2nd degree curves) and Flash (which uses quadratics as the native curve representation and represents cubics by subdividing them into quadratics). Few examples of quadratic curves:

Now, let’s look at how we can hook up the programmable GPU hardware to rasterize quadratics. The first observation is that the three points describing the curve form a triangle and this triangle covers the whole area of the curve. Triangle is the most basicrasterization primitive in modern graphics hardware. Let’s assign two texture coordinates (v and w) for each of the three points. We’re going to use [0.0; 0.5] , [0.0; 1.0] and [1.0; 1.0] for, respectively — the start point, the control point and the end point.

As the triangle is being rendered the hardware will interpolate v and w across the three vertices. For each pixel belonging to the triangle we get a unique, interpolated v and w texture coords pair. And here comes the crucial part — as the actual “texture” for this triangle we use a dynamic fragment program that evaluates the following expression:

If the expression evaluates to true, we pass the pixel. If not, we discard it. What we get is:

Here is a shader implementation that does this operation. As we see, the rastered picture represents the curve we’re trying to visualize. To be precise, we get the fill for the curve. If we replaced the < sign with = sign we would get the actual stroke (the green line). As we zoom towards the curve, the shader generates more pixels giving a more accurate representation. A true resolution-independent rendering.

I'm going to come back to why this is so fundamentally amazing later on, but now let’s move on to the cubics.

Cubic curves

Cubics (third-degree polynomials, the bezier-curves) are a bit more complex. They consist of two arbitrary control points plus start/end points. As a result a cubic can self-intersect, loop, inflect or cusp. Beziers are the thing in vector drawing and most of the data we get to render these days (icons, buttons, UI elements…) are sets of shapes defined by cubic curves.

For blazing-fast rendering of cubics we’re going to use a similar approach that we used for quadratics. Since cubics consist of four points we need more than a single triangle. Actually, depending on the control points set we’re dealing with, we need 2 or 3 triangles. In other words — we need to triangulate the points. In this case (very fixed) triangulation is trivial and essentially we can discover the case we have by doing a few dot products between the vectors of the control points.

Since we’re dealing with a cubic equation, we need three texture coordinates per point (that’s perfectly fine with the OpenGL API). Let’s call those three coords: v, w and t. In our fragment shader (implementation here) we’re going to evaluate the following expression:

And the last hard part — unlike quadratics, for cubics there are no static texture coords to use. We need to calculate them separately for each curve. The method to do that is a subject for a separate article, but it’s enough to say that it’s a fast fixed-time operation that involves few matrix multiplications. Essentially we need to put the control point coordinates in a matrix, move it to power basis and analyze the determinants. Depending on the number of square roots, we have one of the few distinct cubic-cases which further dictate which v, w, t coords to use. Those computations could be put in hardware-accelerated matrix pipeline but I haven’t found that to be critical enough to do so.

In the end we end up with:

Using this technique we can render any cubic at any resolution in a fixed time.

Practical results

Two following screenshots (click for bigger versions) show sample renderings (a font glyph and a mono-project logo) obtained using this method. Shapes consist of roughly 30 cubics/lines. The first figure represents the inner-mesh hardware-accelerated triangulation. The second one — a rendering of the curve data. By combining the two we end up with a final mask for the shape. This method works for any polygon including complex self-intersecting concave/convex shapes.

Why it’s cool

Traditional approaches to curve rasterization usually require recursive subdividing of the curve towards a certain level of line-approximation or reaching a pixel-precision. The complexity/processing time grows exponentially and the result might be not correct. With the approach presented above we achieve high quality by keeping the mathematically-correct (not compromised) information about the curve till the very last step — the rasterization . The precision of the final image (output) is only limited by the resolution of the display system, not the implementation. The complexity of the algorithm is linear and the processing time is only constrained by the pixel fill rate of the GPU board (that value approaching hundreds of millions for modern equipment).
From my experiments, attaching the (presented) fragment shaders to the triangle rasterization process has no any impact on the performance. In other words, it seems that on modern hardware rendering a solid-filled triangle is equally fast as rendering a triangle with a simple shader.
As we’re not generating/storing any extra geometry data and just using two (max three) triangles per curve, the memory requirements are minimal — even for extremally complex shapes.
By using some additional extensions (such as a compiled vertex array) after the initial pre-calculation step we can completely move the geometry data to the GPU unit and render by just invoking display lists. In this case the expose events theoretically come cost-free for the CPU.

Smart curve rasterization is the first step towards efficient drawing API implementation. By combining the solution with additional dynamical GPU-programmable pipeline elements (gradients, triangulation, anti-aliasing, multi-sample rendering) we can achieve blazing-fast vector-based drawing tool. This is my current approach towards building a new OpenGL-based cairo backend. World domination follows. Obviously.

Update: for better math overview check this article by Loop & Blinn. It’s a good starting point even though it’s not complete and has certain mistakes (check comments).

Nokia N810 announced!

2007-10-17T19:41:48+02:00

It’s announced, we did it!

Ari has some more gory details about what’s new and cool. From the toolkit point of view one thing worth mentioning is that we’re now running the full gtk-2.10 stack in Chinook (the OS release powering the n810). Now, there are two things to that:

The bad thing is that due to the consolidation efforts the API compatibility is broken. Let me stress that again: if your application uses UI, it won’t run at all on Chinook without (often trivial) modifications. We have documents and tools to assist you in porting the applications. So go ahead, download Chinook beta and update your app — there is a lot of cool stuff in maemo garage that we need to make run on Chinook also. You can nag us on the IRC channel or mailing lists for help on specific issues. We’ll help.

The good thing is that we’re now very much closer to the gtk upstream and you can expect the toolkit stack to behave in a much more sane and predictable way. We’ll also now be able to actually track the API stability more closely.

As Ari also mentioned, Chinook is going to be available for n800 also. While it’s common for companies to provide firmware/bugfix updates for legacy hardware, it’s pretty rare to get a full new OS release + new features for free. I'm glad we did it since… well… it’s exactly the right thing to do!

Service interrupted

2007-10-14T19:10:28+02:00

I finally manged to go through the maintenance pain and migrated my blog to a completely new system and design. I put effort into making sure that all links & serivces work like they did but in some corner cases the RSS feed might stop working for you. If that happens and you’re still interested in reading, please re-subscribe.

I'd also like to appologize to all people who commented and put their opinions on my blog in the past despite the commenting system being completely bolox. It’s finally fixed now and works as expected.

Sorry for the inconviences. More interesting service to follow.

Vector drawing: OpenGL polygon tessellation

2007-08-16T09:50:39+02:00

After having looked into the hardware-accelerated bezier curve computations I checked something more difficult and closer to the reality: hardware-accelerated arbitrary polygon tessellation with OpenGL. This topic has been covered by Zack some time ago, spawning a lot of flame (as most of the GNOME vs. KDE performance comparisons do). All benchmarks are flawed, of course.

Test case

I used same setup as with my previous experiment. This time I measured the real framerate to make sure that no anomaly occurs due to GL async API. Each frame of the test consists of random flowers being drawn to screen with random parameters. Each flower is a polygon outlined by eight bezier curves. The flower shape is not special/optimized in any way. Any closed polygon made out of any number of curves could be used for this purpose. Summarizing:

Thinkpad t43 with ATI mobility x300 card (fglrx proprietary driver with GL support)
200 flowers being drawn in each frame
Each flower has a random position, rotation, scale and fill
Fill is a linear gradient from a random RGBA color to another random RGBA color
640x480 space is used
Same set of random data was used in both examples
Anti-aliasing was turned on
cairo 1.4.10-1 was used in the cairo version
Source code for the programs

The OpenGL rendering seems to be a pixel “fatter” than the cairo version (prolly a bug in my code). The GL output seems to be slightly brighter blended. I guess the significant difference between cairo x surface performance and cairo image surface performance also comes from the intensive blending.

Optimizations

Some optimizations in the GL code could be made to speed up the code even further:

Computed bezier vertices could be stored (even as compiled vertices, if available) to skip the need to generate them twice for the anti-aliasing run.
As in my prev example, vertex shader could be used to generate bezier points. That would require a different way to get the polygon extents though.
The quality of the curve approximation (detail level) doesn’t seem to affect performance much and could be increased.

Algorithm

To render the polygons I'm using a variation of the stencil-based algorithm described in the OpenGL Red Book. It relies on a 1bit stencil buffer, which is commonly available. The basic method is:

Disable framebuffer, enable stencil buffer & stencil testing.
Draw triangle fans for every vertex in the polygon with an odd-even stencil flip rule.
Enable framebuffer, disable stencil writes, keep stencil testing.
Draw anti-aliased outline of the polygon but only where the stencil bit is not set (those are the anti-aliasing artifact pixels that theoretically doesn’t belong to the shape).
Switch stencil test rule to pass only when stencil bit is set.
Switch stencil write to zero the bit when passed (spares us a separate stencil clear call later on).
Render the actual polygon shape with ie. quad.

Worthy benefit of this approach is that it fits (works with) all the standard OpenGL matrix transformations, depth buffer testing, texturing model etc. It can be easily extended with 2d boolean operations. The CPU is not performing any calculations (except the original path calculation which can be offset to the GPU with a vertex shader).

Once in a while I'm getting questions how did I implement hardware-accelerated video color space conversions in Diva. I'm going to write a bit about that soon along with some boolean operations coverage.

Vector drawing: OpenGL shaders and cairo

2007-08-06T14:52:34+02:00

The mystery

Some time ago I had a chance to talk to Zack Rusin about the differences between QT and the Gnome/Gtk drawing stack. Zack was showing some impressive visual toolkit demos using tiny fractions of the CPU horse power. One of the subjects we started arguing about was using GPU hardware to perform tessellation — as opposed to cairo, where tessellation happens always on the software side. The idea seemed tempting though the practical benefits were unclear to me.

During GUADEC I poked a few people about the possibility of using OpenGL and shader programs with cairo to perform hw-accelerated tessellation. I got some constructive and interesting (yet discouraging) feedback about the problems and complications related to this approach. A lot of those (highly valid) points are summarized by Tim Janik in his blog. Still, the possible gains/performance improvements were highly unclear.

Investigation

I therefore decided to write a small benchmark to see what kind of speed differences we could possibly be talking about. To see if the game is worth playing at all. As the testbed I've chosen one of the most fundamental bits of the vector graphics — a bezier curve drawing algorithm. I implemented a 100% hw-accelerated version as a vertex shader program running on the GPU. I compared it against cairo software version in two scenarios — using xsurface and image surface. The following setup was used for the test:

Thinkpad t43 with ATI mobility x300 card (fglrx proprietary driver with GL support)
A time to draw 100 random (pre-generated) bezier curves was measured
Curves were randomized in a 640x480 space with a random width (1-10pixels) and a random color (red, green, blue, alpha)
Same set of random curves was used in both examples
Anti-aliasing was turned off
An best of 3 test runs was taken
Source code (CG toolkit from NVidia is needed to compile the shader program)

The rough-rough result of the test is that drawing using hardware opengl tessellation is 30 times faster than current software cairo implementation. By overlying the resulting images in ie. GIMP one can see tiny pixel differences between the two implementations (cairo implementation begin prolly more accurate) but essentially it’s the same thing. The OpenGL shader implementation is not optimized at all and could be made faster by using a geometry shader instead of a vertex shader.

Not only about speed

Using GPU to perform things normally happening on the CPU has one additional advantage — it frees the processor to do other things. In my setup, with the cairo implementation drawing random curves as fast as possible, I can get a ~10fps animation (100 curves per frame). This keeps the CPU busy at 100% and the framerate will drop as soon as CPU starts doing anything else.

With my 100% GPU implementation I get around 400fps and the CPU usage never goes beyond the 30% threshold (lots of it being the random-number generation I presume).

Caveats

OpenGL shader program support is not yet a commodity, even though it’s coming fast even to the mobile space (ie. MBX chip having vertex shader support and the SGX chip having a full set of pixel/vertex/geometry shaders support).
As Tim pointed out, OpenGL implementations vary and per-implementation fine tuning might be in order
To efficiently use shader programs one needs a full OpenGL-based drawing stack
Shader programs + math + drawing algorithms are hard
OpenGL drivers suck on Linux

I still think that the results are interesting though. I quickly hacked another shader implementation to draw solid-filled bezier shapes (more about that soon). The performance differences seem to be even bigger. My gut feeling here is that the programmable hardware drawing might be the only way to go for the resolution-independent fully vector-drawn UI’s. Especially on the mobile where the CPU power is scarce, it scales badly, and everything that doesn’t throttle the processor means longer battery life.

GUADEC 2007

2007-07-12T17:42:14+02:00

I’ll be attending GUADEC this year in Birmingham. During the tutorial day (Friday) I’ll be giving a practical introduction to the maemo UI and showing some key differences from the full-blown desktop GNOME interface. If you’re an application developer and you'd like to learn few new quirks about making your software feel responsive and look good on the mobile — please do come.

There is quite a bunch of us from nokia coming to the event including a strong representation of our magnificent three-letter tookit team starring luc, tko, fer, xan and mdk. Great chance to poke us about our future plans regarding hildon, bitch about sardine and discuss some revolutionary UI ideas you might have for the internet tablets. “Hildon — now open more than ever!”. Ehm.

See you in the UK.

Chapter #1 in which we meet Graff

2007-04-23T17:14:22+02:00

Long time, no news.

I'm working now on a (new) set of libraries called Graff. Graff is a lighweight high-performance graphics rendering library. I guess it falls into the category of canvas — as currently discussed on the gtk mailing list. It’s a bit more generic though and focused on providing ways of animating graphical elements over time. It knows about motion paths, timelines, animating parameters, etc. The use case here is building new rich custom UI’s, providing a building-block for higher-level toolkits and abstracting hardware-specific quirks. It provides a basic model-view-controller environment with the UI elements (“faces”) being cleanly separated from the “motors” driving them. “Touches” provide event sources.

Graff can currently render using two runtime-selectable backends — a hardware-accelerated OpenGL backend or a software-only driver. The software backend is extremelly highly optimized using all the ugly demo-scene tips&tricks straight form the ‘90ties. It performs suprisingly well and the demo applications mentioned below can actually run good on our existing hardware (nokia 770, nokia n800).

Speaking of demos, I made a few simplistic test applications to sketch the idea of what Graff can already do. Video recordings available below. It’s a work in progress, early on.

Image viewer: a basic image viewer controlled with thumbs.

Dancing emotes: an example showing objects running along morphable paths.

Scrolling list: contact list with inertia scrolling.

Drag: trivial drag and drop with some smooth blending.

The image viewer example uses Jakub’s nice photos. Icons come from our awsome Tango artists.

Fosdem 2007

2007-02-22T15:01:10+01:00

There is a few of us from nokia coming to fosdem, Brussels. Catch us to chat about gtk, hildon and maemo. Or we’ll catch you.

I also released nflick 0.4.0 — a flickr browser for the maemo platform. Binaries for scirocco and bora can be found at the usual place.

Main changes are:

Adding hw-keys navigation to fullscreen view
Pressing “escape” key while viewing a photo will return to the photo list
Worker dialogs have now proper transiency so they don’t block whole device
Other dialogs have now proper transiency too
Fixing the bad-paging bug for good

Maemo theming

2007-02-13T15:23:55+01:00

A bit old news, but Tuomas recently released a new version of his awesome plankton theme. Judging by the comments on his blog and the screenshots posted on planet maemo, It looks like the theme is liked and appreciated.

I also find tigert’s theme aesthetically pleasing and nicely-balanced. It reminds me of a well-formed piece of metal that just feels good in the hands. This is, quite unfortunately, in contrast to default n800 stock themes that remind me of disco mirror balls and DDR.

I sometimes have a feeling that the psychological effect of good theming artwork (understood as well-drawn artwork) is underestimated. After all, this is what the user of the product is going to be living with on a daily basis. It’s the face of the device. It can cover-up for many shortcomings of the software or badly expose them — very much like a pretty-faced girl can often cover up for a plump figure (it doesn’t seem to work the other way round, does it?).

For developing the themes we created a system that decouples the layouts from the actual graphics. The layout contains the common gtkrc styles and other internal bits shared among all themes. The graphics consists of a single template file that can be easily handled by the artist. A set of tools can be used for various helper tasks.

This dual system is very much similar to the libraries vs. applications in software development. Library (layout) contains some common bits shared among all applications (themes).

The only things missing in this system is some documentation — so that someone can actually use it. Coming soon.