1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
/*
* Copyright 2012 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#ifndef SkLineParameters_DEFINED
#define SkLineParameters_DEFINED
#include "SkPathOpsCubic.h"
#include "SkPathOpsLine.h"
#include "SkPathOpsQuad.h"
// Sources
// computer-aided design - volume 22 number 9 november 1990 pp 538 - 549
// online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
// This turns a line segment into a parameterized line, of the form
// ax + by + c = 0
// When a^2 + b^2 == 1, the line is normalized.
// The distance to the line for (x, y) is d(x,y) = ax + by + c
//
// Note that the distances below are not necessarily normalized. To get the true
// distance, it's necessary to either call normalize() after xxxEndPoints(), or
// divide the result of xxxDistance() by sqrt(normalSquared())
class SkLineParameters {
public:
bool cubicEndPoints(const SkDCubic& pts) {
int endIndex = 1;
cubicEndPoints(pts, 0, endIndex);
if (dy() != 0) {
return true;
}
if (dx() == 0) {
cubicEndPoints(pts, 0, ++endIndex);
SkASSERT(endIndex == 2);
if (dy() != 0) {
return true;
}
if (dx() == 0) {
cubicEndPoints(pts, 0, ++endIndex); // line
SkASSERT(endIndex == 3);
return false;
}
}
// FIXME: after switching to round sort, remove bumping fA
if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
return true;
}
// if cubic tangent is on x axis, look at next control point to break tie
// control point may be approximate, so it must move significantly to account for error
if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) {
if (pts[0].fY > pts[endIndex].fY) {
fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
}
return true;
}
if (endIndex == 3) {
return true;
}
SkASSERT(endIndex == 2);
if (pts[0].fY > pts[3].fY) {
fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
}
return true;
}
void cubicEndPoints(const SkDCubic& pts, int s, int e) {
fA = pts[s].fY - pts[e].fY;
fB = pts[e].fX - pts[s].fX;
fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
}
double cubicPart(const SkDCubic& part) {
cubicEndPoints(part);
if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) {
return pointDistance(part[3]);
}
return pointDistance(part[2]);
}
void lineEndPoints(const SkDLine& pts) {
fA = pts[0].fY - pts[1].fY;
fB = pts[1].fX - pts[0].fX;
fC = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY;
}
bool quadEndPoints(const SkDQuad& pts) {
quadEndPoints(pts, 0, 1);
if (dy() != 0) {
return true;
}
if (dx() == 0) {
quadEndPoints(pts, 0, 2);
return false;
}
if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
return true;
}
// FIXME: after switching to round sort, remove this
if (pts[0].fY > pts[2].fY) {
fA = DBL_EPSILON;
}
return true;
}
void quadEndPoints(const SkDQuad& pts, int s, int e) {
fA = pts[s].fY - pts[e].fY;
fB = pts[e].fX - pts[s].fX;
fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
}
double quadPart(const SkDQuad& part) {
quadEndPoints(part);
return pointDistance(part[2]);
}
double normalSquared() const {
return fA * fA + fB * fB;
}
bool normalize() {
double normal = sqrt(normalSquared());
if (approximately_zero(normal)) {
fA = fB = fC = 0;
return false;
}
double reciprocal = 1 / normal;
fA *= reciprocal;
fB *= reciprocal;
fC *= reciprocal;
return true;
}
void cubicDistanceY(const SkDCubic& pts, SkDCubic& distance) const {
double oneThird = 1 / 3.0;
for (int index = 0; index < 4; ++index) {
distance[index].fX = index * oneThird;
distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC;
}
}
void quadDistanceY(const SkDQuad& pts, SkDQuad& distance) const {
double oneHalf = 1 / 2.0;
for (int index = 0; index < 3; ++index) {
distance[index].fX = index * oneHalf;
distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC;
}
}
double controlPtDistance(const SkDCubic& pts, int index) const {
SkASSERT(index == 1 || index == 2);
return fA * pts[index].fX + fB * pts[index].fY + fC;
}
double controlPtDistance(const SkDQuad& pts) const {
return fA * pts[1].fX + fB * pts[1].fY + fC;
}
double pointDistance(const SkDPoint& pt) const {
return fA * pt.fX + fB * pt.fY + fC;
}
double dx() const {
return fB;
}
double dy() const {
return -fA;
}
private:
double fA;
double fB;
double fC;
};
#endif
|
