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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 cairo_private void
  43 _cairo_box_from_doubles (cairo_box_t *box,
  44                          double *x1, double *y1,
  45                          double *x2, double *y2)
  46 {
  47     box->p1.x = _cairo_fixed_from_double (*x1);
  48     box->p1.y = _cairo_fixed_from_double (*y1);
  49     box->p2.x = _cairo_fixed_from_double (*x2);
  50     box->p2.y = _cairo_fixed_from_double (*y2);
  51 }
  52
  53 cairo_private void
  54 _cairo_box_to_doubles (const cairo_box_t *box,
  55                        double *x1, double *y1,
  56                        double *x2, double *y2)
  57 {
  58     *x1 = _cairo_fixed_to_double (box->p1.x);
  59     *y1 = _cairo_fixed_to_double (box->p1.y);
  60     *x2 = _cairo_fixed_to_double (box->p2.x);
  61     *y2 = _cairo_fixed_to_double (box->p2.y);
  62 }
  63
  64 void
  65 _cairo_box_from_rectangle (cairo_box_t                 *box,
  66                            const cairo_rectangle_int_t *rect)
  67 {
  68     box->p1.x = _cairo_fixed_from_int (rect->x);
  69     box->p1.y = _cairo_fixed_from_int (rect->y);
  70     box->p2.x = _cairo_fixed_from_int (rect->x + rect->width);
  71     box->p2.y = _cairo_fixed_from_int (rect->y + rect->height);
  72 }
  73
  74 /* XXX We currently have a confusing mix of boxes and rectangles as
  75  * exemplified by this function.  A #cairo_box_t is a rectangular area
  76  * represented by the coordinates of the upper left and lower right
  77  * corners, expressed in fixed point numbers.  A #cairo_rectangle_int_t is
  78  * also a rectangular area, but represented by the upper left corner
  79  * and the width and the height, as integer numbers.
  80  *
  81  * This function converts a #cairo_box_t to a #cairo_rectangle_int_t by
  82  * increasing the area to the nearest integer coordinates.  We should
  83  * standardize on #cairo_rectangle_fixed_t and #cairo_rectangle_int_t, and
  84  * this function could be renamed to the more reasonable
  85  * _cairo_rectangle_fixed_round.
  86  */
  87
  88 void
  89 _cairo_box_round_to_rectangle (const cairo_box_t     *box,
  90                                cairo_rectangle_int_t *rectangle)
  91 {
  92     rectangle->x = _cairo_fixed_integer_floor (box->p1.x);
  93     rectangle->y = _cairo_fixed_integer_floor (box->p1.y);
  94     rectangle->width = _cairo_fixed_integer_ceil (box->p2.x) - rectangle->x;
  95     rectangle->height = _cairo_fixed_integer_ceil (box->p2.y) - rectangle->y;
  96 }
  97
  98 cairo_bool_t
  99 _cairo_rectangle_intersect (cairo_rectangle_int_t *dst,
 100                             const cairo_rectangle_int_t *src)
 101 {
 102     int x1, y1, x2, y2;
 103
 104     x1 = MAX (dst->x, src->x);
 105     y1 = MAX (dst->y, src->y);
 106     /* Beware the unsigned promotion, fortunately we have bits to spare
 107      * as (CAIRO_RECT_INT_MAX - CAIRO_RECT_INT_MIN) < UINT_MAX
 108      */
 109     x2 = MIN (dst->x + (int) dst->width,  src->x + (int) src->width);
 110     y2 = MIN (dst->y + (int) dst->height, src->y + (int) src->height);
 111
 112     if (x1 >= x2 || y1 >= y2) {
 113         dst->x = 0;
 114         dst->y = 0;
 115         dst->width  = 0;
 116         dst->height = 0;
 117
 118         return FALSE;
 119     } else {
 120         dst->x = x1;
 121         dst->y = y1;
 122         dst->width  = x2 - x1;
 123         dst->height = y2 - y1;
 124
 125         return TRUE;
 126     }
 127 }
 128
 129 #define P1x (line->p1.x)
 130 #define P1y (line->p1.y)
 131 #define P2x (line->p2.x)
 132 #define P2y (line->p2.y)
 133 #define B1x (box->p1.x)
 134 #define B1y (box->p1.y)
 135 #define B2x (box->p2.x)
 136 #define B2y (box->p2.y)
 137
 138 /*
 139  * Check whether any part of line intersects box.  This function essentially
 140  * computes whether the ray starting at line->p1 in the direction of line->p2
 141  * intersects the box before it reaches p2.  Normally, this is done
 142  * by dividing by the lengths of the line projected onto each axis.  Because
 143  * we're in fixed point, this function does a bit more work to avoid having to
 144  * do the division -- we don't care about the actual intersection point, so
 145  * it's of no interest to us.
 146  */
 147
 148 cairo_bool_t
 149 _cairo_box_intersects_line_segment (cairo_box_t *box, cairo_line_t *line)
 150 {
 151     cairo_fixed_t t1=0, t2=0, t3=0, t4=0;
 152     cairo_int64_t t1y, t2y, t3x, t4x;
 153
 154     cairo_fixed_t xlen, ylen;
 155
 156     if (_cairo_box_contains_point (box, &line->p1) ||
 157         _cairo_box_contains_point (box, &line->p2))
 158         return TRUE;
 159
 160     xlen = P2x - P1x;
 161     ylen = P2y - P1y;
 162
 163     if (xlen) {
 164         if (xlen > 0) {
 165             t1 = B1x - P1x;
 166             t2 = B2x - P1x;
 167         } else {
 168             t1 = P1x - B2x;
 169             t2 = P1x - B1x;
 170             xlen = - xlen;
 171         }
 172
 173         if ((t1 < 0 || t1 > xlen) &&
 174             (t2 < 0 || t2 > xlen))
 175             return FALSE;
 176     } else {
 177         /* Fully vertical line -- check that X is in bounds */
 178         if (P1x < B1x || P1x > B2x)
 179             return FALSE;
 180     }
 181
 182     if (ylen) {
 183         if (ylen > 0) {
 184             t3 = B1y - P1y;
 185             t4 = B2y - P1y;
 186         } else {
 187             t3 = P1y - B2y;
 188             t4 = P1y - B1y;
 189             ylen = - ylen;
 190         }
 191
 192         if ((t3 < 0 || t3 > ylen) &&
 193             (t4 < 0 || t4 > ylen))
 194             return FALSE;
 195     } else {
 196         /* Fully horizontal line -- check Y */
 197         if (P1y < B1y || P1y > B2y)
 198             return FALSE;
 199     }
 200
 201     /* If we had a horizontal or vertical line, then it's already been checked */
 202     if (P1x == P2x || P1y == P2y)
 203         return TRUE;
 204
 205     /* Check overlap.  Note that t1 < t2 and t3 < t4 here. */
 206     t1y = _cairo_int32x32_64_mul (t1, ylen);
 207     t2y = _cairo_int32x32_64_mul (t2, ylen);
 208     t3x = _cairo_int32x32_64_mul (t3, xlen);
 209     t4x = _cairo_int32x32_64_mul (t4, xlen);
 210
 211     if (_cairo_int64_lt(t1y, t4x) &&
 212         _cairo_int64_lt(t3x, t2y))
 213         return TRUE;
 214
 215     return FALSE;
 216 }
 217
 218 cairo_bool_t
 219 _cairo_box_contains_point (cairo_box_t *box, const cairo_point_t *point)
 220 {
 221     if (point->x < box->p1.x || point->x > box->p2.x ||
 222         point->y < box->p1.y || point->y > box->p2.y)
 223         return FALSE;
 224     return TRUE;
 225 }
 226
 227 void
 228 _cairo_composite_rectangles_init(
 229         cairo_composite_rectangles_t    *rects,
 230         int                              all_x,
 231         int                              all_y,
 232         int                              width,
 233         int                              height)
 234 {
 235         rects->src.x = all_x;
 236         rects->src.y = all_y;
 237         rects->mask.x = all_x;
 238         rects->mask.y = all_y;
 239         rects->clip.x = all_x;
 240         rects->clip.y = all_y;
 241         rects->dst.x = all_x;
 242         rects->dst.y = all_y;
 243
 244         rects->width = width;
 245         rects->height = height;
 246 }