SkDistanceFieldGen.cpp 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562
  1. /*
  2. * Copyright 2014 Google Inc.
  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. #include "include/private/SkColorData.h"
  8. #include "include/private/SkTemplates.h"
  9. #include "src/core/SkAutoMalloc.h"
  10. #include "src/core/SkDistanceFieldGen.h"
  11. #include "src/core/SkMask.h"
  12. #include "src/core/SkPointPriv.h"
  13. #include <utility>
  14. struct DFData {
  15. float fAlpha; // alpha value of source texel
  16. float fDistSq; // distance squared to nearest (so far) edge texel
  17. SkPoint fDistVector; // distance vector to nearest (so far) edge texel
  18. };
  19. enum NeighborFlags {
  20. kLeft_NeighborFlag = 0x01,
  21. kRight_NeighborFlag = 0x02,
  22. kTopLeft_NeighborFlag = 0x04,
  23. kTop_NeighborFlag = 0x08,
  24. kTopRight_NeighborFlag = 0x10,
  25. kBottomLeft_NeighborFlag = 0x20,
  26. kBottom_NeighborFlag = 0x40,
  27. kBottomRight_NeighborFlag = 0x80,
  28. kAll_NeighborFlags = 0xff,
  29. kNeighborFlagCount = 8
  30. };
  31. // We treat an "edge" as a place where we cross from >=128 to <128, or vice versa, or
  32. // where we have two non-zero pixels that are <128.
  33. // 'neighborFlags' is used to limit the directions in which we test to avoid indexing
  34. // outside of the image
  35. static bool found_edge(const unsigned char* imagePtr, int width, int neighborFlags) {
  36. // the order of these should match the neighbor flags above
  37. const int kNum8ConnectedNeighbors = 8;
  38. const int offsets[8] = {-1, 1, -width-1, -width, -width+1, width-1, width, width+1 };
  39. SkASSERT(kNum8ConnectedNeighbors == kNeighborFlagCount);
  40. // search for an edge
  41. unsigned char currVal = *imagePtr;
  42. unsigned char currCheck = (currVal >> 7);
  43. for (int i = 0; i < kNum8ConnectedNeighbors; ++i) {
  44. unsigned char neighborVal;
  45. if ((1 << i) & neighborFlags) {
  46. const unsigned char* checkPtr = imagePtr + offsets[i];
  47. neighborVal = *checkPtr;
  48. } else {
  49. neighborVal = 0;
  50. }
  51. unsigned char neighborCheck = (neighborVal >> 7);
  52. SkASSERT(currCheck == 0 || currCheck == 1);
  53. SkASSERT(neighborCheck == 0 || neighborCheck == 1);
  54. // if sharp transition
  55. if (currCheck != neighborCheck ||
  56. // or both <128 and >0
  57. (!currCheck && !neighborCheck && currVal && neighborVal)) {
  58. return true;
  59. }
  60. }
  61. return false;
  62. }
  63. static void init_glyph_data(DFData* data, unsigned char* edges, const unsigned char* image,
  64. int dataWidth, int dataHeight,
  65. int imageWidth, int imageHeight,
  66. int pad) {
  67. data += pad*dataWidth;
  68. data += pad;
  69. edges += (pad*dataWidth + pad);
  70. for (int j = 0; j < imageHeight; ++j) {
  71. for (int i = 0; i < imageWidth; ++i) {
  72. if (255 == *image) {
  73. data->fAlpha = 1.0f;
  74. } else {
  75. data->fAlpha = (*image)*0.00392156862f; // 1/255
  76. }
  77. int checkMask = kAll_NeighborFlags;
  78. if (i == 0) {
  79. checkMask &= ~(kLeft_NeighborFlag|kTopLeft_NeighborFlag|kBottomLeft_NeighborFlag);
  80. }
  81. if (i == imageWidth-1) {
  82. checkMask &= ~(kRight_NeighborFlag|kTopRight_NeighborFlag|kBottomRight_NeighborFlag);
  83. }
  84. if (j == 0) {
  85. checkMask &= ~(kTopLeft_NeighborFlag|kTop_NeighborFlag|kTopRight_NeighborFlag);
  86. }
  87. if (j == imageHeight-1) {
  88. checkMask &= ~(kBottomLeft_NeighborFlag|kBottom_NeighborFlag|kBottomRight_NeighborFlag);
  89. }
  90. if (found_edge(image, imageWidth, checkMask)) {
  91. *edges = 255; // using 255 makes for convenient debug rendering
  92. }
  93. ++data;
  94. ++image;
  95. ++edges;
  96. }
  97. data += 2*pad;
  98. edges += 2*pad;
  99. }
  100. }
  101. // from Gustavson (2011)
  102. // computes the distance to an edge given an edge normal vector and a pixel's alpha value
  103. // assumes that direction has been pre-normalized
  104. static float edge_distance(const SkPoint& direction, float alpha) {
  105. float dx = direction.fX;
  106. float dy = direction.fY;
  107. float distance;
  108. if (SkScalarNearlyZero(dx) || SkScalarNearlyZero(dy)) {
  109. distance = 0.5f - alpha;
  110. } else {
  111. // this is easier if we treat the direction as being in the first octant
  112. // (other octants are symmetrical)
  113. dx = SkScalarAbs(dx);
  114. dy = SkScalarAbs(dy);
  115. if (dx < dy) {
  116. using std::swap;
  117. swap(dx, dy);
  118. }
  119. // a1 = 0.5*dy/dx is the smaller fractional area chopped off by the edge
  120. // to avoid the divide, we just consider the numerator
  121. float a1num = 0.5f*dy;
  122. // we now compute the approximate distance, depending where the alpha falls
  123. // relative to the edge fractional area
  124. // if 0 <= alpha < a1
  125. if (alpha*dx < a1num) {
  126. // TODO: find a way to do this without square roots?
  127. distance = 0.5f*(dx + dy) - SkScalarSqrt(2.0f*dx*dy*alpha);
  128. // if a1 <= alpha <= 1 - a1
  129. } else if (alpha*dx < (dx - a1num)) {
  130. distance = (0.5f - alpha)*dx;
  131. // if 1 - a1 < alpha <= 1
  132. } else {
  133. // TODO: find a way to do this without square roots?
  134. distance = -0.5f*(dx + dy) + SkScalarSqrt(2.0f*dx*dy*(1.0f - alpha));
  135. }
  136. }
  137. return distance;
  138. }
  139. static void init_distances(DFData* data, unsigned char* edges, int width, int height) {
  140. // skip one pixel border
  141. DFData* currData = data;
  142. DFData* prevData = data - width;
  143. DFData* nextData = data + width;
  144. for (int j = 0; j < height; ++j) {
  145. for (int i = 0; i < width; ++i) {
  146. if (*edges) {
  147. // we should not be in the one-pixel outside band
  148. SkASSERT(i > 0 && i < width-1 && j > 0 && j < height-1);
  149. // gradient will point from low to high
  150. // +y is down in this case
  151. // i.e., if you're outside, gradient points towards edge
  152. // if you're inside, gradient points away from edge
  153. SkPoint currGrad;
  154. currGrad.fX = (prevData+1)->fAlpha - (prevData-1)->fAlpha
  155. + SK_ScalarSqrt2*(currData+1)->fAlpha
  156. - SK_ScalarSqrt2*(currData-1)->fAlpha
  157. + (nextData+1)->fAlpha - (nextData-1)->fAlpha;
  158. currGrad.fY = (nextData-1)->fAlpha - (prevData-1)->fAlpha
  159. + SK_ScalarSqrt2*nextData->fAlpha
  160. - SK_ScalarSqrt2*prevData->fAlpha
  161. + (nextData+1)->fAlpha - (prevData+1)->fAlpha;
  162. SkPointPriv::SetLengthFast(&currGrad, 1.0f);
  163. // init squared distance to edge and distance vector
  164. float dist = edge_distance(currGrad, currData->fAlpha);
  165. currGrad.scale(dist, &currData->fDistVector);
  166. currData->fDistSq = dist*dist;
  167. } else {
  168. // init distance to "far away"
  169. currData->fDistSq = 2000000.f;
  170. currData->fDistVector.fX = 1000.f;
  171. currData->fDistVector.fY = 1000.f;
  172. }
  173. ++currData;
  174. ++prevData;
  175. ++nextData;
  176. ++edges;
  177. }
  178. }
  179. }
  180. // Danielsson's 8SSEDT
  181. // first stage forward pass
  182. // (forward in Y, forward in X)
  183. static void F1(DFData* curr, int width) {
  184. // upper left
  185. DFData* check = curr - width-1;
  186. SkPoint distVec = check->fDistVector;
  187. float distSq = check->fDistSq - 2.0f*(distVec.fX + distVec.fY - 1.0f);
  188. if (distSq < curr->fDistSq) {
  189. distVec.fX -= 1.0f;
  190. distVec.fY -= 1.0f;
  191. curr->fDistSq = distSq;
  192. curr->fDistVector = distVec;
  193. }
  194. // up
  195. check = curr - width;
  196. distVec = check->fDistVector;
  197. distSq = check->fDistSq - 2.0f*distVec.fY + 1.0f;
  198. if (distSq < curr->fDistSq) {
  199. distVec.fY -= 1.0f;
  200. curr->fDistSq = distSq;
  201. curr->fDistVector = distVec;
  202. }
  203. // upper right
  204. check = curr - width+1;
  205. distVec = check->fDistVector;
  206. distSq = check->fDistSq + 2.0f*(distVec.fX - distVec.fY + 1.0f);
  207. if (distSq < curr->fDistSq) {
  208. distVec.fX += 1.0f;
  209. distVec.fY -= 1.0f;
  210. curr->fDistSq = distSq;
  211. curr->fDistVector = distVec;
  212. }
  213. // left
  214. check = curr - 1;
  215. distVec = check->fDistVector;
  216. distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f;
  217. if (distSq < curr->fDistSq) {
  218. distVec.fX -= 1.0f;
  219. curr->fDistSq = distSq;
  220. curr->fDistVector = distVec;
  221. }
  222. }
  223. // second stage forward pass
  224. // (forward in Y, backward in X)
  225. static void F2(DFData* curr, int width) {
  226. // right
  227. DFData* check = curr + 1;
  228. SkPoint distVec = check->fDistVector;
  229. float distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f;
  230. if (distSq < curr->fDistSq) {
  231. distVec.fX += 1.0f;
  232. curr->fDistSq = distSq;
  233. curr->fDistVector = distVec;
  234. }
  235. }
  236. // first stage backward pass
  237. // (backward in Y, forward in X)
  238. static void B1(DFData* curr, int width) {
  239. // left
  240. DFData* check = curr - 1;
  241. SkPoint distVec = check->fDistVector;
  242. float distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f;
  243. if (distSq < curr->fDistSq) {
  244. distVec.fX -= 1.0f;
  245. curr->fDistSq = distSq;
  246. curr->fDistVector = distVec;
  247. }
  248. }
  249. // second stage backward pass
  250. // (backward in Y, backwards in X)
  251. static void B2(DFData* curr, int width) {
  252. // right
  253. DFData* check = curr + 1;
  254. SkPoint distVec = check->fDistVector;
  255. float distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f;
  256. if (distSq < curr->fDistSq) {
  257. distVec.fX += 1.0f;
  258. curr->fDistSq = distSq;
  259. curr->fDistVector = distVec;
  260. }
  261. // bottom left
  262. check = curr + width-1;
  263. distVec = check->fDistVector;
  264. distSq = check->fDistSq - 2.0f*(distVec.fX - distVec.fY - 1.0f);
  265. if (distSq < curr->fDistSq) {
  266. distVec.fX -= 1.0f;
  267. distVec.fY += 1.0f;
  268. curr->fDistSq = distSq;
  269. curr->fDistVector = distVec;
  270. }
  271. // bottom
  272. check = curr + width;
  273. distVec = check->fDistVector;
  274. distSq = check->fDistSq + 2.0f*distVec.fY + 1.0f;
  275. if (distSq < curr->fDistSq) {
  276. distVec.fY += 1.0f;
  277. curr->fDistSq = distSq;
  278. curr->fDistVector = distVec;
  279. }
  280. // bottom right
  281. check = curr + width+1;
  282. distVec = check->fDistVector;
  283. distSq = check->fDistSq + 2.0f*(distVec.fX + distVec.fY + 1.0f);
  284. if (distSq < curr->fDistSq) {
  285. distVec.fX += 1.0f;
  286. distVec.fY += 1.0f;
  287. curr->fDistSq = distSq;
  288. curr->fDistVector = distVec;
  289. }
  290. }
  291. // enable this to output edge data rather than the distance field
  292. #define DUMP_EDGE 0
  293. #if !DUMP_EDGE
  294. template <int distanceMagnitude>
  295. static unsigned char pack_distance_field_val(float dist) {
  296. // The distance field is constructed as unsigned char values, so that the zero value is at 128,
  297. // Beside 128, we have 128 values in range [0, 128), but only 127 values in range (128, 255].
  298. // So we multiply distanceMagnitude by 127/128 at the latter range to avoid overflow.
  299. dist = SkScalarPin(-dist, -distanceMagnitude, distanceMagnitude * 127.0f / 128.0f);
  300. // Scale into the positive range for unsigned distance.
  301. dist += distanceMagnitude;
  302. // Scale into unsigned char range.
  303. // Round to place negative and positive values as equally as possible around 128
  304. // (which represents zero).
  305. return (unsigned char)SkScalarRoundToInt(dist / (2 * distanceMagnitude) * 256.0f);
  306. }
  307. #endif
  308. // assumes a padded 8-bit image and distance field
  309. // width and height are the original width and height of the image
  310. static bool generate_distance_field_from_image(unsigned char* distanceField,
  311. const unsigned char* copyPtr,
  312. int width, int height) {
  313. SkASSERT(distanceField);
  314. SkASSERT(copyPtr);
  315. // we expand our temp data by one more on each side to simplify
  316. // the scanning code -- will always be treated as infinitely far away
  317. int pad = SK_DistanceFieldPad + 1;
  318. // set params for distance field data
  319. int dataWidth = width + 2*pad;
  320. int dataHeight = height + 2*pad;
  321. // create zeroed temp DFData+edge storage
  322. SkAutoFree storage(sk_calloc_throw(dataWidth*dataHeight*(sizeof(DFData) + 1)));
  323. DFData* dataPtr = (DFData*)storage.get();
  324. unsigned char* edgePtr = (unsigned char*)storage.get() + dataWidth*dataHeight*sizeof(DFData);
  325. // copy glyph into distance field storage
  326. init_glyph_data(dataPtr, edgePtr, copyPtr,
  327. dataWidth, dataHeight,
  328. width+2, height+2, SK_DistanceFieldPad);
  329. // create initial distance data, particularly at edges
  330. init_distances(dataPtr, edgePtr, dataWidth, dataHeight);
  331. // now perform Euclidean distance transform to propagate distances
  332. // forwards in y
  333. DFData* currData = dataPtr+dataWidth+1; // skip outer buffer
  334. unsigned char* currEdge = edgePtr+dataWidth+1;
  335. for (int j = 1; j < dataHeight-1; ++j) {
  336. // forwards in x
  337. for (int i = 1; i < dataWidth-1; ++i) {
  338. // don't need to calculate distance for edge pixels
  339. if (!*currEdge) {
  340. F1(currData, dataWidth);
  341. }
  342. ++currData;
  343. ++currEdge;
  344. }
  345. // backwards in x
  346. --currData; // reset to end
  347. --currEdge;
  348. for (int i = 1; i < dataWidth-1; ++i) {
  349. // don't need to calculate distance for edge pixels
  350. if (!*currEdge) {
  351. F2(currData, dataWidth);
  352. }
  353. --currData;
  354. --currEdge;
  355. }
  356. currData += dataWidth+1;
  357. currEdge += dataWidth+1;
  358. }
  359. // backwards in y
  360. currData = dataPtr+dataWidth*(dataHeight-2) - 1; // skip outer buffer
  361. currEdge = edgePtr+dataWidth*(dataHeight-2) - 1;
  362. for (int j = 1; j < dataHeight-1; ++j) {
  363. // forwards in x
  364. for (int i = 1; i < dataWidth-1; ++i) {
  365. // don't need to calculate distance for edge pixels
  366. if (!*currEdge) {
  367. B1(currData, dataWidth);
  368. }
  369. ++currData;
  370. ++currEdge;
  371. }
  372. // backwards in x
  373. --currData; // reset to end
  374. --currEdge;
  375. for (int i = 1; i < dataWidth-1; ++i) {
  376. // don't need to calculate distance for edge pixels
  377. if (!*currEdge) {
  378. B2(currData, dataWidth);
  379. }
  380. --currData;
  381. --currEdge;
  382. }
  383. currData -= dataWidth-1;
  384. currEdge -= dataWidth-1;
  385. }
  386. // copy results to final distance field data
  387. currData = dataPtr + dataWidth+1;
  388. currEdge = edgePtr + dataWidth+1;
  389. unsigned char *dfPtr = distanceField;
  390. for (int j = 1; j < dataHeight-1; ++j) {
  391. for (int i = 1; i < dataWidth-1; ++i) {
  392. #if DUMP_EDGE
  393. float alpha = currData->fAlpha;
  394. float edge = 0.0f;
  395. if (*currEdge) {
  396. edge = 0.25f;
  397. }
  398. // blend with original image
  399. float result = alpha + (1.0f-alpha)*edge;
  400. unsigned char val = sk_float_round2int(255*result);
  401. *dfPtr++ = val;
  402. #else
  403. float dist;
  404. if (currData->fAlpha > 0.5f) {
  405. dist = -SkScalarSqrt(currData->fDistSq);
  406. } else {
  407. dist = SkScalarSqrt(currData->fDistSq);
  408. }
  409. *dfPtr++ = pack_distance_field_val<SK_DistanceFieldMagnitude>(dist);
  410. #endif
  411. ++currData;
  412. ++currEdge;
  413. }
  414. currData += 2;
  415. currEdge += 2;
  416. }
  417. return true;
  418. }
  419. // assumes an 8-bit image and distance field
  420. bool SkGenerateDistanceFieldFromA8Image(unsigned char* distanceField,
  421. const unsigned char* image,
  422. int width, int height, size_t rowBytes) {
  423. SkASSERT(distanceField);
  424. SkASSERT(image);
  425. // create temp data
  426. SkAutoSMalloc<1024> copyStorage((width+2)*(height+2)*sizeof(char));
  427. unsigned char* copyPtr = (unsigned char*) copyStorage.get();
  428. // we copy our source image into a padded copy to ensure we catch edge transitions
  429. // around the outside
  430. const unsigned char* currSrcScanLine = image;
  431. sk_bzero(copyPtr, (width+2)*sizeof(char));
  432. unsigned char* currDestPtr = copyPtr + width + 2;
  433. for (int i = 0; i < height; ++i) {
  434. *currDestPtr++ = 0;
  435. memcpy(currDestPtr, currSrcScanLine, width);
  436. currSrcScanLine += rowBytes;
  437. currDestPtr += width;
  438. *currDestPtr++ = 0;
  439. }
  440. sk_bzero(currDestPtr, (width+2)*sizeof(char));
  441. return generate_distance_field_from_image(distanceField, copyPtr, width, height);
  442. }
  443. // assumes a 16-bit lcd mask and 8-bit distance field
  444. bool SkGenerateDistanceFieldFromLCD16Mask(unsigned char* distanceField,
  445. const unsigned char* image,
  446. int w, int h, size_t rowBytes) {
  447. SkASSERT(distanceField);
  448. SkASSERT(image);
  449. // create temp data
  450. SkAutoSMalloc<1024> copyStorage((w+2)*(h+2)*sizeof(char));
  451. unsigned char* copyPtr = (unsigned char*) copyStorage.get();
  452. // we copy our source image into a padded copy to ensure we catch edge transitions
  453. // around the outside
  454. const uint16_t* start = reinterpret_cast<const uint16_t*>(image);
  455. auto currSrcScanline = SkMask::AlphaIter<SkMask::kLCD16_Format>(start);
  456. auto endSrcScanline = SkMask::AlphaIter<SkMask::kLCD16_Format>(start + w);
  457. sk_bzero(copyPtr, (w+2)*sizeof(char));
  458. unsigned char* currDestPtr = copyPtr + w + 2;
  459. for (int i = 0; i < h; ++i, currSrcScanline >>= rowBytes, endSrcScanline >>= rowBytes) {
  460. *currDestPtr++ = 0;
  461. for (auto src = currSrcScanline; src < endSrcScanline; ++src) {
  462. *currDestPtr++ = *src;
  463. }
  464. *currDestPtr++ = 0;
  465. }
  466. sk_bzero(currDestPtr, (w+2)*sizeof(char));
  467. return generate_distance_field_from_image(distanceField, copyPtr, w, h);
  468. }
  469. // assumes a 1-bit image and 8-bit distance field
  470. bool SkGenerateDistanceFieldFromBWImage(unsigned char* distanceField,
  471. const unsigned char* image,
  472. int width, int height, size_t rowBytes) {
  473. SkASSERT(distanceField);
  474. SkASSERT(image);
  475. // create temp data
  476. SkAutoSMalloc<1024> copyStorage((width+2)*(height+2)*sizeof(char));
  477. unsigned char* copyPtr = (unsigned char*) copyStorage.get();
  478. // we copy our source image into a padded copy to ensure we catch edge transitions
  479. // around the outside
  480. const unsigned char* currSrcScanLine = image;
  481. sk_bzero(copyPtr, (width+2)*sizeof(char));
  482. unsigned char* currDestPtr = copyPtr + width + 2;
  483. for (int i = 0; i < height; ++i) {
  484. *currDestPtr++ = 0;
  485. int rowWritesLeft = width;
  486. const unsigned char *maskPtr = currSrcScanLine;
  487. while (rowWritesLeft > 0) {
  488. unsigned mask = *maskPtr++;
  489. for (int i = 7; i >= 0 && rowWritesLeft; --i, --rowWritesLeft) {
  490. *currDestPtr++ = (mask & (1 << i)) ? 0xff : 0;
  491. }
  492. }
  493. currSrcScanLine += rowBytes;
  494. *currDestPtr++ = 0;
  495. }
  496. sk_bzero(currDestPtr, (width+2)*sizeof(char));
  497. return generate_distance_field_from_image(distanceField, copyPtr, width, height);
  498. }