[PATCH 7/8] fixes: add support for Pointer Barriers
Soeren Sandmann
sandmann at cs.au.dk
Mon Feb 28 09:52:33 PST 2011
Peter Hutterer <peter.hutterer at who-t.net> writes:
> From: Adam Jackson <ajax at redhat.com>
>
> Pointer barriers block the movement of a pointer past a certain line,
> specified by the barrier. Movement through the barrier may be permitted for
> certain directions of movement.
>
> Algorithm used:
> For each movement, find the nearest-to-origin-of-movement barrier that
> blocks this movement. If found, clamp to that barrier and re-evaluate from
> this new origin.
A problem with the algorithm as described above is illustrated by this
situation:
*
\
\
------------------
\
\
*
where the desired outcome is this:
*
\
\___*
------------------
.
.
*
But the algorithm as described will do this:
- Find blocking barrier
- Clamp to that barrier
- Restart algorithm with new origin
- Find the same blocking barrier again.
and end up in this situation:
*
\
*
------------------
.
.
*
So with the algorithm as described, the pointer will end up not sliding
along the edge.
To fix the algorithm, I think it has to be modified to do this:
(a) find nearest barrier, compute intersection with that barrier
(c) move to the barrier endpoint in the appropriate direction (ie., a
move horizontally to the right for the example above), but never
farther in that direction than the original destination (so only a
short movement in the example).
(d) reevaluate from the point computed in (c)
(e) Repeat until the position stops changing.
Note that this handles this example correctly:
* |
\ |
------------------+----------
\
\
\
\
\
\
\
\
\
\
*
because the horizontal movement will be restrained by the vertical
barrier after which no further movement will be allowed.
In pseudocode:
constrain (ox, oy, nx, ny, *cx, *cy)
{
if ((ox, oy) == (nx, ny))
return;
b, ix, iy = closest intersecting barrier and intersection point()
if (no such barrier)
{
*cx, *cy = nx, ny;
return;
}
else if (b is horizontal)
{
if (dx > 0)
ex = b.x2;
else
ex = b.x1;
constrain (ix, b.y, ex, b.y, cx, cy)
return
}
else /* b is vertical */
{
similar to horizontal case
}
}
and then keep calling that function with (cx, cy) as the new (ox, oy)
until it no longer produces results different from ox, oy.
The code is in general very well-commented and nicely separated into
helper functions, but I do have some more specific concerns about it:
> +static void
> +_fixes_test_direction(struct PointerBarrier *barrier, int d[4], int permitted)
> +{
> + BOOL blocking;
> + int i, j;
> + int dir = barrier_get_direction(d[0], d[1], d[2], d[3]);
> +
> + barrier->directions = 0;
> + blocking = barrier_is_blocking_direction(barrier, dir);
> + g_assert(blocking);
> +
> + for (j = 0; j <= BarrierNegativeY; j++)
> + {
> + barrier->directions = 1 << i;
It looks like i is being used without initialization here. Should it be
"barrier->directions = 0"?
I didn't read the rest of the test code, but it's definitely a good
things that it's there. However, would it be possible to add it in a
separate commit?
> +/**
> + * Test if the movement vector x1/y1 → x2/y2 is intersecting with the
> + * barrier. A movement vector with the startpoint or endpoint on the barrier
> + * itself counts as intersecting.
> + *
> + * @param x1 X start coordinate of movement vector
> + * @param y1 Y start coordinate of movement vector
> + * @param x2 X end coordinate of movement vector
> + * @param y2 Y end coordinate of movement vector
> + * @param[out] distance The distance between the start point and the
> + * intersection with the barrier (if applicable).
> + * @return TRUE if the barrier intersects with the given vector
> + */
> +BOOL
> +barrier_is_blocking(const struct PointerBarrier *barrier,
> + int x1, int y1, int x2, int y2,
> + double *distance)
> +{
> + BOOL rc = FALSE;
> + float ua, ub, ud;
> +
> + /* Algorithm below doesn't handle edge cases well, hence the extra
> + * checks. */
> + if (barrier_is_vertical(barrier)) {
> + /* Startpoint or endpoint on barrier? */
I don't understand what it means for a start point or end point to be
"on" the barrier. As I understand it, a barrier is located between
pixels, so a pointer can't be "on" it.
> + if ((x1 == barrier->x1 && y1 >= barrier->y1 && y1 <= barrier->y2) ||
> + (x2 == barrier->x1 && y2 >= barrier->y1 && y2 <= barrier->y2)) {
> + *distance = 0;
> + return TRUE;
> + }
> + } else {
> + if ((y1 == barrier->y1 && x1 >= barrier->x1 && x1 <= barrier->x2) ||
> + (y2 == barrier->y1 && x2 >= barrier->x1 && x2 <= barrier->x2)) {
> + *distance = 0;
> + return TRUE;
> + }
> + }
What the code actually tests for, in the vertical case, is "is the start
point or end point just _past_ the barrier?" But that is not necessarily
a blocking situation. Consider this, for example:
|*
| \
| \
| *
The function will consider this movement blocked by the barrier, but it
clearly shouldn't be. Even if this is considered a non-issue due to the
function only called for barriers that could potentially block (which
this one wouldn't be), shouldn't there still be an equivalent clause for
when the pointer is just _before_ the barrier? If not, a comment about
this asymmetry would be useful.
Also, the code here assumes that barrier->y2 >= barrier->y1, which is
never checked for. Probably, CreateBarrier() should just return BadValue
in that case.
> + ua = 0;
> + ud = (barrier->y2 - barrier->y1) * (x2 - x1) - (barrier->x2 - barrier->x1) * (y2 - y1);
> + if (ud != 0) {
> + ua = ((barrier->x2 - barrier->x1) * (y1 - barrier->y1) -
> + (barrier->y2 - barrier->y1) * (x1 - barrier->x1)) / ud;
> + ub = ((x2 - x1) * (y1 - barrier->y1) -
> + (y2 - y1) * (x1 - barrier->x1)) / ud;
> + if (ua < 0 || ua > 1 || ub < 0 || ub > 1)
> + ua = 0;
> + }
> +
> + if (ua > 0 && ua <= 1)
> + {
> + double ix = barrier->x1 + ua * (barrier->x2 - barrier->x1);
> + double iy = barrier->y1 + ua * (barrier->y2 - barrier->y1);
> +
> + *distance = sqrt(pow(x1 - ix, 2) + pow(y1 - iy, 2));
> + rc = TRUE;
> + }
> +
> + return rc;
> +}
If you wanted to avoid the square root here, I think the algorithm would
work just as well or better with squared distances.
However, a more fundamental issue is that the code mixes pointer
coordinates and barrier coordinates (this may be why it doesn't handle
edge cases well).
A barrier is located between pixels, which means the barrier coordinate
3 represents the gap between the three first and the fourth
pixel. However, the cursor coordinate 3 represents the center of the
third pixel.
This means any computation that involves both has to add (0.5, 0.5) to
the cursor coordinates to get correct results.
It's probably safe to do the whole thing in double precision and then
round to integers at the end, but another possibility might be to use
exact fractions - since the pseudo code in the modified algorithm above
relies on equality testing which is iffy with floating point.
I think that because diagonal movements in the iterative algorithm are
always followed by either horizontal or vertical moves, the size of the
integers involved in the fractions will never grow large.
Regardless of floating point vs. fractions, some of the math can be done
without divisions. The equation for a cursor movement is this:
dx = x2 - x1
dy = y2 - y1
x = x1 + dx/dy * (y - y1)
We can find the x coordinate where the movement intersects a horizontal
barrier by plugging in the y coordinate of the barrier. By multiplying
with dy on both sides, we get:
dy * x = dy * x1 + dx * (y - y1)
Then, to determine whether the computed x is *on* the barrier, we need
to compare it to the end points:
x >= barrier->x1 && x < barrier->x2
We can multiply by dy on both sides of those equations (though
note that if dy is negative, the inequality signs must be
reversed):
if (dy >= 0)
on_b = (dy * x >= dy * barrier->x1 && dy * x < dy * barrier->x2)
else
on_b = (dy * x <= dy * barrier->x1 && dy * x > dy * barrier->x2)
Then, plugging in dy * x from the equation, we get
dy_x = dy * x1 + dx * (y - y1);
if (dy >= 0)
on_b = (dy_x >= dy * barrier->x1 && dy_x < dy * barrier->x2)
else
on_b = (dy_x <= dy * barrier->x1 && dy_x > dy * barrier->x2)
Computing the precise x value of the intersection would still require
divisions, as far as I can tell, but that has to be done only for
barriers that actually block.
> +/**
> + * Find the nearest barrier that is blocking movement from x1/y1 to x2/y2.
> + *
> + * @param dir Only barriers blocking movement in direction dir are checked
> + * @param x1 X start coordinate of movement vector
> + * @param y1 Y start coordinate of movement vector
> + * @param x2 X end coordinate of movement vector
> + * @param y2 Y end coordinate of movement vector
> + * @param exclude Exclude this barrier from any checks
> + * @return The barrier nearest to the movement origin that blocks this movement.
> + */
> +static struct PointerBarrier*
> +barrier_find_nearest(CursorScreenPtr cs, int dir,
> + int x1, int y1, int x2, int y2,
> + struct PointerBarrier *exclude)
> +{
> + struct PointerBarrierClient *c;
> + struct PointerBarrier *nearest = NULL;
> + double min_distance = INT_MAX; /* can't get higher than that in X anyway */
If squared distances are used, min_distance could be as high as sqrt(2) * UINT32_MAX.
> +/**
> + * Clamp to the given barrier given the movement direction specified in dir.
> + *
> + * @param barrier The barrier to clamp to
> + * @param dir The movement direction
> + * @param[out] x The clamped x coordinate.
> + * @param[out] y The clamped x coordinate.
> + */
> +void
> +barrier_clamp_to_barrier(struct PointerBarrier *barrier, int dir, int *x, int *y)
> +{
> + if (barrier_is_vertical(barrier)) {
> + if ((dir & BarrierNegativeX) & ~barrier->directions)
> + *x = barrier->x1 + 1;
> + if ((dir & BarrierPositiveX) & ~barrier->directions)
> + *x = barrier->x1 - 1;
> + }
> + if (barrier_is_horizontal(barrier))
> + {
> + if ((dir & BarrierNegativeY) & ~barrier->directions)
> + *y = barrier->y1 + 1;
> + if ((dir & BarrierPositiveY) & ~barrier->directions)
> + *y = barrier->y1 - 1;
> + }
> +}
This function is not quite correct because clamping to the positive side
of a barrier should simply set the coordinate to the barrier
coordinate. Consider for example clamping to a horizontal barrier at
y=1. That barrier should allow a cursor to be positioned at y=1.
Also, the braces are formatted inconsistently in this function.
> +static void
> +CursorConstrainCursorHarder(DeviceIntPtr dev, ScreenPtr screen, int mode, int *x, int *y)
> +{
> + CursorScreenPtr cs = GetCursorScreen(screen);
> +
> + if (cs->barriers && !IsFloating(dev) && mode == Relative) {
> + int ox, oy;
> + int dir;
> + struct PointerBarrier *nearest = NULL;
> +
> + /* where are we coming from */
> + miPointerGetPosition(dev, &ox, &oy);
> +
> + /* How this works:
> + * Given the origin and the movement vector, get the nearest barrier
> + * to the origin that is blocking the movement.
> + * Clamp to that barrier.
> + * Then, check from the clamped position to the original
> + * destination, again finding the nearest barrier and clamping.
> + */
> + dir = barrier_get_direction(ox, oy, *x, *y);
> +
> + nearest = barrier_find_nearest(cs, dir, ox, oy, *x, *y, NULL);
> + if (nearest) {
> + barrier_clamp_to_barrier(nearest, dir, x, y);
I might be misunderstanding this code, but it seems to me that the
clamped position is used as the new *destination*, and not as the new
origin as the comment says.
> +
> + if (barrier_is_vertical(nearest)) {
> + dir &= ~(BarrierNegativeX | BarrierPositiveX);
> + ox = *x;
> + } else if (barrier_is_horizontal(nearest)) {
> + dir &= ~(BarrierNegativeY | BarrierPositiveY);
> + oy = *y;
> + }
> +
> + nearest = barrier_find_nearest(cs, dir, ox, oy, *x, *y, nearest);
> + if (nearest) {
> + barrier_clamp_to_barrier(nearest, dir, x, y);
> + }
> + }
> + }
Does this code handle this situation correctly:
*
-------------\-----
--------\-
*
I may be misunderstanding something, but it seems to me that the code
will first clamp to the top barrier, and then it will exclude that
barrier, find the bottom barrier and clamp to that - ie., it can
penetrate the top barrier and get trapped between them.
Also, doesn't this function need to keep iterating until the cursor
position stops changing?
> +int
> +ProcXFixesCreatePointerBarrier (ClientPtr client)
> +{
...
> + /* This sure does need fixing. */
> + if (stuff->num_devices)
> + return BadImplementation;
This still does need fixing, although maybe the multiple-device support
could be dropped from the first version, and then later a new request
could be added with that feature.
> + b.x1 = stuff->x1;
> + b.x2 = stuff->x2;
> + b.y1 = stuff->y1;
> + b.y2 = stuff->y2;
> +
> + if (!barrier_is_horizontal(&b) && !barrier_is_vertical(&b))
> + return BadValue;
As mentioned earlier, I think we also need a check that y2 >= y1 and
x2 >= x1. Also, degenerate barriers with zero extents in both directions
should probably case BadValue as well.
Soren
More information about the xorg-devel
mailing list