18065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org/* 28065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org * Copyright 2014 Google Inc. 38065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org * 48065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org * Use of this source code is governed by a BSD-style license that can be 58065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org * found in the LICENSE file. 68065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org */ 78065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 88065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org#include "SkDistanceFieldGen.h" 98065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org#include "SkPoint.h" 108065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 118065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.orgstruct DFData { 128065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org float fAlpha; // alpha value of source texel 138065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org float fDistSq; // distance squared to nearest (so far) edge texel 148065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org SkPoint fDistVector; // distance vector to nearest (so far) edge texel 158065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org}; 168065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 1798e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.orgenum NeighborFlags { 1898e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org kLeft_NeighborFlag = 0x01, 1998e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org kRight_NeighborFlag = 0x02, 2098e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org kTopLeft_NeighborFlag = 0x04, 2198e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org kTop_NeighborFlag = 0x08, 2298e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org kTopRight_NeighborFlag = 0x10, 2398e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org kBottomLeft_NeighborFlag = 0x20, 2498e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org kBottom_NeighborFlag = 0x40, 2598e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org kBottomRight_NeighborFlag = 0x80, 2698e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org kAll_NeighborFlags = 0xff, 27bc3d92a7d84b56eb235d6c2d9b7de00625200713skia.committer@gmail.com 2898e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org kNeighborFlagCount = 8 2998e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org}; 3098e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org 31a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org// We treat an "edge" as a place where we cross from >=128 to <128, or vice versa, or 32a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org// where we have two non-zero pixels that are <128. 3398e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org// 'neighborFlags' is used to limit the directions in which we test to avoid indexing 3498e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org// outside of the image 3598e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.orgstatic bool found_edge(const unsigned char* imagePtr, int width, int neighborFlags) { 3698e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org // the order of these should match the neighbor flags above 3798e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org const int kNum8ConnectedNeighbors = 8; 388065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org const int offsets[8] = {-1, 1, -width-1, -width, -width+1, width-1, width, width+1 }; 3998e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org SkASSERT(kNum8ConnectedNeighbors == kNeighborFlagCount); 408065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 418065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // search for an edge 42a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org unsigned char currVal = *imagePtr; 43a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org unsigned char currCheck = (currVal >> 7); 4498e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org for (int i = 0; i < kNum8ConnectedNeighbors; ++i) { 45a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org unsigned char neighborVal; 4698e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org if ((1 << i) & neighborFlags) { 4798e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org const unsigned char* checkPtr = imagePtr + offsets[i]; 48a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org neighborVal = *checkPtr; 4998e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org } else { 50a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org neighborVal = 0; 5198e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org } 52a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org unsigned char neighborCheck = (neighborVal >> 7); 53a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org SkASSERT(currCheck == 0 || currCheck == 1); 54a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org SkASSERT(neighborCheck == 0 || neighborCheck == 1); 55a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org // if sharp transition 56a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org if (currCheck != neighborCheck || 57a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org // or both <128 and >0 58a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org (!currCheck && !neighborCheck && currVal && neighborVal)) { 598065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org return true; 608065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 618065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 628065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 638065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org return false; 648065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org} 658065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 668065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.orgstatic void init_glyph_data(DFData* data, unsigned char* edges, const unsigned char* image, 670b70816eb157ed6492623eea1e55005ef40c908cskia.committer@gmail.com int dataWidth, int dataHeight, 688065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org int imageWidth, int imageHeight, 698065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org int pad) { 708065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org data += pad*dataWidth; 718065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org data += pad; 728065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org edges += (pad*dataWidth + pad); 738065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 748065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org for (int j = 0; j < imageHeight; ++j) { 758065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org for (int i = 0; i < imageWidth; ++i) { 768065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (255 == *image) { 778065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org data->fAlpha = 1.0f; 788065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } else { 798065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org data->fAlpha = (*image)*0.00392156862f; // 1/255 808065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 8198e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org int checkMask = kAll_NeighborFlags; 8298e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org if (i == 0) { 8398e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org checkMask &= ~(kLeft_NeighborFlag|kTopLeft_NeighborFlag|kBottomLeft_NeighborFlag); 8498e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org } 8598e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org if (i == imageWidth-1) { 8698e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org checkMask &= ~(kRight_NeighborFlag|kTopRight_NeighborFlag|kBottomRight_NeighborFlag); 8798e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org } 8898e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org if (j == 0) { 8998e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org checkMask &= ~(kTopLeft_NeighborFlag|kTop_NeighborFlag|kTopRight_NeighborFlag); 9098e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org } 9198e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org if (j == imageHeight-1) { 9298e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org checkMask &= ~(kBottomLeft_NeighborFlag|kBottom_NeighborFlag|kBottomRight_NeighborFlag); 9398e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org } 9498e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org if (found_edge(image, imageWidth, checkMask)) { 958065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org *edges = 255; // using 255 makes for convenient debug rendering 968065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 978065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++data; 988065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++image; 998065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++edges; 1008065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 1018065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org data += 2*pad; 1028065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org edges += 2*pad; 1038065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 1048065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org} 1058065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 1068065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org// from Gustavson (2011) 1078065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org// computes the distance to an edge given an edge normal vector and a pixel's alpha value 1088065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org// assumes that direction has been pre-normalized 1098065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.orgstatic float edge_distance(const SkPoint& direction, float alpha) { 1108065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org float dx = direction.fX; 1118065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org float dy = direction.fY; 1128065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org float distance; 1138065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (SkScalarNearlyZero(dx) || SkScalarNearlyZero(dy)) { 1148065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distance = 0.5f - alpha; 1158065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } else { 1168065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // this is easier if we treat the direction as being in the first octant 1178065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // (other octants are symmetrical) 1188065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org dx = SkScalarAbs(dx); 1198065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org dy = SkScalarAbs(dy); 1208065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (dx < dy) { 1218065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org SkTSwap(dx, dy); 1228065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 1238065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 1248065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // a1 = 0.5*dy/dx is the smaller fractional area chopped off by the edge 1258065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // to avoid the divide, we just consider the numerator 1268065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org float a1num = 0.5f*dy; 1278065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 1288065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // we now compute the approximate distance, depending where the alpha falls 1298065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // relative to the edge fractional area 1308065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 1318065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // if 0 <= alpha < a1 1328065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (alpha*dx < a1num) { 1338065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // TODO: find a way to do this without square roots? 1348065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distance = 0.5f*(dx + dy) - SkScalarSqrt(2.0f*dx*dy*alpha); 1358065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // if a1 <= alpha <= 1 - a1 1368065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } else if (alpha*dx < (dx - a1num)) { 1378065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distance = (0.5f - alpha)*dx; 1388065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // if 1 - a1 < alpha <= 1 1398065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } else { 1408065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // TODO: find a way to do this without square roots? 1418065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distance = -0.5f*(dx + dy) + SkScalarSqrt(2.0f*dx*dy*(1.0f - alpha)); 1428065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 1438065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 1448065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 1458065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org return distance; 1468065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org} 1478065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 1488065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.orgstatic void init_distances(DFData* data, unsigned char* edges, int width, int height) { 1498065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // skip one pixel border 1508065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org DFData* currData = data; 1518065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org DFData* prevData = data - width; 1528065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org DFData* nextData = data + width; 1538065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 1548065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org for (int j = 0; j < height; ++j) { 1558065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org for (int i = 0; i < width; ++i) { 1568065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (*edges) { 1578065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // we should not be in the one-pixel outside band 1588065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org SkASSERT(i > 0 && i < width-1 && j > 0 && j < height-1); 1598065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // gradient will point from low to high 1608065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // +y is down in this case 1618065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // i.e., if you're outside, gradient points towards edge 1628065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // if you're inside, gradient points away from edge 1638065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org SkPoint currGrad; 1648065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currGrad.fX = (prevData+1)->fAlpha - (prevData-1)->fAlpha 1650b70816eb157ed6492623eea1e55005ef40c908cskia.committer@gmail.com + SK_ScalarSqrt2*(currData+1)->fAlpha 1668065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org - SK_ScalarSqrt2*(currData-1)->fAlpha 1678065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org + (nextData+1)->fAlpha - (nextData-1)->fAlpha; 1680b70816eb157ed6492623eea1e55005ef40c908cskia.committer@gmail.com currGrad.fY = (nextData-1)->fAlpha - (prevData-1)->fAlpha 1690b70816eb157ed6492623eea1e55005ef40c908cskia.committer@gmail.com + SK_ScalarSqrt2*nextData->fAlpha 1708065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org - SK_ScalarSqrt2*prevData->fAlpha 1718065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org + (nextData+1)->fAlpha - (prevData+1)->fAlpha; 1728065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currGrad.setLengthFast(1.0f); 1738065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 1748065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // init squared distance to edge and distance vector 1758065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org float dist = edge_distance(currGrad, currData->fAlpha); 1768065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currGrad.scale(dist, &currData->fDistVector); 1778065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currData->fDistSq = dist*dist; 1788065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } else { 1798065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // init distance to "far away" 1808065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currData->fDistSq = 2000000.f; 1818065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currData->fDistVector.fX = 1000.f; 1828065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currData->fDistVector.fY = 1000.f; 1838065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 1848065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++currData; 1858065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++prevData; 1868065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++nextData; 1878065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++edges; 1888065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 1898065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 1908065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org} 1918065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 1928065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org// Danielsson's 8SSEDT 1938065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 1948065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org// first stage forward pass 1958065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org// (forward in Y, forward in X) 1968065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.orgstatic void F1(DFData* curr, int width) { 1978065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // upper left 1988065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org DFData* check = curr - width-1; 1998065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org SkPoint distVec = check->fDistVector; 2008065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org float distSq = check->fDistSq - 2.0f*(distVec.fX + distVec.fY - 1.0f); 2018065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (distSq < curr->fDistSq) { 2028065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fX -= 1.0f; 2038065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fY -= 1.0f; 2048065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistSq = distSq; 2058065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistVector = distVec; 2068065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 2078065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 2088065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // up 2098065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org check = curr - width; 2108065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec = check->fDistVector; 2118065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distSq = check->fDistSq - 2.0f*distVec.fY + 1.0f; 2128065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (distSq < curr->fDistSq) { 2138065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fY -= 1.0f; 2148065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistSq = distSq; 2158065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistVector = distVec; 2168065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 2178065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 2188065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // upper right 2198065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org check = curr - width+1; 2208065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec = check->fDistVector; 2218065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distSq = check->fDistSq + 2.0f*(distVec.fX - distVec.fY + 1.0f); 2228065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (distSq < curr->fDistSq) { 2238065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fX += 1.0f; 2248065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fY -= 1.0f; 2258065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistSq = distSq; 2268065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistVector = distVec; 2278065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 2288065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 2298065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // left 2308065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org check = curr - 1; 2318065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec = check->fDistVector; 2328065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f; 2338065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (distSq < curr->fDistSq) { 2348065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fX -= 1.0f; 2358065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistSq = distSq; 2368065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistVector = distVec; 2378065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 2388065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org} 2398065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 2408065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org// second stage forward pass 2418065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org// (forward in Y, backward in X) 2428065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.orgstatic void F2(DFData* curr, int width) { 2438065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // right 2448065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org DFData* check = curr + 1; 2458065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org float distSq = check->fDistSq; 2468065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org SkPoint distVec = check->fDistVector; 2478065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f; 2488065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (distSq < curr->fDistSq) { 2498065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fX += 1.0f; 2508065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistSq = distSq; 2518065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistVector = distVec; 2528065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 2538065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org} 2548065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 2558065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org// first stage backward pass 2568065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org// (backward in Y, forward in X) 2578065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.orgstatic void B1(DFData* curr, int width) { 2588065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // left 2598065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org DFData* check = curr - 1; 2608065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org SkPoint distVec = check->fDistVector; 2618065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org float distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f; 2628065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (distSq < curr->fDistSq) { 2638065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fX -= 1.0f; 2648065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistSq = distSq; 2658065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistVector = distVec; 2668065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 2678065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org} 2688065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 2698065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org// second stage backward pass 2708065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org// (backward in Y, backwards in X) 2718065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.orgstatic void B2(DFData* curr, int width) { 2728065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // right 2738065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org DFData* check = curr + 1; 2748065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org SkPoint distVec = check->fDistVector; 2758065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org float distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f; 2768065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (distSq < curr->fDistSq) { 2778065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fX += 1.0f; 2788065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistSq = distSq; 2798065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistVector = distVec; 2808065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 2818065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 2828065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // bottom left 2838065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org check = curr + width-1; 2848065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec = check->fDistVector; 2858065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distSq = check->fDistSq - 2.0f*(distVec.fX - distVec.fY - 1.0f); 2868065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (distSq < curr->fDistSq) { 2878065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fX -= 1.0f; 2888065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fY += 1.0f; 2898065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistSq = distSq; 2908065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistVector = distVec; 2918065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 2928065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 2938065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // bottom 2948065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org check = curr + width; 2958065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec = check->fDistVector; 2968065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distSq = check->fDistSq + 2.0f*distVec.fY + 1.0f; 2978065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (distSq < curr->fDistSq) { 2988065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fY += 1.0f; 2998065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistSq = distSq; 3008065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistVector = distVec; 3018065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 3028065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 3038065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // bottom right 3048065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org check = curr + width+1; 3058065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec = check->fDistVector; 3068065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distSq = check->fDistSq + 2.0f*(distVec.fX + distVec.fY + 1.0f); 3078065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (distSq < curr->fDistSq) { 3088065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fX += 1.0f; 3098065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org distVec.fY += 1.0f; 3108065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistSq = distSq; 3118065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org curr->fDistVector = distVec; 3128065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 3138065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org} 3148065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 31598e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org// enable this to output edge data rather than the distance field 31698e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org#define DUMP_EDGE 0 31798e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org 31898e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org#if !DUMP_EDGE 3198065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.orgstatic unsigned char pack_distance_field_val(float dist, float distanceMagnitude) { 3208065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (dist <= -distanceMagnitude) { 3218065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org return 255; 3228065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } else if (dist > distanceMagnitude) { 3238065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org return 0; 3248065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } else { 3258065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org return (unsigned char)((distanceMagnitude-dist)*128.0f/distanceMagnitude); 3268065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 3278065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org} 32898e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org#endif 3298065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 330762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org// assumes a padded 8-bit image and distance field 331762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org// width and height are the original width and height of the image 3322cfa3200fda29279eba1240170c7e873d12f9d48commit-bot@chromium.orgstatic bool generate_distance_field_from_image(unsigned char* distanceField, 3332cfa3200fda29279eba1240170c7e873d12f9d48commit-bot@chromium.org const unsigned char* copyPtr, 3342cfa3200fda29279eba1240170c7e873d12f9d48commit-bot@chromium.org int width, int height) { 33549f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(distanceField); 33649f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(copyPtr); 3378065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 3388065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // we expand our temp data by one more on each side to simplify 3398065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // the scanning code -- will always be treated as infinitely far away 340762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org int pad = SK_DistanceFieldPad + 1; 3418065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 3428065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // set params for distance field data 3438065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org int dataWidth = width + 2*pad; 3448065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org int dataHeight = height + 2*pad; 3458065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 3468065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // create temp data 3478065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org size_t dataSize = dataWidth*dataHeight*sizeof(DFData); 3488065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org SkAutoSMalloc<1024> dfStorage(dataSize); 3498065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org DFData* dataPtr = (DFData*) dfStorage.get(); 3508065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org sk_bzero(dataPtr, dataSize); 3518065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 3528065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org SkAutoSMalloc<1024> edgeStorage(dataWidth*dataHeight*sizeof(char)); 3538065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org unsigned char* edgePtr = (unsigned char*) edgeStorage.get(); 3548065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org sk_bzero(edgePtr, dataWidth*dataHeight*sizeof(char)); 3558065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 3568065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // copy glyph into distance field storage 357a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org init_glyph_data(dataPtr, edgePtr, copyPtr, 3588065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org dataWidth, dataHeight, 359762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org width+2, height+2, SK_DistanceFieldPad); 3608065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 3618065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // create initial distance data, particularly at edges 3628065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org init_distances(dataPtr, edgePtr, dataWidth, dataHeight); 3638065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 3648065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // now perform Euclidean distance transform to propagate distances 3658065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 3668065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // forwards in y 3678065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org DFData* currData = dataPtr+dataWidth+1; // skip outer buffer 3688065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org unsigned char* currEdge = edgePtr+dataWidth+1; 3698065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org for (int j = 1; j < dataHeight-1; ++j) { 3708065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // forwards in x 3718065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org for (int i = 1; i < dataWidth-1; ++i) { 3728065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // don't need to calculate distance for edge pixels 3738065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (!*currEdge) { 3748065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org F1(currData, dataWidth); 3758065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 3768065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++currData; 3778065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++currEdge; 3788065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 3798065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 3808065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // backwards in x 3818065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org --currData; // reset to end 3828065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org --currEdge; 3838065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org for (int i = 1; i < dataWidth-1; ++i) { 3848065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // don't need to calculate distance for edge pixels 3858065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (!*currEdge) { 3868065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org F2(currData, dataWidth); 3878065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 3888065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org --currData; 3898065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org --currEdge; 3908065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 3918065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 3928065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currData += dataWidth+1; 3938065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currEdge += dataWidth+1; 3948065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 3958065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 3968065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // backwards in y 3978065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currData = dataPtr+dataWidth*(dataHeight-2) - 1; // skip outer buffer 3988065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currEdge = edgePtr+dataWidth*(dataHeight-2) - 1; 3998065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org for (int j = 1; j < dataHeight-1; ++j) { 4008065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // forwards in x 4018065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org for (int i = 1; i < dataWidth-1; ++i) { 4028065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // don't need to calculate distance for edge pixels 4038065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (!*currEdge) { 4048065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org B1(currData, dataWidth); 4058065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 4068065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++currData; 4078065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++currEdge; 4088065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 4098065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 4108065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // backwards in x 4118065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org --currData; // reset to end 4128065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org --currEdge; 4138065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org for (int i = 1; i < dataWidth-1; ++i) { 4148065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // don't need to calculate distance for edge pixels 4158065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (!*currEdge) { 4168065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org B2(currData, dataWidth); 4178065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 4188065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org --currData; 4198065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org --currEdge; 4208065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 4218065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 4228065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currData -= dataWidth-1; 4238065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currEdge -= dataWidth-1; 4248065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 4258065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 4268065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org // copy results to final distance field data 4278065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currData = dataPtr + dataWidth+1; 4288065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currEdge = edgePtr + dataWidth+1; 4298065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org unsigned char *dfPtr = distanceField; 4308065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org for (int j = 1; j < dataHeight-1; ++j) { 4318065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org for (int i = 1; i < dataWidth-1; ++i) { 43298e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org#if DUMP_EDGE 433a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org float alpha = currData->fAlpha; 434a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org float edge = 0.0f; 43598e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org if (*currEdge) { 436a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org edge = 0.25f; 43798e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org } 438a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org // blend with original image 439a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org float result = alpha + (1.0f-alpha)*edge; 440a9dae71210c3d4a689518ee87be6b1930d843315commit-bot@chromium.org unsigned char val = sk_float_round2int(255*result); 44198e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org *dfPtr++ = val; 44298e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org#else 4438065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org float dist; 4448065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org if (currData->fAlpha > 0.5f) { 4458065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org dist = -SkScalarSqrt(currData->fDistSq); 4468065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } else { 4478065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org dist = SkScalarSqrt(currData->fDistSq); 4488065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 449762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org *dfPtr++ = pack_distance_field_val(dist, (float)SK_DistanceFieldMagnitude); 45098e22b84ca90c9cf1b8efb2318f5c146881926d4commit-bot@chromium.org#endif 4518065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++currData; 4528065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org ++currEdge; 4538065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 4548065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currData += 2; 4558065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org currEdge += 2; 4568065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org } 4578065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org 4588065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org return true; 4598065ec50f1937c1562810bfe2b216abfb98362b3commit-bot@chromium.org} 460762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org 461762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org// assumes an 8-bit image and distance field 462762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.orgbool SkGenerateDistanceFieldFromA8Image(unsigned char* distanceField, 463762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org const unsigned char* image, 464ef3fcd877aa78c1d0ac802043cd8785180304c12bsalomon int width, int height, size_t rowBytes) { 46549f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(distanceField); 46649f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(image); 467762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org 468762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org // create temp data 469762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org SkAutoSMalloc<1024> copyStorage((width+2)*(height+2)*sizeof(char)); 470762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org unsigned char* copyPtr = (unsigned char*) copyStorage.get(); 471762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org 472762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org // we copy our source image into a padded copy to ensure we catch edge transitions 473762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org // around the outside 474762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org const unsigned char* currSrcScanLine = image; 475762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org sk_bzero(copyPtr, (width+2)*sizeof(char)); 476762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org unsigned char* currDestPtr = copyPtr + width + 2; 477762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org for (int i = 0; i < height; ++i) { 478762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org *currDestPtr++ = 0; 479762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org memcpy(currDestPtr, currSrcScanLine, rowBytes); 480762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org currSrcScanLine += rowBytes; 481762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org currDestPtr += width; 482762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org *currDestPtr++ = 0; 483762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org } 484762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org sk_bzero(currDestPtr, (width+2)*sizeof(char)); 485762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org 486762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org return generate_distance_field_from_image(distanceField, copyPtr, width, height); 487762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org} 488762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org 489762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org// assumes a 1-bit image and 8-bit distance field 490762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.orgbool SkGenerateDistanceFieldFromBWImage(unsigned char* distanceField, 491762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org const unsigned char* image, 492ef3fcd877aa78c1d0ac802043cd8785180304c12bsalomon int width, int height, size_t rowBytes) { 49349f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(distanceField); 49449f085dddff10473b6ebf832a974288300224e60bsalomon SkASSERT(image); 495762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org 496762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org // create temp data 497762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org SkAutoSMalloc<1024> copyStorage((width+2)*(height+2)*sizeof(char)); 498762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org unsigned char* copyPtr = (unsigned char*) copyStorage.get(); 499762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org 500762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org // we copy our source image into a padded copy to ensure we catch edge transitions 501762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org // around the outside 502762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org const unsigned char* currSrcScanLine = image; 503762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org sk_bzero(copyPtr, (width+2)*sizeof(char)); 504762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org unsigned char* currDestPtr = copyPtr + width + 2; 505762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org for (int i = 0; i < height; ++i) { 506762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org *currDestPtr++ = 0; 507762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org int rowWritesLeft = width; 508762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org const unsigned char *maskPtr = currSrcScanLine; 509762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org while (rowWritesLeft > 0) { 510762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org unsigned mask = *maskPtr++; 511762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org for (int i = 7; i >= 0 && rowWritesLeft; --i, --rowWritesLeft) { 512762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org *currDestPtr++ = (mask & (1 << i)) ? 0xff : 0; 513762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org } 514762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org } 515762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org currSrcScanLine += rowBytes; 516762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org *currDestPtr++ = 0; 517762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org } 518762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org sk_bzero(currDestPtr, (width+2)*sizeof(char)); 519762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org 520762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org return generate_distance_field_from_image(distanceField, copyPtr, width, height); 521762cd804375ff8478427dba4fe29379562b8fb60commit-bot@chromium.org} 522