[Weston] More discussion about weston output relative motion algorithm

[Wang, Quanxian]

> -----Original Message-----
> From: Pekka Paalanen [mailto:ppaalanen at gmail.com]
> Sent: Tuesday, May 6, 2014 2:36 PM
> To: Wang, Quanxian
> Cc: wayland-devel at lists.freedesktop.org; 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: Re: [Weston] More discussion about weston output relative motion
> algorithm
> 
> On Wed, 16 Apr 2014 04:21:46 +0000
> "Wang, Quanxian" <quanxian.wang at intel.com> wrote:
> 
> > 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.
> 
> Hi,
> 
> I have nothing against an algorithm for placing outputs in Weston, and it
> would fit Weston core. I think we would like to support all kinds of layouts
> based on weston.ini alone, even without any dynamic configuration like your
> proposed protocol extension.
> 
> However, from your algorithm description, I am not sure how it'll work for
> hotplug or hot-unplug.
[Wang, Quanxian] The algorithm will process all dynamic layout change. If you hotplug, just add one output into the tree, just call enable_node(A), supposed you hot-plug A. The initial design is inserted it into tail of master's hlink. (master is at (0,0)). 
When you hot-unplug, that means you delete this output from the tree. Following the algorithm, just call delete_node(A), supposed you hot-unplug A. the detail algorithm, you can refer to the disable_node algorithm in V4.  The order to take its place is clone link, horizontal link and vertical link. (If no clink, then hlink, still no, vlink)
In file module/wrandr/randr_layout_algorithm.h
115  * Disable Node Rules:
116  *     1) The node is deleted and the place is replaced by others.
117  *     2) The order to take the place of parent:
118  *        clink, hlink and then vlink.
119  *     Others are the same as clean_node.
> 
> Let's imagine a physical setting of four monitors, arranged like this:
> 
> ┌───┬───┐
> │ A │ B │
> ├───┼───┤
> │ C │ D │
> └───┴───┘
> 
> That is a 2x2 grid.
> 
> There are two ways to represent this in your tree structure, I believe:
> 
> A.hlink -> B
> A.vlink -> C
> C.hlink -> D
> 
> or
> 
> A.hlink -> B
> A.vlink -> C
> B.vlink -> D
> 
[Wang, Quanxian] Firstly, you imagine the grid. But from the very beginning,  C is not present. You can do like this.
a) Initial status
 ┌───┬───┐
 │ A │ B │
 ├───┼───┤
 │     │ D │
 └───┴───┘
 b) hot-plugged C and move C below of A
 ┌───┬───┐
 │ A │ B │
 ├───┼───┤
 │ C  │ D │
 └───┴───┘
Remember, since D is below of B, there will not any relation between C and D. Otherwise D will have two parents (horizontal C and vertical B).

> What happens, if C is not present originally and gets hotplugged?
[Wang, Quanxian] 
Original status: C is not present
 ┌───┬───┐
 │ A │ B │
 ├───┼───┤
 │     │ D │
 └───┴───┘
 A.hlink -> B
 B.vlink -> D

C is hot-plugged, it will go to tail of Master(A)'s hlink.
┌───┬───┐
 │ A │ B │C |
 ├───┼───┤
 │   │ D │
 └───┴───┘
A.hlink -> B
B.hlink -> C
B.vlink -> D
> What happens, if C gets hot-unplugged? And then plugged back?
[Wang, Quanxian] 
C is hot-unplugged based on previous. In previous status, C has no any child link (clink, hlink, vlink)
┌───┬───┐
 │ A │ B │    |
 ├───┼───┤
 │   │ D │
 └───┴───┘
C is hot-plugged, it will be as before.
┌───┬───┐
 │ A │ B │C |
 ├───┼───┤
 │   │ D │
 └───┴───┘
> What happens, if a user adds a new output and defines it to be left-of C? Will
> C end up below B or will it stay below A?
[Wang, Quanxian] 
If a new output called E is added and define it as left-of C. It will do two actions. One is add, another is move.
Adding:
┌───┬───┐
 │ A │ B │C | E
 ├───┼───┤
 │   │ D │
 └───┴───┘
Move: move E left of C (it will have the actions: remove E, and then E replace C'place, C is moving to right of E)
 ┌───┬───┐
 │ A │ B │E  | C
 ├───┼───┤
 │   │ D │
 └───┴───┘
> What if A is wider than C; will there be a gap between C and D?
[Wang, Quanxian] 
You imagine
 ┌───┬───┐
 │ A │ B   |
 ├───┼───┤
 │ C  │ D │
 └───┴───┘

A's hlink == B
A's vlink = C
B's vlink = D

It is possible based on C's size. It depends on A and C's width. Also it depends on A and B's height.
Noticed that, C has no any relation with D. Maybe their area will be overlapped or some gap.

> 
> Is there a behavioral difference between the two tree structures?
> 
> Can you realize the following arrangement?
>     ┌───┬───┐
>     │ A │ B │
> ┌───┼───┼───┤
> │ E │ C │ D │
> └───┴───┴───┘
[Wang, Quanxian] You could not make it. We only has one master which is (0,0). It is the top-left. In this case, A has y=0, but x is not 0 and E's x =0, and y is not 0.
If you want to do that, it will implement pos(x,y) function to move a output to defined (x,y).
> 
> 
> Then an even better question is, what would the user expect?
> Which outputs should move, and which should stay in place with respect to
> the desktop coordinate system (global coordinates)?
> 
> I don't have the correct answers here. I only agree that it would be nice if
> Weston supported more than just a horizontal line of monitors.
> Personally I have a vertical line setup.
> 
> I don't even think the problem is well-defined.
> 
> Maybe we need completely different algorithms for vertical/horizontal line
> vs. a grid pattern?
> 
> In the end, the algorithm will only compute positions for each output in the
> global coordinate system. Quite likely no algorithm will be able to realize all
> possible arrangements and alignments (for differing output sizes) without
> becoming practically unusable, so we would still need the option of just
> defining the output position as coordinates in the global space.
[Wang, Quanxian] I believe the algorithm could be implemented, you can add the gap or others parameter to make it happen. The only thing is algorithm become very complex.
In this algorithm, it links all outputs. Maybe some has gap, maybe some has the overlapped, but you still can make it. It depends on what you want.

Thanks for your comment. :)
> 
> 
> Thanks,
> pq
> 
> 
> > 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
> >
> >