1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkPathOpsLine.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,201 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +#include "SkPathOpsLine.h"
1.11 +
1.12 +SkDLine SkDLine::subDivide(double t1, double t2) const {
1.13 + SkDVector delta = tangent();
1.14 + SkDLine dst = {{{
1.15 + fPts[0].fX - t1 * delta.fX, fPts[0].fY - t1 * delta.fY}, {
1.16 + fPts[0].fX - t2 * delta.fX, fPts[0].fY - t2 * delta.fY}}};
1.17 + return dst;
1.18 +}
1.19 +
1.20 +// may have this below somewhere else already:
1.21 +// copying here because I thought it was clever
1.22 +
1.23 +// Copyright 2001, softSurfer (www.softsurfer.com)
1.24 +// This code may be freely used and modified for any purpose
1.25 +// providing that this copyright notice is included with it.
1.26 +// SoftSurfer makes no warranty for this code, and cannot be held
1.27 +// liable for any real or imagined damage resulting from its use.
1.28 +// Users of this code must verify correctness for their application.
1.29 +
1.30 +// Assume that a class is already given for the object:
1.31 +// Point with coordinates {float x, y;}
1.32 +//===================================================================
1.33 +
1.34 +// isLeft(): tests if a point is Left|On|Right of an infinite line.
1.35 +// Input: three points P0, P1, and P2
1.36 +// Return: >0 for P2 left of the line through P0 and P1
1.37 +// =0 for P2 on the line
1.38 +// <0 for P2 right of the line
1.39 +// See: the January 2001 Algorithm on Area of Triangles
1.40 +// return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y));
1.41 +double SkDLine::isLeft(const SkDPoint& pt) const {
1.42 + SkDVector p0 = fPts[1] - fPts[0];
1.43 + SkDVector p2 = pt - fPts[0];
1.44 + return p0.cross(p2);
1.45 +}
1.46 +
1.47 +SkDPoint SkDLine::ptAtT(double t) const {
1.48 + if (0 == t) {
1.49 + return fPts[0];
1.50 + }
1.51 + if (1 == t) {
1.52 + return fPts[1];
1.53 + }
1.54 + double one_t = 1 - t;
1.55 + SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY };
1.56 + return result;
1.57 +}
1.58 +
1.59 +double SkDLine::exactPoint(const SkDPoint& xy) const {
1.60 + if (xy == fPts[0]) { // do cheapest test first
1.61 + return 0;
1.62 + }
1.63 + if (xy == fPts[1]) {
1.64 + return 1;
1.65 + }
1.66 + return -1;
1.67 +}
1.68 +
1.69 +double SkDLine::nearPoint(const SkDPoint& xy) const {
1.70 + if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX)
1.71 + || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) {
1.72 + return -1;
1.73 + }
1.74 + // project a perpendicular ray from the point to the line; find the T on the line
1.75 + SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
1.76 + double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay
1.77 + SkDVector ab0 = xy - fPts[0];
1.78 + double numer = len.fX * ab0.fX + ab0.fY * len.fY;
1.79 + if (!between(0, numer, denom)) {
1.80 + return -1;
1.81 + }
1.82 + double t = numer / denom;
1.83 + SkDPoint realPt = ptAtT(t);
1.84 + double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ?
1.85 + // find the ordinal in the original line with the largest unsigned exponent
1.86 + double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
1.87 + double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
1.88 + largest = SkTMax(largest, -tiniest);
1.89 + if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
1.90 + return -1;
1.91 + }
1.92 + t = SkPinT(t);
1.93 + SkASSERT(between(0, t, 1));
1.94 + return t;
1.95 +}
1.96 +
1.97 +bool SkDLine::nearRay(const SkDPoint& xy) const {
1.98 + // project a perpendicular ray from the point to the line; find the T on the line
1.99 + SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
1.100 + double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay
1.101 + SkDVector ab0 = xy - fPts[0];
1.102 + double numer = len.fX * ab0.fX + ab0.fY * len.fY;
1.103 + double t = numer / denom;
1.104 + SkDPoint realPt = ptAtT(t);
1.105 + double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ?
1.106 + // find the ordinal in the original line with the largest unsigned exponent
1.107 + double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
1.108 + double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
1.109 + largest = SkTMax(largest, -tiniest);
1.110 + return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance?
1.111 +}
1.112 +
1.113 +// Returns true if a ray from (0,0) to (x1,y1) is coincident with a ray (0,0) to (x2,y2)
1.114 +// OPTIMIZE: a specialty routine could speed this up -- may not be called very often though
1.115 +bool SkDLine::NearRay(double x1, double y1, double x2, double y2) {
1.116 + double denom1 = x1 * x1 + y1 * y1;
1.117 + double denom2 = x2 * x2 + y2 * y2;
1.118 + SkDLine line = {{{0, 0}, {x1, y1}}};
1.119 + SkDPoint pt = {x2, y2};
1.120 + if (denom2 > denom1) {
1.121 + SkTSwap(line[1], pt);
1.122 + }
1.123 + return line.nearRay(pt);
1.124 +}
1.125 +
1.126 +double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) {
1.127 + if (xy.fY == y) {
1.128 + if (xy.fX == left) {
1.129 + return 0;
1.130 + }
1.131 + if (xy.fX == right) {
1.132 + return 1;
1.133 + }
1.134 + }
1.135 + return -1;
1.136 +}
1.137 +
1.138 +double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) {
1.139 + if (!AlmostBequalUlps(xy.fY, y)) {
1.140 + return -1;
1.141 + }
1.142 + if (!AlmostBetweenUlps(left, xy.fX, right)) {
1.143 + return -1;
1.144 + }
1.145 + double t = (xy.fX - left) / (right - left);
1.146 + t = SkPinT(t);
1.147 + SkASSERT(between(0, t, 1));
1.148 + double realPtX = (1 - t) * left + t * right;
1.149 + SkDVector distU = {xy.fY - y, xy.fX - realPtX};
1.150 + double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
1.151 + double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
1.152 + double tiniest = SkTMin(SkTMin(y, left), right);
1.153 + double largest = SkTMax(SkTMax(y, left), right);
1.154 + largest = SkTMax(largest, -tiniest);
1.155 + if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
1.156 + return -1;
1.157 + }
1.158 + return t;
1.159 +}
1.160 +
1.161 +double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) {
1.162 + if (xy.fX == x) {
1.163 + if (xy.fY == top) {
1.164 + return 0;
1.165 + }
1.166 + if (xy.fY == bottom) {
1.167 + return 1;
1.168 + }
1.169 + }
1.170 + return -1;
1.171 +}
1.172 +
1.173 +double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) {
1.174 + if (!AlmostBequalUlps(xy.fX, x)) {
1.175 + return -1;
1.176 + }
1.177 + if (!AlmostBetweenUlps(top, xy.fY, bottom)) {
1.178 + return -1;
1.179 + }
1.180 + double t = (xy.fY - top) / (bottom - top);
1.181 + t = SkPinT(t);
1.182 + SkASSERT(between(0, t, 1));
1.183 + double realPtY = (1 - t) * top + t * bottom;
1.184 + SkDVector distU = {xy.fX - x, xy.fY - realPtY};
1.185 + double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
1.186 + double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
1.187 + double tiniest = SkTMin(SkTMin(x, top), bottom);
1.188 + double largest = SkTMax(SkTMax(x, top), bottom);
1.189 + largest = SkTMax(largest, -tiniest);
1.190 + if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
1.191 + return -1;
1.192 + }
1.193 + return t;
1.194 +}
1.195 +
1.196 +#ifdef SK_DEBUG
1.197 +void SkDLine::dump() {
1.198 + SkDebugf("{{");
1.199 + fPts[0].dump();
1.200 + SkDebugf(", ");
1.201 + fPts[1].dump();
1.202 + SkDebugf("}}\n");
1.203 +}
1.204 +#endif
