RE: [Weston] More discussion about weston output relative motion algorithm
Hi, Pq Thanks for your comment and idea. I list several cases for discussion. Case 1: Original: ├── │ B │ └── Action: Move A leftof B ├───┼───┤ │ A │ B │ └───┴───┘ As you said, B must not change, A will have negative coordinates. That is fine. Case 2: Original: ├───┼───┤ │ C │ D │E └───┴───┘ Move D leftof C: C must not change. How about E? E does not need change. ├───┼───┤ │ D │ C │ | E └───┴───┘ D will have negative coordinates. A big hole is left. It is not accepted by user at least I think so. An optimization is E will move left and is side with C ├───┼───┤ │ D │ C │E └───┴───┘ Case 3: ├───┼───┤ │ C │ D │E | F └───┴───┘ Action: Move E leftof D C, D's coordinate will not change. E and C will have the same relation with D, however they are not clone. F will be move forward. Right? ├───┼───┤ │C/E│D | F └───┴───┘ Case 4: ├───┼───┤ │ C │ D │E | F └───┴───┘ ││ │ G | └───┴───┘ Action: Move E leftof D C, D's coordinate will not change. E and C will have the same relation with D. F will be move forward. The relation between F and G will be built up. Maybe you want G to be moved with E. That will be crazy. ├───┼───┤ │C/E│D | F | └───┴───┘ │ ││ G| └───┴───┘ After the cases above, list a complex one. ├───┼───┤ │ │H | I | └───┴───┘ │ ││ G| ├───┼───┤ │C/E│D | F | K/L│M └───┴─┘ │ ││J || | N| └───┴───┘ Move F leftof H, and find some output to take F's position. Then chain reaction will happen. Here you will define an order who take the place. For example, K/L will take the place of F. What is the relation between G and K or L? what is the relation between J and K or L? Things turns to be much more complex. Just have a think what will be. It is an interesting thing. After that, you find a conclusion. 1) position to new place will be easy. 2) find replacer and rebuild the relations will be complex. 3) Chain reaction will make you crazy. Because no one expect how many outputs will be available and how many links after that. Maybe 1, or 2 or 3 or more... It is very easy to be in a loop. And more hole in layout happens. Anyway, it is a little hard to make everything happy. :) Thanks Regards Quanxian Wang ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel
Re: [Weston] More discussion about weston output relative motion algorithm
On Wed, 7 May 2014 03:26:56 + Wang, Quanxian quanxian.w...@intel.com wrote: Thanks Pq's comment. Before you continue my comment, I mentioned one point. This is output movement algorithm and it is completely different with pre-configuration of output in weston.ini. For output, no alive, no movement. If you want to keep pre-configuration in weston.ini when output change, just keep it in some place and follow it when pre-defined output is plugged or unplugged. But anyway, it is a static configuration. It is conflict with dynamic output movement. Of course it is, but users expect both to work at the same time, not have an option to choose between dynamic and static configuration. They want to configure what the dynamic code will do on hotplug, hence these two cases are inseparable. The weston-randr protocol could be seen as a way to modify the static configuration in-memory and then trigger a re-layout. Btw. there is no reason to avoid negative global coordinates. If you have output A at 0,0 and add output B to the left of it, it is perfectly valid to put B at -widthB,0. You *can* add to the left or above without moving all the existing outputs. Also nothing says that you have to have an output with origin at 0,0. (There may be bugs, but that is all.) If you haven't, and I certainly have not, you really should study how existing monitor layout algorithms work. Do not set out to replicate them as is, but find out how they solve the problems and whether those solutions would be applicable here. For getting this work forward and upstream, I think it is much less controversial to first expand weston.ini to allow setting other than just horizontal line of outputs. That would be interesting to a lot more people than the dynamic configuration protocol, and you would still need to deal with hotplug. Btw. I don't understand the comment no alive, no movement. Thanks, pq ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel
RE: [Weston] More discussion about weston output relative motion algorithm
-Original Message- From: Pekka Paalanen [mailto:ppaala...@gmail.com] Sent: Wednesday, May 7, 2014 2:17 PM To: Wang, Quanxian Cc: Hardening (rdp.eff...@gmail.com); Bryce W. Harrington (b.harring...@samsung.com); wayland-devel@lists.freedesktop.org; Jason Ekstrand (ja...@jlekstrand.net); Kang, Jeong Seok; Fu, Michael Subject: Re: [Weston] More discussion about weston output relative motion algorithm On Wed, 7 May 2014 03:26:56 + Wang, Quanxian quanxian.w...@intel.com wrote: Thanks Pq's comment. Before you continue my comment, I mentioned one point. This is output movement algorithm and it is completely different with pre- configuration of output in weston.ini. For output, no alive, no movement. If you want to keep pre-configuration in weston.ini when output change, just keep it in some place and follow it when pre-defined output is plugged or unplugged. But anyway, it is a static configuration. It is conflict with dynamic output movement. Of course it is, but users expect both to work at the same time, not have an option to choose between dynamic and static configuration. They want to configure what the dynamic code will do on hotplug, hence these two cases are inseparable. The weston-randr protocol could be seen as a way to modify the static configuration in-memory and then trigger a re-layout. Btw. there is no reason to avoid negative global coordinates. If you have output A at 0,0 and add output B to the left of it, it is perfectly valid to put B at -widthB,0. You *can* add to the left or above without moving all the existing outputs. Also nothing says that you have to have an output with origin at 0,0. (There may be bugs, but that is all.) [Wang, Quanxian] no negative coordinate happens. Top left most is the (0,0), it is the primary output. When you move output left of or above primary output(0,0), other outputs will be moved consistently based on the change. Once you primary output is changed, for example in this case, primary output will be changed to another output. All others outputs' coordinate will be calculated again. But the relative position between outputs will not be changed. Top left most output is the root of tree. All other outputs must be descendants of it.(including clone link, hlink, vlink). Output movement algorithm have implemented that. Negative coordinate is invalid. If you haven't, and I certainly have not, you really should study how existing monitor layout algorithms work. Do not set out to replicate them as is, but find out how they solve the problems and whether those solutions would be applicable here. [Wang, Quanxian] You are right. Refer to others could get more valuable idea and be helpful to make algorithm stronger. My goal is to provide a reasonable algorithm for weston output movement. For getting this work forward and upstream, I think it is much less controversial to first expand weston.ini to allow setting other than just horizontal line of outputs. That would be interesting to a lot more people than the dynamic configuration protocol, and you would still need to deal with hotplug. Btw. I don't understand the comment no alive, no movement. [Wang, Quanxian] if output is not active, no movement should happens on this output. Any movement on such kind of output will be invalid. The inactive status include two status. a)unplugged-hardware disable b) plugged but disabled - software disable Thanks, pq ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel
Re: [Weston] More discussion about weston output relative motion algorithm
On Wed, 7 May 2014 07:03:32 + Wang, Quanxian quanxian.w...@intel.com wrote: -Original Message- From: Pekka Paalanen [mailto:ppaala...@gmail.com] Sent: Wednesday, May 7, 2014 2:17 PM To: Wang, Quanxian Cc: Hardening (rdp.eff...@gmail.com); Bryce W. Harrington (b.harring...@samsung.com); wayland-devel@lists.freedesktop.org; Jason Ekstrand (ja...@jlekstrand.net); Kang, Jeong Seok; Fu, Michael Subject: Re: [Weston] More discussion about weston output relative motion algorithm On Wed, 7 May 2014 03:26:56 + Wang, Quanxian quanxian.w...@intel.com wrote: Thanks Pq's comment. Before you continue my comment, I mentioned one point. This is output movement algorithm and it is completely different with pre- configuration of output in weston.ini. For output, no alive, no movement. If you want to keep pre-configuration in weston.ini when output change, just keep it in some place and follow it when pre-defined output is plugged or unplugged. But anyway, it is a static configuration. It is conflict with dynamic output movement. Of course it is, but users expect both to work at the same time, not have an option to choose between dynamic and static configuration. They want to configure what the dynamic code will do on hotplug, hence these two cases are inseparable. The weston-randr protocol could be seen as a way to modify the static configuration in-memory and then trigger a re-layout. Btw. there is no reason to avoid negative global coordinates. If you have output A at 0,0 and add output B to the left of it, it is perfectly valid to put B at -widthB,0. You *can* add to the left or above without moving all the existing outputs. Also nothing says that you have to have an output with origin at 0,0. (There may be bugs, but that is all.) [Wang, Quanxian] no negative coordinate happens. Top left most is the (0,0), it is the primary output. You misunderstood. I mean that sometimes it is *good* to use negative coordinates, exactly to avoid moving the world, and that is *perfectly ok*. Moving the world (all existing outputs) is usually not what a user might expect when adding a new output. The top-left most output does not need to be at 0,0. When you move output left of or above primary output(0,0), other outputs will be moved consistently based on the change. Once you primary output is changed, for example in this case, primary output will be changed to another output. All others outputs' coordinate will be calculated again. But the relative position between outputs will not be changed. Top left most output is the root of tree. All other outputs must be descendants of it.(including clone link, hlink, vlink). Output movement algorithm have implemented that. Negative coordinate is invalid. I'm not talking about your specific algorithm anymore. I am talking in general. Existing outputs are usually expected to stay put, when adding outputs to the extremes. Literally that means that the position of the existing outputs must not change, but only the position of the new output is computed appropriately, even if it results in negative coordinates. If I have one output active, and I add another output to the left of it, I certainly do not expect all windows to jump from the existing output to the new output. IOW, the position of the existing output must not change, and the new output will get a negative position. This is about the absolute global coordinates, not the relative positioning between outputs. Btw. I don't understand the comment no alive, no movement. [Wang, Quanxian] if output is not active, no movement should happens on this output. Any movement on such kind of output will be invalid. The inactive status include two status. a)unplugged-hardware disable b) plugged but disabled - software disable What does movement happening on an output mean? What could be moving on that inactive output? Are you perhaps instead trying to say, that using an inactive output as the reference point for placing another output is not allowed? Thanks, pq ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/wayland-devel
RE: [Weston] More discussion about weston output relative motion algorithm
-Original Message- From: Pekka Paalanen [mailto:ppaala...@gmail.com] Sent: Wednesday, May 7, 2014 3:41 PM To: Wang, Quanxian Cc: Hardening (rdp.eff...@gmail.com); Bryce W. Harrington (b.harring...@samsung.com); wayland-devel@lists.freedesktop.org; Jason Ekstrand (ja...@jlekstrand.net); Kang, Jeong Seok; Fu, Michael Subject: Re: [Weston] More discussion about weston output relative motion algorithm On Wed, 7 May 2014 07:03:32 + Wang, Quanxian quanxian.w...@intel.com wrote: -Original Message- From: Pekka Paalanen [mailto:ppaala...@gmail.com] Sent: Wednesday, May 7, 2014 2:17 PM To: Wang, Quanxian Cc: Hardening (rdp.eff...@gmail.com); Bryce W. Harrington (b.harring...@samsung.com); wayland-devel@lists.freedesktop.org; Jason Ekstrand (ja...@jlekstrand.net); Kang, Jeong Seok; Fu, Michael Subject: Re: [Weston] More discussion about weston output relative motion algorithm On Wed, 7 May 2014 03:26:56 + Wang, Quanxian quanxian.w...@intel.com wrote: Thanks Pq's comment. Before you continue my comment, I mentioned one point. This is output movement algorithm and it is completely different with pre- configuration of output in weston.ini. For output, no alive, no movement. If you want to keep pre-configuration in weston.ini when output change, just keep it in some place and follow it when pre-defined output is plugged or unplugged. But anyway, it is a static configuration. It is conflict with dynamic output movement. Of course it is, but users expect both to work at the same time, not have an option to choose between dynamic and static configuration. They want to configure what the dynamic code will do on hotplug, hence these two cases are inseparable. The weston-randr protocol could be seen as a way to modify the static configuration in-memory and then trigger a re-layout. Btw. there is no reason to avoid negative global coordinates. If you have output A at 0,0 and add output B to the left of it, it is perfectly valid to put B at -widthB,0. You *can* add to the left or above without moving all the existing outputs. Also nothing says that you have to have an output with origin at 0,0. (There may be bugs, but that is all.) [Wang, Quanxian] no negative coordinate happens. Top left most is the (0,0), it is the primary output. You misunderstood. I mean that sometimes it is *good* to use negative coordinates, exactly to avoid moving the world, and that is *perfectly ok*. Moving the world (all existing outputs) is usually not what a user might expect when adding a new output. The top-left most output does not need to be at 0,0. When you move output left of or above primary output(0,0), other outputs will be moved consistently based on the change. Once you primary output is changed, for example in this case, primary output will be changed to another output. All others outputs' coordinate will be calculated again. But the relative position between outputs will not be changed. Top left most output is the root of tree. All other outputs must be descendants of it.(including clone link, hlink, vlink). Output movement algorithm have implemented that. Negative coordinate is invalid. I'm not talking about your specific algorithm anymore. I am talking in general. Existing outputs are usually expected to stay put, when adding outputs to the extremes. Literally that means that the position of the existing outputs must not change, but only the position of the new output is computed appropriately, even if it results in negative coordinates. If I have one output active, and I add another output to the left of it, I certainly do not expect all windows to jump from the existing output to the new output. IOW, the position of the existing output must not change, and the new output will get a negative position. This is about the absolute global coordinates, not the relative positioning between outputs. [Wang, Quanxian] Hi, Pq After getting your opinion, I called back my initial thought for this algorithm. I ever thought it like you, but after draw them one by one, I found I was wrong. The following information will tell you how to get the principle of algorithm. How to get that principle? Take a very simple example, it is a horizontal link. Current output layout: A-B-C-D Next action: Move new E output into left of C A-B-E-C-D Question: Can you keep un-changed on all output's coordinate? Absolutely not. C and D will be changed(right extension) or A and B are changed (left extension). Take common case to allow right extension. E will take place of C, C and D's coordinate will be changed at the same time. It is the minor change. The same thing for moving E leftof A. They are the same principle. Therefore in this case no negative happens. We implicitly support right extension. Now you get the principle
Re: [Weston] More discussion about weston output relative motion algorithm
On Wed, 7 May 2014 08:49:47 + Wang, Quanxian quanxian.w...@intel.com wrote: -Original Message- From: Pekka Paalanen [mailto:ppaala...@gmail.com] Sent: Wednesday, May 7, 2014 3:41 PM To: Wang, Quanxian Subject: Re: [Weston] More discussion about weston output relative motion algorithm On Wed, 7 May 2014 07:03:32 + Wang, Quanxian quanxian.w...@intel.com wrote: -Original Message- From: Pekka Paalanen [mailto:ppaala...@gmail.com] Sent: Wednesday, May 7, 2014 2:17 PM To: Wang, Quanxian Michael Subject: Re: [Weston] More discussion about weston output relative motion algorithm On Wed, 7 May 2014 03:26:56 + Wang, Quanxian quanxian.w...@intel.com wrote: Thanks Pq's comment. Before you continue my comment, I mentioned one point. This is output movement algorithm and it is completely different with pre- configuration of output in weston.ini. For output, no alive, no movement. If you want to keep pre-configuration in weston.ini when output change, just keep it in some place and follow it when pre-defined output is plugged or unplugged. But anyway, it is a static configuration. It is conflict with dynamic output movement. Of course it is, but users expect both to work at the same time, not have an option to choose between dynamic and static configuration. They want to configure what the dynamic code will do on hotplug, hence these two cases are inseparable. The weston-randr protocol could be seen as a way to modify the static configuration in-memory and then trigger a re-layout. Btw. there is no reason to avoid negative global coordinates. If you have output A at 0,0 and add output B to the left of it, it is perfectly valid to put B at -widthB,0. You *can* add to the left or above without moving all the existing outputs. Also nothing says that you have to have an output with origin at 0,0. (There may be bugs, but that is all.) [Wang, Quanxian] no negative coordinate happens. Top left most is the (0,0), it is the primary output. You misunderstood. I mean that sometimes it is *good* to use negative coordinates, exactly to avoid moving the world, and that is *perfectly ok*. Moving the world (all existing outputs) is usually not what a user might expect when adding a new output. The top-left most output does not need to be at 0,0. When you move output left of or above primary output(0,0), other outputs will be moved consistently based on the change. Once you primary output is changed, for example in this case, primary output will be changed to another output. All others outputs' coordinate will be calculated again. But the relative position between outputs will not be changed. Top left most output is the root of tree. All other outputs must be descendants of it.(including clone link, hlink, vlink). Output movement algorithm have implemented that. Negative coordinate is invalid. I'm not talking about your specific algorithm anymore. I am talking in general. Existing outputs are usually expected to stay put, when adding outputs to the extremes. Literally that means that the position of the existing outputs must not change, but only the position of the new output is computed appropriately, even if it results in negative coordinates. If I have one output active, and I add another output to the left of it, I certainly do not expect all windows to jump from the existing output to the new output. IOW, the position of the existing output must not change, and the new output will get a negative position. This is about the absolute global coordinates, not the relative positioning between outputs. [Wang, Quanxian] Hi, Pq After getting your opinion, I called back my initial thought for this algorithm. I ever thought it like you, but after draw them one by one, I found I was wrong. The following information will tell you how to get the principle of algorithm. How to get that principle? Take a very simple example, it is a horizontal link. Current output layout: A-B-C-D Next action: Move new E output into left of C A-B-E-C-D Question: Can you keep un-changed on all output's coordinate? Absolutely not. C and D will be changed(right extension) or A and B are changed (left extension). Take common case to allow right extension. E will take place of C, C and D's coordinate will be changed at the same time. It is the minor change. The same thing for moving E leftof A. They are the same principle. Therefore in this case no negative happens. We implicitly support right extension. That is obvious, and not the case I was talking about. I meant this very simple example: There is only one output A. A Then I add output B to the left of A. B-A The position of A must not change. This means that B must get
RE: [Weston] More discussion about weston output relative motion algorithm
Hi, Pq I meant this very simple example: There is only one output A. A Then I add output B to the left of A. B-A The position of A must not change. This means that B must get negative coordinates, and A's position stays at 0,0. In Weston, window positions are stored in global coordinates, and to keep windows that were on output A, still on output A, the position of A must not change. [Wang, Quanxian] This case is a special case, from it, you could not find the principle. Because in this case, you have the choice 'A must not change' or 'A must change'. But for C-B-A, it will be very clear why we follow the principle. We must think about how to make the principle to be accepted anywhere instead of special case. If we randomly define the rule, will make everything complex. It is not what we want. By the way, when moving output, the move event will be sent to windows in this output. The window will be moved at the same time. Note, that you cannot infer this from the syntax B-A, but you can from put B left-of A: B is being set and A is the reference point. Another case: First we have A-B Then add C right-of A. Now you could get the chain A-C-B, or C could end up cloning B. I do not care too much on what happens there, since it is sort of ill-defined. But I do care about the first case where we are not adding in the middle. Now you get the principle from simple link. And then vlink is the same thing. And then combine vlink and hlink together. At last I got this algorithm. I know principle will exist in both complex and simple layout. The algorithm can be summarized from them. Therefore my first step is to study simple case and find what the rule is. And then turn to complex and enhance the algorithm. Make the algorithm to be complete. Here I list several questions for you. 1) Why use tree to link all outputs together? If just use coordinate to calculated the x, y, you will be lost. Because when you moving output, you can't avoid affecting the position of other outputs. You have to review all coordinates of outputs and make decision who is left, right, above, below. It will be much more complex. But if you use tree to link all, everything is very clear. Who is left, right, above, below. It is very clear. Coordinate and relative motion could be easily figured out. It will be very easy to control the position and movement of outputs. My alternate proposition was to keep the ordered list of configuration directives instead of a tree structure. Not just x,y for each live output. Instead of going through the tree to assing new positions, you would execute the list of directives. You would also need some additional rule on where to add outputs that are not placed by any directive. Most likely this rule would just create directives for the outputs. Whether that would work or not, I am not sure. 2) Why one root One root will tell you, this is the top left most. No other outputs will be left or above it. From this, you can calculate and review all outputs. No one is lost. Your definition of top-left most causes you to have problems in realizing an arrangement where the top-left output does not exist, e.g.: - C B A OTOH with directives, there is no need to define a root output. Directives could also refer to inactive outputs. Inactive outputs would simply have zero size, and the directive would be executed as always. [Wang, Quanxian] Let me think about that case. In current algorithm, this case will not happen. The algorithm design will avoid such condition. But in practice, this layout really exists. The solution could be: Root output should exist because it will link all outputs. We really need that. But I like you suggestion to make root virtual (just as you said, zero size). At the same time we can define gap for every output. In this case, C'x coordinate will have this gap. So the link could be Root-hlink = C (x's gap is x) Root-vlink = B (y's gap is y) C-vlink = A or B-hlink = A. Is it reasonable? :) If so, pos(x,y) will take into consideration. But you definitely can not define such case B-hlink = A C-vlink = A If you has such case, it will crash all. A can't have two parent because it will cause conflict of A's coordinate. 3) Why only one parent? If two parents, you will find more links will cross each other. It is absolutely a disaster. (This could cause conflict of coordinates, from this path, it will A, for that path, it will B. A and B is not same.) I am not sure if you understand my idea. Sorry for my poor language. No, I do understand the tree structure well. It is just the rationale behind that is unclear, it clearly has some reasonable cases it cannot represent, and some IMO surprising behaviour. Thanks, pq ___ wayland-devel mailing list wayland-devel@lists.freedesktop.org
Re: [Weston] More discussion about weston output relative motion algorithm
On Wed, 16 Apr 2014 04:21:46 + Wang, Quanxian quanxian.w...@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@lists.freedesktop.org Cc: Wang, Quanxian; Pekka Paalanen (ppaala...@gmail.com); Jason Ekstrand (ja...@jlekstrand.net); Bryce W. Harrington (b.harring...@samsung.com); Fu, Michael; Hardening (rdp.eff...@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
RE: [Weston] More discussion about weston output relative motion algorithm
-Original Message- From: Pekka Paalanen [mailto:ppaala...@gmail.com] Sent: Tuesday, May 6, 2014 2:36 PM To: Wang, Quanxian Cc: wayland-devel@lists.freedesktop.org; Jason Ekstrand (ja...@jlekstrand.net); Bryce W. Harrington (b.harring...@samsung.com); Fu, Michael; Hardening (rdp.eff...@gmail.com); Kang, Jeong Seok Subject: Re: [Weston] More discussion about weston output relative motion algorithm On Wed, 16 Apr 2014 04:21:46 + Wang, Quanxian quanxian.w...@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
RE: [Weston] More discussion about weston output relative motion algorithm
Thanks Pq's comment. Before you continue my comment, I mentioned one point. This is output movement algorithm and it is completely different with pre-configuration of output in weston.ini. For output, no alive, no movement. If you want to keep pre-configuration in weston.ini when output change, just keep it in some place and follow it when pre-defined output is plugged or unplugged. But anyway, it is a static configuration. It is conflict with dynamic output movement. Currently in my weston randr's patches has provided an interface to put your configure requests into one file. -Original Message- From: wayland-devel [mailto:wayland-devel-boun...@lists.freedesktop.org] On Behalf Of Pekka Paalanen Sent: Tuesday, May 6, 2014 5:16 PM To: Wang, Quanxian Cc: Hardening (rdp.eff...@gmail.com); Bryce W. Harrington (b.harring...@samsung.com); wayland-devel@lists.freedesktop.org; Jason Ekstrand (ja...@jlekstrand.net); Kang, Jeong Seok; Fu, Michael Subject: Re: [Weston] More discussion about weston output relative motion algorithm On Tue, 6 May 2014 07:26:32 + Wang, Quanxian quanxian.w...@intel.com wrote: -Original Message- From: Pekka Paalanen [mailto:ppaala...@gmail.com] Sent: Tuesday, May 6, 2014 2:36 PM To: Wang, Quanxian Cc: wayland-devel@lists.freedesktop.org; Jason Ekstrand (ja...@jlekstrand.net); Bryce W. Harrington (b.harring...@samsung.com); Fu, Michael; Hardening (rdp.eff...@gmail.com); Kang, Jeong Seok Subject: Re: [Weston] More discussion about weston output relative motion algorithm On Wed, 16 Apr 2014 04:21:46 + Wang, Quanxian quanxian.w...@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. Hi, each question I made was independent, and supposed to start from this particulat setup. Not as a sequence of operations, but always starting with this. [Wang, Quanxian] you expected it in pre-configuration. The algorithm is designed for output alive. For output, no alive, no movement. 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
RE: [Weston] More discussion about weston output relative motion algorithm
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@lists.freedesktop.org Cc: Wang, Quanxian; Pekka Paalanen (ppaala...@gmail.com); Jason Ekstrand (ja...@jlekstrand.net); Bryce W. Harrington (b.harring...@samsung.com); Fu, Michael; Hardening (rdp.eff...@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_numberOne_line_possbile_layout_number 1 1 1 2 2x2=4 (2=2x1)2 35x6=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
