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 "src/pathops/SkPathOpsCubic.h"
12 #include "src/pathops/SkPathOpsLine.h"
13 #include "src/pathops/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 
cubicEndPoints(const SkDCubic & pts)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 
cubicEndPoints(const SkDCubic & pts,int s,int e)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 
cubicPart(const SkDCubic & part)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 
lineEndPoints(const SkDLine & pts)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 
quadEndPoints(const SkDQuad & pts)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 
quadEndPoints(const SkDQuad & pts,int s,int e)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 
quadPart(const SkDQuad & part)116     double quadPart(const SkDQuad& part) {
117         quadEndPoints(part);
118         return pointDistance(part[2]);
119     }
120 
normalSquared()121     double normalSquared() const {
122         return fA * fA + fB * fB;
123     }
124 
normalize()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 
cubicDistanceY(const SkDCubic & pts,SkDCubic & distance)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 
quadDistanceY(const SkDQuad & pts,SkDQuad & distance)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 
controlPtDistance(const SkDCubic & pts,int index)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 
controlPtDistance(const SkDQuad & pts)159     double controlPtDistance(const SkDQuad& pts) const {
160         return fA * pts[1].fX + fB * pts[1].fY + fC;
161     }
162 
pointDistance(const SkDPoint & pt)163     double pointDistance(const SkDPoint& pt) const {
164         return fA * pt.fX + fB * pt.fY + fC;
165     }
166 
dx()167     double dx() const {
168         return fB;
169     }
170 
dy()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