SkIntersections.cpp revision 94c902e63d77641cadd76155c2b248d04f63b560
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 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkIntersections.h" 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1054359294a7c9dc54802d512a5d891a35c1663392caryclarkint SkIntersections::closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt, 1154359294a7c9dc54802d512a5d891a35c1663392caryclark double* closestDist) const { 1254359294a7c9dc54802d512a5d891a35c1663392caryclark int closest = -1; 1354359294a7c9dc54802d512a5d891a35c1663392caryclark *closestDist = SK_ScalarMax; 1454359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < fUsed; ++index) { 1554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!between(rangeStart, fT[0][index], rangeEnd)) { 1654359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 1754359294a7c9dc54802d512a5d891a35c1663392caryclark } 1854359294a7c9dc54802d512a5d891a35c1663392caryclark const SkDPoint& iPt = fPt[index]; 1954359294a7c9dc54802d512a5d891a35c1663392caryclark double dist = testPt.distanceSquared(iPt); 2054359294a7c9dc54802d512a5d891a35c1663392caryclark if (*closestDist > dist) { 2154359294a7c9dc54802d512a5d891a35c1663392caryclark *closestDist = dist; 2254359294a7c9dc54802d512a5d891a35c1663392caryclark closest = index; 2354359294a7c9dc54802d512a5d891a35c1663392caryclark } 24a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 2554359294a7c9dc54802d512a5d891a35c1663392caryclark return closest; 26a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com} 27a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comvoid SkIntersections::flip() { 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int index = 0; index < fUsed; ++index) { 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fT[1][index] = 1 - fT[1][index]; 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 3307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 34fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.comint SkIntersections::insert(double one, double two, const SkDPoint& pt) { 35b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) { 36b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com // For now, don't allow a mix of coincident and non-coincident intersections 37b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com return -1; 38b3f0921fba9457ba7ea79f220d8c1ec9345bfd3acaryclark@google.com } 3907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]); 4007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int index; 4107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (index = 0; index < fUsed; ++index) { 4207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double oldOne = fT[0][index]; 4307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double oldTwo = fT[1][index]; 44fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (one == oldOne && two == oldTwo) { 45fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com return -1; 46fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 47fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) { 4807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if ((precisely_zero(one) && !precisely_zero(oldOne)) 4907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1)) 5007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com || (precisely_zero(two) && !precisely_zero(oldTwo)) 5107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) { 5265f553182ab7069378ef863d30094d0327f178d0caryclark SkASSERT(one >= 0 && one <= 1); 5365f553182ab7069378ef863d30094d0327f178d0caryclark SkASSERT(two >= 0 && two <= 1); 5407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fT[0][index] = one; 5507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fT[1][index] = two; 56fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fPt[index] = pt; 5707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return -1; 5907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #if ONE_OFF_DEBUG 6107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (pt.roughlyEqual(fPt[index])) { 6207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one); 6307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com #endif 6507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (fT[0][index] > one) { 6607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com break; 6707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 6807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 697eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com if (fUsed >= fMax) { 707eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com SkASSERT(0); // FIXME : this error, if it is to be handled at runtime in release, must 717eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com // be propagated all the way back down to the caller, and return failure. 727eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com fUsed = 0; 737eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com return 0; 747eaa53d8f7e48fd17d02b5e3bd91f90e9c1899efcaryclark@google.com } 7507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int remaining = fUsed - index; 7607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (remaining > 0) { 7707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining); 7807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); 7907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); 80570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com int clearMask = ~((1 << index) - 1); 81570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com fIsCoincident[0] += fIsCoincident[0] & clearMask; 82570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com fIsCoincident[1] += fIsCoincident[1] & clearMask; 8307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 84fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fPt[index] = pt; 8565f553182ab7069378ef863d30094d0327f178d0caryclark SkASSERT(one >= 0 && one <= 1); 8665f553182ab7069378ef863d30094d0327f178d0caryclark SkASSERT(two >= 0 && two <= 1); 8707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fT[0][index] = one; 8807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fT[1][index] = two; 8907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com ++fUsed; 9094c902e63d77641cadd76155c2b248d04f63b560caryclark SkASSERT(fUsed <= SK_ARRAY_COUNT(fPt)); 9107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return index; 9207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 9307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 94dac1d17027dcaa5596885a9f333979418b35001ccaryclarkvoid SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) { 95dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(one == 0 || one == 1); 96dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(two == 0 || two == 1); 97dac1d17027dcaa5596885a9f333979418b35001ccaryclark SkASSERT(pt1 != pt2); 9854359294a7c9dc54802d512a5d891a35c1663392caryclark fNearlySame[one ? 1 : 0] = true; 99dac1d17027dcaa5596885a9f333979418b35001ccaryclark (void) insert(one, two, pt1); 10054359294a7c9dc54802d512a5d891a35c1663392caryclark fPt2[one ? 1 : 0] = pt2; 101dac1d17027dcaa5596885a9f333979418b35001ccaryclark} 102dac1d17027dcaa5596885a9f333979418b35001ccaryclark 10354359294a7c9dc54802d512a5d891a35c1663392caryclarkint SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) { 10407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int index = insertSwap(one, two, pt); 10554359294a7c9dc54802d512a5d891a35c1663392caryclark if (index >= 0) { 10654359294a7c9dc54802d512a5d891a35c1663392caryclark setCoincident(index); 10754359294a7c9dc54802d512a5d891a35c1663392caryclark } 10854359294a7c9dc54802d512a5d891a35c1663392caryclark return index; 10954359294a7c9dc54802d512a5d891a35c1663392caryclark} 11054359294a7c9dc54802d512a5d891a35c1663392caryclark 11154359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkIntersections::setCoincident(int index) { 11254359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(index >= 0); 11307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int bit = 1 << index; 11407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fIsCoincident[0] |= bit; 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fIsCoincident[1] |= bit; 11607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 11707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 11854359294a7c9dc54802d512a5d891a35c1663392caryclarkvoid SkIntersections::merge(const SkIntersections& a, int aIndex, const SkIntersections& b, 11954359294a7c9dc54802d512a5d891a35c1663392caryclark int bIndex) { 12054359294a7c9dc54802d512a5d891a35c1663392caryclark this->reset(); 12154359294a7c9dc54802d512a5d891a35c1663392caryclark fT[0][0] = a.fT[0][aIndex]; 12254359294a7c9dc54802d512a5d891a35c1663392caryclark fT[1][0] = b.fT[0][bIndex]; 12354359294a7c9dc54802d512a5d891a35c1663392caryclark fPt[0] = a.fPt[aIndex]; 12454359294a7c9dc54802d512a5d891a35c1663392caryclark fPt2[0] = b.fPt[bIndex]; 12554359294a7c9dc54802d512a5d891a35c1663392caryclark fUsed = 1; 126a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com} 127a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com 12854359294a7c9dc54802d512a5d891a35c1663392caryclarkint SkIntersections::mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const { 12954359294a7c9dc54802d512a5d891a35c1663392caryclark int result = -1; 13054359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < fUsed; ++index) { 13154359294a7c9dc54802d512a5d891a35c1663392caryclark if (!between(rangeStart, fT[0][index], rangeEnd)) { 13254359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 13354359294a7c9dc54802d512a5d891a35c1663392caryclark } 13454359294a7c9dc54802d512a5d891a35c1663392caryclark if (result < 0) { 13554359294a7c9dc54802d512a5d891a35c1663392caryclark result = index; 13654359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 13754359294a7c9dc54802d512a5d891a35c1663392caryclark } 13854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector best = fPt[result] - origin; 13954359294a7c9dc54802d512a5d891a35c1663392caryclark SkDVector test = fPt[index] - origin; 14054359294a7c9dc54802d512a5d891a35c1663392caryclark if (test.crossCheck(best) < 0) { 14154359294a7c9dc54802d512a5d891a35c1663392caryclark result = index; 14254359294a7c9dc54802d512a5d891a35c1663392caryclark } 14307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 14454359294a7c9dc54802d512a5d891a35c1663392caryclark return result; 14507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 14607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 14707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comvoid SkIntersections::removeOne(int index) { 14807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int remaining = --fUsed - index; 14907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (remaining <= 0) { 15007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return; 15107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 15207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); 15307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); 15407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); 15565f553182ab7069378ef863d30094d0327f178d0caryclark// SkASSERT(fIsCoincident[0] == 0); 15607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int coBit = fIsCoincident[0] & (1 << index); 15707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit; 15807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); 15907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; 16007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 161