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     int n;
  89
  90     assert (num_boxes > 0);
  91     *extents = *boxes;
  92
  93     for (n = 1; n < num_boxes; n++) {
  94         if (boxes[n].p1.x < extents->p1.x)
  95             extents->p1.x = boxes[n].p1.x;
  96         if (boxes[n].p2.x > extents->p2.x)
  97             extents->p2.x = boxes[n].p2.x;
  98
  99         if (boxes[n].p1.y < extents->p1.y)
 100             extents->p1.y = boxes[n].p1.y;
 101         if (boxes[n].p2.y > extents->p2.y)
 102             extents->p2.y = boxes[n].p2.y;
 103     }
 104 }
 105
 106 /* XXX We currently have a confusing mix of boxes and rectangles as
 107  * exemplified by this function.  A #cairo_box_t is a rectangular area
 108  * represented by the coordinates of the upper left and lower right
 109  * corners, expressed in fixed point numbers.  A #cairo_rectangle_int_t is
 110  * also a rectangular area, but represented by the upper left corner
 111  * and the width and the height, as integer numbers.
 112  *
 113  * This function converts a #cairo_box_t to a #cairo_rectangle_int_t by
 114  * increasing the area to the nearest integer coordinates.  We should
 115  * standardize on #cairo_rectangle_fixed_t and #cairo_rectangle_int_t, and
 116  * this function could be renamed to the more reasonable
 117  * _cairo_rectangle_fixed_round.
 118  */
 119
 120 void
 121 _cairo_box_round_to_rectangle (const cairo_box_t     *box,
 122                                cairo_rectangle_int_t *rectangle)
 123 {
 124     rectangle->x = _cairo_fixed_integer_floor (box->p1.x);
 125     rectangle->y = _cairo_fixed_integer_floor (box->p1.y);
 126     rectangle->width = _cairo_fixed_integer_ceil (box->p2.x) - rectangle->x;
 127     rectangle->height = _cairo_fixed_integer_ceil (box->p2.y) - rectangle->y;
 128 }
 129
 130 cairo_bool_t
 131 _cairo_rectangle_intersect (cairo_rectangle_int_t *dst,
 132                             const cairo_rectangle_int_t *src)
 133 {
 134     int x1, y1, x2, y2;
 135
 136     x1 = MAX (dst->x, src->x);
 137     y1 = MAX (dst->y, src->y);
 138     /* Beware the unsigned promotion, fortunately we have bits to spare
 139      * as (CAIRO_RECT_INT_MAX - CAIRO_RECT_INT_MIN) < UINT_MAX
 140      */
 141     x2 = MIN (dst->x + (int) dst->width,  src->x + (int) src->width);
 142     y2 = MIN (dst->y + (int) dst->height, src->y + (int) src->height);
 143
 144     if (x1 >= x2 || y1 >= y2) {
 145         dst->x = 0;
 146         dst->y = 0;
 147         dst->width  = 0;
 148         dst->height = 0;
 149
 150         return FALSE;
 151     } else {
 152         dst->x = x1;
 153         dst->y = y1;
 154         dst->width  = x2 - x1;
 155         dst->height = y2 - y1;
 156
 157         return TRUE;
 158     }
 159 }
 160
 161 /* Extends the dst rectangle to also contain src.
 162  * If one of the rectangles is empty, the result is undefined
 163  */
 164 void
 165 _cairo_rectangle_union (cairo_rectangle_int_t *dst,
 166                         const cairo_rectangle_int_t *src)
 167 {
 168     int x1, y1, x2, y2;
 169
 170     x1 = MIN (dst->x, src->x);
 171     y1 = MIN (dst->y, src->y);
 172     /* Beware the unsigned promotion, fortunately we have bits to spare
 173      * as (CAIRO_RECT_INT_MAX - CAIRO_RECT_INT_MIN) < UINT_MAX
 174      */
 175     x2 = MAX (dst->x + (int) dst->width,  src->x + (int) src->width);
 176     y2 = MAX (dst->y + (int) dst->height, src->y + (int) src->height);
 177
 178     dst->x = x1;
 179     dst->y = y1;
 180     dst->width  = x2 - x1;
 181     dst->height = y2 - y1;
 182 }
 183
 184 #define P1x (line->p1.x)
 185 #define P1y (line->p1.y)
 186 #define P2x (line->p2.x)
 187 #define P2y (line->p2.y)
 188 #define B1x (box->p1.x)
 189 #define B1y (box->p1.y)
 190 #define B2x (box->p2.x)
 191 #define B2y (box->p2.y)
 192
 193 /*
 194  * Check whether any part of line intersects box.  This function essentially
 195  * computes whether the ray starting at line->p1 in the direction of line->p2
 196  * intersects the box before it reaches p2.  Normally, this is done
 197  * by dividing by the lengths of the line projected onto each axis.  Because
 198  * we're in fixed point, this function does a bit more work to avoid having to
 199  * do the division -- we don't care about the actual intersection point, so
 200  * it's of no interest to us.
 201  */
 202
 203 cairo_bool_t
 204 _cairo_box_intersects_line_segment (cairo_box_t *box, cairo_line_t *line)
 205 {
 206     cairo_fixed_t t1=0, t2=0, t3=0, t4=0;
 207     cairo_int64_t t1y, t2y, t3x, t4x;
 208
 209     cairo_fixed_t xlen, ylen;
 210
 211     if (_cairo_box_contains_point (box, &line->p1) ||
 212         _cairo_box_contains_point (box, &line->p2))
 213         return TRUE;
 214
 215     xlen = P2x - P1x;
 216     ylen = P2y - P1y;
 217
 218     if (xlen) {
 219         if (xlen > 0) {
 220             t1 = B1x - P1x;
 221             t2 = B2x - P1x;
 222         } else {
 223             t1 = P1x - B2x;
 224             t2 = P1x - B1x;
 225             xlen = - xlen;
 226         }
 227
 228         if ((t1 < 0 || t1 > xlen) &&
 229             (t2 < 0 || t2 > xlen))
 230             return FALSE;
 231     } else {
 232         /* Fully vertical line -- check that X is in bounds */
 233         if (P1x < B1x || P1x > B2x)
 234             return FALSE;
 235     }
 236
 237     if (ylen) {
 238         if (ylen > 0) {
 239             t3 = B1y - P1y;
 240             t4 = B2y - P1y;
 241         } else {
 242             t3 = P1y - B2y;
 243             t4 = P1y - B1y;
 244             ylen = - ylen;
 245         }
 246
 247         if ((t3 < 0 || t3 > ylen) &&
 248             (t4 < 0 || t4 > ylen))
 249             return FALSE;
 250     } else {
 251         /* Fully horizontal line -- check Y */
 252         if (P1y < B1y || P1y > B2y)
 253             return FALSE;
 254     }
 255
 256     /* If we had a horizontal or vertical line, then it's already been checked */
 257     if (P1x == P2x || P1y == P2y)
 258         return TRUE;
 259
 260     /* Check overlap.  Note that t1 < t2 and t3 < t4 here. */
 261     t1y = _cairo_int32x32_64_mul (t1, ylen);
 262     t2y = _cairo_int32x32_64_mul (t2, ylen);
 263     t3x = _cairo_int32x32_64_mul (t3, xlen);
 264     t4x = _cairo_int32x32_64_mul (t4, xlen);
 265
 266     if (_cairo_int64_lt(t1y, t4x) &&
 267         _cairo_int64_lt(t3x, t2y))
 268         return TRUE;
 269
 270     return FALSE;
 271 }
 272
 273 static cairo_status_t
 274 _cairo_box_add_spline_point (void *closure,
 275                              const cairo_point_t *point,
 276                              const cairo_slope_t *tangent)
 277 {
 278     _cairo_box_add_point (closure, point);
 279
 280     return CAIRO_STATUS_SUCCESS;
 281 }
 282
 283 /* assumes a has been previously added */
 284 void
 285 _cairo_box_add_curve_to (cairo_box_t *extents,
 286                          const cairo_point_t *a,
 287                          const cairo_point_t *b,
 288                          const cairo_point_t *c,
 289                          const cairo_point_t *d)
 290 {
 291     _cairo_box_add_point (extents, d);
 292     if (!_cairo_box_contains_point (extents, b) ||
 293         !_cairo_box_contains_point (extents, c))
 294     {
 295         cairo_status_t status;
 296
 297         status = _cairo_spline_bound (_cairo_box_add_spline_point,
 298                                       extents, a, b, c, d);
 299         assert (status == CAIRO_STATUS_SUCCESS);
 300     }
 301 }
 302
 303 void
 304 _cairo_rectangle_int_from_double (cairo_rectangle_int_t *recti,
 305                                   const cairo_rectangle_t *rectf)
 306 {
 307         recti->x = floor (rectf->x);
 308         recti->y = floor (rectf->y);
 309         recti->width  = ceil (rectf->x + rectf->width) - floor (rectf->x);
 310         recti->height = ceil (rectf->y + rectf->height) - floor (rectf->y);
 311 }