skia / skia / fb35940de79fd67f8739601bebdd3d75089b1522 / . / experimental / Intersection / thingsToDo.txt

/* | |

* Copyright 2012 Google Inc. | |

* | |

* Use of this source code is governed by a BSD-style license that can be | |

* found in the LICENSE file. | |

*/ | |

add unit test for quadratic horizontal intersection | |

add unit test for cubic horizontal intersection with left/right | |

add unit test for ActiveEdge::calcLeft (can currently loop forever) | |

does ActiveEdge::isCoincidentWith need to support quad, cubic? | |

figure out why variation in ActiveEdge::tooCloseToCall isn't better | |

why does 'lastPtr - 2' in addIntersectingTs break testSimplifyTriangle22? | |

add code to promote quad to cubic, or add quad/cubic intersection | |

figure out why testSimplifySkinnyTriangle13 fails | |

for quadratics and cubics, once various T values are added, see if consecutive | |

Ts have ys that go up instead of down. If so, the edge needs to be broken. | |

when splitting curves at inflection pts, should I retain the original curve | |

data and note that the first/last T are no longer 0/1 ? | |

I need to figure this out before I can proceed | |

would it make sense to leave the InEdge alone, and add multiple copies of | |

ActiveEdge, pointing to the same InEdge, where the copy has only the subset | |

of Ts that need to be walked in reverse order? | |

-- A Digression Which Shows Why Resolving Coincidence Does Not Make Sense -- | |

Consider the following fine ASCII art: | |

+------>-------+ +------>-------+ | |

| | | | | |

^ V ^ V | |

| | | | | |

+------<-------+ +------<-------+ | |

+------>-------+ +------<-------+ | |

| | | | | |

^ V V ^ | |

| | | | | |

+------<-------+ +------>-------+ | |

(assume the bottom and top of the stacked rectangles are coincident) | |

Simplifying said rectangles, regardless of rectangle direction, and regardless | |

of winding or even/odd, eliminates the coincident edge, i.e., the result is | |

always: | |

+------>-------+ | |

| | | |

| | | |

| | | |

^ V | |

| | | |

| | | |

| | | |

+------<-------+ | |

But when the rectangles are enclosed in a larger rectangle: | |

+-------->---------+ +-------->---------+ | |

| +------>-------+ | | +------>-------+ | | |

| | | | | | | | | |

| ^ V | | ^ V | | |

| | | | | | | | | |

| +------<-------+ | | +------<-------+ | | |

| +------>-------+ | | +------<-------+ | | |

| | | | | | | | | |

| ^ V | | V ^ | | |

| | | | | | | | | |

| +------<-------+ | | +------>-------+ | | |

+--------<---------+ +--------<---------+ | |

Simplifying them gives different results depending on the winding setting: | |

winding: | |

+-------->---------+ +-------->---------+ | |

| | | | | |

| | | | | |

| | | | | |

| | | | | |

| | | +------<-------+ | | |

| | | | | | | |

| | | V ^ | | |

| | | | | | | |

| | | +------>-------+ | | |

+--------<---------+ +--------<---------+ | |

even odd: | |

+-------->---------+ +-------->---------+ | |

| +------<-------+ | | +------<-------+ | | |

| | | | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

| V ^ | | V ^ | | |

| | | | | | | | | |

| | | | | | | | | |

| | | | | | | | | |

| +------>-------+ | | +------>-------+ | | |

+--------<---------+ +--------<---------+ | |

So, given the inner rectangles alone (e.g., given coincident pairs in some local | |

context), we can't know whether to keep the coincident edges or not. | |

-- Thoughts About Sortless Ops -- | |

I can't come up with anything truly sortless. It seems that the crossings need | |

to be sorted to know which segment is next on the outside, although sometimes | |

we can use that it is not coincident just to follow the direction. | |

If it is coincident or if there's more than two crossing segments, sorting | |

seems inevitable. | |

Likewise, to resolve whether one contour is inside another, it seems that | |

sorting is required. Given a pair of segments on different contours, to know | |

if one is inside of the other, I need to know for each which side of the edge | |

is the inside/filled side. When the outer contour is walked, it seems like I | |

could record the inside info. I guess when the inner contour is found, its | |

inside sense is reversed (inside is above the top). But how do I know if the | |

next contour is inside another? Maybe shoot out a line and brute-force | |

intersect it with all the segments in all the other contours? If every contour | |

has an extra segment when the intersections are computed, this may not be as | |

crazy as it seems. | |

Suppose each contour has one extra segment shooting straight up from the top | |

(or straight up from any point on the segment). This ray is not intersected | |

with the home contour, but is intersected with all other contours as part of | |

the normal intersection engine. If it is possible to get from the T values to | |

