Rev 1892 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1892 | serge | 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 |
||
38 | */ |
||
39 | |||
40 | #include "cairoint.h" |
||
41 | |||
3959 | Serge | 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 | |||
1892 | serge | 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; |
||
3959 | Serge | 90 | while (--num_boxes) |
91 | _cairo_box_add_box (extents, ++boxes); |
||
1892 | serge | 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 | |||
3959 | Serge | 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 | |||
1892 | serge | 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 |
||
3959 | Serge | 192 | _cairo_box_intersects_line_segment (const cairo_box_t *box, cairo_line_t *line) |
1892 | serge | 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 | |||
3959 | Serge | 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) |
||
1892 | serge | 265 | { |
3959 | Serge | 266 | _cairo_box_add_point (closure, point); |
267 | |||
268 | return CAIRO_STATUS_SUCCESS; |
||
1892 | serge | 269 | } |
3959 | Serge | 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 | }>>>>>>>>>> |