[Weston] More discussion about weston output relative motion algorithm

[Wang, Quanxian]

Clear some definition for easy understanding.
Supposed B is beside A. B maybe leftof, rightof, above, or below A.
If leftof,  output(B) is the horizontal parent of A.
If above, output(B) is the vertical parent of A.
If rightof, output(B) is the horizontal child of A.
If below, output(B) is the vertical child of A.

With definition, you will be easy to set up a binary tree. But you may think some node may have two parent. The answer is no, you can have a try to move and will find it is right. Just let you know my mistakes I ever made. When you move output to be leftof or above of another, the output will take the place of another instead of really above or left of the position of another. :) After that, you will be know why one node has  one parent at most.

Of course, the original layout will be one horizontal line for extended mode.

If clone mode is supported, that is fine. Keep clone link for that in output structure. The algorithm will be updated with minimal. But it will be easy and based on clone mode design.

Thanks

Regards

Quanxian Wang


From: Wang, Quanxian
Sent: Wednesday, April 16, 2014 11:26 AM
To: wayland-devel at lists.freedesktop.org
Cc: Wang, Quanxian; Pekka Paalanen (ppaalanen at gmail.com); Jason Ekstrand (jason at jlekstrand.net); Bryce W. Harrington (b.harrington at samsung.com); Fu, Michael; Hardening (rdp.effort at gmail.com); Kang, Jeong Seok
Subject: [Weston] More discussion about weston output relative motion algorithm

Hi, All

Relative motion of output is needed in Weston compositor or others. For example, plugin a monitor, you want move it above or leftof or rightof or below others.

More details about this motion algorithm will be shown in the email. Before that, I mention one point, I don't refer any code from others including xserver. My idea is based on the current Weston compositor design and statistics. It is original for Weston compositor. At the same time, when I implemented it, I try to make parameters to be general. If possible, make it common instead of only in randr protocol.

Weston movement algorithm

If only support one line layout. For example, all vertical or all horizontal, it is very easy to implement. But if we want support both at the same time, it will be more complex instead of 1+1=2. Currently in Weston compositor, only horizontal is supported. Compositor uses output_list to make it happen.

Here are the summary of motion properties.


1)      It is similar with binary tree.  Here are some related features.  Every node is one output.

a.       Every node have one parent at most, also the parent maybe from vertical, maybe from horizontal(it is different with binary tree). But never has two parents. I will not explain why, you can use 4 outputs to do more movement, and you can find this.

b.      Every node have two children at most. One is for vertical, another is for horizontal.

c.       The tree will link all outputs, if you find some output is not in link, that means link is lost. So when you plugin or output, you need make the link complete. When scan Weston.ini configure, you need to organize the tree following this algorithm.

d.      Only one start point(root) exists whose coordinate is x=0 and y=0). From that, you could find all other outputs and position them from left up most to right down most.

e.      Every branch from the main branch will never cross each other.

2)      The tree is double linked.

3)      The only have-to interrupt is when one node is deleted, which child takes its place? Currently I force its horizontal child will take its place.

By the way,  I list some statistics. Maybe you could find some interesting why I post more effort on this algorithm. Layout means the final result of all outputs' position.

Output_number  Possible_Layout_number    One_line_possbile_layout_number

   1                                  1                                                    1

    2                                 2x2=4       (2=2x1)                    2

    3                                5x6=30     (6=3x2x1)                6

    4                              14x24=336  (24=4x3x2x1)       24

You could find that, if we have 4 outputs, there are 14x24=336 possible layout types. So the algorithm has to be designed as complete instead of only for 2, or 3, or less. It should be designed for more. For example, supposed 500, 1000 outputs. Yes, it is in theory. But the algorithm must be that. I enumerate them based on the movement and get the possible layouts. For example, when you have 4 outputs, even if they are in one line, there are 4x3x2x1=24 layouts.

Algorithm Implementation:
To implement this algorithm, more links have to be added for output. I add vlink and hlink into output structure. Currently I implemented it in randr protocol (will be posted in next version of Weston randr protocol)

With that features above, two links(vlink and hlink) should be added into current output structure and the tree should be set up. (This will not affect the usage of original list in output). More patches will be needed.

1)      Initialization (auto found outputs and link them together)

2)      Dynamic plugin and out.

3)      If Weston.ini supports the layout, it should work with the algorithm.

4)      Randr protocol

Important:
Currently the algorithm is implemented in randr protocol. But I want to move it into common code instead of only randr protocol. I am not sure if it is right and where to put algorithm code. I need agreement and discussion for that. If no permission, I will let it in randr protocol (create another structure for output, plus vlink and hlink).

Thanks

Regards

Quanxian Wang


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/wayland-devel/attachments/20140416/376aef8f/attachment.html>