the other segments to the other contours, it would be straightforward to | |

count the contour crossings and determine if the home contour is in another | |

contour or not (if the count is even, not, if odd, is inside). By itself that | |

doesn't tell us about winding, but it's a start. | |

Since intersecting these rays is unrelated to computing other intersections, | |

it can be lazily done once the contour is found. | |

So | |

repeat the following | |

find the top segment of all contours | |

trace the outside, marking touching first and last segments as inside | |

continue tracing the touched segments with reversed outside/inside sense | |

once the edges are exhausted, remaining must be disjoint contours | |

send a ray from a disjoint point through all other contours | |

count the crossings, determine if disjoint is inside or outside, then continue | |

=== | |

On Quadratic (and Cubic) Intersections | |

Currently, if only the end points touch, QuadracticIntersections does a lot of | |

work to figure that out. Can I test for that up front, then short circuit the | |

recursive search for the end points? | |

Or, is there something defective in the current approach that makes the end | |

point recursion go so deep? I'm seeing 56 stack frames (about 28 divides, but | |

thankfully, no splits) to find one matching endpoint. | |

Bezier curve focus may allow more quickly determining that end points with | |

identical tangents are practically coicident for some range of T, but I don't | |

understand the math yet to know. | |

Another approach is to determine how flat the curve is to make good guesses | |

about how far to move away in T before doing the intersection for the remainder | |

and/or to determine whether one curve is to the inside or outside of another. | |

According to Mike/Rob, the flatness for quadratics increases by 4 for each | |

subdivision, and a crude guess of the curvature can be had by comparing P1 to | |

(P0+P2)/2. By looking at the ULPS of the numbers, I can guess what value of | |

T may be far enough that the curves diverge but don't cross. | |

==== | |

Code I May Not Need Any More | |

static bool CoincidentCandidate(const Angle* current) { | |

const Segment* segment = current->segment(); | |

int min = SkMin32(current->start(), current->end()); | |

do { | |

const Span& span = segment->fTs[min]; | |

if (span.fCoincident == Span::kStart_Coincidence) { | |

return true; | |

} | |

} while (--min >= 0); | |

return false; | |

} | |

static bool CoincidentHalf(const Angle* current, const Angle* next) { | |

const Segment* other = next->segment(); | |

const Segment* segment = current->segment(); | |

int min = SkMin32(current->start(), current->end()); | |

const Span& minSpan = segment->fTs[min]; | |

if (minSpan.fOther == other) { | |

return minSpan.fCoincident == Span::kStart_Coincidence; | |

} | |

int index = min; | |

int spanCount = segment->fTs.count(); | |

while (++index < spanCount) { | |

const Span& span = segment->fTs[index]; | |

if (minSpan.fT != span.fT) { | |

break; | |

} | |

if (span.fOther != other) { | |

continue; | |

} | |

return span.fCoincident == Span::kStart_Coincidence; | |

} | |

index = min; | |

while (--index >= 0) { | |

const Span& span = segment->fTs[index]; | |

if (span.fOther != other) { | |

continue; | |

} | |

return span.fCoincident == Span::kStart_Coincidence; | |

} | |

return false; | |

} | |

static bool Coincident(const Angle* current, const Angle* next) { | |

return CoincidentHalf(current, next) && | |

CoincidentHalf(next, current); | |

} | |

// If three lines cancel in a - b - c order, a - b may or may not | |

// eliminate the edge that describes the b - c cancellation. Check done to | |

// determine this. | |

static bool CoincidentCancels(const Angle* current, const Angle* next) { | |

int curMin = SkMin32(current->start(), current->end()); | |

if (current->segment()->fTs[curMin].fDone) { | |

return false; | |

} | |

int nextMin = SkMin32(next->start(), next->end()); | |

if (next->segment()->fTs[nextMin].fDone) { | |

return false; | |

} | |

return SkSign32(current->start() - current->end()) | |

!= SkSign32(next->start() - next->end()); | |

} | |

// FIXME: at this point, just have two functions for the different steps | |

int coincidentEnd(int from, int step) const { | |

double fromT = fTs[from].fT; | |

int count = fTs.count(); | |

int to = from; | |

while (step > 0 ? ++to < count : --to >= 0) { | |

const Span& span = fTs[to]; | |

if ((step > 0 ? span.fT - fromT : fromT - span.fT) >= FLT_EPSILON ) { | |

// FIXME: we assume that if the T changes, we don't care about | |

// coincident -- but in nextSpan, we require that both the T | |

// and actual loc change to represent a span. This asymettry may | |

// be OK or may be trouble -- if trouble, probably will need to | |

// detect coincidence earlier or sort differently | |

break; | |

} | |

#if 01 | |

if (span.fCoincident == (step < 0 ? Span::kStart_Coincidence : | |

Span::kEnd_Coincidence)) { | |

from = to; | |

} | |

#else | |

from = to; | |

#endif | |

} | |

return from; | |

} | |

