1fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot/* 2fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * Copyright 2012 Google Inc. 3fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * 4fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * Use of this source code is governed by a BSD-style license that can be 5fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * found in the LICENSE file. 6fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot */ 7fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#include "SkPathOpsLine.h" 8fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 9fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team RobotSkDPoint SkDLine::ptAtT(double t) const { 10fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (0 == t) { 11fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fPts[0]; 12fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 13fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (1 == t) { 14fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fPts[1]; 15fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 16fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double one_t = 1 - t; 17fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY }; 18fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return result; 19fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 20fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 21fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotdouble SkDLine::exactPoint(const SkDPoint& xy) const { 22fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (xy == fPts[0]) { // do cheapest test first 23fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return 0; 24fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 25fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (xy == fPts[1]) { 26fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return 1; 27fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 28fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -1; 29fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 30fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 31fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotdouble SkDLine::nearPoint(const SkDPoint& xy, bool* unequal) const { 32fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX) 33fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) { 34fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -1; 35fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 36fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // project a perpendicular ray from the point to the line; find the T on the line 37fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line 38fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay 39fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDVector ab0 = xy - fPts[0]; 40fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double numer = len.fX * ab0.fX + ab0.fY * len.fY; 41fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!between(0, numer, denom)) { 42fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -1; 43fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 44fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!denom) { 45fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return 0; 46fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 47fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double t = numer / denom; 48fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint realPt = ptAtT(t); 49fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ? 50fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // find the ordinal in the original line with the largest unsigned exponent 51fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 52fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 53fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot largest = SkTMax(largest, -tiniest); 54fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!AlmostEqualUlps_Pin(largest, largest + dist)) { // is the dist within ULPS tolerance? 55fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -1; 56fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 57fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (unequal) { 58fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot *unequal = (float) largest != (float) (largest + dist); 59fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 60fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot t = SkPinT(t); // a looser pin breaks skpwww_lptemp_com_3 61fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkASSERT(between(0, t, 1)); 62fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return t; 63fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 64fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 65fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotbool SkDLine::nearRay(const SkDPoint& xy) const { 66fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // project a perpendicular ray from the point to the line; find the T on the line 67fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line 68fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay 69fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDVector ab0 = xy - fPts[0]; 70fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double numer = len.fX * ab0.fX + ab0.fY * len.fY; 71fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double t = numer / denom; 72fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDPoint realPt = ptAtT(t); 73fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ? 74fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // find the ordinal in the original line with the largest unsigned exponent 75fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 76fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 77fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot largest = SkTMax(largest, -tiniest); 78fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance? 79fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 80fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 81fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotdouble SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) { 82fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (xy.fY == y) { 83fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (xy.fX == left) { 84fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return 0; 85fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 86fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (xy.fX == right) { 87fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return 1; 88fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 89fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 90fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -1; 91fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 92fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 93fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotdouble SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) { 94fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!AlmostBequalUlps(xy.fY, y)) { 95fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -1; 96fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 97fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!AlmostBetweenUlps(left, xy.fX, right)) { 98fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -1; 99fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 100fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double t = (xy.fX - left) / (right - left); 101fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot t = SkPinT(t); 102fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkASSERT(between(0, t, 1)); 103fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double realPtX = (1 - t) * left + t * right; 104fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDVector distU = {xy.fY - y, xy.fX - realPtX}; 105fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double distSq = distU.fX * distU.fX + distU.fY * distU.fY; 106fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? 107fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double tiniest = SkTMin(SkTMin(y, left), right); 108fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double largest = SkTMax(SkTMax(y, left), right); 109fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot largest = SkTMax(largest, -tiniest); 110fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? 111fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -1; 112fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 113fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return t; 114fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 115fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 116fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotdouble SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) { 117fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (xy.fX == x) { 118fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (xy.fY == top) { 119fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return 0; 120fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 121fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (xy.fY == bottom) { 122fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return 1; 123fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 124fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 125fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -1; 126fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 127fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 128fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotdouble SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) { 129fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!AlmostBequalUlps(xy.fX, x)) { 130fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -1; 131fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 132fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!AlmostBetweenUlps(top, xy.fY, bottom)) { 133fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -1; 134fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 135fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double t = (xy.fY - top) / (bottom - top); 136fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot t = SkPinT(t); 137fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkASSERT(between(0, t, 1)); 138fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double realPtY = (1 - t) * top + t * bottom; 139fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkDVector distU = {xy.fX - x, xy.fY - realPtY}; 140fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double distSq = distU.fX * distU.fX + distU.fY * distU.fY; 141fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? 142fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double tiniest = SkTMin(SkTMin(x, top), bottom); 143fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double largest = SkTMax(SkTMax(x, top), bottom); 144fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot largest = SkTMax(largest, -tiniest); 145fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? 146fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -1; 147fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 148fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return t; 149fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot} 150