Line data Source code
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 "SkPathOpsCubic.h"
12 : #include "SkPathOpsLine.h"
13 : #include "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 :
31 0 : bool cubicEndPoints(const SkDCubic& pts) {
32 0 : int endIndex = 1;
33 0 : cubicEndPoints(pts, 0, endIndex);
34 0 : if (dy() != 0) {
35 0 : return true;
36 : }
37 0 : if (dx() == 0) {
38 0 : cubicEndPoints(pts, 0, ++endIndex);
39 0 : SkASSERT(endIndex == 2);
40 0 : if (dy() != 0) {
41 0 : return true;
42 : }
43 0 : if (dx() == 0) {
44 0 : cubicEndPoints(pts, 0, ++endIndex); // line
45 0 : SkASSERT(endIndex == 3);
46 0 : return false;
47 : }
48 : }
49 : // FIXME: after switching to round sort, remove bumping fA
50 0 : if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
51 0 : 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 0 : if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) {
56 0 : if (pts[0].fY > pts[endIndex].fY) {
57 0 : fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
58 : }
59 0 : return true;
60 : }
61 0 : if (endIndex == 3) {
62 0 : return true;
63 : }
64 0 : SkASSERT(endIndex == 2);
65 0 : if (pts[0].fY > pts[3].fY) {
66 0 : fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
67 : }
68 0 : return true;
69 : }
70 :
71 0 : void cubicEndPoints(const SkDCubic& pts, int s, int e) {
72 0 : fA = pts[s].fY - pts[e].fY;
73 0 : fB = pts[e].fX - pts[s].fX;
74 0 : fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
75 0 : }
76 :
77 0 : double cubicPart(const SkDCubic& part) {
78 0 : cubicEndPoints(part);
79 0 : if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) {
80 0 : return pointDistance(part[3]);
81 : }
82 0 : return pointDistance(part[2]);
83 : }
84 :
85 0 : void lineEndPoints(const SkDLine& pts) {
86 0 : fA = pts[0].fY - pts[1].fY;
87 0 : fB = pts[1].fX - pts[0].fX;
88 0 : fC = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY;
89 0 : }
90 :
91 0 : bool quadEndPoints(const SkDQuad& pts) {
92 0 : quadEndPoints(pts, 0, 1);
93 0 : if (dy() != 0) {
94 0 : return true;
95 : }
96 0 : if (dx() == 0) {
97 0 : quadEndPoints(pts, 0, 2);
98 0 : return false;
99 : }
100 0 : if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
101 0 : return true;
102 : }
103 : // FIXME: after switching to round sort, remove this
104 0 : if (pts[0].fY > pts[2].fY) {
105 0 : fA = DBL_EPSILON;
106 : }
107 0 : return true;
108 : }
109 :
110 0 : void quadEndPoints(const SkDQuad& pts, int s, int e) {
111 0 : fA = pts[s].fY - pts[e].fY;
112 0 : fB = pts[e].fX - pts[s].fX;
113 0 : fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
114 0 : }
115 :
116 : double quadPart(const SkDQuad& part) {
117 : quadEndPoints(part);
118 : return pointDistance(part[2]);
119 : }
120 :
121 0 : double normalSquared() const {
122 0 : return fA * fA + fB * fB;
123 : }
124 :
125 0 : bool normalize() {
126 0 : double normal = sqrt(normalSquared());
127 0 : if (approximately_zero(normal)) {
128 0 : fA = fB = fC = 0;
129 0 : return false;
130 : }
131 0 : double reciprocal = 1 / normal;
132 0 : fA *= reciprocal;
133 0 : fB *= reciprocal;
134 0 : fC *= reciprocal;
135 0 : return true;
136 : }
137 :
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 :
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 :
154 0 : double controlPtDistance(const SkDCubic& pts, int index) const {
155 0 : SkASSERT(index == 1 || index == 2);
156 0 : return fA * pts[index].fX + fB * pts[index].fY + fC;
157 : }
158 :
159 0 : double controlPtDistance(const SkDQuad& pts) const {
160 0 : return fA * pts[1].fX + fB * pts[1].fY + fC;
161 : }
162 :
163 0 : double pointDistance(const SkDPoint& pt) const {
164 0 : return fA * pt.fX + fB * pt.fY + fC;
165 : }
166 :
167 0 : double dx() const {
168 0 : return fB;
169 : }
170 :
171 0 : double dy() const {
172 0 : return -fA;
173 : }
174 :
175 : private:
176 : double fA;
177 : double fB;
178 : double fC;
179 : };
180 :
181 : #endif
|
