it. i.e., find the highest parametric edge where: // // parametricEdgeID + floor(numRadialSegmentsAtParametricT) <= combinedEdgeID // float lastParametricEdgeID = 0.0; float maxParametricEdgeID = min(numParametricSegments - 1.0, combinedEdgeID); float negAbsRadsPerSegment = -abs(radsPerSegment); float maxRotation0 = (1.0 + combinedEdgeID) * abs(radsPerSegment); for (int exp = %i - 1; exp >= 0; --exp) { // Test the parametric edge at lastParametricEdgeID + 2^exp. float testParametricID = lastParametricEdgeID + exp2(float(exp)); if (testParametricID <= maxParametricEdgeID) { float2 testTan = fma(float2(testParametricID), A, B_); testTan = fma(float2(testParametricID), testTan, C_); float cosRotation = dot(normalize(testTan), tan0); float maxRotation = fma(testParametricID, negAbsRadsPerSegment, maxRotation0); maxRotation = min(maxRotation, PI); // Is rotation <= maxRotation? (i.e., is the number of complete radial segments // behind testT, + testParametricID <= combinedEdgeID?) if (cosRotation >= cos(maxRotation)) { // testParametricID is on or before the combinedEdgeID. Keep it! lastParametricEdgeID = testParametricID; } } } // Find the T value of the parametric edge at lastParametricEdgeID. float parametricT = lastParametricEdgeID / numParametricSegments; // Now that we've identified the highest parametric edge on or before the // combinedEdgeID, the highest radial edge is easy: float lastRadialEdgeID = combinedEdgeID - lastParametricEdgeID; // Find the angle of tan0, i.e. the angle between tan0 and the positive x axis. float angle0 = acos(clamp(tan0.x, -1.0, 1.0)); angle0 = tan0.y >= 0.0 ? angle0 : -angle0; // Find the tangent vector on the edge at lastRadialEdgeID. By construction it is already // normalized. float radialAngle = fma(lastRadialEdgeID, radsPerSegment, angle0); tangent = float2(cos(radialAngle), sin(radialAngle)); float2 norm = float2(-tangent.y, tangent.x); // Find the T value where the tangent is orthogonal to norm. This is a quadratic: // // dot(norm, Tangent_Direction(T)) == 0 // // |T^2| // norm * |A 2B C| * |T | == 0 // |. . .| |1 | // float a=dot(norm,A), b_over_2=dot(norm,B), c=dot(norm,C); float discr_over_4 = max(b_over_2*b_over_2 - a*c, 0.0); float q = sqrt(discr_over_4); if (b_over_2 > 0.0) { q = -q; } q -= b_over_2; // Roots are q/a and c/q. Since each curve section does not inflect or rotate more than 180 // degrees, there can only be one tangent orthogonal to "norm" inside 0..1. Pick the root // nearest .5. float _5qa = -.5*q*a; float2 root = (abs(fma(q,q,_5qa)) < abs(fma(a,c,_5qa))) ? float2(q,a) : float2(c,q); float radialT = (root.t != 0.0) ? root.s / root.t : 0.0; radialT = clamp(radialT, 0.0, 1.0); if (lastRadialEdgeID == 0.0) { // The root finder above can become unstable when lastRadialEdgeID == 0 (e.g., if // there are roots at exatly 0 and 1 both). radialT should always == 0 in this case. radialT = 0.0; } // Now that we've identified the T values of the last parametric and radial edges, our final // T value for combinedEdgeID is whichever is larger. float T = max(parametricT, radialT); // Evaluate the cubic at T. Use De Casteljau's for its accuracy and stability. float2 ab = unchecked_mix(p0, p1, T); float2 bc = unchecked_mix(p1, p2, T); float2 cd = unchecked_mix(p2, p3, T); float2 abc = unchecked_mix(ab, bc, T); float2 bcd = unchecked_mix(bc, cd, T); float2 abcd = unchecked_mix(abc, bcd, T); // Evaluate the conic weight at T. float u = unchecked_mix(1.0, w, T); float v = w + 1 - u; // == mix(w, 1, T) float uv = unchecked_mix(u, v, T); // If we went with T=parametricT, then update the tangent. Otherwise leave it at the radial // tangent found previously. (In the event that parametricT == radialT, we keep the radial // tangent.) if (T != radialT) { // We must re-normalize here because the tangent is determined by the curve coefficients tangent = w >= 0.0 ? robust_normalize_diff(bc*u, ab*v) : robust_normalize_diff(bcd, abc); } strokeCoord = (w >= 0.0) ? abc/uv : abcd; } else { // Edges at the beginning and end of the strip use exact endpoints and tangents. This // ensures crack-free seaming between instances. tangent = (combinedEdgeID == 0) ? tan0 : tan1; strokeCoord = (combinedEdgeID == 0) ? p0 : p3; }