// once past current span, if step>0, look for coicident==1 | |

// if step<0, look for coincident==-1 | |

int nextSpanEnd(int from, int step) const { | |

int result = nextSpan(from, step); | |

if (result < 0) { | |

return result; | |

} | |

return coincidentEnd(result, step); | |

} | |

void adjustFirst(const SkTDArray<Angle*>& sorted, int& first, int& winding, | |

bool outside) { | |

int firstIndex = first; | |

int angleCount = sorted.count(); | |

if (true || outside) { | |

const Angle* angle = sorted[firstIndex]; | |

int prior = firstIndex; | |

do { | |

if (--prior < 0) { | |

prior = angleCount - 1; | |

} | |

if (prior == firstIndex) { // all are coincident with each other | |

return; | |

} | |

if (!Coincident(sorted[prior], sorted[first])) { | |

return; | |

} | |

winding += angle->sign(); | |

first = prior; | |

angle = sorted[prior]; | |

winding -= angle->sign(); | |

} while (true); | |

} | |

do { | |

int next = first + 1; | |

if (next == angleCount) { | |

next = 0; | |

} | |

if (next == firstIndex) { // all are coincident with each other | |

return; | |

} | |

if (!Coincident(sorted[first], sorted[next])) { | |

return; | |

} | |

first = next; | |

} while (true); | |

} | |

bool nextIsCoincident = CoincidentCandidate(nextAngle); | |

bool finalOrNoCoincident = true; | |

bool pairCoincides = false; | |

bool pairCancels = false; | |

if (nextIsCoincident) { | |

int followIndex = nextIndex + 1; | |

if (followIndex == angleCount) { | |

followIndex = 0; | |

} | |

const Angle* followAngle = sorted[followIndex]; | |

finalOrNoCoincident = !Coincident(nextAngle, followAngle); | |

if ((pairCoincides = Coincident(angle, nextAngle))) { | |

pairCancels = CoincidentCancels(angle, nextAngle); | |

} | |

} | |

if (pairCancels && !foundAngle && !nextSegment->done()) { | |

Segment* aSeg = angle->segment(); | |

// alreadyMarked |= aSeg == sorted[firstIndex]->segment(); | |

aSeg->markAndChaseCoincident(angle->start(), angle->end(), | |

nextSegment); | |

if (firstEdge) { | |

return NULL; | |

} | |

} | |

if (pairCoincides) { | |

if (pairCancels) { | |

goto doNext; | |

} | |

int minT = SkMin32(nextAngle->start(), nextAngle->end()); | |

bool markNext = abs(maxWinding) < abs(winding); | |

if (markNext) { | |

nextSegment->markDone(minT, winding); | |

} | |

int oldMinT = SkMin32(angle->start(), angle->end()); | |

if (true || !foundAngle) { | |

// SkASSERT(0); // do we ever get here? | |

Segment* aSeg = angle->segment(); | |

// alreadyMarked |= aSeg == sorted[firstIndex]->segment(); | |

aSeg->markDone(oldMinT, maxWinding); | |

} | |

} | |

// OPTIMIZATION: uses tail recursion. Unwise? | |

