src/cairo-line.c

   1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
   2 /*
   3  * Copyright © 2004 Carl Worth
   4  * Copyright © 2006 Red Hat, Inc.
   5  * Copyright © 2008 Chris Wilson
   6  * Copyright © 2014 Intel Corporation
   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 Keith Packard
  34  *
  35  * Contributor(s):
  36  *      Carl D. Worth <cworth@cworth.org>
  37  *      Chris Wilson <chris@chris-wilson.co.uk>
  38  *
  39  */
  40
  41 #include "cairoint.h"
  42
  43 #include "cairo-line-inline.h"
  44 #include "cairo-slope-private.h"
  45
  46 static int
  47 line_compare_for_y_against_x (const cairo_line_t *a,
  48                               int32_t y,
  49                               int32_t x)
  50 {
  51     int32_t adx, ady;
  52     int32_t dx, dy;
  53     cairo_int64_t L, R;
  54
  55     if (x < a->p1.x && x < a->p2.x)
  56         return 1;
  57     if (x > a->p1.x && x > a->p2.x)
  58         return -1;
  59
  60     adx = a->p2.x - a->p1.x;
  61     dx = x - a->p1.x;
  62
  63     if (adx == 0)
  64         return -dx;
  65     if (dx == 0 || (adx ^ dx) < 0)
  66         return adx;
  67
  68     dy = y - a->p1.y;
  69     ady = a->p2.y - a->p1.y;
  70
  71     L = _cairo_int32x32_64_mul (dy, adx);
  72     R = _cairo_int32x32_64_mul (dx, ady);
  73
  74     return _cairo_int64_cmp (L, R);
  75 }
  76
  77 /*
  78  * We need to compare the x-coordinates of a pair of lines for a particular y,
  79  * without loss of precision.
  80  *
  81  * The x-coordinate along an edge for a given y is:
  82  *   X = A_x + (Y - A_y) * A_dx / A_dy
  83  *
  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.
  87  *
  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
  92  *
  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
  96  * deltas.
  97  *
  98  * (And put the burden of the work on developing fast 128 bit ops, which are
  99  * required throughout the tessellator.)
 100  *
 101  * See the similar discussion for _slope_compare().
 102  */
 103 static int
 104 lines_compare_x_for_y_general (const cairo_line_t *a,
 105                                const cairo_line_t *b,
 106                                int32_t y)
 107 {
 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
 111      * begins.
 112      */
 113     int32_t dx;
 114     int32_t adx, ady;
 115     int32_t bdx, bdy;
 116     enum {
 117        HAVE_NONE    = 0x0,
 118        HAVE_DX      = 0x1,
 119        HAVE_ADX     = 0x2,
 120        HAVE_DX_ADX  = HAVE_DX | HAVE_ADX,
 121        HAVE_BDX     = 0x4,
 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;
 126
 127     ady = a->p2.y - a->p1.y;
 128     adx = a->p2.x - a->p1.x;
 129     if (adx == 0)
 130         have_dx_adx_bdx &= ~HAVE_ADX;
 131
 132     bdy = b->p2.y - b->p1.y;
 133     bdx = b->p2.x - b->p1.x;
 134     if (bdx == 0)
 135         have_dx_adx_bdx &= ~HAVE_BDX;
 136
 137     dx = a->p1.x - b->p1.x;
 138     if (dx == 0)
 139         have_dx_adx_bdx &= ~HAVE_DX;
 140
 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) {
 145     default:
 146     case HAVE_NONE:
 147         return 0;
 148     case HAVE_DX:
 149         /* A_dy * B_dy * (A_x - B_x) ∘ 0 */
 150         return dx; /* ady * bdy is positive definite */
 151     case HAVE_ADX:
 152         /* 0 ∘  - (Y - A_y) * A_dx * B_dy */
 153         return adx; /* bdy * (y - a->top.y) is positive definite */
 154     case HAVE_BDX:
 155         /* 0 ∘ (Y - B_y) * B_dx * A_dy */
 156         return -bdx; /* ady * (y - b->top.y) is positive definite */
 157     case HAVE_ADX_BDX:
 158         /*  0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */
 159         if ((adx ^ bdx) < 0) {
 160             return adx;
 161         } else if (a->p1.y == b->p1.y) { /* common origin */
 162             cairo_int64_t adx_bdy, bdx_ady;
 163
 164             /* ∴ A_dx * B_dy ∘ B_dx * A_dy */
 165
 166             adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
 167             bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
 168
 169             return _cairo_int64_cmp (adx_bdy, bdx_ady);
 170         } else
 171             return _cairo_int128_cmp (A, B);
 172     case HAVE_DX_ADX:
 173         /* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */
 174         if ((-adx ^ dx) < 0) {
 175             return dx;
 176         } else {
 177             cairo_int64_t ady_dx, dy_adx;
 178
 179             ady_dx = _cairo_int32x32_64_mul (ady, dx);
 180             dy_adx = _cairo_int32x32_64_mul (a->p1.y - y, adx);
 181
 182             return _cairo_int64_cmp (ady_dx, dy_adx);
 183         }
 184     case HAVE_DX_BDX:
 185         /* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */
 186         if ((bdx ^ dx) < 0) {
 187             return dx;
 188         } else {
 189             cairo_int64_t bdy_dx, dy_bdx;
 190
 191             bdy_dx = _cairo_int32x32_64_mul (bdy, dx);
 192             dy_bdx = _cairo_int32x32_64_mul (y - b->p1.y, bdx);
 193
 194             return _cairo_int64_cmp (bdy_dx, dy_bdx);
 195         }
 196     case HAVE_ALL:
 197         /* XXX try comparing (a->p2.x - b->p2.x) et al */
 198         return _cairo_int128_cmp (L, _cairo_int128_sub (B, A));
 199     }
 200 #undef B
 201 #undef A
 202 #undef L
 203 }
 204
 205 static int
 206 lines_compare_x_for_y (const cairo_line_t *a,
 207                        const cairo_line_t *b,
 208                        int32_t y)
 209 {
 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
 213      * special casing).
 214      */
 215     enum {
 216        HAVE_NEITHER = 0x0,
 217        HAVE_AX      = 0x1,
 218        HAVE_BX      = 0x2,
 219        HAVE_BOTH    = HAVE_AX | HAVE_BX
 220     } have_ax_bx = HAVE_BOTH;
 221     int32_t ax, bx;
 222
 223     if (y == a->p1.y)
 224         ax = a->p1.x;
 225     else if (y == a->p2.y)
 226         ax = a->p2.x;
 227     else
 228         have_ax_bx &= ~HAVE_AX;
 229
 230     if (y == b->p1.y)
 231         bx = b->p1.x;
 232     else if (y == b->p2.y)
 233         bx = b->p2.x;
 234     else
 235         have_ax_bx &= ~HAVE_BX;
 236
 237     switch (have_ax_bx) {
 238     default:
 239     case HAVE_NEITHER:
 240         return lines_compare_x_for_y_general (a, b, y);
 241     case HAVE_AX:
 242         return -line_compare_for_y_against_x (b, y, ax);
 243     case HAVE_BX:
 244         return line_compare_for_y_against_x (a, y, bx);
 245     case HAVE_BOTH:
 246         return ax - bx;
 247     }
 248 }
 249
 250 static int bbox_compare (const cairo_line_t *a,
 251                          const cairo_line_t *b)
 252 {
 253     int32_t amin, amax;
 254     int32_t bmin, bmax;
 255
 256     if (a->p1.x < a->p2.x) {
 257         amin = a->p1.x;
 258         amax = a->p2.x;
 259     } else {
 260         amin = a->p2.x;
 261         amax = a->p1.x;
 262     }
 263
 264     if (b->p1.x < b->p2.x) {
 265         bmin = b->p1.x;
 266         bmax = b->p2.x;
 267     } else {
 268         bmin = b->p2.x;
 269         bmax = b->p1.x;
 270     }
 271
 272     if (amax < bmin)
 273         return -1;
 274
 275     if (amin > bmax)
 276         return +1;
 277
 278     return 0;
 279 }
 280
 281 int cairo_lines_compare_at_y (const cairo_line_t *a,
 282                               const cairo_line_t *b,
 283                               int y)
 284 {
 285     cairo_slope_t sa, sb;
 286     int ret;
 287
 288     if (cairo_lines_equal (a, b))
 289         return 0;
 290
 291     /* Don't bother solving for abscissa if the edges' bounding boxes
 292      * can be used to order them.
 293      */
 294     ret = bbox_compare (a, b);
 295     if (ret)
 296         return ret;
 297
 298     ret = lines_compare_x_for_y (a, b, y);
 299     if (ret)
 300         return ret;
 301
 302     _cairo_slope_init (&sa, &a->p1, &a->p2);
 303     _cairo_slope_init (&sb, &b->p1, &b->p2);
 304
 305     return _cairo_slope_compare (&sb, &sa);
 306 }