michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #include "SkPathOpsCubic.h"
michael@0: #include "SkPathOpsLine.h"
michael@0: #include "SkPathOpsQuad.h"
michael@0: 
michael@0: // Sources
michael@0: // computer-aided design - volume 22 number 9 november 1990 pp 538 - 549
michael@0: // online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
michael@0: 
michael@0: // This turns a line segment into a parameterized line, of the form
michael@0: // ax + by + c = 0
michael@0: // When a^2 + b^2 == 1, the line is normalized.
michael@0: // The distance to the line for (x, y) is d(x,y) = ax + by + c
michael@0: //
michael@0: // Note that the distances below are not necessarily normalized. To get the true
michael@0: // distance, it's necessary to either call normalize() after xxxEndPoints(), or
michael@0: // divide the result of xxxDistance() by sqrt(normalSquared())
michael@0: 
michael@0: class SkLineParameters {
michael@0: public:
michael@0: 
michael@0:     void cubicEndPoints(const SkDCubic& pts) {
michael@0:         int endIndex = 1;
michael@0:         cubicEndPoints(pts, 0, endIndex);
michael@0:         if (dy() != 0) {
michael@0:             return;
michael@0:         }
michael@0:         if (dx() == 0) {
michael@0:             cubicEndPoints(pts, 0, ++endIndex);
michael@0:             SkASSERT(endIndex == 2);
michael@0:             if (dy() != 0) {
michael@0:                 return;
michael@0:             }
michael@0:             if (dx() == 0) {
michael@0:                 cubicEndPoints(pts, 0, ++endIndex);  // line
michael@0:                 SkASSERT(endIndex == 3);
michael@0:                 return;
michael@0:             }
michael@0:         }
michael@0:         if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
michael@0:             return;
michael@0:         }
michael@0:         // if cubic tangent is on x axis, look at next control point to break tie
michael@0:         // control point may be approximate, so it must move significantly to account for error
michael@0:         if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) {
michael@0:             if (pts[0].fY > pts[endIndex].fY) {
michael@0:                 a = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
michael@0:             }
michael@0:             return;
michael@0:         }
michael@0:         if (endIndex == 3) {
michael@0:             return;
michael@0:         }
michael@0:         SkASSERT(endIndex == 2);
michael@0:         if (pts[0].fY > pts[3].fY) {
michael@0:             a = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     void cubicEndPoints(const SkDCubic& pts, int s, int e) {
michael@0:         a = pts[s].fY - pts[e].fY;
michael@0:         b = pts[e].fX - pts[s].fX;
michael@0:         c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
michael@0:     }
michael@0: 
michael@0:     double cubicPart(const SkDCubic& part) {
michael@0:         cubicEndPoints(part);
michael@0:         if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) {
michael@0:             return pointDistance(part[3]);
michael@0:         }
michael@0:         return pointDistance(part[2]);
michael@0:     }
michael@0: 
michael@0:     void lineEndPoints(const SkDLine& pts) {
michael@0:         a = pts[0].fY - pts[1].fY;
michael@0:         b = pts[1].fX - pts[0].fX;
michael@0:         c = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY;
michael@0:     }
michael@0: 
michael@0:     void quadEndPoints(const SkDQuad& pts) {
michael@0:         quadEndPoints(pts, 0, 1);
michael@0:         if (dy() != 0) {
michael@0:             return;
michael@0:         }
michael@0:         if (dx() == 0) {
michael@0:             quadEndPoints(pts, 0, 2);
michael@0:             return;
michael@0:         }
michael@0:         if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
michael@0:             return;
michael@0:         }
michael@0:         if (pts[0].fY > pts[2].fY) {
michael@0:             a = DBL_EPSILON;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     void quadEndPoints(const SkDQuad& pts, int s, int e) {
michael@0:         a = pts[s].fY - pts[e].fY;
michael@0:         b = pts[e].fX - pts[s].fX;
michael@0:         c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
michael@0:     }
michael@0: 
michael@0:     double quadPart(const SkDQuad& part) {
michael@0:         quadEndPoints(part);
michael@0:         return pointDistance(part[2]);
michael@0:     }
michael@0: 
michael@0:     double normalSquared() const {
michael@0:         return a * a + b * b;
michael@0:     }
michael@0: 
michael@0:     bool normalize() {
michael@0:         double normal = sqrt(normalSquared());
michael@0:         if (approximately_zero(normal)) {
michael@0:             a = b = c = 0;
michael@0:             return false;
michael@0:         }
michael@0:         double reciprocal = 1 / normal;
michael@0:         a *= reciprocal;
michael@0:         b *= reciprocal;
michael@0:         c *= reciprocal;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     void cubicDistanceY(const SkDCubic& pts, SkDCubic& distance) const {
michael@0:         double oneThird = 1 / 3.0;
michael@0:         for (int index = 0; index < 4; ++index) {
michael@0:             distance[index].fX = index * oneThird;
michael@0:             distance[index].fY = a * pts[index].fX + b * pts[index].fY + c;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     void quadDistanceY(const SkDQuad& pts, SkDQuad& distance) const {
michael@0:         double oneHalf = 1 / 2.0;
michael@0:         for (int index = 0; index < 3; ++index) {
michael@0:             distance[index].fX = index * oneHalf;
michael@0:             distance[index].fY = a * pts[index].fX + b * pts[index].fY + c;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     double controlPtDistance(const SkDCubic& pts, int index) const {
michael@0:         SkASSERT(index == 1 || index == 2);
michael@0:         return a * pts[index].fX + b * pts[index].fY + c;
michael@0:     }
michael@0: 
michael@0:     double controlPtDistance(const SkDQuad& pts) const {
michael@0:         return a * pts[1].fX + b * pts[1].fY + c;
michael@0:     }
michael@0: 
michael@0:     double pointDistance(const SkDPoint& pt) const {
michael@0:         return a * pt.fX + b * pt.fY + c;
michael@0:     }
michael@0: 
michael@0:     double dx() const {
michael@0:         return b;
michael@0:     }
michael@0: 
michael@0:     double dy() const {
michael@0:         return -a;
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     double a;
michael@0:     double b;
michael@0:     double c;
michael@0: };