Google Git
Sign in
skia/skia/6a541bef31d1d03747e53fb2d6b750c82a43ff6e/./src/core/SkEdge.cpp
blob: 0329e810997b77c2c30f1de79313a57a9c28323a [file]
/*
* Copyright 2006 The Android Open Source Project
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "src/core/SkEdge.h"
#include "include/core/SkRect.h"
#include "include/private/SkDebug.h"
#include "include/private/SkSafe32.h"
#include "include/private/SkTo.h"
#include "src/core/SkFDot6.h"
#include "src/core/SkMathPriv.h"
#include <algorithm>
#include <utility>
/*
Note on Coordinate Formats and Antialiasing:
In setLine, setQuadratic, setCubic, the first thing we do is to convert the points
into FDot6. In some variants (such as SkAnalyticEdge), this conversion is modulated
by an external antialiasing/supersampling shift parameter (usually 0, or 2 for
antialiasing) which scales up the input coordinates.
In the float case, we turn the float into FDot6 by multiplying by 64 (or 256 for
antialiasing). This is implemented as 1 << (shift + 6).
In the fixed case, we turn the fixed (FDot16) into FDot6 by shifting right by 10
(or 8 for antialiasing). This is implemented as pt >> (10 - shift).
Do not confuse this external coordinate-scaling shift with the internal
variables used during curve subdivision and forward-differencing in quadratics
and cubics:
- 'stepExponent' (defines subdivision resolution N = 2^stepExponent)
- 'precisionUpScale' (scales coordinates up for precision during setup)
- 'toFixedShift' (realigns internal derivatives back to standard SkFixed)
*/
// Local type aliases to clarify different fixed-point formats.
//
// 1. SkFDot6Scaled: FDot6 coordinates that are shifted left (scaled up) by the
// precision upscale factor 'precisionUpScale' before evaluating the polynomial.
// This format has (6 + precisionUpScale) fractional bits.
//
// 2. SkFixedScaled: Derivatives stored at a scaled precision so they can be efficiently
// updated and then scaled down back to standard SkFixed (FDot16) inside the loop
// using 'toFixedShift'.
using SkFDot6Scaled = int32_t;
using SkFixedScaled = int32_t;
static inline SkFixed SkFDot6ToFixedDiv2(SkFDot6 value) {
// we want to return SkFDot6ToFixed(value >> 1), but we don't want to throw
// away data in value, so just perform a modify up-shift
return SkLeftShift(value, 16 - 6 - 1);
}
/////////////////////////////////////////////////////////////////////////
#if defined(SK_DEBUG)
void SkEdge::dump() const {
SkASSERT(fSegmentCount == 0);
SkDebugf("line edge: firstY:%d lastY:%d x:%g dx/dy:%g\n"
"\twinding:%d curveShift:%u\n",
fFirstY,
fLastY,
SkFixedToFloat(fX),
SkFixedToFloat(fDxDy),
static_cast<int8_t>(fWinding),
fCurveShift);
}
void SkQuadraticEdge::dump() const {
SkDebugf("quad edge; %u segment(s) left: firstY:%d lastY:%d x:%g dx/dy:%g\n"
"\tqx:%g qy:%g dqx:%g dqy:%g ddqx:%g ddqy:%g qLastX:%g qLastY:%g\n"
"\twinding:%d curveShift:%u\n",
fSegmentCount,
fFirstY,
fLastY,
SkFixedToFloat(fX),
SkFixedToFloat(fDxDy),
SkFixedToFloat(fQx),
SkFixedToFloat(fQy),
SkFixedToFloat(fQDxDt),
SkFixedToFloat(fQDyDt),
SkFixedToFloat(fQD2xDt2),
SkFixedToFloat(fQD2yDt2),
SkFixedToFloat(fQLastX),
SkFixedToFloat(fQLastY),
static_cast<int8_t>(fWinding),
fCurveShift);
}
void SkCubicEdge::dump() const {
SkDebugf("cube edge; %u segment(s) left: firstY:%d lastY:%d x:%g dx/dy:%g\n"
"qx:%g qy:%g dcx:%g dcy:%g ddcx:%g ddcy:%g dddcx:%g dddcy:%g cLastX:%g cLastY:%g\n"
"\twinding:%d curveShift:%u toFixedShift:%u\n",
fSegmentCount,
fFirstY,
fLastY,
SkFixedToFloat(fX),
SkFixedToFloat(fDxDy),
SkFixedToFloat(fCx),
SkFixedToFloat(fCy),
SkFixedToFloat(fCDxDt),
SkFixedToFloat(fCDyDt),
SkFixedToFloat(fCD2xDt2),
SkFixedToFloat(fCD2yDt2),
SkFixedToFloat(fCD3xDt3),
SkFixedToFloat(fCD3yDt3),
SkFixedToFloat(fCLastX),
SkFixedToFloat(fCLastY),
static_cast<int8_t>(fWinding),
fCurveShift,
fToFixedShift);
}
#endif
bool SkEdge::setLine(const SkPoint& p0, const SkPoint& p1, const SkIRect* clip) {
SkFDot6 x0, y0, x1, y1;
#ifdef SK_RASTERIZE_EVEN_ROUNDING
x0 = SkScalarRoundToFDot6(p0.fX, 0);
y0 = SkScalarRoundToFDot6(p0.fY, 0);
x1 = SkScalarRoundToFDot6(p1.fX, 0);
y1 = SkScalarRoundToFDot6(p1.fY, 0);
#else
x0 = SkFloatToFDot6(p0.fX);
y0 = SkFloatToFDot6(p0.fY);
x1 = SkFloatToFDot6(p1.fX);
y1 = SkFloatToFDot6(p1.fY);
#endif
Winding winding = Winding::kCW;
if (y0 > y1) {
std::swap(x0, x1);
std::swap(y0, y1);
winding = Winding::kCCW;
}
int top = SkFDot6Round(y0);
int bot = SkFDot6Round(y1);
// are we a zero-height line?
if (top == bot) {
return false;
}
// are we completely above or below the clip?
if (clip && (top >= clip->fBottom || bot <= clip->fTop)) {
return false;
}
SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
const SkFDot6 dy = SkEdge_Compute_DY(top, y0);
// Note that SkFixedMul(SkFixed, SkFDot6) produces results in SkFDot6
fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy));
fDxDy = slope;
fFirstY = top;
fLastY = bot - 1;
fEdgeType = Type::kLine;
fSegmentCount = 0;
fWinding = winding;
fCurveShift = 0;
if (clip) {
this->chopLineWithClip(*clip);
}
return true;
}
bool SkEdge::nextSegment() {
SkDEBUGFAILF("Shouldn't be asking a linear edge to go to the next curve.");
return false;
}
// Draws a line between the provided points and then calculates the slope and starting
// x value to line up with the closest pixel center. Updates the fields in the SkEdge
// base class appropriately. Returns false if this edge would start and stop in the
// same row.
bool SkEdge::updateLine(SkFixed xStart, SkFixed yStart, SkFixed xEnd, SkFixed yEnd) {
SkASSERT(fWinding == Winding::kCW || fWinding == Winding::kCCW);
SkASSERT(fSegmentCount != 0);
const SkFDot6 y0 = SkFixedToFDot6(yStart);
const SkFDot6 y1 = SkFixedToFDot6(yEnd);
SkASSERT(y0 <= y1);
const int top = SkFDot6Round(y0);
const int bot = SkFDot6Round(y1);
// are we a zero-height line?
if (top == bot) {
return false;
}
const SkFDot6 x0 = SkFixedToFDot6(xStart);
const SkFDot6 x1 = SkFixedToFDot6(xEnd);
SkFixed slope = SkFDot6Div(x1 - x0, y1 - y0);
const SkFDot6 dy = SkEdge_Compute_DY(top, y0);
// We could do this math in fixed point, but it would potentially require some
// rebaselining https://codereview.chromium.org/960353005/#msg6
// Note that SkFixedMul(SkFixed, SkFDot6) produces results in SkFDot6
fX = SkFDot6ToFixed(x0 + SkFixedMul(slope, dy));
fDxDy = slope;
fFirstY = top;
fLastY = bot - 1;
return true;
}
void SkEdge::chopLineWithClip(const SkIRect& clip)
{
int top = fFirstY;
SkASSERT(top < clip.fBottom);
// clip the line to the top
if (top < clip.fTop)
{
SkASSERT(fLastY >= clip.fTop);
fX += fDxDy * (clip.fTop - top);
fFirstY = clip.fTop;
}
}
///////////////////////////////////////////////////////////////////////////////
/* This limits the number of lines we use to approximate a curve.
If we need to increase this, we need to store fSegmentCount in a larger data type.
TODO(kjlubick): now that this is in an unsigned byte, we could go up to 7
*/
#define MAX_COEFF_SHIFT 6
// Approximate the distance from (0,0) to (dx, dy).
// When dx and dy are about the same
// sqrt(dx^2 + dy^2) => sqrt(2dx^2) => dx sqrt(2) = 1.41 * dx
// When dx >> dy
// sqrt(dx^2 + dy^2) => sqrt(dx^2) => dx
// So this is a reasonable approximation
static inline SkFDot6 cheap_distance(SkFDot6 dx, SkFDot6 dy) {
dx = SkAbs32(dx);
dy = SkAbs32(dy);
// return max + min/2
if (dx > dy) {
return dx + (dy / 2);
}
return dy + (dx / 2);
}
static inline int diff_to_steps(SkFDot6 dx, SkFDot6 dy, int accuracy) {
// cheap calc of distance from center of p0-p2 to the center of the curve
SkFDot6 dist = cheap_distance(dx, dy);
// shift down dist (it is currently in dot6)
// down by 3 should give us 1/8 pixel accuracy (assuming our dist is accurate...)
// this is chosen by heuristic: make it as big as possible (to minimize segments)
// ... but small enough so that our curves still look smooth
// When shift > 0, we're using AA and everything is scaled up so we can
// lower the accuracy.
// For cubics still, we have shift > 0. TODO(kjlubick) can we align cubics and quads?
dist = (dist + (1 << (2 + accuracy))) >> (3 + accuracy);
// each subdivision (shift value) cuts this dist (error) by 1/4
return (32 - SkCLZ(dist)) >> 1;
}
bool SkQuadraticEdge::setQuadratic(const SkPoint pts[3]) {
SkFDot6 x0, y0, x1, y1, x2, y2;
#if defined(SK_RASTERIZE_EVEN_ROUNDING)
x0 = SkScalarRoundToFDot6(pts[0].fX, 0);
y0 = SkScalarRoundToFDot6(pts[0].fY, 0);
x1 = SkScalarRoundToFDot6(pts[1].fX, 0);
y1 = SkScalarRoundToFDot6(pts[1].fY, 0);
x2 = SkScalarRoundToFDot6(pts[2].fX, 0);
y2 = SkScalarRoundToFDot6(pts[2].fY, 0);
#else
x0 = SkFloatToFDot6(pts[0].fX);
y0 = SkFloatToFDot6(pts[0].fY);
x1 = SkFloatToFDot6(pts[1].fX);
y1 = SkFloatToFDot6(pts[1].fY);
x2 = SkFloatToFDot6(pts[2].fX);
y2 = SkFloatToFDot6(pts[2].fY);
#endif
Winding winding = Winding::kCW;
if (y0 > y2) {
std::swap(x0, x2);
std::swap(y0, y2);
winding = Winding::kCCW;
}
SkASSERTF(y0 <= y1 && y1 <= y2, "curve must be monotonic");
const int top = SkFDot6Round(y0);
const int bot = SkFDot6Round(y2);
// are we a zero-height quad (line)?
if (top == bot) {
return false;
}
// compute number of steps needed (2^shift) based on the distance between
// this curve at the half-way point (t=0.5) and the midpoint of a straight
// line between p0 and p2.
// B(1/2) = p0 (1-t)^2 + 2 p1 t(1-t) + p2 t^2; t = 1/2
// = p0 (1/2)^2 + 2 p1 (1/2)(1/2) + p2 (1/2)^2
// = 1/4 (p0 + 2 p1 + p2)
// Midpoint of p0 and p2 is M(p0, p2) = (p2 + p0) / 2
// Subtracting the two terms to get the vector representing the difference
// distance = B(1/2) - M(p0, p2)
// = 1/4 (p0 + 2 p1 + p2) - (p2 + p0) / 2
// = 1/4 (p0 + 2 p1 + p2) - (2 p2 + 2 p0) / 4
// = 1/4 (-p0 + 2 p1 - p2)
SkFDot6 deltaX = (2*x1 - x0 - x2) >> 2;
SkFDot6 deltaY = (2*y1 - y0 - y2) >> 2;
// We pass those points into this function which will find the total distance
// and use a heuristic to reduce the error to some threshold.
int shift = diff_to_steps(deltaX, deltaY, 0);
SkASSERT(shift >= 0);
// We need at least 2 line segments for us to be able to save the derivatives as
// half their values to avoid overflow.
if (shift == 0) {
shift = 1;
} else if (shift > MAX_COEFF_SHIFT) {
shift = MAX_COEFF_SHIFT;
}
fWinding = winding;
fEdgeType = Type::kQuad;
fSegmentCount = SkToU8(1 << shift);
/*
* By re-arranging the Bezier curve in polynomial form, it is easier to
* find the derivatives and forward-differentiate from one segment to the next.
*
* p0 (1-t)^2 + 2 p1 t(1-t) + p2 t^2 ==> At^2 + Bt + C
*
* A = p0 - 2p1 + p2
* B = 2(p1 - p0)
* C = p0
*
* Our caller must have constrained our inputs (p0..p2) to all fit into
* 16.16. However, as seen above, we sometimes compute values that can be
* larger (e.g. B = 2*(p1 - p0)). To guard against overflow, we will store
* A and B at 1/2 of their actual value, and just apply a 2x scale during
* application in nextSegment(). Hence we store (shift - 1) in
* fCurveShift.
*/
fCurveShift = SkToU8(shift - 1);
// TODO(kjlubick): Can we use SkVx and calculate both X and Y at once?
// The extra 1/2 factor avoids overflow
SkFixed A_half = SkFDot6ToFixedDiv2(x0 - x1 - x1 + x2);
SkFixed B_half = SkFDot6ToFixed(x1 - x0);
// We want to calculate the slope at the midpoint of our first segment. This means evaluating
// dx/dt = 2A*t + B
// dx^2/dt^2 = 2A
// at t = 1/N * 1/2
// There's an extra 1/2 on the whole expression to avoid overflows (as above).
// 1/2 ( 2A*t + B) => 1/2 (2A*1/2N + B) => A/2*1/N + B/2 => A/2 * 1/2^shift + B/2
fQDxDt = B_half + (A_half >> shift);
// The second derivatives are constant, so we can pre-multiply them by 1/N to save having
// to do it in nextSegment(). Since A_half was already calculated we can use a smaller shift.
// 1/2 (2A * 1/N) => A * 1/N => A * 1/2^shift => A/2 * 1/2^(shift-1)
fQD2xDt2 = A_half >> (shift - 1);
A_half = SkFDot6ToFixedDiv2(y0 - y1 - y1 + y2);
B_half = SkFDot6ToFixed(y1 - y0);
fQDyDt = B_half + (A_half >> shift);
fQD2yDt2 = A_half >> (shift - 1);
fQx = SkFDot6ToFixed(x0);
fQy = SkFDot6ToFixed(y0);
fQLastX = SkFDot6ToFixed(x2);
fQLastY = SkFDot6ToFixed(y2);
return this->nextSegment();
}
bool SkQuadraticEdge::nextSegment() {
bool success;
int count = fSegmentCount;
SkFixed oldx = fQx;
SkFixed oldy = fQy;
SkFixed dx = fQDxDt;
SkFixed dy = fQDyDt;
SkFixed newx, newy;
int shift = fCurveShift;
SkASSERT(count > 0);
do {
if (--count > 0) {
newx = oldx + (dx >> shift);
dx += fQD2xDt2;
newy = oldy + (dy >> shift);
dy += fQD2yDt2;
}
else // last segment
{
newx = fQLastX;
newy = fQLastY;
}
success = this->updateLine(oldx, oldy, newx, newy);
oldx = newx;
oldy = newy;
} while (count > 0 && !success);
fQx = newx;
fQy = newy;
fQDxDt = dx;
fQDyDt = dy;
fSegmentCount = SkToU8(count);
return success;
}
/////////////////////////////////////////////////////////////////////////
static inline SkFDot6Scaled SkFDot6UpShift(SkFDot6 x, int upShift) {
SkASSERT((SkLeftShift(x, upShift) >> upShift) == x);
return SkLeftShift(x, upShift);
}
/* f(1/3) = (8a + 12b + 6c + d) / 27
f(2/3) = (a + 6b + 12c + 8d) / 27
f(1/3)-b = (8a - 15b + 6c + d) / 27
f(2/3)-c = (a + 6b - 15c + 8d) / 27
use 16/512 to approximate 1/27
*/
static SkFDot6 cubic_delta_from_line(SkFDot6 a, SkFDot6 b, SkFDot6 c, SkFDot6 d)
{
// since our parameters may be negative, we don't use << to avoid ASAN warnings
SkFDot6 oneThird = (a*8 - b*15 + 6*c + d) * 19 >> 9;
SkFDot6 twoThird = (a + 6*b - c*15 + d*8) * 19 >> 9;
return std::max(SkAbs32(oneThird), SkAbs32(twoThird));
}
bool SkCubicEdge::setCubic(const SkPoint pts[4]) {
SkFDot6 x0, y0, x1, y1, x2, y2, x3, y3;
#if defined(SK_RASTERIZE_EVEN_ROUNDING)
x0 = SkScalarRoundToFDot6(pts[0].fX, 0);
y0 = SkScalarRoundToFDot6(pts[0].fY, 0);
x1 = SkScalarRoundToFDot6(pts[1].fX, 0);
y1 = SkScalarRoundToFDot6(pts[1].fY, 0);
x2 = SkScalarRoundToFDot6(pts[2].fX, 0);
y2 = SkScalarRoundToFDot6(pts[2].fY, 0);
x3 = SkScalarRoundToFDot6(pts[3].fX, 0);
y3 = SkScalarRoundToFDot6(pts[3].fY, 0);
#else
x0 = SkFloatToFDot6(pts[0].fX);
y0 = SkFloatToFDot6(pts[0].fY);
x1 = SkFloatToFDot6(pts[1].fX);
y1 = SkFloatToFDot6(pts[1].fY);
x2 = SkFloatToFDot6(pts[2].fX);
y2 = SkFloatToFDot6(pts[2].fY);
x3 = SkFloatToFDot6(pts[3].fX);
y3 = SkFloatToFDot6(pts[3].fY);
#endif
Winding winding = Winding::kCW;
if (y0 > y3) {
std::swap(x0, x3);
std::swap(x1, x2);
std::swap(y0, y3);
std::swap(y1, y2);
winding = Winding::kCCW;
}
int top = SkFDot6Round(y0);
int bot = SkFDot6Round(y3);
// are we a zero-height cubic (line)?
if (top == bot) {
return false;
}
// compute number of steps needed (1 << stepExponent)
// Can't use (center of curve - center of baseline), since center-of-curve
// need not be the max delta from the baseline (it could even be coincident)
// so we try just looking at the two off-curve points
SkFDot6 dx = cubic_delta_from_line(x0, x1, x2, x3);
SkFDot6 dy = cubic_delta_from_line(y0, y1, y2, y3);
// add 1 (by observation)
int stepExponent = diff_to_steps(dx, dy, 2) + 1;
// need at least 1 subdivision for our bias trick
SkASSERT(stepExponent > 0);
if (stepExponent > MAX_COEFF_SHIFT) {
stepExponent = MAX_COEFF_SHIFT;
}
// To maintain maximum precision and avoid intermediate divisions, we manage
// three different "shifts" for the cubic forward-differencing math:
//
// 1. "stepExponent" (Subdivision Exponent):
// - The exponent for the number of segments: N = 2^stepExponent.
// - Parametric step size: h = 1/N = 2^-stepExponent.
// - Stored in fCurveShift. Used to update the first derivative step-to-step.
//
// 2. "precisionUpScale" (Precision Upscale Shift):
// - We scale up the incoming FDot6 coordinates by 2^precisionUpScale (via SkFDot6UpShift)
// before constructing our polynomial coefficients (A, B, C).
// - This prevents fractional bits from being shifted off and lost when dividing
// coefficients by powers of 2^stepExponent (i.e. >> stepExponent or >> 2*stepExponent)
// during setup.
// - Capped at 6 to prevent signed 32-bit integer overflow during intermediate
// computations (which involve multiplications by 3 and 6).
//
// 3. "toFixedShift" (Coordinate Realignment Downshift):
// - Stored in fToFixedShift. Used in nextSegment() to scale the step delta
// back down to standard SkFixed (FDot16) format.
// - Since the coefficients are scaled up by 2^precisionUpScale, the step size h is
// 2^-stepExponent, and standard SkFixed has 10 more fractional bits than
// FDot6 (16 - 6 = 10), the alignment factor for the position update (x + fCDxDt * h) is:
// 2^10 / (2^precisionUpScale * 2^stepExponent) =
// 1 / 2^(stepExponent + precisionUpScale - 10)
// which is implemented as a right-shift by:
// toFixedShift = stepExponent + precisionUpScale - 10.
// - If toFixedShift is negative (which would require an unsupported left-shift),
// we clamp toFixedShift to 0 and reduce precisionUpScale accordingly to
// 10 - stepExponent.
int precisionUpScale = 6; // largest safe value
int toFixedShift = stepExponent + precisionUpScale - 10;
if (toFixedShift < 0) {
toFixedShift = 0;
precisionUpScale = 10 - stepExponent;
}
fWinding = winding;
fEdgeType = Type::kCubic;
fSegmentCount = SkToU8(SkLeftShift(1, stepExponent));
fCurveShift = SkToU8(stepExponent);
fToFixedShift = SkToU8(toFixedShift);
// By re-arranging the Bezier curve in polynomial form, it is easier to
// find the derivatives and forward-differentiate from one segment to the next.
// p0 (1-t)^3 + 3 p1 t(1-t)^2 + 3 p2 t^2 (1-t) + p3 t^3 ==> At^3 + Bt^2 + Ct + D
// Where A = -p0 + 3p1 + -3p2 + p3
// B = 3p0 - 6p1 + 3p2
// C = -3p0 + 3p1
// D = p0
// TODO(kjlubick): Can we use SkVx and calculate both X and Y at once?
SkFDot6Scaled A_scaled = SkFDot6UpShift(x3 + 3 * (x1 - x2) - x0, precisionUpScale);
SkFDot6Scaled B_scaled = SkFDot6UpShift(3 * (x0 - 2*x1 + x2), precisionUpScale);
SkFDot6Scaled C_scaled = SkFDot6UpShift(3 * (x1 - x0), precisionUpScale);
// The cubic curve in polynomial form is: x(t) = A*t^3 + B*t^2 + C*t + D
// With a step size of h = 1/N = 1/(2^stepExponent), the forward differences at t=0 are:
// 1) First Difference: Δx(0) = x(h) - x(0) = A*h^3 + B*h^2 + C*h
// 2) Second Difference: Δ²x(0) = Δx(h) - Δx(0) = 6A*h^3 + 2B*h^2
// 3) Third Difference: Δ³x(0) = Δ²x(h) - Δ²x(0) = 6A*h^3
// To keep the math as precise as possible, we scale up each difference term.
// Because the step size h is a power of 2 (1 / 2^stepExponent), scaling them up
// allows us to perform all loop updates using bit-shifts instead of slow division:
// - fCDxDt = Δx(0) / h = A*h^2 + B*h + C
// = A*(1/2^stepExponent)*(1/2^stepExponent) + B*(1/2^stepExponent) + C
// = A/(1^(2*stepExponent) + B/(2^stepExponent) + C
// - fCD2xDt2 = Δ²x(0) / h² = 6A*h + 2B
// = 6A*(1/2^stepExponent) + 2B # cancel 2 on top and bottom of A
// = 3A/2^(stepExponent-1) + 2B
// - fCD3xDt3 = Δ³x(0) / h² = 6A*h
// = 6A*(1/2^stepExponent)
// = 3A/2^(stepExponent-1)
// These are stored in the edge struct as SkFixedScaled because they must be scaled down
// by toFixedShift or stepExponent (ddshift) before they can be added to standard SkFixed
// coordinates or used to update other derivative terms.
fCDxDt = (A_scaled >> 2*stepExponent) + (B_scaled >> stepExponent) + C_scaled;
fCD2xDt2 = (3*A_scaled >> (stepExponent - 1)) + 2*B_scaled;
fCD3xDt3 = 3*A_scaled >> (stepExponent - 1);
A_scaled = SkFDot6UpShift(y3 + 3 * (y1 - y2) - y0, precisionUpScale);
B_scaled = SkFDot6UpShift(3 * (y0 - 2*y1 + y2), precisionUpScale);
C_scaled = SkFDot6UpShift(3 * (y1 - y0), precisionUpScale);
fCDyDt = (A_scaled >> 2*stepExponent) + (B_scaled >> stepExponent) + C_scaled;
fCD2yDt2 = (3*A_scaled >> (stepExponent - 1)) + 2*B_scaled;
fCD3yDt3 = 3*A_scaled >> (stepExponent - 1);
fCx = SkFDot6ToFixed(x0);
fCy = SkFDot6ToFixed(y0);
fCLastX = SkFDot6ToFixed(x3);
fCLastY = SkFDot6ToFixed(y3);
return this->nextSegment();
}
bool SkCubicEdge::nextSegment() {
bool success;
int count = fSegmentCount;
SkFixed oldx = fCx;
SkFixed oldy = fCy;
SkFixed newx, newy;
const int stepExponent = fCurveShift; // Subdivision exponent (stepExponent)
const int toFixedShift = fToFixedShift;
SkASSERT(count > 0);
do {
if (--count > 0)
{
// 1. Position Update: x_next = x + (fCDxDt * h)
// Since fCDxDt has units of FDot6 scaled up by precisionUpScale, and is stored
// as (Δx / h) (which scales it up by 1/h = 2^stepExponent), we must:
// a) Divide by 2^stepExponent to multiply by step-size h
// b) Divide by 2^precisionUpScale to remove the precision upscaling
// c) Multiply by 2^10 to convert from FDot6 to SkFixed (since 16 - 6 = 10)
// Combining these: Δx = fCDxDt * (2^10) / (2^stepExponent * 2^precisionUpScale)
// = fCDxDt >> (stepExponent + precisionUpScale - 10)
// This is implemented as shifting right by toFixedShift.
newx = oldx + (fCDxDt >> toFixedShift);
// 2. First Difference Update: fCDxDt_next = fCDxDt + h * fCD2xDt2
// Since fCD2xDt2 has units of Δ²x / h², multiplying by h yields Δ²x / h.
// This is accomplished by right-shifting fCD2xDt2 by stepExponent
// (h = 1/2^stepExponent).
fCDxDt += fCD2xDt2 >> stepExponent;
// 3. Second Difference Update: fCD2xDt2_next = fCD2xDt2 + fCD3xDt3
// Since both fCD2xDt2 and fCD3xDt3 are scaled by 1/h², we add them directly.
fCD2xDt2 += fCD3xDt3;
newy = oldy + (fCDyDt >> toFixedShift);
fCDyDt += fCD2yDt2 >> stepExponent;
fCD2yDt2 += fCD3yDt3;
}
else // last segment
{
newx = fCLastX;
newy = fCLastY;
}
// we want to say SkASSERT(oldy <= newy), but our finite fixedpoint
// doesn't always achieve that, so we have to explicitly pin it here.
if (newy < oldy) {
newy = oldy;
}
success = this->updateLine(oldx, oldy, newx, newy);
oldx = newx;
oldy = newy;
} while (count > 0 && !success);
fCx = newx;
fCy = newy;
fSegmentCount = SkToU8(count);
return success;
}