Home | History | Annotate | Download | only in pathops
      1 /*
      2  * Copyright 2015 Google Inc.
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 
      8 // given a prospective edge, compute its initial winding by projecting a ray
      9 // if the ray hits another edge
     10     // if the edge doesn't have a winding yet, hop up to that edge and start over
     11         // concern : check for hops forming a loop
     12     // if the edge is unsortable, or
     13     // the intersection is nearly at the ends, or
     14     // the tangent at the intersection is nearly coincident to the ray,
     15         // choose a different ray and try again
     16             // concern : if it is unable to succeed after N tries, try another edge? direction?
     17 // if no edge is hit, compute the winding directly
     18 
     19 // given the top span, project the most perpendicular ray and look for intersections
     20     // let's try up and then down. What the hey
     21 
     22 // bestXY is initialized by caller with basePt
     23 
     24 #include "SkOpContour.h"
     25 #include "SkOpSegment.h"
     26 #include "SkPathOpsCurve.h"
     27 
     28 enum class SkOpRayDir {
     29     kLeft,
     30     kTop,
     31     kRight,
     32     kBottom,
     33 };
     34 
     35 #if DEBUG_WINDING
     36 const char* gDebugRayDirName[] = {
     37     "kLeft",
     38     "kTop",
     39     "kRight",
     40     "kBottom"
     41 };
     42 #endif
     43 
     44 static int xy_index(SkOpRayDir dir) {
     45     return static_cast<int>(dir) & 1;
     46 }
     47 
     48 static SkScalar pt_xy(const SkPoint& pt, SkOpRayDir dir) {
     49     return (&pt.fX)[xy_index(dir)];
     50 }
     51 
     52 static SkScalar pt_yx(const SkPoint& pt, SkOpRayDir dir) {
     53     return (&pt.fX)[!xy_index(dir)];
     54 }
     55 
     56 static double pt_dxdy(const SkDVector& v, SkOpRayDir dir) {
     57     return (&v.fX)[xy_index(dir)];
     58 }
     59 
     60 static double pt_dydx(const SkDVector& v, SkOpRayDir dir) {
     61     return (&v.fX)[!xy_index(dir)];
     62 }
     63 
     64 static SkScalar rect_side(const SkRect& r, SkOpRayDir dir) {
     65     return (&r.fLeft)[static_cast<int>(dir)];
     66 }
     67 
     68 static bool sideways_overlap(const SkRect& rect, const SkPoint& pt, SkOpRayDir dir) {
     69     int i = !xy_index(dir);
     70     return approximately_between((&rect.fLeft)[i], (&pt.fX)[i], (&rect.fRight)[i]);
     71 }
     72 
     73 static bool less_than(SkOpRayDir dir) {
     74     return static_cast<bool>((static_cast<int>(dir) & 2) == 0);
     75 }
     76 
     77 static bool ccw_dxdy(const SkDVector& v, SkOpRayDir dir) {
     78     bool vPartPos = pt_dydx(v, dir) > 0;
     79     bool leftBottom = ((static_cast<int>(dir) + 1) & 2) != 0;
     80     return vPartPos == leftBottom;
     81 }
     82 
     83 struct SkOpRayHit {
     84     SkOpRayDir makeTestBase(SkOpSpan* span, double t) {
     85         fNext = nullptr;
     86         fSpan = span;
     87         fT = span->t() * (1 - t) + span->next()->t() * t;
     88         SkOpSegment* segment = span->segment();
     89         fSlope = segment->dSlopeAtT(fT);
     90         fPt = segment->ptAtT(fT);
     91         fValid = true;
     92         return fabs(fSlope.fX) < fabs(fSlope.fY) ? SkOpRayDir::kLeft : SkOpRayDir::kTop;
     93     }
     94 
     95     SkOpRayHit* fNext;
     96     SkOpSpan* fSpan;
     97     SkPoint fPt;
     98     double fT;
     99     SkDVector fSlope;
    100     bool fValid;
    101 };
    102 
    103 void SkOpContour::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits,
    104         SkChunkAlloc* allocator) {
    105     // if the bounds extreme is outside the best, we're done
    106     SkScalar baseXY = pt_xy(base.fPt, dir);
    107     SkScalar boundsXY = rect_side(fBounds, dir);
    108     bool checkLessThan = less_than(dir);
    109     if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) {
    110         return;
    111     }
    112     SkOpSegment* testSegment = &fHead;
    113     do {
    114         testSegment->rayCheck(base, dir, hits, allocator);
    115     } while ((testSegment = testSegment->next()));
    116 }
    117 
    118 void SkOpSegment::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits,
    119         SkChunkAlloc* allocator) {
    120     if (!sideways_overlap(fBounds, base.fPt, dir)) {
    121         return;
    122     }
    123     SkScalar baseXY = pt_xy(base.fPt, dir);
    124     SkScalar boundsXY = rect_side(fBounds, dir);
    125     bool checkLessThan = less_than(dir);
    126     if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) {
    127         return;
    128     }
    129     double tVals[3];
    130     SkScalar baseYX = pt_yx(base.fPt, dir);
    131     int roots = (*CurveIntercept[fVerb * 2 + xy_index(dir)])(fPts, fWeight, baseYX, tVals);
    132     for (int index = 0; index < roots; ++index) {
    133         double t = tVals[index];
    134         if (base.fSpan->segment() == this && approximately_equal(base.fT, t)) {
    135             continue;
    136         }
    137         SkDVector slope;
    138         SkPoint pt;
    139         SkDEBUGCODE(sk_bzero(&slope, sizeof(slope)));
    140         bool valid = false;
    141         if (approximately_zero(t)) {
    142             pt = fPts[0];
    143         } else if (approximately_equal(t, 1)) {
    144             pt = fPts[SkPathOpsVerbToPoints(fVerb)];
    145         } else {
    146             SkASSERT(between(0, t, 1));
    147             pt = this->ptAtT(t);
    148             if (SkDPoint::ApproximatelyEqual(pt, base.fPt)) {
    149                 if (base.fSpan->segment() == this) {
    150                     continue;
    151                 }
    152             } else {
    153                 SkScalar ptXY = pt_xy(pt, dir);
    154                 if (!approximately_equal(baseXY, ptXY) && (baseXY < ptXY) == checkLessThan) {
    155                     continue;
    156                 }
    157                 slope = this->dSlopeAtT(t);
    158                 if (fVerb == SkPath::kCubic_Verb && base.fSpan->segment() == this
    159                         && roughly_equal(base.fT, t)
    160                         && SkDPoint::RoughlyEqual(pt, base.fPt)) {
    161     #if DEBUG_WINDING
    162                     SkDebugf("%s (rarely expect this)\n", __FUNCTION__);
    163     #endif
    164                     continue;
    165                 }
    166                 if (fabs(pt_dydx(slope, dir) * 10000) > fabs(pt_dxdy(slope, dir))) {
    167                     valid = true;
    168                 }
    169             }
    170         }
    171         SkOpSpan* span = this->windingSpanAtT(t);
    172         if (!span) {
    173             valid = false;
    174         } else if (!span->windValue() && !span->oppValue()) {
    175             continue;
    176         }
    177         SkOpRayHit* newHit = SkOpTAllocator<SkOpRayHit>::Allocate(allocator);
    178         newHit->fNext = *hits;
    179         newHit->fPt = pt;
    180         newHit->fSlope = slope;
    181         newHit->fSpan = span;
    182         newHit->fT = t;
    183         newHit->fValid = valid;
    184         *hits = newHit;
    185     }
    186 }
    187 
    188 SkOpSpan* SkOpSegment::windingSpanAtT(double tHit) {
    189     SkOpSpan* span = &fHead;
    190     SkOpSpanBase* next;
    191     do {
    192         next = span->next();
    193         if (approximately_equal(tHit, next->t())) {
    194             return nullptr;
    195         }
    196         if (tHit < next->t()) {
    197             return span;
    198         }
    199     } while (!next->final() && (span = next->upCast()));
    200     return nullptr;
    201 }
    202 
    203 static bool hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) {
    204     return a->fPt.fX < b->fPt.fX;
    205 }
    206 
    207 static bool reverse_hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) {
    208     return b->fPt.fX  < a->fPt.fX;
    209 }
    210 
    211 static bool hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) {
    212     return a->fPt.fY < b->fPt.fY;
    213 }
    214 
    215 static bool reverse_hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) {
    216     return b->fPt.fY  < a->fPt.fY;
    217 }
    218 
    219 static double get_t_guess(int tTry, int* dirOffset) {
    220     double t = 0.5;
    221     *dirOffset = tTry & 1;
    222     int tBase = tTry >> 1;
    223     int tBits = 0;
    224     while (tTry >>= 1) {
    225         t /= 2;
    226         ++tBits;
    227     }
    228     if (tBits) {
    229         int tIndex = (tBase - 1) & ((1 << tBits) - 1);
    230         t += t * 2 * tIndex;
    231     }
    232     return t;
    233 }
    234 
    235 bool SkOpSpan::sortableTop(SkOpContour* contourHead) {
    236     SkChunkAlloc allocator(1024);
    237     int dirOffset;
    238     double t = get_t_guess(fTopTTry++, &dirOffset);
    239     SkOpRayHit hitBase;
    240     SkOpRayDir dir = hitBase.makeTestBase(this, t);
    241     if (hitBase.fSlope.fX == 0 && hitBase.fSlope.fY == 0) {
    242         return false;
    243     }
    244     SkOpRayHit* hitHead = &hitBase;
    245     dir = static_cast<SkOpRayDir>(static_cast<int>(dir) + dirOffset);
    246     SkOpContour* contour = contourHead;
    247     do {
    248         contour->rayCheck(hitBase, dir, &hitHead, &allocator);
    249     } while ((contour = contour->next()));
    250     // sort hits
    251     SkSTArray<1, SkOpRayHit*> sorted;
    252     SkOpRayHit* hit = hitHead;
    253     while (hit) {
    254         sorted.push_back(hit);
    255         hit = hit->fNext;
    256     }
    257     int count = sorted.count();
    258     SkTQSort(sorted.begin(), sorted.end() - 1, xy_index(dir)
    259             ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y
    260             : less_than(dir) ? hit_compare_x : reverse_hit_compare_x);
    261     // verify windings
    262 #if DEBUG_WINDING
    263     SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__,
    264             gDebugRayDirName[static_cast<int>(dir)], hitBase.fSpan->segment()->debugID(),
    265             hitBase.fT, hitBase.fPt.fX, hitBase.fPt.fY);
    266     for (int index = 0; index < count; ++index) {
    267         hit = sorted[index];
    268         SkOpSpan* span = hit->fSpan;
    269         SkOpSegment* hitSegment = span ? span->segment() : nullptr;
    270         bool operand = span ? hitSegment->operand() : false;
    271         bool ccw = ccw_dxdy(hit->fSlope, dir);
    272         SkDebugf("%s [%d] valid=%d operand=%d span=%d ccw=%d ", __FUNCTION__, index,
    273                 hit->fValid, operand, span ? span->debugID() : -1, ccw);
    274         if (span) {
    275             hitSegment->dumpPtsInner();
    276         }
    277         SkDebugf(" t=%1.9g pt=(%1.9g,%1.9g) slope=(%1.9g,%1.9g)\n", hit->fT,
    278                 hit->fPt.fX, hit->fPt.fY, hit->fSlope.fX, hit->fSlope.fY);
    279     }
    280 #endif
    281     const SkPoint* last = nullptr;
    282     int wind = 0;
    283     int oppWind = 0;
    284     for (int index = 0; index < count; ++index) {
    285         hit = sorted[index];
    286         if (!hit->fValid) {
    287             return false;
    288         }
    289         bool ccw = ccw_dxdy(hit->fSlope, dir);
    290 //        SkASSERT(!approximately_zero(hit->fT) || !hit->fValid);
    291         SkOpSpan* span = hit->fSpan;
    292         SkOpSegment* hitSegment = span->segment();
    293         if (!span) {
    294             return false;
    295         }
    296         if (span->windValue() == 0 && span->oppValue() == 0) {
    297             continue;
    298         }
    299         if (last && SkDPoint::ApproximatelyEqual(*last, hit->fPt)) {
    300             return false;
    301         }
    302         if (index < count - 1) {
    303             const SkPoint& next = sorted[index + 1]->fPt;
    304             if (SkDPoint::ApproximatelyEqual(next, hit->fPt)) {
    305                 return false;
    306             }
    307         }
    308         bool operand = hitSegment->operand();
    309         if (operand) {
    310             SkTSwap(wind, oppWind);
    311         }
    312         int lastWind = wind;
    313         int lastOpp = oppWind;
    314         int windValue = ccw ? -span->windValue() : span->windValue();
    315         int oppValue = ccw ? -span->oppValue() : span->oppValue();
    316         wind += windValue;
    317         oppWind += oppValue;
    318         bool sumSet = false;
    319         int spanSum = span->windSum();
    320         int windSum = SkOpSegment::UseInnerWinding(lastWind, wind) ? wind : lastWind;
    321         if (spanSum == SK_MinS32) {
    322             span->setWindSum(windSum);
    323             sumSet = true;
    324         } else {
    325             // the need for this condition suggests that UseInnerWinding is flawed
    326             // happened when last = 1 wind = -1
    327 #if 0
    328             SkASSERT((hitSegment->isXor() ? (windSum & 1) == (spanSum & 1) : windSum == spanSum)
    329                     || (abs(wind) == abs(lastWind)
    330                     && (windSum ^ wind ^ lastWind) == spanSum));
    331 #endif
    332         }
    333         int oSpanSum = span->oppSum();
    334         int oppSum = SkOpSegment::UseInnerWinding(lastOpp, oppWind) ? oppWind : lastOpp;
    335         if (oSpanSum == SK_MinS32) {
    336             span->setOppSum(oppSum);
    337         } else {
    338 #if 0
    339             SkASSERT(hitSegment->oppXor() ? (oppSum & 1) == (oSpanSum & 1) : oppSum == oSpanSum
    340                     || (abs(oppWind) == abs(lastOpp)
    341                     && (oppSum ^ oppWind ^ lastOpp) == oSpanSum));
    342 #endif
    343         }
    344         if (sumSet) {
    345             if (this->globalState()->phase() == SkOpGlobalState::kFixWinding) {
    346                 hitSegment->contour()->setCcw(ccw);
    347             } else {
    348                 (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, nullptr);
    349                 (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, nullptr);
    350             }
    351         }
    352         if (operand) {
    353             SkTSwap(wind, oppWind);
    354         }
    355         last = &hit->fPt;
    356         this->globalState()->bumpNested();
    357     }
    358     return true;
    359 }
    360 
    361 SkOpSpan* SkOpSegment::findSortableTop(SkOpContour* contourHead) {
    362     SkOpSpan* span = &fHead;
    363     SkOpSpanBase* next;
    364     do {
    365         next = span->next();
    366         if (span->done()) {
    367             continue;
    368         }
    369         if (span->windSum() != SK_MinS32) {
    370             return span;
    371         }
    372         if (span->sortableTop(contourHead)) {
    373             return span;
    374         }
    375     } while (!next->final() && (span = next->upCast()));
    376     return nullptr;
    377 }
    378 
    379 SkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) {
    380     SkOpSegment* testSegment = &fHead;
    381     do {
    382         if (testSegment->done()) {
    383             continue;
    384         }
    385         SkOpSpan* result = testSegment->findSortableTop(contourHead);
    386         if (result) {
    387             return result;
    388         }
    389     } while ((testSegment = testSegment->next()));
    390     return nullptr;
    391 }
    392 
    393 SkOpSpan* FindSortableTop(SkOpContourHead* contourHead) {
    394     for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) {
    395         SkOpContour* contour = contourHead;
    396         do {
    397             if (contour->done()) {
    398                 continue;
    399             }
    400             SkOpSpan* result = contour->findSortableTop(contourHead);
    401             if (result) {
    402                 return result;
    403             }
    404         } while ((contour = contour->next()));
    405     }
    406     return nullptr;
    407 }
    408