SkCullPoints.cpp revision 573a42d0250f297ad99369ed88375497c1cb1eca
18a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* libs/graphics/effects/SkCullPoints.cpp 28a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** 38a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** Copyright 2006, The Android Open Source Project 48a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** 58a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** Licensed under the Apache License, Version 2.0 (the "License"); 68a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** you may not use this file except in compliance with the License. 78a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** You may obtain a copy of the License at 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** http://www.apache.org/licenses/LICENSE-2.0 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** Unless required by applicable law or agreed to in writing, software 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** distributed under the License is distributed on an "AS IS" BASIS, 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** See the License for the specific language governing permissions and 158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com** limitations under the License. 168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkCullPoints.h" 198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "Sk64.h" 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 21573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comstatic bool cross_product_is_neg(const SkIPoint& v, int dx, int dy) { 228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#if 0 238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return v.fX * dy - v.fY * dx < 0; 248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Sk64 tmp0, tmp1; 268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp0.setMul(v.fX, dy); 288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp1.setMul(dx, v.fY); 298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp0.sub(tmp1); 308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return tmp0.isNeg(); 318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 34573a42d0250f297ad99369ed88375497c1cb1ecareed@android.combool SkCullPoints::sect_test(int x0, int y0, int x1, int y1) const { 358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkIRect& r = fR; 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 37573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com if ((x0 < r.fLeft && x1 < r.fLeft) || 38573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com (x0 > r.fRight && x1 > r.fRight) || 39573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com (y0 < r.fTop && y1 < r.fTop) || 40573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com (y0 > r.fBottom && y1 > r.fBottom)) { 418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 42573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com } 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // since the crossprod test is a little expensive, check for easy-in cases first 45573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com if (r.contains(x0, y0) || r.contains(x1, y1)) { 468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 47573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com } 488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // At this point we're not sure, so we do a crossprod test 508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkIPoint vec; 518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkIPoint* rAsQuad = fAsQuad; 528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com vec.set(x1 - x0, y1 - y0); 548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool isNeg = cross_product_is_neg(vec, x0 - rAsQuad[0].fX, y0 - rAsQuad[0].fY); 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 1; i < 4; i++) { 56573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com if (cross_product_is_neg(vec, x0 - rAsQuad[i].fX, y0 - rAsQuad[i].fY) != isNeg) { 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; // we didn't intersect 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 63573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comstatic void toQuad(const SkIRect& r, SkIPoint quad[4]) { 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(quad); 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com quad[0].set(r.fLeft, r.fTop); 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com quad[1].set(r.fRight, r.fTop); 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com quad[2].set(r.fRight, r.fBottom); 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com quad[3].set(r.fLeft, r.fBottom); 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 72573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comSkCullPoints::SkCullPoints() { 738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkIRect r; 748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r.setEmpty(); 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->reset(r); 768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 78573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comSkCullPoints::SkCullPoints(const SkIRect& r) { 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->reset(r); 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 82573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comvoid SkCullPoints::reset(const SkIRect& r) { 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fR = r; 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com toQuad(fR, fAsQuad); 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevPt.set(0, 0); 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevResult = kNo_Result; 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 89573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comvoid SkCullPoints::moveTo(int x, int y) { 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevPt.set(x, y); 918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevResult = kNo_Result; // so we trigger a movetolineto later 928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 94573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comSkCullPoints::LineToResult SkCullPoints::lineTo(int x, int y, SkIPoint line[]) { 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(line != NULL); 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com LineToResult result = kNo_Result; 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int x0 = fPrevPt.fX; 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int y0 = fPrevPt.fY; 1008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // need to upgrade sect_test to chop the result 1028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // and to correctly return kLineTo_Result when the result is connected 1038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // to the previous call-out 104573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com if (this->sect_test(x0, y0, x, y)) { 1058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com line[0].set(x0, y0); 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com line[1].set(x, y); 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 108573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com if (fPrevResult != kNo_Result && fPrevPt.equals(x0, y0)) { 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com result = kLineTo_Result; 110573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com } else { 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com result = kMoveToLineTo_Result; 112573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com } 1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevPt.set(x, y); 1168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevResult = result; 1178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return result; 1198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///////////////////////////////////////////////////////////////////////////////////////////////// 1228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkPath.h" 1248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkCullPointsPath::SkCullPointsPath() 126573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com : fCP(), fPath(NULL) { 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst) 130573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com : fCP(r), fPath(dst) { 1318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 133573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comvoid SkCullPointsPath::reset(const SkIRect& r, SkPath* dst) { 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCP.reset(r); 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPath = dst; 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 137573a42d0250f297ad99369ed88375497c1cb1ecareed@android.com 138573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comvoid SkCullPointsPath::moveTo(int x, int y) { 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCP.moveTo(x, y); 1408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 142573a42d0250f297ad99369ed88375497c1cb1ecareed@android.comvoid SkCullPointsPath::lineTo(int x, int y) { 1438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkIPoint pts[2]; 1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com switch (fCP.lineTo(x, y, pts)) { 1468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case SkCullPoints::kMoveToLineTo_Result: 1478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPath->moveTo(SkIntToScalar(pts[0].fX), SkIntToScalar(pts[0].fY)); 1488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // fall through to the lineto case 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com case SkCullPoints::kLineTo_Result: 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPath->lineTo(SkIntToScalar(pts[1].fX), SkIntToScalar(pts[1].fY)); 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 1528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com default: 1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 1548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 157