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     void cubicEndPoints(const SkDCubic& pts) {
     27         cubicEndPoints(pts, 0, 1);
     28         if (dx() == 0 && dy() == 0) {
     29             cubicEndPoints(pts, 0, 2);
     30             if (dx() == 0 && dy() == 0) {
     31                 cubicEndPoints(pts, 0, 3);
     32             }
     33         }
     34     }
     35 
     36     void cubicEndPoints(const SkDCubic& pts, int s, int e) {
     37         a = pts[s].fY - pts[e].fY;
     38         b = pts[e].fX - pts[s].fX;
     39         c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
     40     }
     41 
     42     void lineEndPoints(const SkDLine& pts) {
     43         a = pts[0].fY - pts[1].fY;
     44         b = pts[1].fX - pts[0].fX;
     45         c = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY;
     46     }
     47 
     48     void quadEndPoints(const SkDQuad& pts) {
     49         quadEndPoints(pts, 0, 1);
     50         if (dx() == 0 && dy() == 0) {
     51             quadEndPoints(pts, 0, 2);
     52         }
     53     }
     54 
     55     void quadEndPoints(const SkDQuad& pts, int s, int e) {
     56         a = pts[s].fY - pts[e].fY;
     57         b = pts[e].fX - pts[s].fX;
     58         c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
     59     }
     60 
     61     double normalSquared() const {
     62         return a * a + b * b;
     63     }
     64 
     65     bool normalize() {
     66         double normal = sqrt(normalSquared());
     67         if (approximately_zero(normal)) {
     68             a = b = c = 0;
     69             return false;
     70         }
     71         double reciprocal = 1 / normal;
     72         a *= reciprocal;
     73         b *= reciprocal;
     74         c *= reciprocal;
     75         return true;
     76     }
     77 
     78     void cubicDistanceY(const SkDCubic& pts, SkDCubic& distance) const {
     79         double oneThird = 1 / 3.0;
     80         for (int index = 0; index < 4; ++index) {
     81             distance[index].fX = index * oneThird;
     82             distance[index].fY = a * pts[index].fX + b * pts[index].fY + c;
     83         }
     84     }
     85 
     86     void quadDistanceY(const SkDQuad& pts, SkDQuad& distance) const {
     87         double oneHalf = 1 / 2.0;
     88         for (int index = 0; index < 3; ++index) {
     89             distance[index].fX = index * oneHalf;
     90             distance[index].fY = a * pts[index].fX + b * pts[index].fY + c;
     91         }
     92     }
     93 
     94     double controlPtDistance(const SkDCubic& pts, int index) const {
     95         SkASSERT(index == 1 || index == 2);
     96         return a * pts[index].fX + b * pts[index].fY + c;
     97     }
     98 
     99     double controlPtDistance(const SkDQuad& pts) const {
    100         return a * pts[1].fX + b * pts[1].fY + c;
    101     }
    102 
    103     double pointDistance(const SkDPoint& pt) const {
    104         return a * pt.fX + b * pt.fY + c;
    105     }
    106 
    107     double dx() const {
    108         return b;
    109     }
    110 
    111     double dy() const {
    112         return -a;
    113     }
    114 
    115 private:
    116     double a;
    117     double b;
    118     double c;
    119 };
    120