1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkCullPoints.h" 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 10573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comstatic bool cross_product_is_neg(const SkIPoint& v, int dx, int dy) { 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#if 0 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return v.fX * dy - v.fY * dx < 0; 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 14bf0001d0472d727266762c5967ec0d919a6df083reed@google.com return sk_64_mul(v.fX, dy) < sk_64_mul(dx, v.fY); 158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 18573a42d0250f297ad99369ed88375497c1cb1ecareed@android.combool SkCullPoints::sect_test(int x0, int y0, int x1, int y1) const { 198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkIRect& r = fR; 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 21573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com if ((x0 < r.fLeft && x1 < r.fLeft) || 22573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com (x0 > r.fRight && x1 > r.fRight) || 23573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com (y0 < r.fTop && y1 < r.fTop) || 24573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com (y0 > r.fBottom && y1 > r.fBottom)) { 258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 26573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com } 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 28d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com // since the crossprod test is a little expensive, check for easy-in cases first 29573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com if (r.contains(x0, y0) || r.contains(x1, y1)) { 308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 31573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com } 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // At this point we're not sure, so we do a crossprod test 348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkIPoint vec; 358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkIPoint* rAsQuad = fAsQuad; 36d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com vec.set(x1 - x0, y1 - y0); 388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool isNeg = cross_product_is_neg(vec, x0 - rAsQuad[0].fX, y0 - rAsQuad[0].fY); 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 1; i < 4; i++) { 40573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com if (cross_product_is_neg(vec, x0 - rAsQuad[i].fX, y0 - rAsQuad[i].fY) != isNeg) { 418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; // we didn't intersect 458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 47573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comstatic void toQuad(const SkIRect& r, SkIPoint quad[4]) { 488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(quad); 498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com quad[0].set(r.fLeft, r.fTop); 518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com quad[1].set(r.fRight, r.fTop); 528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com quad[2].set(r.fRight, r.fBottom); 538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com quad[3].set(r.fLeft, r.fBottom); 548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 56573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comSkCullPoints::SkCullPoints() { 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkIRect r; 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r.setEmpty(); 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->reset(r); 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 62573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comSkCullPoints::SkCullPoints(const SkIRect& r) { 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->reset(r); 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 66573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comvoid SkCullPoints::reset(const SkIRect& r) { 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fR = r; 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com toQuad(fR, fAsQuad); 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevPt.set(0, 0); 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevResult = kNo_Result; 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 73573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comvoid SkCullPoints::moveTo(int x, int y) { 748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevPt.set(x, y); 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevResult = kNo_Result; // so we trigger a movetolineto later 768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 78573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comSkCullPoints::LineToResult SkCullPoints::lineTo(int x, int y, SkIPoint line[]) { 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(line != NULL); 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com LineToResult result = kNo_Result; 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int x0 = fPrevPt.fX; 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int y0 = fPrevPt.fY; 84d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // need to upgrade sect_test to chop the result 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // and to correctly return kLineTo_Result when the result is connected 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // to the previous call-out 88573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com if (this->sect_test(x0, y0, x, y)) { 898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com line[0].set(x0, y0); 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com line[1].set(x, y); 91d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 92573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com if (fPrevResult != kNo_Result && fPrevPt.equals(x0, y0)) { 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com result = kLineTo_Result; 94573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com } else { 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com result = kMoveToLineTo_Result; 96573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com } 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevPt.set(x, y); 1008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevResult = result; 1018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return result; 1038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///////////////////////////////////////////////////////////////////////////////////////////////// 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkPath.h" 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkCullPointsPath::SkCullPointsPath() 110573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com : fCP(), fPath(NULL) { 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst) 114573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com : fCP(r), fPath(dst) { 1158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 117573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comvoid SkCullPointsPath::reset(const SkIRect& r, SkPath* dst) { 1188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCP.reset(r); 1198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPath = dst; 1208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 121573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com 122573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comvoid SkCullPointsPath::moveTo(int x, int y) { 1238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCP.moveTo(x, y); 1248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 126573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comvoid SkCullPointsPath::lineTo(int x, int y) { 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkIPoint pts[2]; 128d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 1298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com switch (fCP.lineTo(x, y, pts)) { 1308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case SkCullPoints::kMoveToLineTo_Result: 1318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPath->moveTo(SkIntToScalar(pts[0].fX), SkIntToScalar(pts[0].fY)); 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // fall through to the lineto case 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case SkCullPoints::kLineTo_Result: 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPath->lineTo(SkIntToScalar(pts[1].fX), SkIntToScalar(pts[1].fY)); 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com default: 1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 141a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org/////////////////////////////////////////////////////////////////////////////// 142a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org 143a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org#include "SkMatrix.h" 144a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org#include "SkRegion.h" 145a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org 146a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.orgbool SkHitTestPath(const SkPath& path, SkRect& target, bool hires) { 147a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org if (target.isEmpty()) { 148a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org return false; 149a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org } 150a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org 151a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org bool isInverse = path.isInverseFillType(); 152a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org if (path.isEmpty()) { 153a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org return isInverse; 154a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org } 155a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org 156a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org SkRect bounds = path.getBounds(); 157a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org 158a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org bool sects = SkRect::Intersects(target, bounds); 159a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org if (isInverse) { 160a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org if (!sects) { 161a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org return true; 162a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org } 163a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org } else { 164a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org if (!sects) { 165a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org return false; 166a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org } 167a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org if (target.contains(bounds)) { 168a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org return true; 169a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org } 170a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org } 171a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org 172a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org SkPath devPath; 173a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org const SkPath* pathPtr; 174a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org SkRect devTarget; 175a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org 176a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org if (hires) { 177a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org const SkScalar coordLimit = SkIntToScalar(16384); 178a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org const SkRect limit = { 0, 0, coordLimit, coordLimit }; 179d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 180a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org SkMatrix matrix; 181a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org matrix.setRectToRect(bounds, limit, SkMatrix::kFill_ScaleToFit); 182a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org 183a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org path.transform(matrix, &devPath); 184a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org matrix.mapRect(&devTarget, target); 185a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org 186a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org pathPtr = &devPath; 187a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org } else { 188a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org devTarget = target; 189a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org pathPtr = &path; 190a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org } 191a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org 192a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org SkIRect iTarget; 193a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org devTarget.round(&iTarget); 194a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org if (iTarget.isEmpty()) { 195a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org iTarget.fLeft = SkScalarFloorToInt(devTarget.fLeft); 196a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org iTarget.fTop = SkScalarFloorToInt(devTarget.fTop); 197a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org iTarget.fRight = iTarget.fLeft + 1; 198a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org iTarget.fBottom = iTarget.fTop + 1; 199a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org } 200a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org 201a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org SkRegion clip(iTarget); 202a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org SkRegion rgn; 203a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org return rgn.setPath(*pathPtr, clip) ^ isInverse; 204a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org} 205a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org 206a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.orgbool SkHitTestPath(const SkPath& path, SkScalar x, SkScalar y, bool hires) { 207a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org const SkScalar half = SK_ScalarHalf; 208a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org const SkScalar one = SK_Scalar1; 209a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org SkRect r = SkRect::MakeXYWH(x - half, y - half, one, one); 210a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org return SkHitTestPath(path, r, hires); 211a2a95f9def9e3e1fcb34182ccaceec0e684c3e83mike@reedtribe.org} 212