[Weston] More discussion about weston output relative motion algorithm

[Pekka Paalanen]

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.

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

What happens, if C is not present originally and gets hotplugged?
What happens, if C gets hot-unplugged? And then plugged back?
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?
What if A is wider than C; will there be a gap between C and D?

Is there a behavioral difference between the two tree structures?

Can you realize the following arrangement?
    ┌───┬───┐
    │ A │ B │
┌───┼───┼───┤
│ E │ C │ D │
└───┴───┴───┘


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.


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
> 
>