1 2 /* 3 * Copyright 2006 The Android Open Source Project 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 10 #include "SkCullPoints.h" 11 #include "Sk64.h" 12 13 static bool cross_product_is_neg(const SkIPoint& v, int dx, int dy) { 14 #if 0 15 return v.fX * dy - v.fY * dx < 0; 16 #else 17 Sk64 tmp0, tmp1; 18 19 tmp0.setMul(v.fX, dy); 20 tmp1.setMul(dx, v.fY); 21 tmp0.sub(tmp1); 22 return tmp0.isNeg() != 0; 23 #endif 24 } 25 26 bool SkCullPoints::sect_test(int x0, int y0, int x1, int y1) const { 27 const SkIRect& r = fR; 28 29 if ((x0 < r.fLeft && x1 < r.fLeft) || 30 (x0 > r.fRight && x1 > r.fRight) || 31 (y0 < r.fTop && y1 < r.fTop) || 32 (y0 > r.fBottom && y1 > r.fBottom)) { 33 return false; 34 } 35 36 // since the crossprod test is a little expensive, check for easy-in cases first 37 if (r.contains(x0, y0) || r.contains(x1, y1)) { 38 return true; 39 } 40 41 // At this point we're not sure, so we do a crossprod test 42 SkIPoint vec; 43 const SkIPoint* rAsQuad = fAsQuad; 44 45 vec.set(x1 - x0, y1 - y0); 46 bool isNeg = cross_product_is_neg(vec, x0 - rAsQuad[0].fX, y0 - rAsQuad[0].fY); 47 for (int i = 1; i < 4; i++) { 48 if (cross_product_is_neg(vec, x0 - rAsQuad[i].fX, y0 - rAsQuad[i].fY) != isNeg) { 49 return true; 50 } 51 } 52 return false; // we didn't intersect 53 } 54 55 static void toQuad(const SkIRect& r, SkIPoint quad[4]) { 56 SkASSERT(quad); 57 58 quad[0].set(r.fLeft, r.fTop); 59 quad[1].set(r.fRight, r.fTop); 60 quad[2].set(r.fRight, r.fBottom); 61 quad[3].set(r.fLeft, r.fBottom); 62 } 63 64 SkCullPoints::SkCullPoints() { 65 SkIRect r; 66 r.setEmpty(); 67 this->reset(r); 68 } 69 70 SkCullPoints::SkCullPoints(const SkIRect& r) { 71 this->reset(r); 72 } 73 74 void SkCullPoints::reset(const SkIRect& r) { 75 fR = r; 76 toQuad(fR, fAsQuad); 77 fPrevPt.set(0, 0); 78 fPrevResult = kNo_Result; 79 } 80 81 void SkCullPoints::moveTo(int x, int y) { 82 fPrevPt.set(x, y); 83 fPrevResult = kNo_Result; // so we trigger a movetolineto later 84 } 85 86 SkCullPoints::LineToResult SkCullPoints::lineTo(int x, int y, SkIPoint line[]) { 87 SkASSERT(line != NULL); 88 89 LineToResult result = kNo_Result; 90 int x0 = fPrevPt.fX; 91 int y0 = fPrevPt.fY; 92 93 // need to upgrade sect_test to chop the result 94 // and to correctly return kLineTo_Result when the result is connected 95 // to the previous call-out 96 if (this->sect_test(x0, y0, x, y)) { 97 line[0].set(x0, y0); 98 line[1].set(x, y); 99 100 if (fPrevResult != kNo_Result && fPrevPt.equals(x0, y0)) { 101 result = kLineTo_Result; 102 } else { 103 result = kMoveToLineTo_Result; 104 } 105 } 106 107 fPrevPt.set(x, y); 108 fPrevResult = result; 109 110 return result; 111 } 112 113 ///////////////////////////////////////////////////////////////////////////////////////////////// 114 115 #include "SkPath.h" 116 117 SkCullPointsPath::SkCullPointsPath() 118 : fCP(), fPath(NULL) { 119 } 120 121 SkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst) 122 : fCP(r), fPath(dst) { 123 } 124 125 void SkCullPointsPath::reset(const SkIRect& r, SkPath* dst) { 126 fCP.reset(r); 127 fPath = dst; 128 } 129 130 void SkCullPointsPath::moveTo(int x, int y) { 131 fCP.moveTo(x, y); 132 } 133 134 void SkCullPointsPath::lineTo(int x, int y) { 135 SkIPoint pts[2]; 136 137 switch (fCP.lineTo(x, y, pts)) { 138 case SkCullPoints::kMoveToLineTo_Result: 139 fPath->moveTo(SkIntToScalar(pts[0].fX), SkIntToScalar(pts[0].fY)); 140 // fall through to the lineto case 141 case SkCullPoints::kLineTo_Result: 142 fPath->lineTo(SkIntToScalar(pts[1].fX), SkIntToScalar(pts[1].fY)); 143 break; 144 default: 145 break; 146 } 147 } 148 149