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 #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     void cubicEndPoints(const SkDCubic& pts) {
     28         int endIndex = 1;
     29         cubicEndPoints(pts, 0, endIndex);
     30         if (dy() != 0) {
     31             return;
     32         }
     33         if (dx() == 0) {
     34             cubicEndPoints(pts, 0, ++endIndex);
     35             SkASSERT(endIndex == 2);
     36             if (dy() != 0) {
     37                 return;
     38             }
     39             if (dx() == 0) {
     40                 cubicEndPoints(pts, 0, ++endIndex);  // line
     41                 SkASSERT(endIndex == 3);
     42                 return;
     43             }
     44         }
     45         if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
     46             return;
     47         }
     48         // if cubic tangent is on x axis, look at next control point to break tie
     49         // control point may be approximate, so it must move significantly to account for error
     50         if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) {
     51             if (pts[0].fY > pts[endIndex].fY) {
     52                 a = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
     53             }
     54             return;
     55         }
     56         if (endIndex == 3) {
     57             return;
     58         }
     59         SkASSERT(endIndex == 2);
     60         if (pts[0].fY > pts[3].fY) {
     61             a = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
     62         }
     63     }
     64 
     65     void cubicEndPoints(const SkDCubic& pts, int s, int e) {
     66         a = pts[s].fY - pts[e].fY;
     67         b = pts[e].fX - pts[s].fX;
     68         c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
     69     }
     70 
     71     double cubicPart(const SkDCubic& part) {
     72         cubicEndPoints(part);
     73         if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) {
     74             return pointDistance(part[3]);
     75         }
     76         return pointDistance(part[2]);
     77     }
     78 
     79     void lineEndPoints(const SkDLine& pts) {
     80         a = pts[0].fY - pts[1].fY;
     81         b = pts[1].fX - pts[0].fX;
     82         c = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY;
     83     }
     84 
     85     void quadEndPoints(const SkDQuad& pts) {
     86         quadEndPoints(pts, 0, 1);
     87         if (dy() != 0) {
     88             return;
     89         }
     90         if (dx() == 0) {
     91             quadEndPoints(pts, 0, 2);
     92             return;
     93         }
     94         if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
     95             return;
     96         }
     97         if (pts[0].fY > pts[2].fY) {
     98             a = DBL_EPSILON;
     99         }
    100     }
    101 
    102     void quadEndPoints(const SkDQuad& pts, int s, int e) {
    103         a = pts[s].fY - pts[e].fY;
    104         b = pts[e].fX - pts[s].fX;
    105         c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
    106     }
    107 
    108     double quadPart(const SkDQuad& part) {
    109         quadEndPoints(part);
    110         return pointDistance(part[2]);
    111     }
    112 
    113     double normalSquared() const {
    114         return a * a + b * b;
    115     }
    116 
    117     bool normalize() {
    118         double normal = sqrt(normalSquared());
    119         if (approximately_zero(normal)) {
    120             a = b = c = 0;
    121             return false;
    122         }
    123         double reciprocal = 1 / normal;
    124         a *= reciprocal;
    125         b *= reciprocal;
    126         c *= reciprocal;
    127         return true;
    128     }
    129 
    130     void cubicDistanceY(const SkDCubic& pts, SkDCubic& distance) const {
    131         double oneThird = 1 / 3.0;
    132         for (int index = 0; index < 4; ++index) {
    133             distance[index].fX = index * oneThird;
    134             distance[index].fY = a * pts[index].fX + b * pts[index].fY + c;
    135         }
    136     }
    137 
    138     void quadDistanceY(const SkDQuad& pts, SkDQuad& distance) const {
    139         double oneHalf = 1 / 2.0;
    140         for (int index = 0; index < 3; ++index) {
    141             distance[index].fX = index * oneHalf;
    142             distance[index].fY = a * pts[index].fX + b * pts[index].fY + c;
    143         }
    144     }
    145 
    146     double controlPtDistance(const SkDCubic& pts, int index) const {
    147         SkASSERT(index == 1 || index == 2);
    148         return a * pts[index].fX + b * pts[index].fY + c;
    149     }
    150 
    151     double controlPtDistance(const SkDQuad& pts) const {
    152         return a * pts[1].fX + b * pts[1].fY + c;
    153     }
    154 
    155     double pointDistance(const SkDPoint& pt) const {
    156         return a * pt.fX + b * pt.fY + c;
    157     }
    158 
    159     double dx() const {
    160         return b;
    161     }
    162 
    163     double dy() const {
    164         return -a;
    165     }
    166 
    167 private:
    168     double a;
    169     double b;
    170     double c;
    171 };
    172