source/libs/cairo/cairo-src/src/cairo-slope.c

   1 /* cairo - a vector graphics library with display and print output
   2  *
   3  * Copyright © 2002 University of Southern California
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it either under the terms of the GNU Lesser General Public
   7  * License version 2.1 as published by the Free Software Foundation
   8  * (the "LGPL") or, at your option, under the terms of the Mozilla
   9  * Public License Version 1.1 (the "MPL"). If you do not alter this
  10  * notice, a recipient may use your version of this file under either
  11  * the MPL or the LGPL.
  12  *
  13  * You should have received a copy of the LGPL along with this library
  14  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  15  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  16  * You should have received a copy of the MPL along with this library
  17  * in the file COPYING-MPL-1.1
  18  *
  19  * The contents of this file are subject to the Mozilla Public License
  20  * Version 1.1 (the "License"); you may not use this file except in
  21  * compliance with the License. You may obtain a copy of the License at
  22  * http://www.mozilla.org/MPL/
  23  *
  24  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  25  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  26  * the specific language governing rights and limitations.
  27  *
  28  * The Original Code is the cairo graphics library.
  29  *
  30  * The Initial Developer of the Original Code is University of Southern
  31  * California.
  32  *
  33  * Contributor(s):
  34  *      Carl D. Worth <cworth@cworth.org>
  35  */
  36
  37 #include "cairoint.h"
  38
  39 #include "cairo-slope-private.h"
  40
  41 /* Compare two slopes. Slope angles begin at 0 in the direction of the
  42    positive X axis and increase in the direction of the positive Y
  43    axis.
  44
  45    This function always compares the slope vectors based on the
  46    smaller angular difference between them, (that is based on an
  47    angular difference that is strictly less than pi). To break ties
  48    when comparing slope vectors with an angular difference of exactly
  49    pi, the vector with a positive dx (or positive dy if dx's are zero)
  50    is considered to be more positive than the other.
  51
  52    Also, all slope vectors with both dx==0 and dy==0 are considered
  53    equal and more positive than any non-zero vector.
  54
  55    <  0 => a less positive than b
  56    == 0 => a equal to b
  57    >  0 => a more positive than b
  58 */
  59 int
  60 _cairo_slope_compare (const cairo_slope_t *a, const cairo_slope_t *b)
  61 {
  62     cairo_int64_t ady_bdx = _cairo_int32x32_64_mul (a->dy, b->dx);
  63     cairo_int64_t bdy_adx = _cairo_int32x32_64_mul (b->dy, a->dx);
  64     int cmp;
  65
  66     cmp = _cairo_int64_cmp (ady_bdx, bdy_adx);
  67     if (cmp)
  68         return cmp;
  69
  70     /* special-case zero vectors.  the intended logic here is:
  71      * zero vectors all compare equal, and more positive than any
  72      * non-zero vector.
  73      */
  74     if (a->dx == 0 && a->dy == 0 && b->dx == 0 && b->dy ==0)
  75         return 0;
  76     if (a->dx == 0 && a->dy == 0)
  77         return 1;
  78     if (b->dx == 0 && b->dy ==0)
  79         return -1;
  80
  81     /* Finally, we're looking at two vectors that are either equal or
  82      * that differ by exactly pi. We can identify the "differ by pi"
  83      * case by looking for a change in sign in either dx or dy between
  84      * a and b.
  85      *
  86      * And in these cases, we eliminate the ambiguity by reducing the angle
  87      * of b by an infinitesimally small amount, (that is, 'a' will
  88      * always be considered less than 'b').
  89      */
  90     if ((a->dx ^ b->dx) < 0 || (a->dy ^ b->dy) < 0) {
  91         if (a->dx > 0 || (a->dx == 0 && a->dy > 0))
  92             return -1;
  93         else
  94             return +1;
  95     }
  96
  97     /* Finally, for identical slopes, we obviously return 0. */
  98     return 0;
  99 }