void innerCoincidentChase(int step, Segment* other) { | |

// find other at index | |

// SkASSERT(!done()); | |

const Span* start = NULL; | |

const Span* end = NULL; | |

int index, startIndex, endIndex; | |

int count = fTs.count(); | |

for (index = 0; index < count; ++index) { | |

const Span& span = fTs[index]; | |

if (!span.fCoincident || span.fOther != other) { | |

continue; | |

} | |

if (!start) { | |

startIndex = index; | |

start = &span; | |

} else { | |

SkASSERT(!end); | |

endIndex = index; | |

end = &span; | |

} | |

} | |

if (!end) { | |

return; | |

} | |

bool thisDone = fTs[SkMin32(startIndex, endIndex)].fDone; | |

bool otherDone = other->fTs[SkMin32(start->fOtherIndex, | |

end->fOtherIndex)].fDone; | |

if (thisDone && otherDone) { | |

return; | |

} | |

Segment* next; | |

Segment* nextOther; | |

if (step < 0) { | |

next = start->fT == 0 ? NULL : this; | |

nextOther = other->fTs[start->fOtherIndex].fT > 1 - FLT_EPSILON ? NULL : other; | |

} else { | |

next = end->fT == 1 ? NULL : this; | |

nextOther = other->fTs[end->fOtherIndex].fT < FLT_EPSILON ? NULL : other; | |

} | |

SkASSERT(!next || !nextOther); | |

for (index = 0; index < count; ++index) { | |

const Span& span = fTs[index]; | |

if (span.fCoincident || span.fOther == other) { | |

continue; | |

} | |

bool checkNext = !next && (step < 0 ? span.fT < FLT_EPSILON | |

&& span.fOtherT > 1 - FLT_EPSILON : span.fT > 1 - FLT_EPSILON | |

&& span.fOtherT < FLT_EPSILON); | |

bool checkOther = !nextOther && (step < 0 ? fabs(span.fT - start->fT) < FLT_EPSILON | |

&& span.fOtherT < FLT_EPSILON : fabs(span.fT - end->fT) < FLT_EPSILON | |

&& span.fOtherT > 1 - FLT_EPSILON); | |

if (!checkNext && !checkOther) { | |

continue; | |

} | |

Segment* oSegment = span.fOther; | |

if (oSegment->done()) { | |

continue; | |

} | |

int oCount = oSegment->fTs.count(); | |

for (int oIndex = 0; oIndex < oCount; ++oIndex) { | |

const Span& oSpan = oSegment->fTs[oIndex]; | |

if (oSpan.fT >= FLT_EPSILON && oSpan.fT <= 1 - FLT_EPSILON) { | |

continue; | |

} | |

if (!oSpan.fCoincident) { | |

continue; | |

} | |

if (checkNext && (oSpan.fT < FLT_EPSILON ^ step < 0)) { | |

next = oSegment; | |

checkNext = false; | |

} | |

if (checkOther && (oSpan.fT > 1 - FLT_EPSILON ^ step < 0)) { | |

nextOther = oSegment; | |

checkOther = false; | |

} | |

} | |

} | |

// this needs to walk both spans in lock step, skipping edges that | |

// are already marked done on one or the other | |

markCanceled(startIndex, endIndex); | |

if (next && nextOther) { | |

next->innerCoincidentChase(step, nextOther); | |

} | |

} | |

// cancel coincident edges in lock step | |

void markCanceled(int start, int end) { | |

if (done()) { | |

return; | |

} | |

Segment* other = fTs[start].fOther; | |

if (other->done()) { | |

return; | |

} | |

if (start > end) { | |

SkTSwap<int>(start, end); | |

} | |

double maxT = fTs[end].fT - FLT_EPSILON; | |

int spanCount = fTs.count(); | |

// since these cancel, this walks up and other walks down | |

int oStart = fTs[start].fOtherIndex; | |

double oStartT = other->fTs[oStart].fT; | |

while (oStartT - other->fTs[--oStart].fT < FLT_EPSILON) | |

; | |

double startT = fTs[start].fT; | |

while (start > 0 && startT - fTs[start - 1].fT < FLT_EPSILON) { | |

--start; | |

} | |

do { | |

Span* span = &fTs[start]; | |

Span* oSpan = &other->fTs[oStart]; | |

// find start of each, and see if both are not done | |

bool markDone = !span->fDone && !oSpan->fDone; | |

double spanT = span->fT; | |

do { | |

if (markDone) { | |

span->fCanceled = true; | |

#if DEBUG_MARK_DONE | |

const SkPoint& pt = xyAtT(span); | |

SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g)\n", | |

__FUNCTION__, fID, start, span->fT, pt.fX, pt.fY); | |

#endif | |

SkASSERT(!span->fDone); | |

span->fDone = true; | |

span->fWinding = 0; | |

fDoneSpans++; | |

} | |

if (++start == spanCount) { | |

break; | |

} | |

span = &fTs[start]; | |

} while (span->fT - spanT < FLT_EPSILON); | |

double oSpanT = oSpan->fT; | |

do { | |

if (markDone) { | |

oSpan->fCanceled = true; | |

#if DEBUG_MARK_DONE | |

const SkPoint& oPt = xyAtT(oSpan); | |

SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g)\n", | |

__FUNCTION__, other->fID, oStart, oSpan->fT, | |

oPt.fX, oPt.fY); | |

#endif | |

SkASSERT(!oSpan->fDone); | |

oSpan->fDone = true; | |

oSpan->fWinding = 0; | |

other->fDoneSpans++; | |

} | |

if (--oStart < 0) { | |

break; | |

} | |

oSpan = &other->fTs[oStart]; | |

} while (oSpanT - oSpan->fT < FLT_EPSILON); | |

} while (fTs[start].fT <= maxT); | |

} | |

bool canceled(int start, int end) const { | |

int min = SkMin32(start, end); | |

return fTs[min].fCanceled; | |

} | |

void markAndChaseCoincident(int index, int endIndex, Segment* other) { | |

int step = SkSign32(endIndex - index); | |

innerCoincidentChase(step, other); | |

} | |