| /* |
| * Copyright 2018 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| #include "src/gpu/tessellate/GrStrokePatchBuilder.h" |
| |
| #include "include/core/SkStrokeRec.h" |
| #include "include/private/SkFloatingPoint.h" |
| #include "include/private/SkNx.h" |
| #include "src/core/SkGeometry.h" |
| #include "src/core/SkMathPriv.h" |
| #include "src/core/SkPathPriv.h" |
| #include "src/gpu/tessellate/GrStrokeTessellateShader.h" |
| #include "src/gpu/tessellate/GrVectorXform.h" |
| #include "src/gpu/tessellate/GrWangsFormula.h" |
| |
| using Patch = GrStrokeTessellateShader::Patch; |
| |
| constexpr static float kDoubleSidedRoundJoinType = -Patch::kRoundJoinType; |
| |
| static SkPoint lerp(const SkPoint& a, const SkPoint& b, float T) { |
| SkASSERT(1 != T); // The below does not guarantee lerp(a, b, 1) === b. |
| return (b - a) * T + a; |
| } |
| |
| void GrStrokePatchBuilder::allocPatchChunkAtLeast(int minPatchAllocCount) { |
| PatchChunk* chunk = &fPatchChunkArray->push_back(); |
| fCurrChunkPatchData = (Patch*)fTarget->makeVertexSpaceAtLeast(sizeof(Patch), minPatchAllocCount, |
| minPatchAllocCount, |
| &chunk->fPatchBuffer, |
| &chunk->fBasePatch, |
| &fCurrChunkPatchCapacity); |
| fCurrChunkMinPatchAllocCount = minPatchAllocCount; |
| } |
| |
| Patch* GrStrokePatchBuilder::reservePatch() { |
| if (fPatchChunkArray->back().fPatchCount >= fCurrChunkPatchCapacity) { |
| // The current chunk is full. Time to allocate a new one. (And no need to put back vertices; |
| // the buffer is full.) |
| this->allocPatchChunkAtLeast(fCurrChunkMinPatchAllocCount * 2); |
| } |
| if (!fCurrChunkPatchData) { |
| SkDebugf("WARNING: Failed to allocate vertex buffer for tessellated stroke."); |
| return nullptr; |
| } |
| SkASSERT(fPatchChunkArray->back().fPatchCount <= fCurrChunkPatchCapacity); |
| Patch* patch = fCurrChunkPatchData + fPatchChunkArray->back().fPatchCount; |
| ++fPatchChunkArray->back().fPatchCount; |
| return patch; |
| } |
| |
| void GrStrokePatchBuilder::writeCubicSegment(float prevJoinType, const SkPoint pts[4], |
| float cubicType) { |
| SkPoint c1 = (pts[1] == pts[0]) ? pts[2] : pts[1]; |
| SkPoint c2 = (pts[2] == pts[3]) ? pts[1] : pts[2]; |
| |
| if (fHasPreviousSegment) { |
| this->writeJoin(prevJoinType, fLastControlPoint, pts[0], c1); |
| } else { |
| fCurrContourFirstControlPoint = c1; |
| fHasPreviousSegment = true; |
| } |
| |
| SkASSERT(cubicType == Patch::kStandardCubicType || cubicType == Patch::kFlatLineType); |
| if (Patch* patch = this->reservePatch()) { |
| memcpy(patch->fPts.data(), pts, sizeof(patch->fPts)); |
| patch->fPatchType = cubicType; |
| patch->fStrokeRadius = fCurrStrokeRadius; |
| } |
| |
| fLastControlPoint = c2; |
| fCurrentPoint = pts[3]; |
| } |
| |
| void GrStrokePatchBuilder::writeJoin(float joinType, const SkPoint& prevControlPoint, |
| const SkPoint& anchorPoint, const SkPoint& nextControlPoint) { |
| SkASSERT(SkScalarAbs(joinType) == Patch::kRoundJoinType || |
| SkScalarAbs(joinType) == Patch::kMiterJoinType || |
| SkScalarAbs(joinType) == Patch::kBevelJoinType); |
| if (Patch* joinPatch = this->reservePatch()) { |
| joinPatch->fPts = {{prevControlPoint, anchorPoint, anchorPoint, nextControlPoint}}; |
| joinPatch->fPatchType = joinType; |
| joinPatch->fStrokeRadius = fCurrStrokeRadius; |
| } |
| } |
| |
| void GrStrokePatchBuilder::writeSquareCap(const SkPoint& endPoint, const SkPoint& controlPoint) { |
| SkVector v = (endPoint - controlPoint); |
| v.normalize(); |
| SkPoint capPoint = endPoint + v*fCurrStrokeRadius; |
| // Add a join to guarantee we get water tight seaming. Make the join type negative so it's |
| // double sided. |
| this->writeJoin(-fCurrStrokeJoinType, controlPoint, endPoint, capPoint); |
| if (Patch* capPatch = this->reservePatch()) { |
| capPatch->fPts = {{endPoint, endPoint, capPoint, capPoint}}; |
| capPatch->fPatchType = Patch::kFlatLineType; |
| capPatch->fStrokeRadius = fCurrStrokeRadius; |
| } |
| } |
| |
| void GrStrokePatchBuilder::writeCaps(SkPaint::Cap capType) { |
| if (!fHasPreviousSegment) { |
| // We don't have any control points to orient the caps. In this case, square and round caps |
| // are specified to be drawn as an axis-aligned square or circle respectively. Assign |
| // default control points that achieve this. |
| fCurrContourFirstControlPoint = fCurrContourStartPoint - SkPoint{1,0}; |
| fLastControlPoint = fCurrContourStartPoint + SkPoint{1,0}; |
| fCurrentPoint = fCurrContourStartPoint; |
| } |
| |
| switch (capType) { |
| case SkPaint::kButt_Cap: |
| break; |
| case SkPaint::kRound_Cap: |
| // A round cap is the same thing as a 180-degree round join. |
| this->writeJoin(Patch::kRoundJoinType, fCurrContourFirstControlPoint, |
| fCurrContourStartPoint, fCurrContourFirstControlPoint); |
| this->writeJoin(Patch::kRoundJoinType, fLastControlPoint, fCurrentPoint, |
| fLastControlPoint); |
| break; |
| case SkPaint::kSquare_Cap: |
| this->writeSquareCap(fCurrContourStartPoint, fCurrContourFirstControlPoint); |
| this->writeSquareCap(fCurrentPoint, fLastControlPoint); |
| break; |
| } |
| } |
| |
| static float join_type_from_join(SkPaint::Join join) { |
| switch (join) { |
| case SkPaint::kBevel_Join: |
| return GrStrokeTessellateShader::Patch::kBevelJoinType; |
| case SkPaint::kMiter_Join: |
| return GrStrokeTessellateShader::Patch::kMiterJoinType; |
| case SkPaint::kRound_Join: |
| return GrStrokeTessellateShader::Patch::kRoundJoinType; |
| } |
| SkUNREACHABLE; |
| } |
| |
| void GrStrokePatchBuilder::addPath(const SkPath& path, const SkStrokeRec& stroke) { |
| // We don't support hairline strokes. For now, the client can transform the path into device |
| // space and then use a stroke width of 1. |
| SkASSERT(stroke.getWidth() > 0); |
| |
| fCurrStrokeRadius = stroke.getWidth()/2; |
| fCurrStrokeJoinType = join_type_from_join(stroke.getJoin()); |
| |
| // This is the number of radial segments we need to add to a triangle strip for each radian of |
| // rotation, given the current stroke radius. Any fewer radial segments and our error would fall |
| // outside the linearization tolerance. |
| fNumRadialSegmentsPerRad = 1 / std::acos( |
| std::max(1 - 1 / (fLinearizationIntolerance * fCurrStrokeRadius), -1.f)); |
| |
| // Calculate the worst-case numbers of parametric segments our hardware can support for the |
| // current stroke radius, in the event that there are also enough radial segments to rotate 180 |
| // and 360 degrees respectively. These are used for "quick accepts" that allow us to send almost |
| // all curves directly to the hardware without having to chop or think any further. |
| fMaxParametricSegments180 = fMaxTessellationSegments + 1 - std::max(std::ceil( |
| SK_ScalarPI * fNumRadialSegmentsPerRad), 1.f); |
| fMaxParametricSegments360 = fMaxTessellationSegments + 1 - std::max(std::ceil( |
| 2*SK_ScalarPI * fNumRadialSegmentsPerRad), 1.f); |
| |
| fHasPreviousSegment = false; |
| SkPathVerb previousVerb = SkPathVerb::kClose; |
| for (auto [verb, pts, w] : SkPathPriv::Iterate(path)) { |
| switch (verb) { |
| case SkPathVerb::kMove: |
| // "A subpath ... consisting of a single moveto shall not be stroked." |
| // https://www.w3.org/TR/SVG11/painting.html#StrokeProperties |
| if (previousVerb != SkPathVerb::kMove && previousVerb != SkPathVerb::kClose) { |
| this->writeCaps(stroke.getCap()); |
| } |
| this->moveTo(pts[0]); |
| break; |
| case SkPathVerb::kClose: |
| this->close(stroke.getCap()); |
| break; |
| case SkPathVerb::kLine: |
| SkASSERT(previousVerb != SkPathVerb::kClose); |
| this->lineTo(fCurrStrokeJoinType, pts[0], pts[1]); |
| break; |
| case SkPathVerb::kQuad: |
| SkASSERT(previousVerb != SkPathVerb::kClose); |
| this->quadraticTo(fCurrStrokeJoinType, pts); |
| break; |
| case SkPathVerb::kCubic: |
| SkASSERT(previousVerb != SkPathVerb::kClose); |
| this->cubicTo(fCurrStrokeJoinType, pts); |
| break; |
| case SkPathVerb::kConic: |
| SkASSERT(previousVerb != SkPathVerb::kClose); |
| SkUNREACHABLE; |
| } |
| previousVerb = verb; |
| } |
| if (previousVerb != SkPathVerb::kMove && previousVerb != SkPathVerb::kClose) { |
| this->writeCaps(stroke.getCap()); |
| } |
| } |
| |
| void GrStrokePatchBuilder::moveTo(const SkPoint& pt) { |
| fHasPreviousSegment = false; |
| fCurrContourStartPoint = pt; |
| } |
| |
| void GrStrokePatchBuilder::lineTo(float prevJoinType, const SkPoint& p0, const SkPoint& p1) { |
| // Zero-length paths need special treatment because they are spec'd to behave differently. |
| if (p0 == p1) { |
| return; |
| } |
| |
| SkPoint cubic[4] = {p0, p0, p1, p1}; |
| this->writeCubicSegment(prevJoinType, cubic, Patch::kFlatLineType); |
| } |
| |
| void GrStrokePatchBuilder::quadraticTo(float prevJoinType, const SkPoint p[3], int maxDepth) { |
| // The stroker relies on p1 to find tangents at the endpoints. (We have to treat the endpoint |
| // tangents carefully in order to get water tight seams with the join segments.) If p1 is |
| // colocated on an endpoint then we need to draw this quadratic as a line instead. |
| if (p[1] == p[0] || p[1] == p[2]) { |
| this->lineTo(prevJoinType, p[0], p[2]); |
| return; |
| } |
| |
| // Ensure our hardware supports enough tessellation segments to render the curve. The first |
| // branch assumes a worst-case rotation of 180 degrees and checks if even then we have enough. |
| // In practice it is rare to take even the first branch. |
| float numParametricSegments = GrWangsFormula::quadratic(fLinearizationIntolerance, p); |
| if (numParametricSegments > fMaxParametricSegments180 && maxDepth != 0) { |
| // We still might have enough tessellation segments to render the curve. Check again with |
| // the actual rotation. |
| float numRadialSegments = SkMeasureQuadRotation(p) * fNumRadialSegmentsPerRad; |
| numRadialSegments = std::max(std::ceil(numRadialSegments), 1.f); |
| numParametricSegments = std::max(std::ceil(numParametricSegments), 1.f); |
| if (numParametricSegments + numRadialSegments - 1 > fMaxTessellationSegments) { |
| // The hardware doesn't support enough segments for this curve. Chop and recurse. |
| if (maxDepth < 0) { |
| // Decide on an extremely conservative upper bound for when to quit chopping. This |
| // is solely to protect us from infinite recursion in instances where FP error |
| // prevents us from chopping at the correct midtangent. |
| maxDepth = sk_float_nextlog2(numParametricSegments) + |
| sk_float_nextlog2(numRadialSegments) + 1; |
| SkASSERT(maxDepth >= 1); |
| } |
| SkPoint chopped[5]; |
| if (numParametricSegments >= numRadialSegments) { |
| SkChopQuadAtHalf(p, chopped); |
| } else { |
| SkChopQuadAtMidTangent(p, chopped); |
| } |
| this->quadraticTo(prevJoinType, chopped, maxDepth - 1); |
| // Use kDoubleSidedRoundJoinType in case we happened to chop at the exact turnaround |
| // point of a flat quadratic, in which case we would lose 180 degrees of rotation. |
| this->quadraticTo(kDoubleSidedRoundJoinType, chopped + 2, maxDepth - 1); |
| return; |
| } |
| } |
| |
| SkPoint cubic[4] = {p[0], lerp(p[0], p[1], 2/3.f), lerp(p[1], p[2], 1/3.f), p[2]}; |
| this->writeCubicSegment(prevJoinType, cubic, Patch::kStandardCubicType); |
| } |
| |
| void GrStrokePatchBuilder::cubicTo(float prevJoinType, const SkPoint p[4], int maxDepth, |
| bool mightInflect) { |
| // The stroker relies on p1 and p2 to find tangents at the endpoints. (We have to treat the |
| // endpoint tangents carefully in order to get water tight seams with the join segments.) If p0 |
| // and p1 are both colocated on an endpoint then we need to draw this cubic as a line instead. |
| if (p[1] == p[2] && (p[1] == p[0] || p[1] == p[3])) { |
| this->lineTo(prevJoinType, p[0], p[3]); |
| return; |
| } |
| |
| // Early-out if by conservative estimate we can ensure our hardware supports enough tessellation |
| // segments to render the curve. In practice we almost always take this branch. |
| float numParametricSegments = GrWangsFormula::cubic(fLinearizationIntolerance, p); |
| if (numParametricSegments <= fMaxParametricSegments360 || maxDepth == 0) { |
| this->writeCubicSegment(prevJoinType, p, Patch::kStandardCubicType); |
| return; |
| } |
| |
| // Ensure the curve does not inflect before we attempt to measure its rotation. |
| SkPoint chopped[10]; |
| if (mightInflect) { |
| float inflectT[2]; |
| if (int n = SkFindCubicInflections(p, inflectT)) { |
| SkChopCubicAt(p, chopped, inflectT, n); |
| for (int i = 0; i <= n; ++i) { |
| this->cubicTo(prevJoinType, chopped + i*3, maxDepth, false); |
| // Switch to kDoubleSidedRoundJoinType in case we happened to chop at an exact cusp |
| // or turnaround point of a flat cubic, in which case we would lose 180 degrees of |
| // rotation. |
| prevJoinType = kDoubleSidedRoundJoinType; |
| } |
| return; |
| } |
| } |
| |
| // We still might have enough tessellation segments to render the curve. Check again with |
| // its actual rotation. |
| float numRadialSegments = SkMeasureNonInflectCubicRotation(p) * fNumRadialSegmentsPerRad; |
| numRadialSegments = std::max(std::ceil(numRadialSegments), 1.f); |
| numParametricSegments = std::max(std::ceil(numParametricSegments), 1.f); |
| if (numParametricSegments + numRadialSegments - 1 <= fMaxTessellationSegments) { |
| this->writeCubicSegment(prevJoinType, p, Patch::kStandardCubicType); |
| return; |
| } |
| |
| // The hardware doesn't support enough segments to tessellate this curve. Chop and recurse. |
| if (numParametricSegments >= numRadialSegments) { |
| SkChopCubicAtHalf(p, chopped); |
| } else { |
| SkChopCubicAtMidTangent(p, chopped); |
| } |
| |
| if (maxDepth < 0) { |
| // Decide on an extremely conservative upper bound for when to quit chopping. This |
| // is solely to protect us from infinite recursion in instances where FP error |
| // prevents us from chopping at the correct midtangent. |
| maxDepth = sk_float_nextlog2(numParametricSegments) + |
| sk_float_nextlog2(numRadialSegments) + 1; |
| SkASSERT(maxDepth >= 1); |
| } |
| |
| this->cubicTo(prevJoinType, chopped, maxDepth - 1, false); |
| // Use kDoubleSidedRoundJoinType in case we happened to chop at an exact cusp or |
| // turnaround point of a flat cubic, in which case we would lose 180 degrees of |
| // rotation. |
| this->cubicTo(kDoubleSidedRoundJoinType, chopped + 3, maxDepth - 1, false); |
| } |
| |
| void GrStrokePatchBuilder::close(SkPaint::Cap capType) { |
| if (!fHasPreviousSegment) { |
| // Draw caps instead of closing if the subpath is zero length: |
| // |
| // "Any zero length subpath ... shall be stroked if the 'stroke-linecap' property has a |
| // value of round or square producing respectively a circle or a square." |
| // |
| // (https://www.w3.org/TR/SVG11/painting.html#StrokeProperties) |
| // |
| this->writeCaps(capType); |
| return; |
| } |
| |
| // Draw a line back to the beginning. (This will be discarded if |
| // fCurrentPoint == fCurrContourStartPoint.) |
| this->lineTo(fCurrStrokeJoinType, fCurrentPoint, fCurrContourStartPoint); |
| this->writeJoin(fCurrStrokeJoinType, fLastControlPoint, fCurrContourStartPoint, |
| fCurrContourFirstControlPoint); |
| } |
