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