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
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