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 /* Extends the dst rectangle to also contain src.
 150  * If one of the rectangles is empty, the result is undefined
 151  */
 152 void
 153 _cairo_rectangle_union (cairo_rectangle_int_t *dst,
 154                         const cairo_rectangle_int_t *src)
 155 {
 156     int x1, y1, x2, y2;
 157
 158     x1 = MIN (dst->x, src->x);
 159     y1 = MIN (dst->y, src->y);
 160     /* Beware the unsigned promotion, fortunately we have bits to spare
 161      * as (CAIRO_RECT_INT_MAX - CAIRO_RECT_INT_MIN) < UINT_MAX
 162      */
 163     x2 = MAX (dst->x + (int) dst->width,  src->x + (int) src->width);
 164     y2 = MAX (dst->y + (int) dst->height, src->y + (int) src->height);
 165
 166     dst->x = x1;
 167     dst->y = y1;
 168     dst->width  = x2 - x1;
 169     dst->height = y2 - y1;
 170 }
 171
 172 #define P1x (line->p1.x)
 173 #define P1y (line->p1.y)
 174 #define P2x (line->p2.x)
 175 #define P2y (line->p2.y)
 176 #define B1x (box->p1.x)
 177 #define B1y (box->p1.y)
 178 #define B2x (box->p2.x)
 179 #define B2y (box->p2.y)
 180
 181 /*
 182  * Check whether any part of line intersects box.  This function essentially
 183  * computes whether the ray starting at line->p1 in the direction of line->p2
 184  * intersects the box before it reaches p2.  Normally, this is done
 185  * by dividing by the lengths of the line projected onto each axis.  Because
 186  * we're in fixed point, this function does a bit more work to avoid having to
 187  * do the division -- we don't care about the actual intersection point, so
 188  * it's of no interest to us.
 189  */
 190
 191 cairo_bool_t
 192 _cairo_box_intersects_line_segment (cairo_box_t *box, cairo_line_t *line)
 193 {
 194     cairo_fixed_t t1=0, t2=0, t3=0, t4=0;
 195     cairo_int64_t t1y, t2y, t3x, t4x;
 196
 197     cairo_fixed_t xlen, ylen;
 198
 199     if (_cairo_box_contains_point (box, &line->p1) ||
 200         _cairo_box_contains_point (box, &line->p2))
 201         return TRUE;
 202
 203     xlen = P2x - P1x;
 204     ylen = P2y - P1y;
 205
 206     if (xlen) {
 207         if (xlen > 0) {
 208             t1 = B1x - P1x;
 209             t2 = B2x - P1x;
 210         } else {
 211             t1 = P1x - B2x;
 212             t2 = P1x - B1x;
 213             xlen = - xlen;
 214         }
 215
 216         if ((t1 < 0 || t1 > xlen) &&
 217             (t2 < 0 || t2 > xlen))
 218             return FALSE;
 219     } else {
 220         /* Fully vertical line -- check that X is in bounds */
 221         if (P1x < B1x || P1x > B2x)
 222             return FALSE;
 223     }
 224
 225     if (ylen) {
 226         if (ylen > 0) {
 227             t3 = B1y - P1y;
 228             t4 = B2y - P1y;
 229         } else {
 230             t3 = P1y - B2y;
 231             t4 = P1y - B1y;
 232             ylen = - ylen;
 233         }
 234
 235         if ((t3 < 0 || t3 > ylen) &&
 236             (t4 < 0 || t4 > ylen))
 237             return FALSE;
 238     } else {
 239         /* Fully horizontal line -- check Y */
 240         if (P1y < B1y || P1y > B2y)
 241             return FALSE;
 242     }
 243
 244     /* If we had a horizontal or vertical line, then it's already been checked */
 245     if (P1x == P2x || P1y == P2y)
 246         return TRUE;
 247
 248     /* Check overlap.  Note that t1 < t2 and t3 < t4 here. */
 249     t1y = _cairo_int32x32_64_mul (t1, ylen);
 250     t2y = _cairo_int32x32_64_mul (t2, ylen);
 251     t3x = _cairo_int32x32_64_mul (t3, xlen);
 252     t4x = _cairo_int32x32_64_mul (t4, xlen);
 253
 254     if (_cairo_int64_lt(t1y, t4x) &&
 255         _cairo_int64_lt(t3x, t2y))
 256         return TRUE;
 257
 258     return FALSE;
 259 }
 260
 261 static cairo_status_t
 262 _cairo_box_add_spline_point (void *closure,
 263                              const cairo_point_t *point,
 264                              const cairo_slope_t *tangent)
 265 {
 266     _cairo_box_add_point (closure, point);
 267
 268     return CAIRO_STATUS_SUCCESS;
 269 }
 270
 271 /* assumes a has been previously added */
 272 void
 273 _cairo_box_add_curve_to (cairo_box_t *extents,
 274                          const cairo_point_t *a,
 275                          const cairo_point_t *b,
 276                          const cairo_point_t *c,
 277                          const cairo_point_t *d)
 278 {
 279     _cairo_box_add_point (extents, d);
 280     if (!_cairo_box_contains_point (extents, b) ||
 281         !_cairo_box_contains_point (extents, c))
 282     {
 283         cairo_status_t status;
 284
 285         status = _cairo_spline_bound (_cairo_box_add_spline_point,
 286                                       extents, a, b, c, d);
 287         assert (status == CAIRO_STATUS_SUCCESS);
 288     }
 289 }
 290
 291 void
 292 _cairo_rectangle_int_from_double (cairo_rectangle_int_t *recti,
 293                                   const cairo_rectangle_t *rectf)
 294 {
 295         recti->x = floor (rectf->x);
 296         recti->y = floor (rectf->y);
 297         recti->width  = ceil (rectf->x + rectf->width) - floor (rectf->x);
 298         recti->height = ceil (rectf->y + rectf->height) - floor (rectf->y);
 299 }