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 24class SkLineParameters { 25public: 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 115private: 116 double a; 117 double b; 118 double c; 119}; 120