| SkAddIntersections.cpp |
|
28212 |
| SkAddIntersections.h |
|
355 |
| SkDConicLineIntersection.cpp |
|
14655 |
| SkDCubicLineIntersection.cpp |
Find the intersection of a line and cubic by solving for valid t values.
Analogous to line-quadratic intersection, solve line-cubic intersection by
representing the cubic as:
x = a(1-t)^3 + 2b(1-t)^2t + c(1-t)t^2 + dt^3
y = e(1-t)^3 + 2f(1-t)^2t + g(1-t)t^2 + ht^3
and the line as:
y = i*x + j (if the line is more horizontal)
or:
x = i*y + j (if the line is more vertical)
Then using Mathematica, solve for the values of t where the cubic intersects the
line:
(in) Resultant[
a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - x,
e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - i*x - j, x]
(out) -e + j +
3 e t - 3 f t -
3 e t^2 + 6 f t^2 - 3 g t^2 +
e t^3 - 3 f t^3 + 3 g t^3 - h t^3 +
i ( a -
3 a t + 3 b t +
3 a t^2 - 6 b t^2 + 3 c t^2 -
a t^3 + 3 b t^3 - 3 c t^3 + d t^3 )
if i goes to infinity, we can rewrite the line in terms of x. Mathematica:
(in) Resultant[
a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - i*y - j,
e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - y, y]
(out) a - j -
3 a t + 3 b t +
3 a t^2 - 6 b t^2 + 3 c t^2 -
a t^3 + 3 b t^3 - 3 c t^3 + d t^3 -
i ( e -
3 e t + 3 f t +
3 e t^2 - 6 f t^2 + 3 g t^2 -
e t^3 + 3 f t^3 - 3 g t^3 + h t^3 )
Solving this with Mathematica produces an expression with hundreds of terms;
instead, use Numeric Solutions recipe to solve the cubic.
The near-horizontal case, in terms of: Ax^3 + Bx^2 + Cx + D == 0
A = (-(-e + 3*f - 3*g + h) + i*(-a + 3*b - 3*c + d) )
B = 3*(-( e - 2*f + g ) + i*( a - 2*b + c ) )
C = 3*(-(-e + f ) + i*(-a + b ) )
D = (-( e ) + i*( a ) + j )
The near-vertical case, in terms of: Ax^3 + Bx^2 + Cx + D == 0
A = ( (-a + 3*b - 3*c + d) - i*(-e + 3*f - 3*g + h) )
B = 3*( ( a - 2*b + c ) - i*( e - 2*f + g ) )
C = 3*( (-a + b ) - i*(-e + f ) )
D = ( ( a ) - i*( e ) - j )
For horizontal lines:
(in) Resultant[
a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - j,
e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - y, y]
(out) e - j -
3 e t + 3 f t +
3 e t^2 - 6 f t^2 + 3 g t^2 -
e t^3 + 3 f t^3 - 3 g t^3 + h t^3
|
17023 |
| SkDCubicToQuads.cpp |
http://stackoverflow.com/questions/2009160/how-do-i-convert-the-2-control-points-of-a-cubic-curve-to-the-single-control-poi
|
1397 |
| SkDLineIntersection.cpp |
Slopes match when denom goes to zero:
axLen / ayLen == bxLen / byLen
(ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
byLen * axLen == ayLen * bxLen
byLen * axLen - ayLen * bxLen == 0 ( == denom )
|
12606 |
| SkDQuadLineIntersection.cpp |
Find the intersection of a line and quadratic by solving for valid t values.
From http://stackoverflow.com/questions/1853637/how-to-find-the-mathematical-function-defining-a-bezier-curve
"A Bezier curve is a parametric function. A quadratic Bezier curve (i.e. three
control points) can be expressed as: F(t) = A(1 - t)^2 + B(1 - t)t + Ct^2 where
A, B and C are points and t goes from zero to one.
This will give you two equations:
x = a(1 - t)^2 + b(1 - t)t + ct^2
y = d(1 - t)^2 + e(1 - t)t + ft^2
If you add for instance the line equation (y = kx + m) to that, you'll end up
with three equations and three unknowns (x, y and t)."
Similar to above, the quadratic is represented as
x = a(1-t)^2 + 2b(1-t)t + ct^2
y = d(1-t)^2 + 2e(1-t)t + ft^2
and the line as
y = g*x + h
Using Mathematica, solve for the values of t where the quadratic intersects the
line:
(in) t1 = Resultant[a*(1 - t)^2 + 2*b*(1 - t)*t + c*t^2 - x,
d*(1 - t)^2 + 2*e*(1 - t)*t + f*t^2 - g*x - h, x]
(out) -d + h + 2 d t - 2 e t - d t^2 + 2 e t^2 - f t^2 +
g (a - 2 a t + 2 b t + a t^2 - 2 b t^2 + c t^2)
(in) Solve[t1 == 0, t]
(out) {
{t -> (-2 d + 2 e + 2 a g - 2 b g -
Sqrt[(2 d - 2 e - 2 a g + 2 b g)^2 -
4 (-d + 2 e - f + a g - 2 b g + c g) (-d + a g + h)]) /
(2 (-d + 2 e - f + a g - 2 b g + c g))
},
{t -> (-2 d + 2 e + 2 a g - 2 b g +
Sqrt[(2 d - 2 e - 2 a g + 2 b g)^2 -
4 (-d + 2 e - f + a g - 2 b g + c g) (-d + a g + h)]) /
(2 (-d + 2 e - f + a g - 2 b g + c g))
}
}
Using the results above (when the line tends towards horizontal)
A = (-(d - 2*e + f) + g*(a - 2*b + c) )
B = 2*( (d - e ) - g*(a - b ) )
C = (-(d ) + g*(a ) + h )
If g goes to infinity, we can rewrite the line in terms of x.
x = g'*y + h'
And solve accordingly in Mathematica:
(in) t2 = Resultant[a*(1 - t)^2 + 2*b*(1 - t)*t + c*t^2 - g'*y - h',
d*(1 - t)^2 + 2*e*(1 - t)*t + f*t^2 - y, y]
(out) a - h' - 2 a t + 2 b t + a t^2 - 2 b t^2 + c t^2 -
g' (d - 2 d t + 2 e t + d t^2 - 2 e t^2 + f t^2)
(in) Solve[t2 == 0, t]
(out) {
{t -> (2 a - 2 b - 2 d g' + 2 e g' -
Sqrt[(-2 a + 2 b + 2 d g' - 2 e g')^2 -
4 (a - 2 b + c - d g' + 2 e g' - f g') (a - d g' - h')]) /
(2 (a - 2 b + c - d g' + 2 e g' - f g'))
},
{t -> (2 a - 2 b - 2 d g' + 2 e g' +
Sqrt[(-2 a + 2 b + 2 d g' - 2 e g')^2 -
4 (a - 2 b + c - d g' + 2 e g' - f g') (a - d g' - h')])/
(2 (a - 2 b + c - d g' + 2 e g' - f g'))
}
}
Thus, if the slope of the line tends towards vertical, we use:
A = ( (a - 2*b + c) - g'*(d - 2*e + f) )
B = 2*(-(a - b ) + g'*(d - e ) )
C = ( (a ) - g'*(d ) - h' )
|
17082 |
| SkIntersectionHelper.h |
|
2383 |
| SkIntersections.cpp |
|
5962 |
| SkIntersections.h |
|
11125 |
| SkLineParameters.h |
|
5389 |
| SkOpAngle.cpp |
Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest
positive y. The largest angle has a positive x and a zero y. |
44190 |
| SkOpAngle.h |
|
4310 |
| SkOpBuilder.cpp |
OPTIMIZATION: Union doesn't need to be all-or-nothing. A run of three or more convex
paths with union ops could be locally resolved and still improve over doing the
ops one at a time. |
6865 |
| SkOpCoincidence.cpp |
Please keep this in sync with debugCorrectEnds |
55802 |
| SkOpCoincidence.h |
|
12145 |
| SkOpContour.cpp |
|
3196 |
| SkOpContour.h |
|
11840 |
| SkOpCubicHull.cpp |
Given a cubic, find the convex hull described by the end and control points.
The hull may have 3 or 4 points. Cubics that degenerate into a point or line
are not considered.
The hull is computed by assuming that three points, if unique and non-linear,
form a triangle. The fourth point may replace one of the first three, may be
discarded if in the triangle or on an edge, or may be inserted between any of
the three to form a convex quadralateral.
The indices returned in order describe the convex hull.
|
5595 |
| SkOpEdgeBuilder.cpp |
|
14737 |
| SkOpEdgeBuilder.h |
|
2155 |
| SkOpSegment.cpp |
After computing raw intersections, post process all segments to:
- find small collections of points that can be collapsed to a single point
- find missing intersections to resolve differences caused by different algorithms
Consider segments containing tiny or small intervals. Consider coincident segments
because coincidence finds intersections through distance measurement that non-coincident
intersection tests cannot.
|
63835 |
| SkOpSegment.h |
|
15497 |
| SkOpSpan.cpp |
|
14806 |
| SkOpSpan.h |
|
15717 |
| SkPathOpsAsWinding.cpp |
|
16076 |
| SkPathOpsBounds.h |
|
2225 |
| SkPathOpsCommon.cpp |
|
11534 |
| SkPathOpsCommon.h |
|
1159 |
| SkPathOpsConic.cpp |
see quad subdivide for point rationale |
6183 |
| SkPathOpsConic.h |
|
6357 |
| SkPathOpsCubic.cpp |
classic one t subdivision |
27268 |
| SkPathOpsCubic.h |
Return the number of valid roots (0 < root < 1) for this cubic intersecting the
specified horizontal line.
|
8725 |
| SkPathOpsCurve.cpp |
|
5403 |
| SkPathOpsCurve.h |
|
12369 |
| SkPathOpsDebug.cpp |
|
115123 |
| SkPathOpsDebug.h |
|
14883 |
| SkPathOpsLine.cpp |
|
5400 |
| SkPathOpsLine.h |
|
1288 |
| SkPathOpsOp.cpp |
|
14574 |
| SkPathOpsPoint.h |
|
8735 |
| SkPathOpsQuad.cpp |
started with at_most_end_pts_in_common from SkDQuadIntersection.cpp |
13491 |
| SkPathOpsQuad.h |
Return the number of valid roots (0 < root < 1) for this cubic intersecting the
specified horizontal line.
|
6720 |
| SkPathOpsRect.cpp |
|
2026 |
| SkPathOpsRect.h |
|
2091 |
| SkPathOpsSimplify.cpp |
|
10357 |
| SkPathOpsTCurve.h |
|
1645 |
| SkPathOpsTightBounds.cpp |
|
3002 |
| SkPathOpsTSect.cpp |
|
70342 |
| SkPathOpsTSect.h |
|
10033 |
| SkPathOpsTypes.cpp |
|
7429 |
| SkPathOpsTypes.h |
|
16729 |
| SkPathOpsWinding.cpp |
|
14464 |
| SkPathWriter.cpp |
|
14208 |
| SkPathWriter.h |
defined(__PathOps__SkPathWriter__) |
1983 |
| SkReduceOrder.cpp |
|
9278 |
| SkReduceOrder.h |
|
907 |