1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
3 * Copyright © 2004 Carl Worth
4 * Copyright © 2006 Red Hat, Inc.
5 * Copyright © 2008 Chris Wilson
6 * Copyright © 2014 Intel Corporation
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.
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
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/
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.
31 * The Original Code is the cairo graphics library.
33 * The Initial Developer of the Original Code is Keith Packard
36 * Carl D. Worth <cworth@cworth.org>
37 * Chris Wilson <chris@chris-wilson.co.uk>
43 #include "cairo-line-inline.h"
44 #include "cairo-slope-private.h"
47 line_compare_for_y_against_x (const cairo_line_t
*a
,
55 if (x
< a
->p1
.x
&& x
< a
->p2
.x
)
57 if (x
> a
->p1
.x
&& x
> a
->p2
.x
)
60 adx
= a
->p2
.x
- a
->p1
.x
;
65 if (dx
== 0 || (adx
^ dx
) < 0)
69 ady
= a
->p2
.y
- a
->p1
.y
;
71 L
= _cairo_int32x32_64_mul (dy
, adx
);
72 R
= _cairo_int32x32_64_mul (dx
, ady
);
74 return _cairo_int64_cmp (L
, R
);
78 * We need to compare the x-coordinates of a pair of lines for a particular y,
79 * without loss of precision.
81 * The x-coordinate along an edge for a given y is:
82 * X = A_x + (Y - A_y) * A_dx / A_dy
84 * So the inequality we wish to test is:
85 * A_x + (Y - A_y) * A_dx / A_dy ∘ B_x + (Y - B_y) * B_dx / B_dy,
86 * where ∘ is our inequality operator.
88 * By construction, we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are
89 * all positive, so we can rearrange it thus without causing a sign change:
90 * A_dy * B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx * A_dy
91 * - (Y - A_y) * A_dx * B_dy
93 * Given the assumption that all the deltas fit within 32 bits, we can compute
94 * this comparison directly using 128 bit arithmetic. For certain, but common,
95 * input we can reduce this down to a single 32 bit compare by inspecting the
98 * (And put the burden of the work on developing fast 128 bit ops, which are
99 * required throughout the tessellator.)
101 * See the similar discussion for _slope_compare().
104 lines_compare_x_for_y_general (const cairo_line_t
*a
,
105 const cairo_line_t
*b
,
108 /* XXX: We're assuming here that dx and dy will still fit in 32
109 * bits. That's not true in general as there could be overflow. We
110 * should prevent that before the tessellation algorithm
120 HAVE_DX_ADX
= HAVE_DX
| HAVE_ADX
,
122 HAVE_DX_BDX
= HAVE_DX
| HAVE_BDX
,
123 HAVE_ADX_BDX
= HAVE_ADX
| HAVE_BDX
,
124 HAVE_ALL
= HAVE_DX
| HAVE_ADX
| HAVE_BDX
125 } have_dx_adx_bdx
= HAVE_ALL
;
127 ady
= a
->p2
.y
- a
->p1
.y
;
128 adx
= a
->p2
.x
- a
->p1
.x
;
130 have_dx_adx_bdx
&= ~HAVE_ADX
;
132 bdy
= b
->p2
.y
- b
->p1
.y
;
133 bdx
= b
->p2
.x
- b
->p1
.x
;
135 have_dx_adx_bdx
&= ~HAVE_BDX
;
137 dx
= a
->p1
.x
- b
->p1
.x
;
139 have_dx_adx_bdx
&= ~HAVE_DX
;
141 #define L _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy), dx)
142 #define A _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx, bdy), y - a->p1.y)
143 #define B _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->p1.y)
144 switch (have_dx_adx_bdx
) {
149 /* A_dy * B_dy * (A_x - B_x) ∘ 0 */
150 return dx
; /* ady * bdy is positive definite */
152 /* 0 ∘ - (Y - A_y) * A_dx * B_dy */
153 return adx
; /* bdy * (y - a->top.y) is positive definite */
155 /* 0 ∘ (Y - B_y) * B_dx * A_dy */
156 return -bdx
; /* ady * (y - b->top.y) is positive definite */
158 /* 0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */
159 if ((adx
^ bdx
) < 0) {
161 } else if (a
->p1
.y
== b
->p1
.y
) { /* common origin */
162 cairo_int64_t adx_bdy
, bdx_ady
;
164 /* ∴ A_dx * B_dy ∘ B_dx * A_dy */
166 adx_bdy
= _cairo_int32x32_64_mul (adx
, bdy
);
167 bdx_ady
= _cairo_int32x32_64_mul (bdx
, ady
);
169 return _cairo_int64_cmp (adx_bdy
, bdx_ady
);
171 return _cairo_int128_cmp (A
, B
);
173 /* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */
174 if ((-adx
^ dx
) < 0) {
177 cairo_int64_t ady_dx
, dy_adx
;
179 ady_dx
= _cairo_int32x32_64_mul (ady
, dx
);
180 dy_adx
= _cairo_int32x32_64_mul (a
->p1
.y
- y
, adx
);
182 return _cairo_int64_cmp (ady_dx
, dy_adx
);
185 /* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */
186 if ((bdx
^ dx
) < 0) {
189 cairo_int64_t bdy_dx
, dy_bdx
;
191 bdy_dx
= _cairo_int32x32_64_mul (bdy
, dx
);
192 dy_bdx
= _cairo_int32x32_64_mul (y
- b
->p1
.y
, bdx
);
194 return _cairo_int64_cmp (bdy_dx
, dy_bdx
);
197 /* XXX try comparing (a->p2.x - b->p2.x) et al */
198 return _cairo_int128_cmp (L
, _cairo_int128_sub (B
, A
));
206 lines_compare_x_for_y (const cairo_line_t
*a
,
207 const cairo_line_t
*b
,
210 /* If the sweep-line is currently on an end-point of a line,
211 * then we know its precise x value (and considering that we often need to
212 * compare events at end-points, this happens frequently enough to warrant
219 HAVE_BOTH
= HAVE_AX
| HAVE_BX
220 } have_ax_bx
= HAVE_BOTH
;
225 else if (y
== a
->p2
.y
)
228 have_ax_bx
&= ~HAVE_AX
;
232 else if (y
== b
->p2
.y
)
235 have_ax_bx
&= ~HAVE_BX
;
237 switch (have_ax_bx
) {
240 return lines_compare_x_for_y_general (a
, b
, y
);
242 return -line_compare_for_y_against_x (b
, y
, ax
);
244 return line_compare_for_y_against_x (a
, y
, bx
);
250 static int bbox_compare (const cairo_line_t
*a
,
251 const cairo_line_t
*b
)
256 if (a
->p1
.x
< a
->p2
.x
) {
264 if (b
->p1
.x
< b
->p2
.x
) {
281 int cairo_lines_compare_at_y (const cairo_line_t
*a
,
282 const cairo_line_t
*b
,
285 cairo_slope_t sa
, sb
;
288 if (cairo_lines_equal (a
, b
))
291 /* Don't bother solving for abscissa if the edges' bounding boxes
292 * can be used to order them.
294 ret
= bbox_compare (a
, b
);
298 ret
= lines_compare_x_for_y (a
, b
, y
);
302 _cairo_slope_init (&sa
, &a
->p1
, &a
->p2
);
303 _cairo_slope_init (&sb
, &b
->p1
, &b
->p2
);
305 return _cairo_slope_compare (&sb
, &sa
);