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
28class SkLineParameters {
29public:
30
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
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
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
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
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
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
116 double quadPart(const SkDQuad& part) {
117 quadEndPoints(part);
118 return pointDistance(part[2]);
119 }
120
121 double normalSquared() const {
122 return fA * fA + fB * fB;
123 }
124
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
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 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
159 double controlPtDistance(const SkDQuad& pts) const {
160 return fA * pts[1].fX + fB * pts[1].fY + fC;
161 }
162
163 double pointDistance(const SkDPoint& pt) const {
164 return fA * pt.fX + fB * pt.fY + fC;
165 }
166
167 double dx() const {
168 return fB;
169 }
170
171 double dy() const {
172 return -fA;
173 }
174
175private:
176 double fA;
177 double fB;
178 double fC;
179};
180
181#endif
182