OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2014 Google Inc. | 2 * Copyright 2014 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #include "SkPatchUtils.h" | 8 #include "SkPatchUtils.h" |
9 | 9 |
| 10 #include "SkColorPriv.h" |
| 11 #include "SkGeometry.h" |
| 12 |
| 13 /** |
| 14 * Evaluator to sample the values of a cubic bezier using forward differences. |
| 15 * Forward differences is a method for evaluating a nth degree polynomial at a u
niform step by only |
| 16 * adding precalculated values. |
| 17 * For a linear example we have the function f(t) = m*t+b, then the value of tha
t function at t+h |
| 18 * would be f(t+h) = m*(t+h)+b. If we want to know the uniform step that we must
add to the first |
| 19 * evaluation f(t) then we need to substract f(t+h) - f(t) = m*t + m*h + b - m*t
+ b = mh. After |
| 20 * obtaining this value (mh) we could just add this constant step to our first s
ampled point |
| 21 * to compute the next one. |
| 22 * |
| 23 * For the cubic case the first difference gives as a result a quadratic polynom
ial to which we can |
| 24 * apply again forward differences and get linear function to which we can apply
again forward |
| 25 * differences to get a constant difference. This is why we keep an array of siz
e 4, the 0th |
| 26 * position keeps the sampled value while the next ones keep the quadratic, line
ar and constant |
| 27 * difference values. |
| 28 */ |
| 29 |
| 30 class FwDCubicEvaluator { |
| 31 |
| 32 public: |
| 33 FwDCubicEvaluator() |
| 34 : fMax(0) |
| 35 , fCurrent(0) |
| 36 , fDivisions(0) { |
| 37 memset(fPoints, 0, 4 * sizeof(SkPoint)); |
| 38 memset(fPoints, 0, 4 * sizeof(SkPoint)); |
| 39 memset(fPoints, 0, 4 * sizeof(SkPoint)); |
| 40 } |
| 41 |
| 42 /** |
| 43 * Receives the 4 control points of the cubic bezier. |
| 44 */ |
| 45 FwDCubicEvaluator(SkPoint a, SkPoint b, SkPoint c, SkPoint d) { |
| 46 fPoints[0] = a; |
| 47 fPoints[1] = b; |
| 48 fPoints[2] = c; |
| 49 fPoints[3] = d; |
| 50 |
| 51 SkScalar cx[4], cy[4]; |
| 52 SkGetCubicCoeff(fPoints, cx, cy); |
| 53 fCoefs[0].set(cx[0], cy[0]); |
| 54 fCoefs[1].set(cx[1], cy[1]); |
| 55 fCoefs[2].set(cx[2], cy[2]); |
| 56 fCoefs[3].set(cx[3], cy[3]); |
| 57 |
| 58 this->restart(1); |
| 59 } |
| 60 |
| 61 explicit FwDCubicEvaluator(const SkPoint points[4]) { |
| 62 memcpy(fPoints, points, 4 * sizeof(SkPoint)); |
| 63 |
| 64 SkScalar cx[4], cy[4]; |
| 65 SkGetCubicCoeff(fPoints, cx, cy); |
| 66 fCoefs[0].set(cx[0], cy[0]); |
| 67 fCoefs[1].set(cx[1], cy[1]); |
| 68 fCoefs[2].set(cx[2], cy[2]); |
| 69 fCoefs[3].set(cx[3], cy[3]); |
| 70 |
| 71 this->restart(1); |
| 72 } |
| 73 |
| 74 /** |
| 75 * Restarts the forward differences evaluator to the first value of t = 0. |
| 76 */ |
| 77 void restart(int divisions) { |
| 78 fDivisions = divisions; |
| 79 SkScalar h = 1.f / fDivisions; |
| 80 fCurrent = 0; |
| 81 fMax = fDivisions + 1; |
| 82 fFwDiff[0] = fCoefs[3]; |
| 83 SkScalar h2 = h * h; |
| 84 SkScalar h3 = h2 * h; |
| 85 |
| 86 fFwDiff[3].set(6.f * fCoefs[0].x() * h3, 6.f * fCoefs[0].y() * h3); //6a
h^3 |
| 87 fFwDiff[2].set(fFwDiff[3].x() + 2.f * fCoefs[1].x() * h2, //6ah^3 + 2bh^
2 |
| 88 fFwDiff[3].y() + 2.f * fCoefs[1].y() * h2); |
| 89 fFwDiff[1].set(fCoefs[0].x() * h3 + fCoefs[1].x() * h2 + fCoefs[2].x() *
h,//ah^3 + bh^2 +ch |
| 90 fCoefs[0].y() * h3 + fCoefs[1].y() * h2 + fCoefs[2].y() *
h); |
| 91 } |
| 92 |
| 93 /** |
| 94 * Check if the evaluator is still within the range of 0<=t<=1 |
| 95 */ |
| 96 bool done() const { |
| 97 return fCurrent > fMax; |
| 98 } |
| 99 |
| 100 /** |
| 101 * Call next to obtain the SkPoint sampled and move to the next one. |
| 102 */ |
| 103 SkPoint next() { |
| 104 SkPoint point = fFwDiff[0]; |
| 105 fFwDiff[0] += fFwDiff[1]; |
| 106 fFwDiff[1] += fFwDiff[2]; |
| 107 fFwDiff[2] += fFwDiff[3]; |
| 108 fCurrent++; |
| 109 return point; |
| 110 } |
| 111 |
| 112 const SkPoint* getCtrlPoints() const { |
| 113 return fPoints; |
| 114 } |
| 115 |
| 116 private: |
| 117 int fMax, fCurrent, fDivisions; |
| 118 SkPoint fFwDiff[4], fCoefs[4], fPoints[4]; |
| 119 }; |
| 120 |
| 121 //////////////////////////////////////////////////////////////////////////////// |
| 122 |
10 // size in pixels of each partition per axis, adjust this knob | 123 // size in pixels of each partition per axis, adjust this knob |
11 static const int kPartitionSize = 15; | 124 static const int kPartitionSize = 10; |
12 | 125 |
13 /** | 126 /** |
14 * Calculate the approximate arc length given a bezier curve's control points. | 127 * Calculate the approximate arc length given a bezier curve's control points. |
15 */ | 128 */ |
16 static SkScalar approx_arc_length(SkPoint* points, int count) { | 129 static SkScalar approx_arc_length(SkPoint* points, int count) { |
17 if (count < 2) { | 130 if (count < 2) { |
18 return 0; | 131 return 0; |
19 } | 132 } |
20 SkScalar arcLength = 0; | 133 SkScalar arcLength = 0; |
21 for (int i = 0; i < count - 1; i++) { | 134 for (int i = 0; i < count - 1; i++) { |
22 arcLength += SkPoint::Distance(points[i], points[i + 1]); | 135 arcLength += SkPoint::Distance(points[i], points[i + 1]); |
23 } | 136 } |
24 return arcLength; | 137 return arcLength; |
25 } | 138 } |
26 | 139 |
27 SkISize SkPatchUtils::GetLevelOfDetail(const SkPatch& patch, const SkMatrix* mat
rix) { | 140 static SkScalar bilerp(SkScalar tx, SkScalar ty, SkScalar c00, SkScalar c10, SkS
calar c01, |
28 | 141 SkScalar c11) { |
29 SkPoint mapPts[12]; | 142 SkScalar a = c00 * (1.f - tx) + c10 * tx; |
30 matrix->mapPoints(mapPts, patch.getControlPoints(), 12); | 143 SkScalar b = c01 * (1.f - tx) + c11 * tx; |
| 144 return a * (1.f - ty) + b * ty; |
| 145 } |
| 146 |
| 147 SkISize SkPatchUtils::GetLevelOfDetail(const SkPoint cubics[12], const SkMatrix*
matrix) { |
31 | 148 |
32 // Approximate length of each cubic. | 149 // Approximate length of each cubic. |
33 SkPoint pts[4]; | 150 SkPoint pts[kNumPtsCubic]; |
34 patch.getTopPoints(pts); | 151 SkPatchUtils::getTopCubic(cubics, pts); |
35 matrix->mapPoints(pts, 4); | 152 matrix->mapPoints(pts, kNumPtsCubic); |
36 SkScalar topLength = approx_arc_length(pts, 4); | 153 SkScalar topLength = approx_arc_length(pts, kNumPtsCubic); |
37 | 154 |
38 patch.getBottomPoints(pts); | 155 SkPatchUtils::getBottomCubic(cubics, pts); |
39 matrix->mapPoints(pts, 4); | 156 matrix->mapPoints(pts, kNumPtsCubic); |
40 SkScalar bottomLength = approx_arc_length(pts, 4); | 157 SkScalar bottomLength = approx_arc_length(pts, kNumPtsCubic); |
41 | 158 |
42 patch.getLeftPoints(pts); | 159 SkPatchUtils::getLeftCubic(cubics, pts); |
43 matrix->mapPoints(pts, 4); | 160 matrix->mapPoints(pts, kNumPtsCubic); |
44 SkScalar leftLength = approx_arc_length(pts, 4); | 161 SkScalar leftLength = approx_arc_length(pts, kNumPtsCubic); |
45 | 162 |
46 patch.getRightPoints(pts); | 163 SkPatchUtils::getRightCubic(cubics, pts); |
47 matrix->mapPoints(pts, 4); | 164 matrix->mapPoints(pts, kNumPtsCubic); |
48 SkScalar rightLength = approx_arc_length(pts, 4); | 165 SkScalar rightLength = approx_arc_length(pts, kNumPtsCubic); |
49 | 166 |
50 // Level of detail per axis, based on the larger side between top and bottom
or left and right | 167 // Level of detail per axis, based on the larger side between top and bottom
or left and right |
51 int lodX = static_cast<int>(SkMaxScalar(topLength, bottomLength) / kPartitio
nSize); | 168 int lodX = static_cast<int>(SkMaxScalar(topLength, bottomLength) / kPartitio
nSize); |
52 int lodY = static_cast<int>(SkMaxScalar(leftLength, rightLength) / kPartitio
nSize); | 169 int lodY = static_cast<int>(SkMaxScalar(leftLength, rightLength) / kPartitio
nSize); |
53 | 170 |
54 return SkISize::Make(SkMax32(4, lodX), SkMax32(4, lodY)); | 171 return SkISize::Make(SkMax32(8, lodX), SkMax32(8, lodY)); |
55 } | 172 } |
| 173 |
| 174 void SkPatchUtils::getTopCubic(const SkPoint cubics[12], SkPoint points[4]) { |
| 175 points[0] = cubics[kTopP0_CubicCtrlPts]; |
| 176 points[1] = cubics[kTopP1_CubicCtrlPts]; |
| 177 points[2] = cubics[kTopP2_CubicCtrlPts]; |
| 178 points[3] = cubics[kTopP3_CubicCtrlPts]; |
| 179 } |
| 180 |
| 181 void SkPatchUtils::getBottomCubic(const SkPoint cubics[12], SkPoint points[4]) { |
| 182 points[0] = cubics[kBottomP0_CubicCtrlPts]; |
| 183 points[1] = cubics[kBottomP1_CubicCtrlPts]; |
| 184 points[2] = cubics[kBottomP2_CubicCtrlPts]; |
| 185 points[3] = cubics[kBottomP3_CubicCtrlPts]; |
| 186 } |
| 187 |
| 188 void SkPatchUtils::getLeftCubic(const SkPoint cubics[12], SkPoint points[4]) { |
| 189 points[0] = cubics[kLeftP0_CubicCtrlPts]; |
| 190 points[1] = cubics[kLeftP1_CubicCtrlPts]; |
| 191 points[2] = cubics[kLeftP2_CubicCtrlPts]; |
| 192 points[3] = cubics[kLeftP3_CubicCtrlPts]; |
| 193 } |
| 194 |
| 195 void SkPatchUtils::getRightCubic(const SkPoint cubics[12], SkPoint points[4]) { |
| 196 points[0] = cubics[kRightP0_CubicCtrlPts]; |
| 197 points[1] = cubics[kRightP1_CubicCtrlPts]; |
| 198 points[2] = cubics[kRightP2_CubicCtrlPts]; |
| 199 points[3] = cubics[kRightP3_CubicCtrlPts]; |
| 200 } |
| 201 |
| 202 bool SkPatchUtils::getVertexData(SkPatchUtils::VertexData* data, const SkPoint c
ubics[12], |
| 203 const SkColor colors[4], const SkPoint texCoords[4], int lodX
, int lodY) { |
| 204 if (lodX < 1 || lodY < 1 || NULL == cubics || NULL == data) { |
| 205 return false; |
| 206 } |
| 207 |
| 208 // number of indices is limited by size of uint16_t, so we clamp it to avoid
overflow |
| 209 data->fVertexCount = SkMin32((lodX + 1) * (lodY + 1), 65536); |
| 210 lodX = SkMin32(lodX, 255); |
| 211 lodY = SkMin32(lodY, 255); |
| 212 data->fIndexCount = lodX * lodY * 6; |
| 213 |
| 214 data->fPoints = SkNEW_ARRAY(SkPoint, data->fVertexCount); |
| 215 data->fIndices = SkNEW_ARRAY(uint16_t, data->fIndexCount); |
| 216 |
| 217 // if colors is not null then create array for colors |
| 218 SkPMColor colorsPM[kNumCorners]; |
| 219 if (NULL != colors) { |
| 220 // premultiply colors to avoid color bleeding. |
| 221 for (int i = 0; i < kNumCorners; i++) { |
| 222 colorsPM[i] = SkPreMultiplyColor(colors[i]); |
| 223 } |
| 224 data->fColors = SkNEW_ARRAY(uint32_t, data->fVertexCount); |
| 225 } |
| 226 |
| 227 // if texture coordinates are not null then create array for them |
| 228 if (NULL != texCoords) { |
| 229 data->fTexCoords = SkNEW_ARRAY(SkPoint, data->fVertexCount); |
| 230 } |
| 231 |
| 232 SkPoint pts[kNumPtsCubic]; |
| 233 SkPatchUtils::getBottomCubic(cubics, pts); |
| 234 FwDCubicEvaluator fBottom(pts); |
| 235 SkPatchUtils::getTopCubic(cubics, pts); |
| 236 FwDCubicEvaluator fTop(pts); |
| 237 SkPatchUtils::getLeftCubic(cubics, pts); |
| 238 FwDCubicEvaluator fLeft(pts); |
| 239 SkPatchUtils::getRightCubic(cubics, pts); |
| 240 FwDCubicEvaluator fRight(pts); |
| 241 |
| 242 fBottom.restart(lodX); |
| 243 fTop.restart(lodX); |
| 244 |
| 245 SkScalar u = 0.0f; |
| 246 int stride = lodY + 1; |
| 247 for (int x = 0; x <= lodX; x++) { |
| 248 SkPoint bottom = fBottom.next(), top = fTop.next(); |
| 249 fLeft.restart(lodY); |
| 250 fRight.restart(lodY); |
| 251 SkScalar v = 0.f; |
| 252 for (int y = 0; y <= lodY; y++) { |
| 253 int dataIndex = x * (lodY + 1) + y; |
| 254 |
| 255 SkPoint left = fLeft.next(), right = fRight.next(); |
| 256 |
| 257 SkPoint s0 = SkPoint::Make((1.0f - v) * top.x() + v * bottom.x(), |
| 258 (1.0f - v) * top.y() + v * bottom.y()); |
| 259 SkPoint s1 = SkPoint::Make((1.0f - u) * left.x() + u * right.x(), |
| 260 (1.0f - u) * left.y() + u * right.y()); |
| 261 SkPoint s2 = SkPoint::Make( |
| 262 (1.0f - v) * ((1.0f - u) * fTop.getCtrlPo
ints()[0].x() |
| 263 + u * fTop.getCtrlPoints()[
3].x()) |
| 264 + v * ((1.0f - u) * fBottom.getCtrlPoints
()[0].x() |
| 265 + u * fBottom.getCtrlPoints()[3].x
()), |
| 266 (1.0f - v) * ((1.0f - u) * fTop.getCtrlPo
ints()[0].y() |
| 267 + u * fTop.getCtrlPoints()[
3].y()) |
| 268 + v * ((1.0f - u) * fBottom.getCtrlPoints
()[0].y() |
| 269 + u * fBottom.getCtrlPoints()[3].y
())); |
| 270 data->fPoints[dataIndex] = s0 + s1 - s2; |
| 271 |
| 272 if (NULL != colors) { |
| 273 uint8_t a = uint8_t(bilerp(u, v, |
| 274 SkScalar(SkColorGetA(colorsPM[kTopLeft_Corner
])), |
| 275 SkScalar(SkColorGetA(colorsPM[kTopRight_Corne
r])), |
| 276 SkScalar(SkColorGetA(colorsPM[kBottomLeft_Cor
ner])), |
| 277 SkScalar(SkColorGetA(colorsPM[kBottomRight_Co
rner])))); |
| 278 uint8_t r = uint8_t(bilerp(u, v, |
| 279 SkScalar(SkColorGetR(colorsPM[kTopLeft_Corner
])), |
| 280 SkScalar(SkColorGetR(colorsPM[kTopRight_Corne
r])), |
| 281 SkScalar(SkColorGetR(colorsPM[kBottomLeft_Cor
ner])), |
| 282 SkScalar(SkColorGetR(colorsPM[kBottomRight_Co
rner])))); |
| 283 uint8_t g = uint8_t(bilerp(u, v, |
| 284 SkScalar(SkColorGetG(colorsPM[kTopLeft_Corner
])), |
| 285 SkScalar(SkColorGetG(colorsPM[kTopRight_Corne
r])), |
| 286 SkScalar(SkColorGetG(colorsPM[kBottomLeft_Cor
ner])), |
| 287 SkScalar(SkColorGetG(colorsPM[kBottomRight_Co
rner])))); |
| 288 uint8_t b = uint8_t(bilerp(u, v, |
| 289 SkScalar(SkColorGetB(colorsPM[kTopLeft_Corner
])), |
| 290 SkScalar(SkColorGetB(colorsPM[kTopRight_Corne
r])), |
| 291 SkScalar(SkColorGetB(colorsPM[kBottomLeft_Cor
ner])), |
| 292 SkScalar(SkColorGetB(colorsPM[kBottomRight_Co
rner])))); |
| 293 data->fColors[dataIndex] = SkPackARGB32(a,r,g,b); |
| 294 } |
| 295 |
| 296 if (NULL != texCoords) { |
| 297 data->fTexCoords[dataIndex] = SkPoint::Make( |
| 298 bilerp(u, v, texCoords[kTopLeft_Corn
er].x(), |
| 299 texCoords[kTopRight_Corner].x
(), |
| 300 texCoords[kBottomLeft_Corner]
.x(), |
| 301 texCoords[kBottomRight_Corner
].x()), |
| 302 bilerp(u, v, texCoords[kTopLeft_Corn
er].y(), |
| 303 texCoords[kTopRight_Corner].y
(), |
| 304 texCoords[kBottomLeft_Corner]
.y(), |
| 305 texCoords[kBottomRight_Corner
].y())); |
| 306 |
| 307 } |
| 308 |
| 309 if(x < lodX && y < lodY) { |
| 310 int i = 6 * (x * lodY + y); |
| 311 data->fIndices[i] = x * stride + y; |
| 312 data->fIndices[i + 1] = x * stride + 1 + y; |
| 313 data->fIndices[i + 2] = (x + 1) * stride + 1 + y; |
| 314 data->fIndices[i + 3] = data->fIndices[i]; |
| 315 data->fIndices[i + 4] = data->fIndices[i + 2]; |
| 316 data->fIndices[i + 5] = (x + 1) * stride + y; |
| 317 } |
| 318 v = SkScalarClampMax(v + 1.f / lodY, 1); |
| 319 } |
| 320 u = SkScalarClampMax(u + 1.f / lodX, 1); |
| 321 } |
| 322 return true; |
| 323 |
| 324 } |
OLD | NEW |