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 #include "src/pathops/SkPathOpsCubic.h"
8 #include "src/pathops/SkPathOpsPoint.h"
9 #include "src/pathops/SkPathOpsTypes.h"
10
11 #include <algorithm>
12 #include <cstddef>
13
rotate(const SkDCubic & cubic,int zero,int index,SkDCubic & rotPath)14 static bool rotate(const SkDCubic& cubic, int zero, int index, SkDCubic& rotPath) {
15 double dy = cubic[index].fY - cubic[zero].fY;
16 double dx = cubic[index].fX - cubic[zero].fX;
17 if (approximately_zero(dy)) {
18 if (approximately_zero(dx)) {
19 return false;
20 }
21 rotPath = cubic;
22 if (dy) {
23 rotPath[index].fY = cubic[zero].fY;
24 int mask = other_two(index, zero);
25 int side1 = index ^ mask;
26 int side2 = zero ^ mask;
27 if (approximately_equal(cubic[side1].fY, cubic[zero].fY)) {
28 rotPath[side1].fY = cubic[zero].fY;
29 }
30 if (approximately_equal(cubic[side2].fY, cubic[zero].fY)) {
31 rotPath[side2].fY = cubic[zero].fY;
32 }
33 }
34 return true;
35 }
36 for (int i = 0; i < 4; ++i) {
37 rotPath[i].fX = cubic[i].fX * dx + cubic[i].fY * dy;
38 rotPath[i].fY = cubic[i].fY * dx - cubic[i].fX * dy;
39 }
40 return true;
41 }
42
43
44 // Returns 0 if negative, 1 if zero, 2 if positive
side(double x)45 static int side(double x) {
46 return (x > 0) + (x >= 0);
47 }
48
49 /* Given a cubic, find the convex hull described by the end and control points.
50 The hull may have 3 or 4 points. Cubics that degenerate into a point or line
51 are not considered.
52
53 The hull is computed by assuming that three points, if unique and non-linear,
54 form a triangle. The fourth point may replace one of the first three, may be
55 discarded if in the triangle or on an edge, or may be inserted between any of
56 the three to form a convex quadralateral.
57
58 The indices returned in order describe the convex hull.
59 */
convexHull(char order[4]) const60 int SkDCubic::convexHull(char order[4]) const {
61 size_t index;
62 // find top point
63 size_t yMin = 0;
64 for (index = 1; index < 4; ++index) {
65 if (fPts[yMin].fY > fPts[index].fY || (fPts[yMin].fY == fPts[index].fY
66 && fPts[yMin].fX > fPts[index].fX)) {
67 yMin = index;
68 }
69 }
70 order[0] = yMin;
71 int midX = -1;
72 int backupYMin = -1;
73 for (int pass = 0; pass < 2; ++pass) {
74 for (index = 0; index < 4; ++index) {
75 if (index == yMin) {
76 continue;
77 }
78 // rotate line from (yMin, index) to axis
79 // see if remaining two points are both above or below
80 // use this to find mid
81 int mask = other_two(yMin, index);
82 int side1 = yMin ^ mask;
83 int side2 = index ^ mask;
84 SkDCubic rotPath;
85 if (!rotate(*this, yMin, index, rotPath)) { // ! if cbc[yMin]==cbc[idx]
86 order[1] = side1;
87 order[2] = side2;
88 return 3;
89 }
90 int sides = side(rotPath[side1].fY - rotPath[yMin].fY);
91 sides ^= side(rotPath[side2].fY - rotPath[yMin].fY);
92 if (sides == 2) { // '2' means one remaining point <0, one >0
93 if (midX >= 0) {
94 // one of the control points is equal to an end point
95 order[0] = 0;
96 order[1] = 3;
97 if (fPts[1] == fPts[0] || fPts[1] == fPts[3]) {
98 order[2] = 2;
99 return 3;
100 }
101 if (fPts[2] == fPts[0] || fPts[2] == fPts[3]) {
102 order[2] = 1;
103 return 3;
104 }
105 // one of the control points may be very nearly but not exactly equal --
106 double dist1_0 = fPts[1].distanceSquared(fPts[0]);
107 double dist1_3 = fPts[1].distanceSquared(fPts[3]);
108 double dist2_0 = fPts[2].distanceSquared(fPts[0]);
109 double dist2_3 = fPts[2].distanceSquared(fPts[3]);
110 double smallest1distSq = std::min(dist1_0, dist1_3);
111 double smallest2distSq = std::min(dist2_0, dist2_3);
112 if (approximately_zero(std::min(smallest1distSq, smallest2distSq))) {
113 order[2] = smallest1distSq < smallest2distSq ? 2 : 1;
114 return 3;
115 }
116 }
117 midX = index;
118 } else if (sides == 0) { // '0' means both to one side or the other
119 backupYMin = index;
120 }
121 }
122 if (midX >= 0) {
123 break;
124 }
125 if (backupYMin < 0) {
126 break;
127 }
128 yMin = backupYMin;
129 backupYMin = -1;
130 }
131 if (midX < 0) {
132 midX = yMin ^ 3; // choose any other point
133 }
134 int mask = other_two(yMin, midX);
135 int least = yMin ^ mask;
136 int most = midX ^ mask;
137 order[0] = yMin;
138 order[1] = least;
139
140 // see if mid value is on same side of line (least, most) as yMin
141 SkDCubic midPath;
142 if (!rotate(*this, least, most, midPath)) { // ! if cbc[least]==cbc[most]
143 order[2] = midX;
144 return 3;
145 }
146 int midSides = side(midPath[yMin].fY - midPath[least].fY);
147 midSides ^= side(midPath[midX].fY - midPath[least].fY);
148 if (midSides != 2) { // if mid point is not between
149 order[2] = most;
150 return 3; // result is a triangle
151 }
152 order[2] = midX;
153 order[3] = most;
154 return 4; // result is a quadralateral
155 }
156