14 Nov 2008 tampe   » (Journeyer)

In the beginning there was a Layout

I think that a great layout engine should be the base of a great Gui. So here is some thoughts about layout.

I don't now about all quirks of TeX, but basically, it seems, its that art about stacking rectangles where the rectangles themselves can be based of stacked rectangles and so on. It is a simplified description but you can see one fundamental point in this argument, you can use an object oriented description of the rectangles. Actually you should be able to use the TeX engine to do a automatic layout of a Gui. Anyone now anything about how to do this in a nice way?

Automatic Layout of graphs are cool, and I ones made a huge call-graph of a python program on a A2 paper with the help of the ghraphviz package, really nice. In graphviz you can have nodes that are rectangles. You should then be able to use the graphviz engine to find the coordinates of your gui elements as well to get a certain kind of layout. Is there such a link out in the wild?

Constraint Programming for layout is cool and of cause not a new idea. You basically give constraints for how the coordinates in each rectangle can vary in relation to other coordinates in different rectangles. Something like x>y,x-y>d (x is after y and at minimum d units apart). Then you might add a penalty av magnitude, say C((x-y) - d)^2 and include all these in a quadratic criteria telling how much you like a deviation from d distance and play with that. This is a more fuzzy and general way of implementing stacking. Say that we implement stacking according to this. We might want to align stuffs in different ways e.g. want your coordinate to be close to other coordinate in some way, close can again be related to quadratic criteria. You can express that a linear transformation of a set of coordinates can be close to another set of coordinates and so on. It is a powerful concept. You will end up with quadratic programming QP.

There are some special cases. For example if you always stack in an exact way when you build your rectangles, you may skip the inequalities and just solve the fuzzy constraints that's left in the quadratic criteria. Then you basically need to solve linear equation systems. Kan we do this fast? Well in order to have as an exact and general solution and keep it simple you may start using linear algebra routines of full matrices. The order of this algorithm is n^3 if I'm not misstaken so a layout of 1000 coordinate values will take 10GFlops to calculate, Maximum space is about 100MB for doubles. (The transfer to the computing unit may actually be much less due to sparseness of the matrix)) Now considering that GPGPU solutions can deliver 400GFlops (see one of the examples at the CUDA site (with a TESLA card)). You may now understand that you in a few years when the GPU technology have been standardized and matured, you will be able to do some cool things with layouts. To the reader, for cases with sparse matrices you will find other mathematical tools and GPGPU may not be suited.

Solving quadratic programming problems with constraints is if I remember correctly heavily dependant on solving equation systems as well so GPGPU technology is probably welcomed for this case as well

Can we dream up more layout tricks? Well some kind of morphing. Say that I have a set of symbols and wants them to be more square like. How can we implement this? Maybe one way is to make the best fit of a square to some set of coordinates from a symbol. Then you can calculate the closest points on the square for each point on the symbol. A new symbol with the same coordinate identities will then be searched for so that you weight the variance to the square and the variance to the old symbol and then hence morph between them. I don't now how this works, but there are plenty of tricks like this that have the potential to implement more fuzzy notions about a layout.

And then the content begun

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!