Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(52)

Side by Side Diff: src/pathops/SkOpSegment.cpp

Issue 1037953004: add conics to path ops (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: fix linux build Created 5 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
1 /* 1 /*
2 * Copyright 2012 Google Inc. 2 * Copyright 2012 Google Inc.
3 * 3 *
4 * Use of this source code is governed by a BSD-style license that can be 4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file. 5 * found in the LICENSE file.
6 */ 6 */
7 #include "SkOpCoincidence.h" 7 #include "SkOpCoincidence.h"
8 #include "SkOpContour.h" 8 #include "SkOpContour.h"
9 #include "SkOpSegment.h" 9 #include "SkOpSegment.h"
10 #include "SkPathWriter.h" 10 #include "SkPathWriter.h"
(...skipping 104 matching lines...) Expand 10 before | Expand all | Expand 10 after
115 } 115 }
116 { 116 {
117 const SkPoint& xy = span->pt(); 117 const SkPoint& xy = span->pt();
118 if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) { 118 if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
119 topPt = xy; 119 topPt = xy;
120 if (firstSpan) { 120 if (firstSpan) {
121 *firstSpan = span; 121 *firstSpan = span;
122 } 122 }
123 } 123 }
124 if (fVerb != SkPath::kLine_Verb && !lastDone) { 124 if (fVerb != SkPath::kLine_Verb && !lastDone) {
125 SkPoint curveTop = (*CurveTop[SkPathOpsVerbToPoints(fVerb)])(fPt s, lastT, 125 SkPoint curveTop = (*CurveTop[fVerb])(fPts, fWeight, lastT, span ->t());
126 span->t());
127 if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY 126 if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
128 && topPt.fX > curveTop.fX)) { 127 && topPt.fX > curveTop.fX)) {
129 topPt = curveTop; 128 topPt = curveTop;
130 if (firstSpan) { 129 if (firstSpan) {
131 *firstSpan = span; 130 *firstSpan = span;
132 } 131 }
133 } 132 }
134 } 133 }
135 lastT = span->t(); 134 lastT = span->t();
136 } 135 }
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after
195 int maxWinding; 194 int maxWinding;
196 setUpWinding(start, end, &maxWinding, sumWinding); 195 setUpWinding(start, end, &maxWinding, sumWinding);
197 bool from = maxWinding != 0; 196 bool from = maxWinding != 0;
198 bool to = *sumWinding != 0; 197 bool to = *sumWinding != 0;
199 bool result = gUnaryActiveEdge[from][to]; 198 bool result = gUnaryActiveEdge[from][to];
200 return result; 199 return result;
201 } 200 }
202 201
203 void SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, 202 void SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
204 SkPathWriter* path, bool active) const { 203 SkPathWriter* path, bool active) const {
205 SkPoint edge[4]; 204 SkOpCurve edge;
206 const SkPoint* ePtr; 205 const SkPoint* ePtr;
206 SkScalar eWeight;
207 if ((start == &fHead && end == &fTail) || (start == &fTail && end == &fHead) ) { 207 if ((start == &fHead && end == &fTail) || (start == &fTail && end == &fHead) ) {
208 ePtr = fPts; 208 ePtr = fPts;
209 eWeight = fWeight;
209 } else { 210 } else {
210 // OPTIMIZE? if not active, skip remainder and return xyAtT(end) 211 // OPTIMIZE? if not active, skip remainder and return xyAtT(end)
211 subDivide(start, end, edge); 212 subDivide(start, end, &edge);
212 ePtr = edge; 213 ePtr = edge.fPts;
214 eWeight = edge.fWeight;
213 } 215 }
214 if (active) { 216 if (active) {
215 bool reverse = ePtr == fPts && start != &fHead; 217 bool reverse = ePtr == fPts && start != &fHead;
216 if (reverse) { 218 if (reverse) {
217 path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]); 219 path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]);
218 switch (fVerb) { 220 switch (fVerb) {
219 case SkPath::kLine_Verb: 221 case SkPath::kLine_Verb:
220 path->deferredLine(ePtr[0]); 222 path->deferredLine(ePtr[0]);
221 break; 223 break;
222 case SkPath::kQuad_Verb: 224 case SkPath::kQuad_Verb:
223 path->quadTo(ePtr[1], ePtr[0]); 225 path->quadTo(ePtr[1], ePtr[0]);
224 break; 226 break;
227 case SkPath::kConic_Verb:
228 path->conicTo(ePtr[1], ePtr[0], eWeight);
229 break;
225 case SkPath::kCubic_Verb: 230 case SkPath::kCubic_Verb:
226 path->cubicTo(ePtr[2], ePtr[1], ePtr[0]); 231 path->cubicTo(ePtr[2], ePtr[1], ePtr[0]);
227 break; 232 break;
228 default: 233 default:
229 SkASSERT(0); 234 SkASSERT(0);
230 } 235 }
231 } else { 236 } else {
232 path->deferredMoveLine(ePtr[0]); 237 path->deferredMoveLine(ePtr[0]);
233 switch (fVerb) { 238 switch (fVerb) {
234 case SkPath::kLine_Verb: 239 case SkPath::kLine_Verb:
235 path->deferredLine(ePtr[1]); 240 path->deferredLine(ePtr[1]);
236 break; 241 break;
237 case SkPath::kQuad_Verb: 242 case SkPath::kQuad_Verb:
238 path->quadTo(ePtr[1], ePtr[2]); 243 path->quadTo(ePtr[1], ePtr[2]);
239 break; 244 break;
245 case SkPath::kConic_Verb:
246 path->conicTo(ePtr[1], ePtr[2], eWeight);
247 break;
240 case SkPath::kCubic_Verb: 248 case SkPath::kCubic_Verb:
241 path->cubicTo(ePtr[1], ePtr[2], ePtr[3]); 249 path->cubicTo(ePtr[1], ePtr[2], ePtr[3]);
242 break; 250 break;
243 default: 251 default:
244 SkASSERT(0); 252 SkASSERT(0);
245 } 253 }
246 } 254 }
247 } 255 }
248 } 256 }
249 257
(...skipping 219 matching lines...) Expand 10 before | Expand all | Expand 10 after
469 angle = span->toAngle(); 477 angle = span->toAngle();
470 if (angle && angle->fCheckCoincidence) { 478 if (angle && angle->fCheckCoincidence) {
471 angle->checkNearCoincidence(); 479 angle->checkNearCoincidence();
472 } 480 }
473 } while ((base = span->next())); 481 } while ((base = span->next()));
474 } 482 }
475 483
476 // from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of -polygon-points-are-in-clockwise-order 484 // from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of -polygon-points-are-in-clockwise-order
477 bool SkOpSegment::clockwise(const SkOpSpanBase* start, const SkOpSpanBase* end, bool* swap) const { 485 bool SkOpSegment::clockwise(const SkOpSpanBase* start, const SkOpSpanBase* end, bool* swap) const {
478 SkASSERT(fVerb != SkPath::kLine_Verb); 486 SkASSERT(fVerb != SkPath::kLine_Verb);
479 SkPoint edge[4]; 487 SkOpCurve edge;
480 if (fVerb == SkPath::kCubic_Verb) { 488 if (fVerb == SkPath::kCubic_Verb) {
481 double startT = start->t(); 489 double startT = start->t();
482 double endT = end->t(); 490 double endT = end->t();
483 bool flip = startT > endT; 491 bool flip = startT > endT;
484 SkDCubic cubic; 492 SkDCubic cubic;
485 cubic.set(fPts); 493 cubic.set(fPts);
486 double inflectionTs[2]; 494 double inflectionTs[2];
487 int inflections = cubic.findInflections(inflectionTs); 495 int inflections = cubic.findInflections(inflectionTs);
488 for (int index = 0; index < inflections; ++index) { 496 for (int index = 0; index < inflections; ++index) {
489 double inflectionT = inflectionTs[index]; 497 double inflectionT = inflectionTs[index];
490 if (between(startT, inflectionT, endT)) { 498 if (between(startT, inflectionT, endT)) {
491 if (flip) { 499 if (flip) {
492 if (inflectionT != endT) { 500 if (!roughly_equal(inflectionT, endT)) {
493 startT = inflectionT; 501 startT = inflectionT;
494 } 502 }
495 } else { 503 } else {
496 if (inflectionT != startT) { 504 if (!roughly_equal(inflectionT, startT)) {
497 endT = inflectionT; 505 endT = inflectionT;
498 } 506 }
499 } 507 }
500 } 508 }
501 } 509 }
502 SkDCubic part = cubic.subDivide(startT, endT); 510 SkDCubic part = cubic.subDivide(startT, endT);
503 for (int index = 0; index < 4; ++index) { 511 edge.set(part);
504 edge[index] = part[index].asSkPoint();
505 }
506 } else { 512 } else {
507 subDivide(start, end, edge); 513 subDivide(start, end, &edge);
508 } 514 }
509 bool sumSet = false; 515 bool sumSet = false;
510 int points = SkPathOpsVerbToPoints(fVerb); 516 int points = SkPathOpsVerbToPoints(fVerb);
511 double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY) ; 517 double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY) ;
512 if (!sumSet) { 518 if (!sumSet) {
513 for (int idx = 0; idx < points; ++idx){ 519 for (int idx = 0; idx < points; ++idx){
514 sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[ idx].fY); 520 sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[ idx].fY);
515 } 521 }
516 } 522 }
517 if (fVerb == SkPath::kCubic_Verb) { 523 if (fVerb == SkPath::kCubic_Verb) {
518 SkDCubic cubic; 524 SkDCubic cubic;
519 cubic.set(edge); 525 cubic.set(edge.fPts);
520 *swap = sum > 0 && !cubic.monotonicInY(); 526 *swap = sum > 0 && !cubic.monotonicInY();
521 } else { 527 } else {
522 SkDQuad quad; 528 SkDQuad quad;
523 quad.set(edge); 529 quad.set(edge.fPts);
524 *swap = sum > 0 && !quad.monotonicInY(); 530 *swap = sum > 0 && !quad.monotonicInY();
525 } 531 }
526 return sum <= 0; 532 return sum <= 0;
527 } 533 }
528 534
529 void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle , 535 void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle ,
530 SkOpAngle::IncludeType includeType) { 536 SkOpAngle::IncludeType includeType) {
531 const SkOpSegment* baseSegment = baseAngle->segment(); 537 const SkOpSegment* baseSegment = baseAngle->segment();
532 int sumMiWinding = baseSegment->updateWindingReverse(baseAngle); 538 int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
533 int sumSuWinding; 539 int sumSuWinding;
(...skipping 141 matching lines...) Expand 10 before | Expand all | Expand 10 after
675 if (fBounds.fLeft == fBounds.fRight) { 681 if (fBounds.fLeft == fBounds.fRight) {
676 // if vertical, and directly above test point, wait for another one 682 // if vertical, and directly above test point, wait for another one
677 *vertical = AlmostEqualUlps(basePt.fX, fBounds.fLeft); 683 *vertical = AlmostEqualUlps(basePt.fX, fBounds.fLeft);
678 return NULL; 684 return NULL;
679 } 685 }
680 // intersect ray starting at basePt with edge 686 // intersect ray starting at basePt with edge
681 SkIntersections intersections; 687 SkIntersections intersections;
682 // OPTIMIZE: use specialty function that intersects ray with curve, 688 // OPTIMIZE: use specialty function that intersects ray with curve,
683 // returning t values only for curve (we don't care about t on ray) 689 // returning t values only for curve (we don't care about t on ray)
684 intersections.allowNear(false); 690 intersections.allowNear(false);
685 int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)]) 691 int pts = (intersections.*CurveVertical[fVerb])(fPts, fWeight, top, bottom, basePt.fX, false);
686 (fPts, top, bottom, basePt.fX, false);
687 if (pts == 0 || (current && pts == 1)) { 692 if (pts == 0 || (current && pts == 1)) {
688 return NULL; 693 return NULL;
689 } 694 }
690 if (current) { 695 if (current) {
691 SkASSERT(pts > 1); 696 SkASSERT(pts > 1);
692 int closestIdx = 0; 697 int closestIdx = 0;
693 double closest = fabs(intersections[0][0] - mid); 698 double closest = fabs(intersections[0][0] - mid);
694 for (int idx = 1; idx < pts; ++idx) { 699 for (int idx = 1; idx < pts; ++idx) {
695 double test = fabs(intersections[0][idx] - mid); 700 double test = fabs(intersections[0][idx] - mid);
696 if (closest > test) { 701 if (closest > test) {
697 closestIdx = idx; 702 closestIdx = idx;
698 closest = test; 703 closest = test;
699 } 704 }
700 } 705 }
701 intersections.quickRemoveOne(closestIdx, --pts); 706 intersections.quickRemoveOne(closestIdx, --pts);
702 } 707 }
703 double bestT = -1; 708 double bestT = -1;
704 for (int index = 0; index < pts; ++index) { 709 for (int index = 0; index < pts; ++index) {
705 double foundT = intersections[0][index]; 710 double foundT = intersections[0][index];
706 if (approximately_less_than_zero(foundT) 711 if (approximately_less_than_zero(foundT)
707 || approximately_greater_than_one(foundT)) { 712 || approximately_greater_than_one(foundT)) {
708 continue; 713 continue;
709 } 714 }
710 SkScalar testY = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fo undT).fY; 715 SkScalar testY = (*CurvePointAtT[fVerb])(fPts, fWeight, foundT).fY;
711 if (approximately_negative(testY - *bestY) 716 if (approximately_negative(testY - *bestY)
712 || approximately_negative(basePt.fY - testY)) { 717 || approximately_negative(basePt.fY - testY)) {
713 continue; 718 continue;
714 } 719 }
715 if (pts > 1 && fVerb == SkPath::kLine_Verb) { 720 if (pts > 1 && fVerb == SkPath::kLine_Verb) {
716 *vertical = true; 721 *vertical = true;
717 return NULL; // if the intersection is edge on, wait for another on e 722 return NULL; // if the intersection is edge on, wait for another on e
718 } 723 }
719 if (fVerb > SkPath::kLine_Verb) { 724 if (fVerb > SkPath::kLine_Verb) {
720 SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, f oundT).fX; 725 SkScalar dx = (*CurveSlopeAtT[fVerb])(fPts, fWeight, foundT).fX;
721 if (approximately_zero(dx)) { 726 if (approximately_zero(dx)) {
722 *vertical = true; 727 *vertical = true;
723 return NULL; // hit vertical, wait for another one 728 return NULL; // hit vertical, wait for another one
724 } 729 }
725 } 730 }
726 *bestY = testY; 731 *bestY = testY;
727 bestT = foundT; 732 bestT = foundT;
728 } 733 }
729 if (bestT < 0) { 734 if (bestT < 0) {
730 return NULL; 735 return NULL;
(...skipping 29 matching lines...) Expand all
760 } 765 }
761 766
762 double SkOpSegment::distSq(double t, SkOpAngle* oppAngle) { 767 double SkOpSegment::distSq(double t, SkOpAngle* oppAngle) {
763 SkDPoint testPt = this->dPtAtT(t); 768 SkDPoint testPt = this->dPtAtT(t);
764 SkDLine testPerp = {{ testPt, testPt }}; 769 SkDLine testPerp = {{ testPt, testPt }};
765 SkDVector slope = this->dSlopeAtT(t); 770 SkDVector slope = this->dSlopeAtT(t);
766 testPerp[1].fX += slope.fY; 771 testPerp[1].fX += slope.fY;
767 testPerp[1].fY -= slope.fX; 772 testPerp[1].fY -= slope.fX;
768 SkIntersections i; 773 SkIntersections i;
769 SkOpSegment* oppSegment = oppAngle->segment(); 774 SkOpSegment* oppSegment = oppAngle->segment();
770 int oppPtCount = SkPathOpsVerbToPoints(oppSegment->verb()); 775 (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weig ht(), testPerp, &i);
771 (*CurveIntersectRay[oppPtCount])(oppSegment->pts(), testPerp, &i);
772 double closestDistSq = SK_ScalarInfinity; 776 double closestDistSq = SK_ScalarInfinity;
773 for (int index = 0; index < i.used(); ++index) { 777 for (int index = 0; index < i.used(); ++index) {
774 if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) { 778 if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) {
775 continue; 779 continue;
776 } 780 }
777 double testDistSq = testPt.distanceSquared(i.pt(index)); 781 double testDistSq = testPt.distanceSquared(i.pt(index));
778 if (closestDistSq > testDistSq) { 782 if (closestDistSq > testDistSq) {
779 closestDistSq = testDistSq; 783 closestDistSq = testDistSq;
780 } 784 }
781 } 785 }
(...skipping 372 matching lines...) Expand 10 before | Expand all | Expand 10 after
1154 __FUNCTION__, 1158 __FUNCTION__,
1155 swap, leftSegment->debugInflections(start, end), 1159 swap, leftSegment->debugInflections(start, end),
1156 leftSegment->monotonicInY(start, end)); 1160 leftSegment->monotonicInY(start, end));
1157 #endif 1161 #endif
1158 if (swap) { 1162 if (swap) {
1159 // FIXME: I doubt it makes sense to (necessarily) swap if the edge was not t he first 1163 // FIXME: I doubt it makes sense to (necessarily) swap if the edge was not t he first
1160 // sorted but merely the first not already processed (i.e., not done) 1164 // sorted but merely the first not already processed (i.e., not done)
1161 SkTSwap(*startPtr, *endPtr); 1165 SkTSwap(*startPtr, *endPtr);
1162 } 1166 }
1163 } 1167 }
1168 // FIXME: clockwise isn't reliable -- try computing swap from tangent ?
1164 } 1169 }
1165 return leftSegment; 1170 return leftSegment;
1166 } 1171 }
1167 1172
1168 SkOpGlobalState* SkOpSegment::globalState() const { 1173 SkOpGlobalState* SkOpSegment::globalState() const {
1169 return contour()->globalState(); 1174 return contour()->globalState();
1170 } 1175 }
1171 1176
1172 void SkOpSegment::init(SkPoint pts[], SkOpContour* contour, SkPath::Verb verb) { 1177 void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkP ath::Verb verb) {
1173 fContour = contour; 1178 fContour = contour;
1174 fNext = NULL; 1179 fNext = NULL;
1175 fPts = pts; 1180 fPts = pts;
1181 fWeight = weight;
1176 fVerb = verb; 1182 fVerb = verb;
1177 fCount = 0; 1183 fCount = 0;
1178 fDoneCount = 0; 1184 fDoneCount = 0;
1179 fVisited = false; 1185 fVisited = false;
1180 SkOpSpan* zeroSpan = &fHead; 1186 SkOpSpan* zeroSpan = &fHead;
1181 zeroSpan->init(this, NULL, 0, fPts[0]); 1187 zeroSpan->init(this, NULL, 0, fPts[0]);
1182 SkOpSpanBase* oneSpan = &fTail; 1188 SkOpSpanBase* oneSpan = &fTail;
1183 zeroSpan->setNext(oneSpan); 1189 zeroSpan->setNext(oneSpan);
1184 oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]); 1190 oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]);
1185 PATH_OPS_DEBUG_CODE(fID = globalState()->nextSegmentID()); 1191 SkDEBUGCODE(fID = globalState()->nextSegmentID());
1186 } 1192 }
1187 1193
1188 void SkOpSegment::initWinding(SkOpSpanBase* start, SkOpSpanBase* end, 1194 void SkOpSegment::initWinding(SkOpSpanBase* start, SkOpSpanBase* end,
1189 SkOpAngle::IncludeType angleIncludeType) { 1195 SkOpAngle::IncludeType angleIncludeType) {
1190 int local = SkOpSegment::SpanSign(start, end); 1196 int local = SkOpSegment::SpanSign(start, end);
1191 SkDEBUGCODE(bool success); 1197 SkDEBUGCODE(bool success);
1192 if (angleIncludeType == SkOpAngle::kBinarySingle) { 1198 if (angleIncludeType == SkOpAngle::kBinarySingle) {
1193 int oppLocal = SkOpSegment::OppSign(start, end); 1199 int oppLocal = SkOpSegment::OppSign(start, end);
1194 SkDEBUGCODE(success =) markAndChaseWinding(start, end, local, oppLocal, NULL); 1200 SkDEBUGCODE(success =) markAndChaseWinding(start, end, local, oppLocal, NULL);
1195 // OPTIMIZATION: the reverse mark and chase could skip the first marking 1201 // OPTIMIZATION: the reverse mark and chase could skip the first marking
(...skipping 12 matching lines...) Expand all
1208 sign or not. However, this isn't enough. 1214 sign or not. However, this isn't enough.
1209 If the supplied sign (winding) is zero, then we didn't hit another vertical span , so dx is needed. 1215 If the supplied sign (winding) is zero, then we didn't hit another vertical span , so dx is needed.
1210 If there was a winding, then it may or may not need adjusting. If the span the w inding was borrowed 1216 If there was a winding, then it may or may not need adjusting. If the span the w inding was borrowed
1211 from has the same x direction as this span, the winding should change. If the dx is opposite, then 1217 from has the same x direction as this span, the winding should change. If the dx is opposite, then
1212 the same winding is shared by both. 1218 the same winding is shared by both.
1213 */ 1219 */
1214 bool SkOpSegment::initWinding(SkOpSpanBase* start, SkOpSpanBase* end, double tHi t, 1220 bool SkOpSegment::initWinding(SkOpSpanBase* start, SkOpSpanBase* end, double tHi t,
1215 int winding, SkScalar hitDx, int oppWind, SkScalar hitOppDx) { 1221 int winding, SkScalar hitDx, int oppWind, SkScalar hitOppDx) {
1216 SkASSERT(this == start->segment()); 1222 SkASSERT(this == start->segment());
1217 SkASSERT(hitDx || !winding); 1223 SkASSERT(hitDx || !winding);
1218 SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX; 1224 SkScalar dx = (*CurveSlopeAtT[fVerb])(fPts, fWeight, tHit).fX;
1219 // SkASSERT(dx); 1225 // SkASSERT(dx);
1220 int windVal = start->starter(end)->windValue(); 1226 int windVal = start->starter(end)->windValue();
1221 #if DEBUG_WINDING_AT_T 1227 #if DEBUG_WINDING_AT_T
1222 SkDebugf("%s id=%d oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, d ebugID(), winding, 1228 SkDebugf("%s id=%d oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, d ebugID(), winding,
1223 hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal); 1229 hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
1224 #endif 1230 #endif
1225 int sideWind = winding + (dx < 0 ? windVal : -windVal); 1231 int sideWind = winding + (dx < 0 ? windVal : -windVal);
1226 if (abs(winding) < abs(sideWind)) { 1232 if (abs(winding) < abs(sideWind)) {
1227 winding = sideWind; 1233 winding = sideWind;
1228 } 1234 }
(...skipping 13 matching lines...) Expand all
1242 #endif 1248 #endif
1243 // if this fails to mark (because the edges are too small) inform caller to try again 1249 // if this fails to mark (because the edges are too small) inform caller to try again
1244 bool success = markAndChaseWinding(start, end, winding, oppWind, NULL); 1250 bool success = markAndChaseWinding(start, end, winding, oppWind, NULL);
1245 // OPTIMIZATION: the reverse mark and chase could skip the first marking 1251 // OPTIMIZATION: the reverse mark and chase could skip the first marking
1246 success |= markAndChaseWinding(end, start, winding, oppWind, NULL); 1252 success |= markAndChaseWinding(end, start, winding, oppWind, NULL);
1247 return success; 1253 return success;
1248 } 1254 }
1249 1255
1250 bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const { 1256 bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const {
1251 SkDPoint cPt = this->dPtAtT(t); 1257 SkDPoint cPt = this->dPtAtT(t);
1252 int pts = SkPathOpsVerbToPoints(this->verb()); 1258 SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight() , t);
1253 SkDVector dxdy = (*CurveDSlopeAtT[pts])(this->pts(), t);
1254 SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; 1259 SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
1255 SkIntersections i; 1260 SkIntersections i;
1256 int oppPts = SkPathOpsVerbToPoints(opp->verb()); 1261 (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i);
1257 (*CurveIntersectRay[oppPts])(opp->pts(), perp, &i);
1258 int used = i.used(); 1262 int used = i.used();
1259 for (int index = 0; index < used; ++index) { 1263 for (int index = 0; index < used; ++index) {
1260 if (cPt.roughlyEqual(i.pt(index))) { 1264 if (cPt.roughlyEqual(i.pt(index))) {
1261 return true; 1265 return true;
1262 } 1266 }
1263 } 1267 }
1264 return false; 1268 return false;
1265 } 1269 }
1266 1270
1267 bool SkOpSegment::isXor() const { 1271 bool SkOpSegment::isXor() const {
(...skipping 178 matching lines...) Expand 10 before | Expand all | Expand 10 after
1446 } 1450 }
1447 return NULL; 1451 return NULL;
1448 } 1452 }
1449 1453
1450 bool SkOpSegment::monotonicInY(const SkOpSpanBase* start, const SkOpSpanBase* en d) const { 1454 bool SkOpSegment::monotonicInY(const SkOpSpanBase* start, const SkOpSpanBase* en d) const {
1451 SkASSERT(fVerb != SkPath::kLine_Verb); 1455 SkASSERT(fVerb != SkPath::kLine_Verb);
1452 if (fVerb == SkPath::kQuad_Verb) { 1456 if (fVerb == SkPath::kQuad_Verb) {
1453 SkDQuad dst = SkDQuad::SubDivide(fPts, start->t(), end->t()); 1457 SkDQuad dst = SkDQuad::SubDivide(fPts, start->t(), end->t());
1454 return dst.monotonicInY(); 1458 return dst.monotonicInY();
1455 } 1459 }
1460 if (fVerb == SkPath::kConic_Verb) {
1461 SkDConic dst = SkDConic::SubDivide(fPts, fWeight, start->t(), end->t());
1462 return dst.monotonicInY();
1463 }
1456 SkASSERT(fVerb == SkPath::kCubic_Verb); 1464 SkASSERT(fVerb == SkPath::kCubic_Verb);
1457 SkDCubic dst = SkDCubic::SubDivide(fPts, start->t(), end->t()); 1465 SkDCubic dst = SkDCubic::SubDivide(fPts, start->t(), end->t());
1458 return dst.monotonicInY(); 1466 return dst.monotonicInY();
1459 } 1467 }
1460 1468
1461 bool SkOpSegment::NextCandidate(SkOpSpanBase* span, SkOpSpanBase** start, 1469 bool SkOpSegment::NextCandidate(SkOpSpanBase* span, SkOpSpanBase** start,
1462 SkOpSpanBase** end) { 1470 SkOpSpanBase** end) {
1463 while (span->final() || span->upCast()->done()) { 1471 while (span->final() || span->upCast()->done()) {
1464 if (span->final()) { 1472 if (span->final()) {
1465 return false; 1473 return false;
(...skipping 142 matching lines...) Expand 10 before | Expand all | Expand 10 after
1608 { 1616 {
1609 // average t, find mid pt 1617 // average t, find mid pt
1610 double midT = (prior->t() + span->t()) / 2; 1618 double midT = (prior->t() + span->t()) / 2;
1611 SkPoint midPt = this->ptAtT(midT); 1619 SkPoint midPt = this->ptAtT(midT);
1612 coincident = true; 1620 coincident = true;
1613 // if the mid pt is not near either end pt, project perpendicula r through opp seg 1621 // if the mid pt is not near either end pt, project perpendicula r through opp seg
1614 if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt) 1622 if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt)
1615 && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) { 1623 && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
1616 coincident = false; 1624 coincident = false;
1617 SkIntersections i; 1625 SkIntersections i;
1618 int ptCount = SkPathOpsVerbToPoints(this->verb()); 1626 SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->w eight(), midT);
1619 SkVector dxdy = (*CurveSlopeAtT[ptCount])(pts(), midT);
1620 SkDLine ray = {{{midPt.fX, midPt.fY}, 1627 SkDLine ray = {{{midPt.fX, midPt.fY},
1621 {midPt.fX + dxdy.fY, midPt.fY - dxdy.fX}}}; 1628 {midPt.fX + dxdy.fY, midPt.fY - dxdy.fX}}};
1622 int oppPtCount = SkPathOpsVerbToPoints(opp->verb()); 1629 (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), ray, &i);
1623 (*CurveIntersectRay[oppPtCount])(opp->pts(), ray, &i);
1624 // measure distance and see if it's small enough to denote c oincidence 1630 // measure distance and see if it's small enough to denote c oincidence
1625 for (int index = 0; index < i.used(); ++index) { 1631 for (int index = 0; index < i.used(); ++index) {
1626 SkDPoint oppPt = i.pt(index); 1632 SkDPoint oppPt = i.pt(index);
1627 if (oppPt.approximatelyEqual(midPt)) { 1633 if (oppPt.approximatelyEqual(midPt)) {
1628 SkVector oppDxdy = (*CurveSlopeAtT[oppPtCount])(opp- >pts(), 1634 SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp ->pts(),
1629 i[index][0]); 1635 opp->weight(), i[index][0]);
1630 oppDxdy.normalize(); 1636 oppDxdy.normalize();
1631 dxdy.normalize(); 1637 dxdy.normalize();
1632 SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON); 1638 SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON);
1633 coincident |= flatness < 5000; // FIXME: replace wi th tuned value 1639 coincident |= flatness < 5000; // FIXME: replace wi th tuned value
1634 } 1640 }
1635 } 1641 }
1636 } 1642 }
1637 } 1643 }
1638 if (coincident) { 1644 if (coincident) {
1639 // mark coincidence 1645 // mark coincidence
(...skipping 182 matching lines...) Expand 10 before | Expand all | Expand 10 after
1822 baseAngle = NULL; 1828 baseAngle = NULL;
1823 } 1829 }
1824 #if DEBUG_SORT 1830 #if DEBUG_SORT
1825 SkASSERT(!baseAngle || baseAngle->loopCount() > 1); 1831 SkASSERT(!baseAngle || baseAngle->loopCount() > 1);
1826 #endif 1832 #endif
1827 } while (!span->final() && (span = span->upCast()->next())); 1833 } while (!span->final() && (span = span->upCast()->next()));
1828 } 1834 }
1829 1835
1830 // return true if midpoints were computed 1836 // return true if midpoints were computed
1831 bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, 1837 bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
1832 SkPoint edge[4]) const { 1838 SkOpCurve* edge) const {
1833 SkASSERT(start != end); 1839 SkASSERT(start != end);
1834 const SkOpPtT& startPtT = *start->ptT(); 1840 const SkOpPtT& startPtT = *start->ptT();
1835 const SkOpPtT& endPtT = *end->ptT(); 1841 const SkOpPtT& endPtT = *end->ptT();
1836 edge[0] = startPtT.fPt; 1842 SkDEBUGCODE(edge->fVerb = fVerb);
1843 edge->fPts[0] = startPtT.fPt;
1837 int points = SkPathOpsVerbToPoints(fVerb); 1844 int points = SkPathOpsVerbToPoints(fVerb);
1838 edge[points] = endPtT.fPt; 1845 edge->fPts[points] = endPtT.fPt;
1846 edge->fWeight = 1;
1839 if (fVerb == SkPath::kLine_Verb) { 1847 if (fVerb == SkPath::kLine_Verb) {
1840 return false; 1848 return false;
1841 } 1849 }
1842 double startT = startPtT.fT; 1850 double startT = startPtT.fT;
1843 double endT = endPtT.fT; 1851 double endT = endPtT.fT;
1844 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { 1852 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
1845 // don't compute midpoints if we already have them 1853 // don't compute midpoints if we already have them
1846 if (fVerb == SkPath::kQuad_Verb) { 1854 if (fVerb == SkPath::kQuad_Verb) {
1847 edge[1] = fPts[1]; 1855 edge->fPts[1] = fPts[1];
1856 return false;
1857 }
1858 if (fVerb == SkPath::kConic_Verb) {
1859 edge->fPts[1] = fPts[1];
1860 edge->fWeight = fWeight;
1848 return false; 1861 return false;
1849 } 1862 }
1850 SkASSERT(fVerb == SkPath::kCubic_Verb); 1863 SkASSERT(fVerb == SkPath::kCubic_Verb);
1851 if (start < end) { 1864 if (start < end) {
1852 edge[1] = fPts[1]; 1865 edge->fPts[1] = fPts[1];
1853 edge[2] = fPts[2]; 1866 edge->fPts[2] = fPts[2];
1854 return false; 1867 return false;
1855 } 1868 }
1856 edge[1] = fPts[2]; 1869 edge->fPts[1] = fPts[2];
1857 edge[2] = fPts[1]; 1870 edge->fPts[2] = fPts[1];
1858 return false; 1871 return false;
1859 } 1872 }
1860 const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[p oints].fY }}; 1873 const SkDPoint sub[2] = {{ edge->fPts[0].fX, edge->fPts[0].fY},
1874 {edge->fPts[points].fX, edge->fPts[points].fY }};
1861 if (fVerb == SkPath::kQuad_Verb) { 1875 if (fVerb == SkPath::kQuad_Verb) {
1862 edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoi nt(); 1876 edge->fPts[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).a sSkPoint();
1877 } else if (fVerb == SkPath::kConic_Verb) {
1878 edge->fPts[1] = SkDConic::SubDivide(fPts, fWeight, sub[0], sub[1],
1879 startT, endT, &edge->fWeight).asSkPoint();
1863 } else { 1880 } else {
1864 SkASSERT(fVerb == SkPath::kCubic_Verb); 1881 SkASSERT(fVerb == SkPath::kCubic_Verb);
1865 SkDPoint ctrl[2]; 1882 SkDPoint ctrl[2];
1866 SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl); 1883 SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl);
1867 edge[1] = ctrl[0].asSkPoint(); 1884 edge->fPts[1] = ctrl[0].asSkPoint();
1868 edge[2] = ctrl[1].asSkPoint(); 1885 edge->fPts[2] = ctrl[1].asSkPoint();
1869 } 1886 }
1870 return true; 1887 return true;
1871 } 1888 }
1872 1889
1873 bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, 1890 bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
1874 SkDCubic* result) const { 1891 SkDCurve* edge) const {
1875 SkASSERT(start != end); 1892 SkASSERT(start != end);
1876 const SkOpPtT& startPtT = *start->ptT(); 1893 const SkOpPtT& startPtT = *start->ptT();
1877 const SkOpPtT& endPtT = *end->ptT(); 1894 const SkOpPtT& endPtT = *end->ptT();
1878 (*result)[0].set(startPtT.fPt); 1895 SkDEBUGCODE(edge->fVerb = fVerb);
1896 edge->fCubic[0].set(startPtT.fPt);
1879 int points = SkPathOpsVerbToPoints(fVerb); 1897 int points = SkPathOpsVerbToPoints(fVerb);
1880 (*result)[points].set(endPtT.fPt); 1898 edge->fCubic[points].set(endPtT.fPt);
1881 if (fVerb == SkPath::kLine_Verb) { 1899 if (fVerb == SkPath::kLine_Verb) {
1882 return false; 1900 return false;
1883 } 1901 }
1884 double startT = startPtT.fT; 1902 double startT = startPtT.fT;
1885 double endT = endPtT.fT; 1903 double endT = endPtT.fT;
1886 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { 1904 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
1887 // don't compute midpoints if we already have them 1905 // don't compute midpoints if we already have them
1888 if (fVerb == SkPath::kQuad_Verb) { 1906 if (fVerb == SkPath::kQuad_Verb) {
1889 (*result)[1].set(fPts[1]); 1907 edge->fLine[1].set(fPts[1]);
1908 return false;
1909 }
1910 if (fVerb == SkPath::kConic_Verb) {
1911 edge->fConic[1].set(fPts[1]);
1912 edge->fConic.fWeight = fWeight;
1890 return false; 1913 return false;
1891 } 1914 }
1892 SkASSERT(fVerb == SkPath::kCubic_Verb); 1915 SkASSERT(fVerb == SkPath::kCubic_Verb);
1893 if (startT == 0) { 1916 if (startT == 0) {
1894 (*result)[1].set(fPts[1]); 1917 edge->fCubic[1].set(fPts[1]);
1895 (*result)[2].set(fPts[2]); 1918 edge->fCubic[2].set(fPts[2]);
1896 return false; 1919 return false;
1897 } 1920 }
1898 (*result)[1].set(fPts[2]); 1921 edge->fCubic[1].set(fPts[2]);
1899 (*result)[2].set(fPts[1]); 1922 edge->fCubic[2].set(fPts[1]);
1900 return false; 1923 return false;
1901 } 1924 }
1902 if (fVerb == SkPath::kQuad_Verb) { 1925 if (fVerb == SkPath::kQuad_Verb) {
1903 (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], star tT, endT); 1926 edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2] , startT, endT);
1927 } else if (fVerb == SkPath::kConic_Verb) {
1928 edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edg e->fQuad[2],
1929 startT, endT, &edge->fConic.fWeight);
1904 } else { 1930 } else {
1905 SkASSERT(fVerb == SkPath::kCubic_Verb); 1931 SkASSERT(fVerb == SkPath::kCubic_Verb);
1906 SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*r esult)[1]); 1932 SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT , &edge->fCubic[1]);
1907 } 1933 }
1908 return true; 1934 return true;
1909 } 1935 }
1910 1936
1911 void SkOpSegment::subDivideBounds(const SkOpSpanBase* start, const SkOpSpanBase* end, 1937 void SkOpSegment::subDivideBounds(const SkOpSpanBase* start, const SkOpSpanBase* end,
1912 SkPathOpsBounds* bounds) const { 1938 SkPathOpsBounds* bounds) const {
1913 SkPoint edge[4]; 1939 SkOpCurve edge;
1914 subDivide(start, end, edge); 1940 subDivide(start, end, &edge);
1915 (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge); 1941 (bounds->*SetCurveBounds[fVerb])(edge.fPts, edge.fWeight);
1916 } 1942 }
1917 1943
1918 void SkOpSegment::undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end) { 1944 void SkOpSegment::undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end) {
1919 SkOpSpan* span = this->head(); 1945 SkOpSpan* span = this->head();
1920 do { 1946 do {
1921 if (!span->done()) { 1947 if (!span->done()) {
1922 break; 1948 break;
1923 } 1949 }
1924 } while ((span = span->next()->upCastable())); 1950 } while ((span = span->next()->upCastable()));
1925 SkASSERT(span); 1951 SkASSERT(span);
(...skipping 68 matching lines...) Expand 10 before | Expand all | Expand 10 after
1994 return SK_MinS32; 2020 return SK_MinS32;
1995 } 2021 }
1996 int winding = crossOpp ? span->oppSum() : span->windSum(); 2022 int winding = crossOpp ? span->oppSum() : span->windSum();
1997 SkASSERT(winding != SK_MinS32); 2023 SkASSERT(winding != SK_MinS32);
1998 int windVal = crossOpp ? span->oppValue() : span->windValue(); 2024 int windVal = crossOpp ? span->oppValue() : span->windValue();
1999 #if DEBUG_WINDING_AT_T 2025 #if DEBUG_WINDING_AT_T
2000 SkDebugf("%s id=%d opp=%d tHit=%1.9g t=%1.9g oldWinding=%d windValue=%d", __ FUNCTION__, 2026 SkDebugf("%s id=%d opp=%d tHit=%1.9g t=%1.9g oldWinding=%d windValue=%d", __ FUNCTION__,
2001 debugID(), crossOpp, tHit, span->t(), winding, windVal); 2027 debugID(), crossOpp, tHit, span->t(), winding, windVal);
2002 #endif 2028 #endif
2003 // see if a + change in T results in a +/- change in X (compute x'(T)) 2029 // see if a + change in T results in a +/- change in X (compute x'(T))
2004 *dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX; 2030 *dx = (*CurveSlopeAtT[fVerb])(fPts, fWeight, tHit).fX;
2005 if (fVerb > SkPath::kLine_Verb && approximately_zero(*dx)) { 2031 if (fVerb > SkPath::kLine_Verb && approximately_zero(*dx)) {
2006 *dx = fPts[2].fX - fPts[1].fX - *dx; 2032 *dx = fPts[2].fX - fPts[1].fX - *dx;
2007 } 2033 }
2008 if (*dx == 0) { 2034 if (*dx == 0) {
2009 #if DEBUG_WINDING_AT_T 2035 #if DEBUG_WINDING_AT_T
2010 SkDebugf(" dx=0 winding=SK_MinS32\n"); 2036 SkDebugf(" dx=0 winding=SK_MinS32\n");
2011 #endif 2037 #endif
2012 return SK_MinS32; 2038 return SK_MinS32;
2013 } 2039 }
2014 if (windVal < 0) { // reverse sign if opp contour traveled in reverse 2040 if (windVal < 0) { // reverse sign if opp contour traveled in reverse
2015 *dx = -*dx; 2041 *dx = -*dx;
2016 } 2042 }
2017 if (winding * *dx > 0) { // if same signs, result is negative 2043 if (winding * *dx > 0) { // if same signs, result is negative
2018 winding += *dx > 0 ? -windVal : windVal; 2044 winding += *dx > 0 ? -windVal : windVal;
2019 } 2045 }
2020 #if DEBUG_WINDING_AT_T 2046 #if DEBUG_WINDING_AT_T
2021 SkDebugf(" dx=%c winding=%d\n", *dx > 0 ? '+' : '-', winding); 2047 SkDebugf(" dx=%c winding=%d\n", *dx > 0 ? '+' : '-', winding);
2022 #endif 2048 #endif
2023 return winding; 2049 return winding;
2024 } 2050 }
2025 2051
2026 int SkOpSegment::windSum(const SkOpAngle* angle) const { 2052 int SkOpSegment::windSum(const SkOpAngle* angle) const {
2027 const SkOpSpan* minSpan = angle->start()->starter(angle->end()); 2053 const SkOpSpan* minSpan = angle->start()->starter(angle->end());
2028 return minSpan->windSum(); 2054 return minSpan->windSum();
2029 } 2055 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698