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