src/third_party/skia/src/pathops/SkLineParameters.h

   1 /*
   2  * Copyright 2012 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7 #include "SkPathOpsCubic.h"
   8 #include "SkPathOpsLine.h"
   9 #include "SkPathOpsQuad.h"
  10
  11 // Sources
  12 // computer-aided design - volume 22 number 9 november 1990 pp 538 - 549
  13 // online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
  14
  15 // This turns a line segment into a parameterized line, of the form
  16 // ax + by + c = 0
  17 // When a^2 + b^2 == 1, the line is normalized.
  18 // The distance to the line for (x, y) is d(x,y) = ax + by + c
  19 //
  20 // Note that the distances below are not necessarily normalized. To get the true
  21 // distance, it's necessary to either call normalize() after xxxEndPoints(), or
  22 // divide the result of xxxDistance() by sqrt(normalSquared())
  23
  24 class SkLineParameters {
  25 public:
  26
  27     bool cubicEndPoints(const SkDCubic& pts) {
  28         int endIndex = 1;
  29         cubicEndPoints(pts, 0, endIndex);
  30         if (dy() != 0) {
  31             return true;
  32         }
  33         if (dx() == 0) {
  34             cubicEndPoints(pts, 0, ++endIndex);
  35             SkASSERT(endIndex == 2);
  36             if (dy() != 0) {
  37                 return true;
  38             }
  39             if (dx() == 0) {
  40                 cubicEndPoints(pts, 0, ++endIndex);  // line
  41                 SkASSERT(endIndex == 3);
  42                 return false;
  43             }
  44         }
  45         // FIXME: after switching to round sort, remove bumping fA
  46         if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
  47             return true;
  48         }
  49         // if cubic tangent is on x axis, look at next control point to break tie
  50         // control point may be approximate, so it must move significantly to account for error
  51         if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) {
  52             if (pts[0].fY > pts[endIndex].fY) {
  53                 fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
  54             }
  55             return true;
  56         }
  57         if (endIndex == 3) {
  58             return true;
  59         }
  60         SkASSERT(endIndex == 2);
  61         if (pts[0].fY > pts[3].fY) {
  62             fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
  63         }
  64         return true;
  65     }
  66
  67     void cubicEndPoints(const SkDCubic& pts, int s, int e) {
  68         fA = pts[s].fY - pts[e].fY;
  69         fB = pts[e].fX - pts[s].fX;
  70         fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
  71     }
  72
  73     double cubicPart(const SkDCubic& part) {
  74         cubicEndPoints(part);
  75         if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) {
  76             return pointDistance(part[3]);
  77         }
  78         return pointDistance(part[2]);
  79     }
  80
  81     void lineEndPoints(const SkDLine& pts) {
  82         fA = pts[0].fY - pts[1].fY;
  83         fB = pts[1].fX - pts[0].fX;
  84         fC = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY;
  85     }
  86
  87     bool quadEndPoints(const SkDQuad& pts) {
  88         quadEndPoints(pts, 0, 1);
  89         if (dy() != 0) {
  90             return true;
  91         }
  92         if (dx() == 0) {
  93             quadEndPoints(pts, 0, 2);
  94             return false;
  95         }
  96         if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
  97             return true;
  98         }
  99         // FIXME: after switching to round sort, remove this
 100         if (pts[0].fY > pts[2].fY) {
 101             fA = DBL_EPSILON;
 102         }
 103         return true;
 104     }
 105
 106     void quadEndPoints(const SkDQuad& pts, int s, int e) {
 107         fA = pts[s].fY - pts[e].fY;
 108         fB = pts[e].fX - pts[s].fX;
 109         fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
 110     }
 111
 112     double quadPart(const SkDQuad& part) {
 113         quadEndPoints(part);
 114         return pointDistance(part[2]);
 115     }
 116
 117     double normalSquared() const {
 118         return fA * fA + fB * fB;
 119     }
 120
 121     bool normalize() {
 122         double normal = sqrt(normalSquared());
 123         if (approximately_zero(normal)) {
 124             fA = fB = fC = 0;
 125             return false;
 126         }
 127         double reciprocal = 1 / normal;
 128         fA *= reciprocal;
 129         fB *= reciprocal;
 130         fC *= reciprocal;
 131         return true;
 132     }
 133
 134     void cubicDistanceY(const SkDCubic& pts, SkDCubic& distance) const {
 135         double oneThird = 1 / 3.0;
 136         for (int index = 0; index < 4; ++index) {
 137             distance[index].fX = index * oneThird;
 138             distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC;
 139         }
 140     }
 141
 142     void quadDistanceY(const SkDQuad& pts, SkDQuad& distance) const {
 143         double oneHalf = 1 / 2.0;
 144         for (int index = 0; index < 3; ++index) {
 145             distance[index].fX = index * oneHalf;
 146             distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC;
 147         }
 148     }
 149
 150     double controlPtDistance(const SkDCubic& pts, int index) const {
 151         SkASSERT(index == 1 || index == 2);
 152         return fA * pts[index].fX + fB * pts[index].fY + fC;
 153     }
 154
 155     double controlPtDistance(const SkDQuad& pts) const {
 156         return fA * pts[1].fX + fB * pts[1].fY + fC;
 157     }
 158
 159     double pointDistance(const SkDPoint& pt) const {
 160         return fA * pt.fX + fB * pt.fY + fC;
 161     }
 162
 163     double dx() const {
 164         return fB;
 165     }
 166
 167     double dy() const {
 168         return -fA;
 169     }
 170
 171 private:
 172     double fA;
 173     double fB;
 174     double fC;
 175 };