src/cairo-rectangle.c

   1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
   2 /* cairo - a vector graphics library with display and print output
   3  *
   4  * Copyright © 2002 University of Southern California
   5  * Copyright © 2005 Red Hat, Inc.
   6  * Copyright © 2006 Red Hat, Inc.
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it either under the terms of the GNU Lesser General Public
  10  * License version 2.1 as published by the Free Software Foundation
  11  * (the "LGPL") or, at your option, under the terms of the Mozilla
  12  * Public License Version 1.1 (the "MPL"). If you do not alter this
  13  * notice, a recipient may use your version of this file under either
  14  * the MPL or the LGPL.
  15  *
  16  * You should have received a copy of the LGPL along with this library
  17  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  19  * You should have received a copy of the MPL along with this library
  20  * in the file COPYING-MPL-1.1
  21  *
  22  * The contents of this file are subject to the Mozilla Public License
  23  * Version 1.1 (the "License"); you may not use this file except in
  24  * compliance with the License. You may obtain a copy of the License at
  25  * http://www.mozilla.org/MPL/
  26  *
  27  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  28  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  29  * the specific language governing rights and limitations.
  30  *
  31  * The Original Code is the cairo graphics library.
  32  *
  33  * The Initial Developer of the Original Code is University of Southern
  34  * California.
  35  *
  36  * Contributor(s):
  37  *      Carl D. Worth <cworth@cworth.org>
  38  */
  39
  40 #include "cairoint.h"
  41
  42 #include "cairo-box-inline.h"
  43
  44 const cairo_rectangle_int_t _cairo_empty_rectangle = { 0, 0, 0, 0 };
  45 const cairo_rectangle_int_t _cairo_unbounded_rectangle = {
  46      CAIRO_RECT_INT_MIN, CAIRO_RECT_INT_MIN,
  47      CAIRO_RECT_INT_MAX - CAIRO_RECT_INT_MIN,
  48      CAIRO_RECT_INT_MAX - CAIRO_RECT_INT_MIN,
  49 };
  50
  51 cairo_private void
  52 _cairo_box_from_doubles (cairo_box_t *box,
  53                          double *x1, double *y1,
  54                          double *x2, double *y2)
  55 {
  56     box->p1.x = _cairo_fixed_from_double (*x1);
  57     box->p1.y = _cairo_fixed_from_double (*y1);
  58     box->p2.x = _cairo_fixed_from_double (*x2);
  59     box->p2.y = _cairo_fixed_from_double (*y2);
  60 }
  61
  62 cairo_private void
  63 _cairo_box_to_doubles (const cairo_box_t *box,
  64                        double *x1, double *y1,
  65                        double *x2, double *y2)
  66 {
  67     *x1 = _cairo_fixed_to_double (box->p1.x);
  68     *y1 = _cairo_fixed_to_double (box->p1.y);
  69     *x2 = _cairo_fixed_to_double (box->p2.x);
  70     *y2 = _cairo_fixed_to_double (box->p2.y);
  71 }
  72
  73 void
  74 _cairo_box_from_rectangle (cairo_box_t                 *box,
  75                            const cairo_rectangle_int_t *rect)
  76 {
  77     box->p1.x = _cairo_fixed_from_int (rect->x);
  78     box->p1.y = _cairo_fixed_from_int (rect->y);
  79     box->p2.x = _cairo_fixed_from_int (rect->x + rect->width);
  80     box->p2.y = _cairo_fixed_from_int (rect->y + rect->height);
  81 }
  82
  83 void
  84 _cairo_boxes_get_extents (const cairo_box_t *boxes,
  85                           int num_boxes,
  86                           cairo_box_t *extents)
  87 {
  88     assert (num_boxes > 0);
  89     *extents = *boxes;
  90     while (--num_boxes)
  91         _cairo_box_add_box (extents, ++boxes);
  92 }
  93
  94 /* XXX We currently have a confusing mix of boxes and rectangles as
  95  * exemplified by this function.  A #cairo_box_t is a rectangular area
  96  * represented by the coordinates of the upper left and lower right
  97  * corners, expressed in fixed point numbers.  A #cairo_rectangle_int_t is
  98  * also a rectangular area, but represented by the upper left corner
  99  * and the width and the height, as integer numbers.
 100  *
 101  * This function converts a #cairo_box_t to a #cairo_rectangle_int_t by
 102  * increasing the area to the nearest integer coordinates.  We should
 103  * standardize on #cairo_rectangle_fixed_t and #cairo_rectangle_int_t, and
 104  * this function could be renamed to the more reasonable
 105  * _cairo_rectangle_fixed_round.
 106  */
 107
 108 void
 109 _cairo_box_round_to_rectangle (const cairo_box_t     *box,
 110                                cairo_rectangle_int_t *rectangle)
 111 {
 112     rectangle->x = _cairo_fixed_integer_floor (box->p1.x);
 113     rectangle->y = _cairo_fixed_integer_floor (box->p1.y);
 114     rectangle->width = _cairo_fixed_integer_ceil (box->p2.x) - rectangle->x;
 115     rectangle->height = _cairo_fixed_integer_ceil (box->p2.y) - rectangle->y;
 116 }
 117
 118 cairo_bool_t
 119 _cairo_rectangle_intersect (cairo_rectangle_int_t *dst,
 120                             const cairo_rectangle_int_t *src)
 121 {
 122     int x1, y1, x2, y2;
 123
 124     x1 = MAX (dst->x, src->x);
 125     y1 = MAX (dst->y, src->y);
 126     /* Beware the unsigned promotion, fortunately we have bits to spare
 127      * as (CAIRO_RECT_INT_MAX - CAIRO_RECT_INT_MIN) < UINT_MAX
 128      */
 129     x2 = MIN (dst->x + (int) dst->width,  src->x + (int) src->width);
 130     y2 = MIN (dst->y + (int) dst->height, src->y + (int) src->height);
 131
 132     if (x1 >= x2 || y1 >= y2) {
 133         dst->x = 0;
 134         dst->y = 0;
 135         dst->width  = 0;
 136         dst->height = 0;
 137
 138         return FALSE;
 139     } else {
 140         dst->x = x1;
 141         dst->y = y1;
 142         dst->width  = x2 - x1;
 143         dst->height = y2 - y1;
 144
 145         return TRUE;
 146     }
 147 }
 148
 149 cairo_bool_t
 150 _cairo_rectangle_exact_intersect (cairo_rectangle_t *dst,
 151                                   const cairo_rectangle_t *src)
 152 {
 153     double x1, y1, x2, y2;
 154
 155     x1 = MAX (dst->x, src->x);
 156     y1 = MAX (dst->y, src->y);
 157     /* Beware the unsigned promotion, fortunately we have bits to spare
 158      * as (CAIRO_RECT_INT_MAX - CAIRO_RECT_INT_MIN) < UINT_MAX
 159      */
 160     x2 = MIN (dst->x + dst->width,  src->x + src->width);
 161     y2 = MIN (dst->y + dst->height, src->y + src->height);
 162
 163     if (x1 >= x2 || y1 >= y2) {
 164         dst->x = 0;
 165         dst->y = 0;
 166         dst->width  = 0;
 167         dst->height = 0;
 168
 169         return FALSE;
 170     } else {
 171         dst->x = x1;
 172         dst->y = y1;
 173         dst->width  = x2 - x1;
 174         dst->height = y2 - y1;
 175
 176         return TRUE;
 177     }
 178 }
 179
 180 /* Extends the dst rectangle to also contain src.
 181  * If one of the rectangles is empty, the result is undefined
 182  */
 183 void
 184 _cairo_rectangle_union (cairo_rectangle_int_t *dst,
 185                         const cairo_rectangle_int_t *src)
 186 {
 187     int x1, y1, x2, y2;
 188
 189     x1 = MIN (dst->x, src->x);
 190     y1 = MIN (dst->y, src->y);
 191     /* Beware the unsigned promotion, fortunately we have bits to spare
 192      * as (CAIRO_RECT_INT_MAX - CAIRO_RECT_INT_MIN) < UINT_MAX
 193      */
 194     x2 = MAX (dst->x + (int) dst->width,  src->x + (int) src->width);
 195     y2 = MAX (dst->y + (int) dst->height, src->y + (int) src->height);
 196
 197     dst->x = x1;
 198     dst->y = y1;
 199     dst->width  = x2 - x1;
 200     dst->height = y2 - y1;
 201 }
 202
 203 #define P1x (line->p1.x)
 204 #define P1y (line->p1.y)
 205 #define P2x (line->p2.x)
 206 #define P2y (line->p2.y)
 207 #define B1x (box->p1.x)
 208 #define B1y (box->p1.y)
 209 #define B2x (box->p2.x)
 210 #define B2y (box->p2.y)
 211
 212 /*
 213  * Check whether any part of line intersects box.  This function essentially
 214  * computes whether the ray starting at line->p1 in the direction of line->p2
 215  * intersects the box before it reaches p2.  Normally, this is done
 216  * by dividing by the lengths of the line projected onto each axis.  Because
 217  * we're in fixed point, this function does a bit more work to avoid having to
 218  * do the division -- we don't care about the actual intersection point, so
 219  * it's of no interest to us.
 220  */
 221
 222 cairo_bool_t
 223 _cairo_box_intersects_line_segment (const cairo_box_t *box, cairo_line_t *line)
 224 {
 225     cairo_fixed_t t1=0, t2=0, t3=0, t4=0;
 226     cairo_int64_t t1y, t2y, t3x, t4x;
 227
 228     cairo_fixed_t xlen, ylen;
 229
 230     if (_cairo_box_contains_point (box, &line->p1) ||
 231         _cairo_box_contains_point (box, &line->p2))
 232         return TRUE;
 233
 234     xlen = P2x - P1x;
 235     ylen = P2y - P1y;
 236
 237     if (xlen) {
 238         if (xlen > 0) {
 239             t1 = B1x - P1x;
 240             t2 = B2x - P1x;
 241         } else {
 242             t1 = P1x - B2x;
 243             t2 = P1x - B1x;
 244             xlen = - xlen;
 245         }
 246
 247         if ((t1 < 0 || t1 > xlen) &&
 248             (t2 < 0 || t2 > xlen))
 249             return FALSE;
 250     } else {
 251         /* Fully vertical line -- check that X is in bounds */
 252         if (P1x < B1x || P1x > B2x)
 253             return FALSE;
 254     }
 255
 256     if (ylen) {
 257         if (ylen > 0) {
 258             t3 = B1y - P1y;
 259             t4 = B2y - P1y;
 260         } else {
 261             t3 = P1y - B2y;
 262             t4 = P1y - B1y;
 263             ylen = - ylen;
 264         }
 265
 266         if ((t3 < 0 || t3 > ylen) &&
 267             (t4 < 0 || t4 > ylen))
 268             return FALSE;
 269     } else {
 270         /* Fully horizontal line -- check Y */
 271         if (P1y < B1y || P1y > B2y)
 272             return FALSE;
 273     }
 274
 275     /* If we had a horizontal or vertical line, then it's already been checked */
 276     if (P1x == P2x || P1y == P2y)
 277         return TRUE;
 278
 279     /* Check overlap.  Note that t1 < t2 and t3 < t4 here. */
 280     t1y = _cairo_int32x32_64_mul (t1, ylen);
 281     t2y = _cairo_int32x32_64_mul (t2, ylen);
 282     t3x = _cairo_int32x32_64_mul (t3, xlen);
 283     t4x = _cairo_int32x32_64_mul (t4, xlen);
 284
 285     if (_cairo_int64_lt(t1y, t4x) &&
 286         _cairo_int64_lt(t3x, t2y))
 287         return TRUE;
 288
 289     return FALSE;
 290 }
 291
 292 static cairo_status_t
 293 _cairo_box_add_spline_point (void *closure,
 294                              const cairo_point_t *point,
 295                              const cairo_slope_t *tangent)
 296 {
 297     _cairo_box_add_point (closure, point);
 298
 299     return CAIRO_STATUS_SUCCESS;
 300 }
 301
 302 /* assumes a has been previously added */
 303 void
 304 _cairo_box_add_curve_to (cairo_box_t *extents,
 305                          const cairo_point_t *a,
 306                          const cairo_point_t *b,
 307                          const cairo_point_t *c,
 308                          const cairo_point_t *d)
 309 {
 310     _cairo_box_add_point (extents, d);
 311     if (!_cairo_box_contains_point (extents, b) ||
 312         !_cairo_box_contains_point (extents, c))
 313     {
 314         cairo_status_t status;
 315
 316         status = _cairo_spline_bound (_cairo_box_add_spline_point,
 317                                       extents, a, b, c, d);
 318         assert (status == CAIRO_STATUS_SUCCESS);
 319     }
 320 }
 321
 322 void
 323 _cairo_rectangle_int_from_double (cairo_rectangle_int_t *recti,
 324                                   const cairo_rectangle_t *rectf)
 325 {
 326         recti->x = floor (rectf->x);
 327         recti->y = floor (rectf->y);
 328         recti->width  = ceil (rectf->x + rectf->width) - floor (rectf->x);
 329         recti->height = ceil (rectf->y + rectf->height) - floor (rectf->y);
 330 }