*From*: Rob Adams <readams readams net>*To*: Elijah Newren <newren gmail com>*Cc*: metacity-devel-list gnome org*Subject*: Re: Additional issues to address for the constraints_experiments branch?*Date*: Mon, 14 Nov 2005 12:44:25 -0800

Ok so you take your spanning set of safe regions, then given a window position, find the closest region that will contain your window, either completely for placement, or partially for repairing a violated constraint while moving/resizing? Another interesting question: one thing that I couldn't really hack into the constraints.c stuff when I hacked in all my other fixes was that I really wanted the titlebar visibility constraint to only apply if there was no contiguous region of sufficient width. For example, in the current code a top or bottom strut will push up a window if even one pixel intersects the strut, but what I really wanted to do was make it so that it would only push it up too much of the titlebar was covered, but it was really not feasible to do it with the separate constraints generated by each strut, since multiple struts could individually cover parts of the titlebar. It sounds like you'd be able to get the behavior I wanted with your algorithm, perhaps. Example: ______ ______ Strut| | Strut Put a window into that tiny gap between two struts, it should get pushed up, but make the gap wider than some minimum, and you'd be able to shove it down there, ideally. Another thing that I'd be concerned about with your general approach is simply to make sure you don't end up with perhaps unnecessarily fragmented regions. For example, say you have an somewhat odd-sized "safe zone" like this: ____ ___| | | | |_____| There's 3 sensible ways to break this into rectangles, which your algorithm would do, either as 3 small rectangles or as 2 rectangles in one of 2 ways. Regardless, it's necessary to make a choice in advance as to how you break it up. But its possible that, depending how you break it up, a window could fit into the "real" region but not fit into any of the spanning rectangles. So if your algorithm chose: ____ ___| | | | | |__|__| or ____ ___|__| | | |_____| or ____ ___|__| | | | |__|__| Your malicious adversary could make either a wider window (for the first) or a taller window (for the second) such that it would fit into the full region but not into 2 of those 3 possible subdivisions. Also, I'm curious how your algorithm would behave in the case where there exists no solution to the constraint satisfaction problem (or, as above, your algorithm doesn't find it). The heuristic repair technique would iterate for a bit before finally settling on some vaguely ill-defined "best guess" solution that will satisfy some, though not all, constraints. Ideally there'd be a scheme to relax certain "less important" constraints and try again, but there isn't currently. But with the region-finding solution you'd probably have to worry about it a bit more, since you probably don't want to leave the window totally non-constrained in such cases. Not an insurmountable problem. -Rob "Spanner in the Works" Adams On Mon, 2005-11-14 at 13:06 -0700, Elijah Newren wrote: > On 11/14/05, Rob Adams <readams readams net> wrote: > > Things to worry about: > > Solving constraints for partial-width struts can introduce interesting > > interactions. > > > > For example, if you have something like: > > |Strut > > |_____ > > _________ ____ > > | Strut | |Wnd| > > > > if you make the strut on the right taller so that it intersects the > > window, it will push the window over to the left, which then violates > > the other strut constraint. > > Right, this one was a royal pain in the butt to figure out, and I > completely changed my method a few different times to get it right. > :-) > > > So you need to have a pretty powerful constraints solver to be able to > > handle cases like this. The while (!satisfied) try to satisfy loop > > implements a technique called heuristic repair. This is a search > > technique used to constraint satisfaction problems that are generally > > not too tightly constrained; that is relatively easy problems. The idea > > is to simply move the window around so as few constraints are violated > > as possible, then iterate to try to find a feasible position. The > > advantage of heuristic repair is that it is blazing fast, which it needs > > to be in the metacity constraint solver since it runs a lot when > > moving/resizing windows. The disadvantage is that it's not a complete > > search algorithm, i.e. it's not guaranteed to find a solution in the > > general case. However, given the way the constraints in metacity work, > > it will nearly always find a solution if one exists (though its possible > > that there is no solution). > > > > So I'd be interested to hear what search algorithm you use to solve the > > constraint satisfaction problem in your branch. Iterative deepening A* > > perhaps? > > Nope, it's not iterative at all. Whenever any struts are modified, I > generate what I've called a minimal rectangle spanning set. This set > is a list of rectangles with the property that a window will fit "on > the screen" (meaning screen minus struts) if and only if it fits > inside one of those rectangles. While generating this list is > definitely more costly than a single iteration of your heuristic > repair, it's something I only have to generate once instead of once > every heuristic repair iteration of every meta_window_constrain[1]. > > The relevant function is > meta_rectangle_get_minimal_spanning_set_for_region() from boxes.c > (plus other *_region() functions) and is thoroughly tested in > testboxes.c:test_regions_okay() (and with related functionality > thoroughly tested by test_region_fitting(), test_clamping_to_region(), > test_clipping_to_region(), and test_shoving_into_region()). > > Cheers, > Elijah > > [1] Okay, I fibbed a little about the once thing. I have to do it > number_xineramas + 1 times inside the update struts stuff, since that > is the number of spanning sets I generate -- one for the whole screen > plus one for each xinerama. (I do one for each xinerama because I've > also added a constrain-to-single-xinerama constraint for > non-user-movement in order to fix Davyd's gripe about windows stupidly > positioning themselves split across xineramas). >

**Follow-Ups**:**Re: Additional issues to address for the constraints_experiments branch?***From:*Elijah Newren

**References**:**Additional issues to address for the constraints_experiments branch?***From:*Elijah Newren

**Re: Additional issues to address for the constraints_experiments branch?***From:*Rob Adams

**Re: Additional issues to address for the constraints_experiments branch?***From:*Elijah Newren

[Date Prev][Date Next] [Thread Prev][Thread Next] [Thread Index] [Date Index] [Author Index]