107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkIntersections.h" 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsLine.h" 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* Determine the intersection point of two lines. This assumes the lines are not parallel, 1107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com and that that the lines are infinite. 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com From http://en.wikipedia.org/wiki/Line-line_intersection 1307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 1407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSkDPoint SkIntersections::Line(const SkDLine& a, const SkDLine& b) { 1507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double axLen = a[1].fX - a[0].fX; 1607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double ayLen = a[1].fY - a[0].fY; 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double bxLen = b[1].fX - b[0].fX; 1807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double byLen = b[1].fY - b[0].fY; 1907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double denom = byLen * axLen - ayLen * bxLen; 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(denom); 2107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double term1 = a[1].fX * a[0].fY - a[1].fY * a[0].fX; 2207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double term2 = b[1].fX * b[0].fY - b[1].fY * b[0].fX; 2307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDPoint p; 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com p.fX = (term1 * bxLen - axLen * term2) / denom; 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com p.fY = (term1 * byLen - ayLen * term2) / denom; 2607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return p; 2707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 297eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.comvoid SkIntersections::cleanUpCoincidence() { 307eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkASSERT(fUsed == 2); 317eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com // both t values are good 327eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com bool startMatch = fT[0][0] == 0 && (fT[1][0] == 0 || fT[1][0] == 1); 337eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com bool endMatch = fT[0][1] == 1 && (fT[1][1] == 0 || fT[1][1] == 1); 347eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (startMatch || endMatch) { 357eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com removeOne(startMatch); 367eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return; 377eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 387eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com // either t value is good 397eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com bool pStartMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1; 407eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com bool pEndMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1; 417eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com removeOne(pStartMatch || !pEndMatch); 427eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com} 437eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com 447eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.comvoid SkIntersections::cleanUpParallelLines(bool parallel) { 457eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com while (fUsed > 2) { 467eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com removeOne(1); 477eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 487eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (fUsed == 2 && !parallel) { 497eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com bool startMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1; 507eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com bool endMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1; 517eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if ((!startMatch && !endMatch) || approximately_equal(fT[0][0], fT[0][1])) { 527eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkASSERT(startMatch || endMatch); 537eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com removeOne(endMatch); 547eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 557eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 567eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com} 577eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com 587eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.comvoid SkIntersections::computePoints(const SkDLine& line, int used) { 594fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fPt[0] = line.ptAtT(fT[0][0]); 6007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if ((fUsed = used) == 2) { 614fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fPt[1] = line.ptAtT(fT[0][1]); 6207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 6407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 65cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.comint SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { 667eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 2; 67570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDVector aLen = a[1] - a[0]; 68570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDVector bLen = b[1] - b[0]; 69cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com /* Slopes match when denom goes to zero: 70cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com axLen / ayLen == bxLen / byLen 71cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen 72cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com byLen * axLen == ayLen * bxLen 73cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com byLen * axLen - ayLen * bxLen == 0 ( == denom ) 74cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com */ 75570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double denom = bLen.fY * aLen.fX - aLen.fY * bLen.fX; 76570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkDVector ab0 = a[0] - b[0]; 77570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double numerA = ab0.fY * bLen.fX - bLen.fY * ab0.fX; 78570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double numerB = ab0.fY * aLen.fX - aLen.fY * ab0.fX; 794431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#if 0 804431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!between(0, numerA, denom) || !between(0, numerB, denom)) { 814431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fUsed = 0; 824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return 0; 834431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org } 844431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org#endif 85cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com numerA /= denom; 86cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com numerB /= denom; 87cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com int used; 88cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com if (!approximately_zero(denom)) { 89cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com fT[0][0] = numerA; 90cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com fT[1][0] = numerB; 91cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com used = 1; 92cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } else { 93cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com /* See if the axis intercepts match: 94cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com ay - ax * ayLen / axLen == by - bx * ayLen / axLen 95cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen) 96cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com axLen * ay - ax * ayLen == axLen * by - bx * ayLen 97cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com */ 98570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (!AlmostEqualUlps(aLen.fX * a[0].fY - aLen.fY * a[0].fX, 99570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com aLen.fX * b[0].fY - aLen.fY * b[0].fX)) { 100cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com return fUsed = 0; 101cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 102cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com // there's no great answer for intersection points for coincident rays, but return something 103cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com fT[0][0] = fT[1][0] = 0; 104cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com fT[1][0] = fT[1][1] = 1; 105cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com used = 2; 106cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1077eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com computePoints(a, used); 1087eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return fUsed; 109cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com} 110cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com 11107e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com// note that this only works if both lines are neither horizontal nor vertical 11207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { 1137eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 3; // note that we clean up so that there is no more than two in the end 11407e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com // see if end points intersect the opposite line 11507e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com double t; 11607e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com for (int iA = 0; iA < 2; ++iA) { 117fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if ((t = b.exactPoint(a[iA])) >= 0) { 118fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com insert(iA, t, a[iA]); 11907e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 12007e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 12107e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com for (int iB = 0; iB < 2; ++iB) { 122fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if ((t = a.exactPoint(b[iB])) >= 0) { 123fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com insert(t, iB, b[iB]); 12407e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 12507e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 12607e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com /* Determine the intersection point of two line segments 12707e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com Return FALSE if the lines don't intersect 12807e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com from: http://paulbourke.net/geometry/lineline2d/ */ 12907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double axLen = a[1].fX - a[0].fX; 13007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double ayLen = a[1].fY - a[0].fY; 13107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double bxLen = b[1].fX - b[0].fX; 13207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double byLen = b[1].fY - b[0].fY; 13307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com /* Slopes match when denom goes to zero: 13407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com axLen / ayLen == bxLen / byLen 13507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen 13607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com byLen * axLen == ayLen * bxLen 13707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com byLen * axLen - ayLen * bxLen == 0 ( == denom ) 13807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 1394fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double axByLen = axLen * byLen; 1404fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double ayBxLen = ayLen * bxLen; 1414fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // detect parallel lines the same way here and in SkOpAngle operator < 1424fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com // so that non-parallel means they are also sortable 1437eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com bool unparallel = fAllowNear ? NotAlmostEqualUlps(axByLen, ayBxLen) 1447eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com : NotAlmostDequalUlps(axByLen, ayBxLen); 1457eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (unparallel && fUsed == 0) { 146fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double ab0y = a[0].fY - b[0].fY; 147fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double ab0x = a[0].fX - b[0].fX; 148fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double numerA = ab0y * bxLen - byLen * ab0x; 149fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double numerB = ab0y * axLen - ayLen * ab0x; 1504fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double denom = axByLen - ayBxLen; 151fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (between(0, numerA, denom) && between(0, numerB, denom)) { 152fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[0][0] = numerA / denom; 153fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[1][0] = numerB / denom; 1544fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com computePoints(a, 1); 15507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 15607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 157dac1d17027dcaa5596885a9f333979418b35001ccaryclark/* Allow tracking that both sets of end points are near each other -- the lines are entirely 158dac1d17027dcaa5596885a9f333979418b35001ccaryclark coincident -- even when the end points are not exactly the same. 159dac1d17027dcaa5596885a9f333979418b35001ccaryclark Mark this as a 'wild card' for the end points, so that either point is considered totally 160dac1d17027dcaa5596885a9f333979418b35001ccaryclark coincident. Then, avoid folding the lines over each other, but allow either end to mate 161dac1d17027dcaa5596885a9f333979418b35001ccaryclark to the next set of lines. 162dac1d17027dcaa5596885a9f333979418b35001ccaryclark */ 163570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (fAllowNear || !unparallel) { 164dac1d17027dcaa5596885a9f333979418b35001ccaryclark double aNearB[2]; 165dac1d17027dcaa5596885a9f333979418b35001ccaryclark double bNearA[2]; 166dac1d17027dcaa5596885a9f333979418b35001ccaryclark bool aNotB[2] = {false, false}; 167dac1d17027dcaa5596885a9f333979418b35001ccaryclark bool bNotA[2] = {false, false}; 168dac1d17027dcaa5596885a9f333979418b35001ccaryclark int nearCount = 0; 169dac1d17027dcaa5596885a9f333979418b35001ccaryclark for (int index = 0; index < 2; ++index) { 170dac1d17027dcaa5596885a9f333979418b35001ccaryclark aNearB[index] = t = b.nearPoint(a[index], &aNotB[index]); 171dac1d17027dcaa5596885a9f333979418b35001ccaryclark nearCount += t >= 0; 172dac1d17027dcaa5596885a9f333979418b35001ccaryclark bNearA[index] = t = a.nearPoint(b[index], &bNotA[index]); 173dac1d17027dcaa5596885a9f333979418b35001ccaryclark nearCount += t >= 0; 174fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 175dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (nearCount > 0) { 17619eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark // Skip if each segment contributes to one end point. 17719eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark if (nearCount != 2 || aNotB[0] == aNotB[1]) { 17819eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark for (int iA = 0; iA < 2; ++iA) { 17919eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark if (!aNotB[iA]) { 18019eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark continue; 18119eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark } 18219eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark int nearer = aNearB[iA] > 0.5; 18319eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark if (!bNotA[nearer]) { 18419eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark continue; 18519eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark } 18619eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark SkASSERT(a[iA] != b[nearer]); 18719eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark SkASSERT(iA == (bNearA[nearer] > 0.5)); 18819eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark fNearlySame[iA] = true; 18919eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark insertNear(iA, nearer, a[iA], b[nearer]); 19019eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark aNearB[iA] = -1; 19119eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark bNearA[nearer] = -1; 19219eb3b2f0aa6dce5c0335230a8930e90733e5d5dcaryclark nearCount -= 2; 193dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 194dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 195dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (nearCount > 0) { 196dac1d17027dcaa5596885a9f333979418b35001ccaryclark for (int iA = 0; iA < 2; ++iA) { 197dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (aNearB[iA] >= 0) { 198dac1d17027dcaa5596885a9f333979418b35001ccaryclark insert(iA, aNearB[iA], a[iA]); 199dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 200dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 201dac1d17027dcaa5596885a9f333979418b35001ccaryclark for (int iB = 0; iB < 2; ++iB) { 202dac1d17027dcaa5596885a9f333979418b35001ccaryclark if (bNearA[iB] >= 0) { 203dac1d17027dcaa5596885a9f333979418b35001ccaryclark insert(bNearA[iB], iB, b[iB]); 204dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 205dac1d17027dcaa5596885a9f333979418b35001ccaryclark } 206fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 207fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 208fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 2097eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com cleanUpParallelLines(!unparallel); 2107eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkASSERT(fUsed <= 2); 211fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return fUsed; 21207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 21307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 214fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comstatic int horizontal_coincident(const SkDLine& line, double y) { 21507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double min = line[0].fY; 21607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double max = line[1].fY; 21707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (min > max) { 21807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkTSwap(min, max); 21907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 22007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (min > y || max < y) { 221fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 0; 22207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 22307e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) { 224fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 2; 22507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 226fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 1; 22707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 22807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 229fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comstatic double horizontal_intercept(const SkDLine& line, double y) { 230a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY)); 231fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 232fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 233fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comint SkIntersections::horizontal(const SkDLine& line, double y) { 2347eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 2; 235fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com int horizontalType = horizontal_coincident(line, y); 236fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (horizontalType == 1) { 237fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[0][0] = horizontal_intercept(line, y); 238fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } else if (horizontalType == 2) { 239fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[0][0] = 0; 240fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[0][1] = 1; 24107e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 242fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return fUsed = horizontalType; 24307e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com} 24407e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com 24507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkIntersections::horizontal(const SkDLine& line, double left, double right, 24607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double y, bool flipped) { 2474431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fMax = 3; // clean up parallel at the end will limit the result to 2 at the most 24807e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com // see if end points intersect the opposite line 24907e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com double t; 250fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com const SkDPoint leftPt = { left, y }; 251fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if ((t = line.exactPoint(leftPt)) >= 0) { 252fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com insert(t, (double) flipped, leftPt); 25307e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 25407e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com if (left != right) { 255fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com const SkDPoint rightPt = { right, y }; 256fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if ((t = line.exactPoint(rightPt)) >= 0) { 257fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com insert(t, (double) !flipped, rightPt); 25807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 25907e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com for (int index = 0; index < 2; ++index) { 260fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if ((t = SkDLine::ExactPointH(line[index], left, right, y)) >= 0) { 261fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com insert((double) index, flipped ? 1 - t : t, line[index]); 26207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 26307e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 26407e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 265fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com int result = horizontal_coincident(line, y); 266fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (result == 1 && fUsed == 0) { 267fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[0][0] = horizontal_intercept(line, y); 268fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX); 269fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (between(left, xIntercept, right)) { 270fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[1][0] = (xIntercept - left) / (right - left); 271fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (flipped) { 272fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX 273fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com for (int index = 0; index < result; ++index) { 274fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[1][index] = 1 - fT[1][index]; 275fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 276fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 2771510726d6044119fab42a887d46ba922b890531dcaryclark@google.com fPt[0].fX = xIntercept; 2781510726d6044119fab42a887d46ba922b890531dcaryclark@google.com fPt[0].fY = y; 2791510726d6044119fab42a887d46ba922b890531dcaryclark@google.com fUsed = 1; 280fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 28107e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 2827eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (fAllowNear || result == 2) { 283dac1d17027dcaa5596885a9f333979418b35001ccaryclark if ((t = line.nearPoint(leftPt, NULL)) >= 0) { 2847eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com insert(t, (double) flipped, leftPt); 285fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 2867eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (left != right) { 2877eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com const SkDPoint rightPt = { right, y }; 288dac1d17027dcaa5596885a9f333979418b35001ccaryclark if ((t = line.nearPoint(rightPt, NULL)) >= 0) { 2897eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com insert(t, (double) !flipped, rightPt); 2907eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 2917eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com for (int index = 0; index < 2; ++index) { 2927eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) { 2937eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com insert((double) index, flipped ? 1 - t : t, line[index]); 2947eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 295fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 29607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 29707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 2987eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com cleanUpParallelLines(result == 2); 299fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return fUsed; 30007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 30107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 302fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comstatic int vertical_coincident(const SkDLine& line, double x) { 30307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double min = line[0].fX; 30407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double max = line[1].fX; 30507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (min > max) { 30607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkTSwap(min, max); 30707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3080361032c0b53401030a720bc8b4930c3ec59f19ecaryclark@google.com if (!precisely_between(min, x, max)) { 309fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 0; 31007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 31107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (AlmostEqualUlps(min, max)) { 312fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 2; 31307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 314fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return 1; 31507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 31607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 317fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comstatic double vertical_intercept(const SkDLine& line, double x) { 318a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX)); 319fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com} 320fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 321fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comint SkIntersections::vertical(const SkDLine& line, double x) { 3227eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fMax = 2; 323fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com int verticalType = vertical_coincident(line, x); 324fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (verticalType == 1) { 325fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[0][0] = vertical_intercept(line, x); 326fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } else if (verticalType == 2) { 327fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[0][0] = 0; 328fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[0][1] = 1; 32907e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 330fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return fUsed = verticalType; 33107e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com} 33207e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com 33307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkIntersections::vertical(const SkDLine& line, double top, double bottom, 334fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double x, bool flipped) { 3358cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org fMax = 3; // cleanup parallel lines will bring this back line 33607e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com // see if end points intersect the opposite line 33707e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com double t; 338fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkDPoint topPt = { x, top }; 339fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if ((t = line.exactPoint(topPt)) >= 0) { 340fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com insert(t, (double) flipped, topPt); 34107e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 34207e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com if (top != bottom) { 343fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com SkDPoint bottomPt = { x, bottom }; 344fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if ((t = line.exactPoint(bottomPt)) >= 0) { 345fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com insert(t, (double) !flipped, bottomPt); 34607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 34707e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com for (int index = 0; index < 2; ++index) { 348fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if ((t = SkDLine::ExactPointV(line[index], top, bottom, x)) >= 0) { 349fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com insert((double) index, flipped ? 1 - t : t, line[index]); 35007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 35107e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 35207e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 353fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com int result = vertical_coincident(line, x); 354fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (result == 1 && fUsed == 0) { 355fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[0][0] = vertical_intercept(line, x); 356fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY); 357fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (between(top, yIntercept, bottom)) { 358fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[1][0] = (yIntercept - top) / (bottom - top); 359fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (flipped) { 360fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY 361fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com for (int index = 0; index < result; ++index) { 362fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fT[1][index] = 1 - fT[1][index]; 363fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 364fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 3651510726d6044119fab42a887d46ba922b890531dcaryclark@google.com fPt[0].fX = x; 3661510726d6044119fab42a887d46ba922b890531dcaryclark@google.com fPt[0].fY = yIntercept; 3671510726d6044119fab42a887d46ba922b890531dcaryclark@google.com fUsed = 1; 368fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 36907e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 3707eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (fAllowNear || result == 2) { 371dac1d17027dcaa5596885a9f333979418b35001ccaryclark if ((t = line.nearPoint(topPt, NULL)) >= 0) { 3727eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com insert(t, (double) flipped, topPt); 373fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 3747eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (top != bottom) { 3757eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkDPoint bottomPt = { x, bottom }; 376dac1d17027dcaa5596885a9f333979418b35001ccaryclark if ((t = line.nearPoint(bottomPt, NULL)) >= 0) { 3777eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com insert(t, (double) !flipped, bottomPt); 3787eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 3797eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com for (int index = 0; index < 2; ++index) { 3807eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) { 3817eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com insert((double) index, flipped ? 1 - t : t, line[index]); 3827eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 383fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 38407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 38507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3867eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com cleanUpParallelLines(result == 2); 3878cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org SkASSERT(fUsed <= 2); 388fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return fUsed; 38907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 39007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 39107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py 39207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// 4 subs, 2 muls, 1 cmp 39307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comstatic bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { 39407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); 39507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 39607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 39707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// 16 subs, 8 muls, 6 cmps 39807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.combool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { 39907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) 40007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); 40107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 402