1/* 2 * Copyright 2006 The Android Open Source Project 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 9#include "SkBlurMask.h" 10#include "SkMaskBlurFilter.h" 11#include "SkMath.h" 12#include "SkTemplates.h" 13#include "SkEndian.h" 14 15 16// This constant approximates the scaling done in the software path's 17// "high quality" mode, in SkBlurMask::Blur() (1 / sqrt(3)). 18// IMHO, it actually should be 1: we blur "less" than we should do 19// according to the CSS and canvas specs, simply because Safari does the same. 20// Firefox used to do the same too, until 4.0 where they fixed it. So at some 21// point we should probably get rid of these scaling constants and rebaseline 22// all the blur tests. 23static const SkScalar kBLUR_SIGMA_SCALE = 0.57735f; 24 25SkScalar SkBlurMask::ConvertRadiusToSigma(SkScalar radius) { 26 return radius > 0 ? kBLUR_SIGMA_SCALE * radius + 0.5f : 0.0f; 27} 28 29SkScalar SkBlurMask::ConvertSigmaToRadius(SkScalar sigma) { 30 return sigma > 0.5f ? (sigma - 0.5f) / kBLUR_SIGMA_SCALE : 0.0f; 31} 32 33 34static void merge_src_with_blur(uint8_t dst[], int dstRB, 35 const uint8_t src[], int srcRB, 36 const uint8_t blur[], int blurRB, 37 int sw, int sh) { 38 dstRB -= sw; 39 srcRB -= sw; 40 blurRB -= sw; 41 while (--sh >= 0) { 42 for (int x = sw - 1; x >= 0; --x) { 43 *dst = SkToU8(SkAlphaMul(*blur, SkAlpha255To256(*src))); 44 dst += 1; 45 src += 1; 46 blur += 1; 47 } 48 dst += dstRB; 49 src += srcRB; 50 blur += blurRB; 51 } 52} 53 54static void clamp_with_orig(uint8_t dst[], int dstRowBytes, 55 const uint8_t src[], int srcRowBytes, 56 int sw, int sh, 57 SkBlurStyle style) { 58 int x; 59 while (--sh >= 0) { 60 switch (style) { 61 case kSolid_SkBlurStyle: 62 for (x = sw - 1; x >= 0; --x) { 63 int s = *src; 64 int d = *dst; 65 *dst = SkToU8(s + d - SkMulDiv255Round(s, d)); 66 dst += 1; 67 src += 1; 68 } 69 break; 70 case kOuter_SkBlurStyle: 71 for (x = sw - 1; x >= 0; --x) { 72 if (*src) { 73 *dst = SkToU8(SkAlphaMul(*dst, SkAlpha255To256(255 - *src))); 74 } 75 dst += 1; 76 src += 1; 77 } 78 break; 79 default: 80 SkDEBUGFAIL("Unexpected blur style here"); 81 break; 82 } 83 dst += dstRowBytes - sw; 84 src += srcRowBytes - sw; 85 } 86} 87 88/////////////////////////////////////////////////////////////////////////////// 89 90// we use a local function to wrap the class static method to work around 91// a bug in gcc98 92void SkMask_FreeImage(uint8_t* image); 93void SkMask_FreeImage(uint8_t* image) { 94 SkMask::FreeImage(image); 95} 96 97bool SkBlurMask::BoxBlur(SkMask* dst, const SkMask& src, 98 SkScalar sigma, SkBlurStyle style, SkBlurQuality quality, 99 SkIPoint* margin, bool force_quality) { 100 101 if (src.fFormat != SkMask::kA8_Format) { 102 return false; 103 } 104 105 SkIPoint border; 106 107 SkMaskBlurFilter blurFilter{sigma, sigma}; 108 if (blurFilter.hasNoBlur()) { 109 return false; 110 } 111 border = blurFilter.blur(src, dst); 112 // If src.fImage is null, then this call is only to calculate the border. 113 if (src.fImage != nullptr && dst->fImage == nullptr) { 114 return false; 115 } 116 117 if (src.fImage != nullptr) { 118 // if need be, alloc the "real" dst (same size as src) and copy/merge 119 // the blur into it (applying the src) 120 if (style == kInner_SkBlurStyle) { 121 // now we allocate the "real" dst, mirror the size of src 122 size_t srcSize = src.computeImageSize(); 123 if (0 == srcSize) { 124 return false; // too big to allocate, abort 125 } 126 auto blur = dst->fImage; 127 dst->fImage = SkMask::AllocImage(srcSize); 128 auto blurStart = &blur[border.x() + border.y() * dst->fRowBytes]; 129 merge_src_with_blur(dst->fImage, src.fRowBytes, 130 src.fImage, src.fRowBytes, 131 blurStart, 132 dst->fRowBytes, 133 src.fBounds.width(), src.fBounds.height()); 134 SkMask::FreeImage(blur); 135 } else if (style != kNormal_SkBlurStyle) { 136 auto dstStart = &dst->fImage[border.x() + border.y() * dst->fRowBytes]; 137 clamp_with_orig(dstStart, 138 dst->fRowBytes, src.fImage, src.fRowBytes, 139 src.fBounds.width(), src.fBounds.height(), style); 140 } 141 } 142 143 if (style == kInner_SkBlurStyle) { 144 dst->fBounds = src.fBounds; // restore trimmed bounds 145 dst->fRowBytes = src.fRowBytes; 146 } 147 148 if (margin != nullptr) { 149 *margin = border; 150 } 151 152 return true; 153} 154 155/* Convolving a box with itself three times results in a piecewise 156 quadratic function: 157 158 0 x <= -1.5 159 9/8 + 3/2 x + 1/2 x^2 -1.5 < x <= -.5 160 3/4 - x^2 -.5 < x <= .5 161 9/8 - 3/2 x + 1/2 x^2 0.5 < x <= 1.5 162 0 1.5 < x 163 164 Mathematica: 165 166 g[x_] := Piecewise [ { 167 {9/8 + 3/2 x + 1/2 x^2 , -1.5 < x <= -.5}, 168 {3/4 - x^2 , -.5 < x <= .5}, 169 {9/8 - 3/2 x + 1/2 x^2 , 0.5 < x <= 1.5} 170 }, 0] 171 172 To get the profile curve of the blurred step function at the rectangle 173 edge, we evaluate the indefinite integral, which is piecewise cubic: 174 175 0 x <= -1.5 176 9/16 + 9/8 x + 3/4 x^2 + 1/6 x^3 -1.5 < x <= -0.5 177 1/2 + 3/4 x - 1/3 x^3 -.5 < x <= .5 178 7/16 + 9/8 x - 3/4 x^2 + 1/6 x^3 .5 < x <= 1.5 179 1 1.5 < x 180 181 in Mathematica code: 182 183 gi[x_] := Piecewise[ { 184 { 0 , x <= -1.5 }, 185 { 9/16 + 9/8 x + 3/4 x^2 + 1/6 x^3, -1.5 < x <= -0.5 }, 186 { 1/2 + 3/4 x - 1/3 x^3 , -.5 < x <= .5}, 187 { 7/16 + 9/8 x - 3/4 x^2 + 1/6 x^3, .5 < x <= 1.5} 188 },1] 189*/ 190 191static float gaussianIntegral(float x) { 192 if (x > 1.5f) { 193 return 0.0f; 194 } 195 if (x < -1.5f) { 196 return 1.0f; 197 } 198 199 float x2 = x*x; 200 float x3 = x2*x; 201 202 if ( x > 0.5f ) { 203 return 0.5625f - (x3 / 6.0f - 3.0f * x2 * 0.25f + 1.125f * x); 204 } 205 if ( x > -0.5f ) { 206 return 0.5f - (0.75f * x - x3 / 3.0f); 207 } 208 return 0.4375f + (-x3 / 6.0f - 3.0f * x2 * 0.25f - 1.125f * x); 209} 210 211/* ComputeBlurProfile allocates and fills in an array of floating 212 point values between 0 and 255 for the profile signature of 213 a blurred half-plane with the given blur radius. Since we're 214 going to be doing screened multiplications (i.e., 1 - (1-x)(1-y)) 215 all the time, we actually fill in the profile pre-inverted 216 (already done 255-x). 217 218 It's the responsibility of the caller to delete the 219 memory returned in profile_out. 220*/ 221 222uint8_t* SkBlurMask::ComputeBlurProfile(SkScalar sigma) { 223 int size = SkScalarCeilToInt(6*sigma); 224 225 int center = size >> 1; 226 uint8_t* profile = new uint8_t[size]; 227 228 float invr = 1.f/(2*sigma); 229 230 profile[0] = 255; 231 for (int x = 1 ; x < size ; ++x) { 232 float scaled_x = (center - x - .5f) * invr; 233 float gi = gaussianIntegral(scaled_x); 234 profile[x] = 255 - (uint8_t) (255.f * gi); 235 } 236 237 return profile; 238} 239 240// TODO MAYBE: Maintain a profile cache to avoid recomputing this for 241// commonly used radii. Consider baking some of the most common blur radii 242// directly in as static data? 243 244// Implementation adapted from Michael Herf's approach: 245// http://stereopsis.com/shadowrect/ 246 247uint8_t SkBlurMask::ProfileLookup(const uint8_t *profile, int loc, int blurred_width, int sharp_width) { 248 int dx = SkAbs32(((loc << 1) + 1) - blurred_width) - sharp_width; // how far are we from the original edge? 249 int ox = dx >> 1; 250 if (ox < 0) { 251 ox = 0; 252 } 253 254 return profile[ox]; 255} 256 257void SkBlurMask::ComputeBlurredScanline(uint8_t *pixels, const uint8_t *profile, 258 unsigned int width, SkScalar sigma) { 259 260 unsigned int profile_size = SkScalarCeilToInt(6*sigma); 261 SkAutoTMalloc<uint8_t> horizontalScanline(width); 262 263 unsigned int sw = width - profile_size; 264 // nearest odd number less than the profile size represents the center 265 // of the (2x scaled) profile 266 int center = ( profile_size & ~1 ) - 1; 267 268 int w = sw - center; 269 270 for (unsigned int x = 0 ; x < width ; ++x) { 271 if (profile_size <= sw) { 272 pixels[x] = ProfileLookup(profile, x, width, w); 273 } else { 274 float span = float(sw)/(2*sigma); 275 float giX = 1.5f - (x+.5f)/(2*sigma); 276 pixels[x] = (uint8_t) (255 * (gaussianIntegral(giX) - gaussianIntegral(giX + span))); 277 } 278 } 279} 280 281bool SkBlurMask::BlurRect(SkScalar sigma, SkMask *dst, 282 const SkRect &src, SkBlurStyle style, 283 SkIPoint *margin, SkMask::CreateMode createMode) { 284 int profile_size = SkScalarCeilToInt(6*sigma); 285 286 int pad = profile_size/2; 287 if (margin) { 288 margin->set( pad, pad ); 289 } 290 291 dst->fBounds.set(SkScalarRoundToInt(src.fLeft - pad), 292 SkScalarRoundToInt(src.fTop - pad), 293 SkScalarRoundToInt(src.fRight + pad), 294 SkScalarRoundToInt(src.fBottom + pad)); 295 296 dst->fRowBytes = dst->fBounds.width(); 297 dst->fFormat = SkMask::kA8_Format; 298 dst->fImage = nullptr; 299 300 int sw = SkScalarFloorToInt(src.width()); 301 int sh = SkScalarFloorToInt(src.height()); 302 303 if (createMode == SkMask::kJustComputeBounds_CreateMode) { 304 if (style == kInner_SkBlurStyle) { 305 dst->fBounds.set(SkScalarRoundToInt(src.fLeft), 306 SkScalarRoundToInt(src.fTop), 307 SkScalarRoundToInt(src.fRight), 308 SkScalarRoundToInt(src.fBottom)); // restore trimmed bounds 309 dst->fRowBytes = sw; 310 } 311 return true; 312 } 313 314 std::unique_ptr<uint8_t[]> profile(ComputeBlurProfile(sigma)); 315 316 size_t dstSize = dst->computeImageSize(); 317 if (0 == dstSize) { 318 return false; // too big to allocate, abort 319 } 320 321 uint8_t* dp = SkMask::AllocImage(dstSize); 322 323 dst->fImage = dp; 324 325 int dstHeight = dst->fBounds.height(); 326 int dstWidth = dst->fBounds.width(); 327 328 uint8_t *outptr = dp; 329 330 SkAutoTMalloc<uint8_t> horizontalScanline(dstWidth); 331 SkAutoTMalloc<uint8_t> verticalScanline(dstHeight); 332 333 ComputeBlurredScanline(horizontalScanline, profile.get(), dstWidth, sigma); 334 ComputeBlurredScanline(verticalScanline, profile.get(), dstHeight, sigma); 335 336 for (int y = 0 ; y < dstHeight ; ++y) { 337 for (int x = 0 ; x < dstWidth ; x++) { 338 unsigned int maskval = SkMulDiv255Round(horizontalScanline[x], verticalScanline[y]); 339 *(outptr++) = maskval; 340 } 341 } 342 343 if (style == kInner_SkBlurStyle) { 344 // now we allocate the "real" dst, mirror the size of src 345 size_t srcSize = (size_t)(src.width() * src.height()); 346 if (0 == srcSize) { 347 return false; // too big to allocate, abort 348 } 349 dst->fImage = SkMask::AllocImage(srcSize); 350 for (int y = 0 ; y < sh ; y++) { 351 uint8_t *blur_scanline = dp + (y+pad)*dstWidth + pad; 352 uint8_t *inner_scanline = dst->fImage + y*sw; 353 memcpy(inner_scanline, blur_scanline, sw); 354 } 355 SkMask::FreeImage(dp); 356 357 dst->fBounds.set(SkScalarRoundToInt(src.fLeft), 358 SkScalarRoundToInt(src.fTop), 359 SkScalarRoundToInt(src.fRight), 360 SkScalarRoundToInt(src.fBottom)); // restore trimmed bounds 361 dst->fRowBytes = sw; 362 363 } else if (style == kOuter_SkBlurStyle) { 364 for (int y = pad ; y < dstHeight-pad ; y++) { 365 uint8_t *dst_scanline = dp + y*dstWidth + pad; 366 memset(dst_scanline, 0, sw); 367 } 368 } else if (style == kSolid_SkBlurStyle) { 369 for (int y = pad ; y < dstHeight-pad ; y++) { 370 uint8_t *dst_scanline = dp + y*dstWidth + pad; 371 memset(dst_scanline, 0xff, sw); 372 } 373 } 374 // normal and solid styles are the same for analytic rect blurs, so don't 375 // need to handle solid specially. 376 377 return true; 378} 379 380bool SkBlurMask::BlurRRect(SkScalar sigma, SkMask *dst, 381 const SkRRect &src, SkBlurStyle style, 382 SkIPoint *margin, SkMask::CreateMode createMode) { 383 // Temporary for now -- always fail, should cause caller to fall back 384 // to old path. Plumbing just to land API and parallelize effort. 385 386 return false; 387} 388 389// The "simple" blur is a direct implementation of separable convolution with a discrete 390// gaussian kernel. It's "ground truth" in a sense; too slow to be used, but very 391// useful for correctness comparisons. 392 393bool SkBlurMask::BlurGroundTruth(SkScalar sigma, SkMask* dst, const SkMask& src, 394 SkBlurStyle style, SkIPoint* margin) { 395 396 if (src.fFormat != SkMask::kA8_Format) { 397 return false; 398 } 399 400 float variance = sigma * sigma; 401 402 int windowSize = SkScalarCeilToInt(sigma*6); 403 // round window size up to nearest odd number 404 windowSize |= 1; 405 406 SkAutoTMalloc<float> gaussWindow(windowSize); 407 408 int halfWindow = windowSize >> 1; 409 410 gaussWindow[halfWindow] = 1; 411 412 float windowSum = 1; 413 for (int x = 1 ; x <= halfWindow ; ++x) { 414 float gaussian = expf(-x*x / (2*variance)); 415 gaussWindow[halfWindow + x] = gaussWindow[halfWindow-x] = gaussian; 416 windowSum += 2*gaussian; 417 } 418 419 // leave the filter un-normalized for now; we will divide by the normalization 420 // sum later; 421 422 int pad = halfWindow; 423 if (margin) { 424 margin->set( pad, pad ); 425 } 426 427 dst->fBounds = src.fBounds; 428 dst->fBounds.outset(pad, pad); 429 430 dst->fRowBytes = dst->fBounds.width(); 431 dst->fFormat = SkMask::kA8_Format; 432 dst->fImage = nullptr; 433 434 if (src.fImage) { 435 436 size_t dstSize = dst->computeImageSize(); 437 if (0 == dstSize) { 438 return false; // too big to allocate, abort 439 } 440 441 int srcWidth = src.fBounds.width(); 442 int srcHeight = src.fBounds.height(); 443 int dstWidth = dst->fBounds.width(); 444 445 const uint8_t* srcPixels = src.fImage; 446 uint8_t* dstPixels = SkMask::AllocImage(dstSize); 447 SkAutoTCallVProc<uint8_t, SkMask_FreeImage> autoCall(dstPixels); 448 449 // do the actual blur. First, make a padded copy of the source. 450 // use double pad so we never have to check if we're outside anything 451 452 int padWidth = srcWidth + 4*pad; 453 int padHeight = srcHeight; 454 int padSize = padWidth * padHeight; 455 456 SkAutoTMalloc<uint8_t> padPixels(padSize); 457 memset(padPixels, 0, padSize); 458 459 for (int y = 0 ; y < srcHeight; ++y) { 460 uint8_t* padptr = padPixels + y * padWidth + 2*pad; 461 const uint8_t* srcptr = srcPixels + y * srcWidth; 462 memcpy(padptr, srcptr, srcWidth); 463 } 464 465 // blur in X, transposing the result into a temporary floating point buffer. 466 // also double-pad the intermediate result so that the second blur doesn't 467 // have to do extra conditionals. 468 469 int tmpWidth = padHeight + 4*pad; 470 int tmpHeight = padWidth - 2*pad; 471 int tmpSize = tmpWidth * tmpHeight; 472 473 SkAutoTMalloc<float> tmpImage(tmpSize); 474 memset(tmpImage, 0, tmpSize*sizeof(tmpImage[0])); 475 476 for (int y = 0 ; y < padHeight ; ++y) { 477 uint8_t *srcScanline = padPixels + y*padWidth; 478 for (int x = pad ; x < padWidth - pad ; ++x) { 479 float *outPixel = tmpImage + (x-pad)*tmpWidth + y + 2*pad; // transposed output 480 uint8_t *windowCenter = srcScanline + x; 481 for (int i = -pad ; i <= pad ; ++i) { 482 *outPixel += gaussWindow[pad+i]*windowCenter[i]; 483 } 484 *outPixel /= windowSum; 485 } 486 } 487 488 // blur in Y; now filling in the actual desired destination. We have to do 489 // the transpose again; these transposes guarantee that we read memory in 490 // linear order. 491 492 for (int y = 0 ; y < tmpHeight ; ++y) { 493 float *srcScanline = tmpImage + y*tmpWidth; 494 for (int x = pad ; x < tmpWidth - pad ; ++x) { 495 float *windowCenter = srcScanline + x; 496 float finalValue = 0; 497 for (int i = -pad ; i <= pad ; ++i) { 498 finalValue += gaussWindow[pad+i]*windowCenter[i]; 499 } 500 finalValue /= windowSum; 501 uint8_t *outPixel = dstPixels + (x-pad)*dstWidth + y; // transposed output 502 int integerPixel = int(finalValue + 0.5f); 503 *outPixel = SkClampMax( SkClampPos(integerPixel), 255 ); 504 } 505 } 506 507 dst->fImage = dstPixels; 508 // if need be, alloc the "real" dst (same size as src) and copy/merge 509 // the blur into it (applying the src) 510 if (style == kInner_SkBlurStyle) { 511 // now we allocate the "real" dst, mirror the size of src 512 size_t srcSize = src.computeImageSize(); 513 if (0 == srcSize) { 514 return false; // too big to allocate, abort 515 } 516 dst->fImage = SkMask::AllocImage(srcSize); 517 merge_src_with_blur(dst->fImage, src.fRowBytes, 518 srcPixels, src.fRowBytes, 519 dstPixels + pad*dst->fRowBytes + pad, 520 dst->fRowBytes, srcWidth, srcHeight); 521 SkMask::FreeImage(dstPixels); 522 } else if (style != kNormal_SkBlurStyle) { 523 clamp_with_orig(dstPixels + pad*dst->fRowBytes + pad, 524 dst->fRowBytes, srcPixels, src.fRowBytes, srcWidth, srcHeight, style); 525 } 526 (void)autoCall.release(); 527 } 528 529 if (style == kInner_SkBlurStyle) { 530 dst->fBounds = src.fBounds; // restore trimmed bounds 531 dst->fRowBytes = src.fRowBytes; 532 } 533 534 return true; 535} 536