blob: 92343c691bd20c9a13d3f632db9e15b71cffa2d0 [file] [log] [blame]
caryclark@google.com07393ca2013-04-08 11:47:37 +00001/*
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:
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000026
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000027 bool cubicEndPoints(const SkDCubic& pts) {
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000028 int endIndex = 1;
29 cubicEndPoints(pts, 0, endIndex);
30 if (dy() != 0) {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000031 return true;
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000032 }
33 if (dx() == 0) {
34 cubicEndPoints(pts, 0, ++endIndex);
35 SkASSERT(endIndex == 2);
36 if (dy() != 0) {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000037 return true;
caryclark@google.comcffbcc32013-06-04 17:59:42 +000038 }
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000039 if (dx() == 0) {
40 cubicEndPoints(pts, 0, ++endIndex); // line
41 SkASSERT(endIndex == 3);
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000042 return false;
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000043 }
44 }
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000045 // FIXME: after switching to round sort, remove bumping fA
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000046 if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000047 return true;
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000048 }
49 // if cubic tangent is on x axis, look at next control point to break tie
50 // control point may be approximate, so it must move significantly to account for error
51 if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) {
52 if (pts[0].fY > pts[endIndex].fY) {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000053 fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000054 }
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000055 return true;
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000056 }
57 if (endIndex == 3) {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000058 return true;
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000059 }
60 SkASSERT(endIndex == 2);
61 if (pts[0].fY > pts[3].fY) {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000062 fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
caryclark@google.comcffbcc32013-06-04 17:59:42 +000063 }
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000064 return true;
caryclark@google.com07393ca2013-04-08 11:47:37 +000065 }
66
67 void cubicEndPoints(const SkDCubic& pts, int s, int e) {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000068 fA = pts[s].fY - pts[e].fY;
69 fB = pts[e].fX - pts[s].fX;
70 fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
caryclark@google.com07393ca2013-04-08 11:47:37 +000071 }
72
caryclark@google.com570863f2013-09-16 15:55:01 +000073 double cubicPart(const SkDCubic& part) {
74 cubicEndPoints(part);
75 if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) {
76 return pointDistance(part[3]);
77 }
78 return pointDistance(part[2]);
79 }
80
caryclark@google.com07393ca2013-04-08 11:47:37 +000081 void lineEndPoints(const SkDLine& pts) {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000082 fA = pts[0].fY - pts[1].fY;
83 fB = pts[1].fX - pts[0].fX;
84 fC = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY;
caryclark@google.com07393ca2013-04-08 11:47:37 +000085 }
86
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000087 bool quadEndPoints(const SkDQuad& pts) {
caryclark@google.comcffbcc32013-06-04 17:59:42 +000088 quadEndPoints(pts, 0, 1);
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000089 if (dy() != 0) {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000090 return true;
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000091 }
92 if (dx() == 0) {
caryclark@google.comcffbcc32013-06-04 17:59:42 +000093 quadEndPoints(pts, 0, 2);
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000094 return false;
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000095 }
96 if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000097 return true;
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +000098 }
commit-bot@chromium.org4431e772014-04-14 17:08:59 +000099 // FIXME: after switching to round sort, remove this
commit-bot@chromium.org866f4e32013-11-21 17:04:29 +0000100 if (pts[0].fY > pts[2].fY) {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000101 fA = DBL_EPSILON;
caryclark@google.comcffbcc32013-06-04 17:59:42 +0000102 }
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000103 return true;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000104 }
105
106 void quadEndPoints(const SkDQuad& pts, int s, int e) {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000107 fA = pts[s].fY - pts[e].fY;
108 fB = pts[e].fX - pts[s].fX;
109 fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000110 }
111
caryclark@google.com570863f2013-09-16 15:55:01 +0000112 double quadPart(const SkDQuad& part) {
113 quadEndPoints(part);
114 return pointDistance(part[2]);
115 }
116
caryclark@google.com07393ca2013-04-08 11:47:37 +0000117 double normalSquared() const {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000118 return fA * fA + fB * fB;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000119 }
120
121 bool normalize() {
122 double normal = sqrt(normalSquared());
123 if (approximately_zero(normal)) {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000124 fA = fB = fC = 0;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000125 return false;
126 }
127 double reciprocal = 1 / normal;
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000128 fA *= reciprocal;
129 fB *= reciprocal;
130 fC *= reciprocal;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000131 return true;
132 }
133
134 void cubicDistanceY(const SkDCubic& pts, SkDCubic& distance) const {
135 double oneThird = 1 / 3.0;
136 for (int index = 0; index < 4; ++index) {
137 distance[index].fX = index * oneThird;
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000138 distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000139 }
140 }
141
142 void quadDistanceY(const SkDQuad& pts, SkDQuad& distance) const {
143 double oneHalf = 1 / 2.0;
144 for (int index = 0; index < 3; ++index) {
145 distance[index].fX = index * oneHalf;
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000146 distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000147 }
148 }
149
150 double controlPtDistance(const SkDCubic& pts, int index) const {
151 SkASSERT(index == 1 || index == 2);
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000152 return fA * pts[index].fX + fB * pts[index].fY + fC;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000153 }
154
155 double controlPtDistance(const SkDQuad& pts) const {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000156 return fA * pts[1].fX + fB * pts[1].fY + fC;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000157 }
158
159 double pointDistance(const SkDPoint& pt) const {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000160 return fA * pt.fX + fB * pt.fY + fC;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000161 }
162
163 double dx() const {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000164 return fB;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000165 }
166
167 double dy() const {
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000168 return -fA;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000169 }
170
171private:
commit-bot@chromium.org4431e772014-04-14 17:08:59 +0000172 double fA;
173 double fB;
174 double fC;
caryclark@google.com07393ca2013-04-08 11:47:37 +0000175};