Last 5 Posts from 2007/June

Ottawa, here we are!

After 24h travel (Recife to São Paulo, then to Toronto, then Ottawa), Marcio, Aldenor and I arrived. We plan to join other attendees at Vineyards bar tonight, let's see who we find there.

They say it's hot, but Recife, even in winter, is much more hot than here, at least here is kinda dry.

Ottawa, here we go!

I'm heading to Ottawa Linux Symposium, my plane leaves in a few hours!

It's my first time in Canada, any suggestions for 2-3 spare days there? I'll stay from 26-June to 3-July.

Edje demo on N800: application launcher mockup

This is a demo I wrote today to demonstrate Edje running via a 60 line python script. The edje file itself is about 190 lines and kind of simple, yet complete in features.

Code can be found at http://www.enlightenment.org/viewvc/e17/proto/python-efl/python-edje/examples/evas-demo/

EFL on N800: packages and video!

As promised, packages for efl-core, python-efl-core and expedite!

This is expedite running on my N800, movie by Kenneth and myself.

I've setup a repository at http://www.gustavobarbieri.com.br/e17-n800/ with ARMEL packages: expedite "single click" install, efl-core and python-efl-core, libraries should be installed from Application Installer using "red pill" mode (they're not user-visible) or command line:

echo "deb http://www.gustavobarbieri.com.br/e17-n800/ bora free" >> /etc/apt/sources.list
apt-get -y install efl-core python-efl-core

I've some code examples at https://garage.maemo.org/svn/maemo-efl/examples/ and http://barbieri-playground.googlecode.com/svn/efl-tests/, Kenneth should post some others soon.

Evas on N800: blazing fast!

After some time working on 16bpp engine for Evas, I finally managed to get something working, and working really fast!

The code, which I've already commited it to CVS, does transparency, scale, colorize, operates on images, rectangles and fonts (gradients, polygon and lines are postponed due reduced usage).

Those interested in porting apps written with Enlightenment Foundation Libraries can start to port, since I've also made it available from Ecore_Evas. [if you are such interested guy, let me know]

Sorry for no videos, but I have no camera in hand today, maybe tomorrow I can post one. In meantime, you can get your scratchbox and compile it straight from CVS:

cvs -z3 -d :pserver:anonymous@anoncvs.enlightenment.org:/var/cvs/e checkout e17
compile e17/libs/evas and e17/apps/expedite, run expedite -e x11-16 to use my engine.

Now observer at FSFLA

Last week I was invited to become an observer of Free Software Foundation Latin America and I did accept.

Observer are not meant to do much, basically track the mail list (one more, oh god!) and provide feedback, getting used to their work flow so maybe you can turn into a more useful member if required.

"But you're hacker, WTF you'll do there, waste your code time?" you may ask (I asked that myself). Well, I'll try to keep focus on SW-related things instead of political issues I really dislike. FSF is about software in the end, and one of the few organizations that have some power to help us hackers... just hope that discussions were like those technical I was used to :-(

Evas now using rectangle split and merge!

As you might know, I'm working on getting Evas running as fast as possible on Nokia N800 but for the last 2 weeks I was being annoyed by a problem related to selecting areas to get updated by X11... I think some improvements now!

Every scene manager or drawing canvas, in order to be fast, must not redraw or ask the underlying system to redraw parts that didn't change since last iteration and we shouldn't draw the same area twice (if it's opaque drawing).

This can be solved by splitting rectangles so overlaps are removed, but this can generate a lot of rectangles, and since you have to communicate with X11 and even do some operation on this rectangles yourself, the more rectangles, the worse...

So you also need to merge neighbor rectangles, maybe let some rectangles overlap, if this area is not that big... or even merge rectangles that are not exact neighbors but have an acceptable error if you get their bounding box.

Problem: complexity of these algoritms are quadratic, at least if you compare on 2-by-2 basis.

In order to avoid this, Evas did a really nice trick: use a boolean matrix to represent the screen segmented in tiles (8x8 by default), when you add some rectangle, mark with "True", when you delete, mark with "False", when you need to discover rectangles, walk the matrix and as soon as you find a horizontal "True" span, you walk next lines to see if you can make this rectangle taller. This makes things really easy and complexity is linear on screen size ((width * height) / TILESIZE²).

On PCs, with huge data caches and enhanced branch prediction, this is really fast, but on N800, OProfile points both evas_common_tilebuf_add_redraw() and evas_common_tilebuf_get_render_rects() as time consuming. Problem is that although complexity is O(n), n = (800 * 480) / 8² = 6000, and we walk this amount even if there is no rectangles to paint! If you have the full screen to render, you'll walk it twice, so 12000 iterations.

As usually we have small amount of rectangles, and usually these overlap, we can get these merged and n will be reduced, with O(n²) worst case but something around O(nlogn) for common cases not being so bad.

So after discussing and drawing many ideas with Chenca, we found some good speedup cases and I wrote a small test in Python (pygame test), then in C (sdl test) and then moved it to Evas. Rasterman did some tests and he liked it, so he accepted my patch and code is already in CVS, it's used by default but you can have the old code by commenting out "#define EVAS_RECT_SPLIT" from evas_common.h.

I'm still looking for improvements and speed up changes to this algorithms, ideas?

Code can be downloaded from: http://barbieri-playground.googlecode.com/svn/rectangular-areas/ (SVN)

More details:

  • I keep rectangles in an unordered list, so yes I do compare rectangles that are distant on screen;
  • We've already considered using some smarter data structure, like R-Tree or Quad-Tree, but probably they would add more overhead than it worth. Probaby finding ways to simplify rectangles and keeping number of rectangles low is better (try to use bounding box more often);
  • I want to implement some checks to avoid generating 3 splits on fuzzy split, if one split is to generate 3 new rectangles, it's better to invert the order and generate just 2;
  • I want to avoid rectangles with Height/Width >> 1.0 to overlap others, overlaps just worth to rectangles with small height;
  • Evas implementation downsize resolution in order to help number of rectangles being small, to avoid 1px rectangles and to keep buffers aligned (my focus is 16bpp system, so 2 bytes per pixel, 2 pixels is 4 bytes, N800 memory alignment).