[PATCH] DIX/ConfineTo: Improve algorithm to jump to the nearest point inside

[Egbert Eich]

Hi Keith,

sorry for delaying this. I was occupied with other things and
therefore wanted to wait for a bigger time window.

On Fri, Oct 04, 2013 at 04:07:28PM -0700, Keith Packard wrote:
> Egbert Eich <eich at freedesktop.org> writes:
> 
> > ConfineToShape does not work well: The cursor often times doesn't jump
> > to the point closest to the current cursor position outside the shape.
> > This patch fixes this.
> 
> I came up with something a bit simpler which confines the point to each
> box in the region and then picks the result which moves the cursor the
> shortest distance. I think it would generate the same result, but I
> stuck a bunch of range tests in the distance computation to avoid
> overflow in weird cases. Dunno if you like this better or not?

Yeah, it's definitely simpler and it is doing the same thing.
It tests for the opposite condition and therefore doesn't need 
as many test cases.

Something else I noticed: If the pointer is placed outside the horizontal
and vertical strips determined by the bounding box of the window, placement 
is still wrong.
This is due to the clamping of the cursor coordinates to the bounding box on
grabs. For shaped windows - at least with the new ConfineTo in place - this
clamping seems not to be required.
A patch will follow.

> 
> commit d8a52a3a3b5bc4a1ff0a986e87dd6c36366e531b
> Author: Keith Packard <keithp at keithp.com>
> Date:   Fri Oct 4 16:00:49 2013 -0700
> 
>     Improved ConfineToShape
>     
>     Find the box within the region which is closest to the point and move
>     there.
>     
>     Signed-off-by: Keith Packard <keithp at keithp.com>
> 
> diff --git a/dix/events.c b/dix/events.c
> index 086601a..8610e60 100644
> --- a/dix/events.c
> +++ b/dix/events.c
> @@ -667,37 +667,62 @@ SetCriticalEvent(int event)
>      criticalEvents[event >> 3] |= 1 << (event & 7);
>  }
>  
> +static uint32_t
> +ConfineToBox(int x, int y, BoxPtr box, int *px, int16_t *py)

                                                    ^^^^^^
   You probably want to use an int here or fix the other types
   as well. As it is it will produce a big compiler warning.
   I see your point here, you wanted to make sure that the 
   distance ^ 2 still fits into an int. But this is already
   done by clamping dx and dy to 32767.

> +{
> +    int dx, dy;
> +
> +    *px = x;
> +    *py = y;
> +
> +    if (*px < box->x1)
> +        *px = box->x1;
> +    else if (*px >= box->x2)
> +        *px = box->x2 - 1;
> +
> +    if (*py < box->y1)
> +        *py = box->y1;
> +    else if (*py >= box->y2)
> +        *py = box->y2 - 1;
> +
> +    dx = x - *px;
> +    if (dx < 0) dx = -dx;
> +    if (dx > 32767)
> +        dx = 32767;
> +    dy = y - *py;
> +    if (dy < 0) dy = -dy;
> +    if (dy > 32767)
> +        dy = 32767;
> +
> +    return (uint32_t) dx * (uint32_t) dx + (uint32_t) dy * (uint32_t) dy;
> +}
> +
>  void
>  ConfineToShape(DeviceIntPtr pDev, RegionPtr shape, int *px, int *py)
>  {
> -    BoxRec box;
> +    BoxPtr box;
> +    int nbox;
>      int x = *px, y = *py;
> -    int incx = 1, incy = 1;
> +    int bx, by;
> +    uint32_t box_dist_2;
> +    int best_x, best_y;
> +    uint32_t best_dist_2;
> +    int i;
>  
> -    if (RegionContainsPoint(shape, x, y, &box))
> +    if (RegionContainsPoint(shape, x, y, NULL))
>          return;
> -    box = *RegionExtents(shape);
> -    /* this is rather crude */
> -    do {
> -        x += incx;
> -        if (x >= box.x2) {
> -            incx = -1;
> -            x = *px - 1;
> -        }
> -        else if (x < box.x1) {
> -            incx = 1;
> -            x = *px;
> -            y += incy;
> -            if (y >= box.y2) {
> -                incy = -1;
> -                y = *py - 1;
> -            }
> -            else if (y < box.y1)
> -                return;         /* should never get here! */
> +    box = REGION_RECTS(shape);

You probably intended to do:

       nbox = REGION_NUM_RECTS(shape);
       for (i = 0; i < nbox; i++) {
       ....

> +    for (i = 0; i < REGION_NUM_RECTS(shape); i++) {
> +        box_dist_2 = ConfineToBox(x, y, &box[i], &bx, &by);


[..]

Cheers,
	Egbert.