caryclark | 45fa447 | 2015-01-16 07:04:10 -0800 | [diff] [blame] | 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 | static bool rotate(const SkDCubic& cubic, int zero, int index, SkDCubic& rotPath) { |
| 10 | double dy = cubic[index].fY - cubic[zero].fY; |
| 11 | double dx = cubic[index].fX - cubic[zero].fX; |
| 12 | if (approximately_zero(dy)) { |
| 13 | if (approximately_zero(dx)) { |
| 14 | return false; |
| 15 | } |
| 16 | rotPath = cubic; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 17 | if (dy) { |
| 18 | rotPath[index].fY = cubic[zero].fY; |
| 19 | int mask = other_two(index, zero); |
| 20 | int side1 = index ^ mask; |
| 21 | int side2 = zero ^ mask; |
| 22 | if (approximately_equal(cubic[side1].fY, cubic[zero].fY)) { |
| 23 | rotPath[side1].fY = cubic[zero].fY; |
| 24 | } |
| 25 | if (approximately_equal(cubic[side2].fY, cubic[zero].fY)) { |
| 26 | rotPath[side2].fY = cubic[zero].fY; |
| 27 | } |
| 28 | } |
caryclark | 45fa447 | 2015-01-16 07:04:10 -0800 | [diff] [blame] | 29 | return true; |
| 30 | } |
| 31 | for (int index = 0; index < 4; ++index) { |
| 32 | rotPath[index].fX = cubic[index].fX * dx + cubic[index].fY * dy; |
| 33 | rotPath[index].fY = cubic[index].fY * dx - cubic[index].fX * dy; |
| 34 | } |
| 35 | return true; |
| 36 | } |
| 37 | |
| 38 | |
| 39 | // Returns 0 if negative, 1 if zero, 2 if positive |
| 40 | static int side(double x) { |
| 41 | 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 | int SkDCubic::convexHull(char order[4]) const { |
| 56 | size_t index; |
| 57 | // find top point |
| 58 | size_t yMin = 0; |
| 59 | for (index = 1; index < 4; ++index) { |
| 60 | if (fPts[yMin].fY > fPts[index].fY || (fPts[yMin].fY == fPts[index].fY |
| 61 | && fPts[yMin].fX > fPts[index].fX)) { |
| 62 | yMin = index; |
| 63 | } |
| 64 | } |
| 65 | order[0] = yMin; |
| 66 | int midX = -1; |
| 67 | int backupYMin = -1; |
| 68 | for (int pass = 0; pass < 2; ++pass) { |
| 69 | for (index = 0; index < 4; ++index) { |
| 70 | if (index == yMin) { |
| 71 | 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 | int mask = other_two(yMin, index); |
| 77 | int side1 = yMin ^ mask; |
| 78 | int side2 = index ^ mask; |
| 79 | SkDCubic rotPath; |
| 80 | if (!rotate(*this, yMin, index, rotPath)) { // ! if cbc[yMin]==cbc[idx] |
| 81 | order[1] = side1; |
| 82 | order[2] = side2; |
| 83 | return 3; |
| 84 | } |
| 85 | int sides = side(rotPath[side1].fY - rotPath[yMin].fY); |
| 86 | sides ^= side(rotPath[side2].fY - rotPath[yMin].fY); |
| 87 | if (sides == 2) { // '2' means one remaining point <0, one >0 |
| 88 | if (midX >= 0) { |
| 89 | // one of the control points is equal to an end point |
| 90 | order[0] = 0; |
| 91 | order[1] = 3; |
| 92 | if (fPts[1] == fPts[0] || fPts[1] == fPts[3]) { |
| 93 | order[2] = 2; |
| 94 | return 3; |
| 95 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 96 | if (fPts[2] == fPts[0] || fPts[2] == fPts[3]) { |
| 97 | order[2] = 1; |
| 98 | return 3; |
| 99 | } |
| 100 | // one of the control points may be very nearly but not exactly equal -- |
| 101 | double dist1_0 = fPts[1].distanceSquared(fPts[0]); |
| 102 | double dist1_3 = fPts[1].distanceSquared(fPts[3]); |
| 103 | double dist2_0 = fPts[2].distanceSquared(fPts[0]); |
| 104 | double dist2_3 = fPts[2].distanceSquared(fPts[3]); |
| 105 | double smallest1distSq = SkTMin(dist1_0, dist1_3); |
| 106 | double smallest2distSq = SkTMin(dist2_0, dist2_3); |
caryclark | 08bc848 | 2015-04-24 09:08:57 -0700 | [diff] [blame] | 107 | if (approximately_zero(SkTMin(smallest1distSq, smallest2distSq))) { |
| 108 | order[2] = smallest1distSq < smallest2distSq ? 2 : 1; |
| 109 | return 3; |
| 110 | } |
caryclark | 45fa447 | 2015-01-16 07:04:10 -0800 | [diff] [blame] | 111 | } |
| 112 | midX = index; |
| 113 | } else if (sides == 0) { // '0' means both to one side or the other |
| 114 | backupYMin = index; |
| 115 | } |
| 116 | } |
| 117 | if (midX >= 0) { |
| 118 | break; |
| 119 | } |
| 120 | if (backupYMin < 0) { |
| 121 | break; |
| 122 | } |
| 123 | yMin = backupYMin; |
| 124 | backupYMin = -1; |
| 125 | } |
| 126 | if (midX < 0) { |
| 127 | midX = yMin ^ 3; // choose any other point |
| 128 | } |
| 129 | int mask = other_two(yMin, midX); |
| 130 | int least = yMin ^ mask; |
| 131 | int most = midX ^ mask; |
| 132 | order[0] = yMin; |
| 133 | order[1] = least; |
| 134 | |
| 135 | // see if mid value is on same side of line (least, most) as yMin |
| 136 | SkDCubic midPath; |
| 137 | if (!rotate(*this, least, most, midPath)) { // ! if cbc[least]==cbc[most] |
| 138 | order[2] = midX; |
| 139 | return 3; |
| 140 | } |
| 141 | int midSides = side(midPath[yMin].fY - midPath[least].fY); |
| 142 | midSides ^= side(midPath[midX].fY - midPath[least].fY); |
| 143 | if (midSides != 2) { // if mid point is not between |
| 144 | order[2] = most; |
| 145 | return 3; // result is a triangle |
| 146 | } |
| 147 | order[2] = midX; |
| 148 | order[3] = most; |
| 149 | return 4; // result is a quadralateral |
| 150 | } |