SkDistanceFieldGen.cpp File Reference

#include "src/core/SkDistanceFieldGen.h"
#include "include/core/SkPoint.h"
#include "include/core/SkScalar.h"
#include "include/private/base/SkMalloc.h"
#include "include/private/base/SkTPin.h"
#include "include/private/base/SkTemplates.h"
#include "src/base/SkAutoMalloc.h"
#include "src/core/SkMask.h"
#include "src/core/SkPointPriv.h"
#include <cstdint>
#include <cstring>
#include <utility>

Go to the source code of this file.

Classes
struct	DFData

Macros
#define	DUMP_EDGE   0

Enumerations
enum	NeighborFlags {   kLeft_NeighborFlag = 0x01 , kRight_NeighborFlag = 0x02 , kTopLeft_NeighborFlag = 0x04 , kTop_NeighborFlag = 0x08 ,   kTopRight_NeighborFlag = 0x10 , kBottomLeft_NeighborFlag = 0x20 , kBottom_NeighborFlag = 0x40 , kBottomRight_NeighborFlag = 0x80 ,   kAll_NeighborFlags = 0xff , kNeighborFlagCount = 8 }

Functions
static bool	found_edge (const unsigned char *imagePtr, int width, int neighborFlags)
static void	init_glyph_data (DFData *data, unsigned char *edges, const unsigned char *image, int dataWidth, int dataHeight, int imageWidth, int imageHeight, int pad)
static float	edge_distance (const SkPoint &direction, float alpha)
static void	init_distances (DFData *data, unsigned char *edges, int width, int height)
static void	F1 (DFData *curr, int width)
static void	F2 (DFData *curr, int width)
static void	B1 (DFData *curr, int width)
static void	B2 (DFData *curr, int width)
template<int distanceMagnitude>
static unsigned char	pack_distance_field_val (float dist)
static bool	generate_distance_field_from_image (unsigned char *distanceField, const unsigned char *copyPtr, int width, int height)
bool	SkGenerateDistanceFieldFromA8Image (unsigned char *distanceField, const unsigned char *image, int width, int height, size_t rowBytes)
bool	SkGenerateDistanceFieldFromLCD16Mask (unsigned char *distanceField, const unsigned char *image, int w, int h, size_t rowBytes)
bool	SkGenerateDistanceFieldFromBWImage (unsigned char *distanceField, const unsigned char *image, int width, int height, size_t rowBytes)

Macro Definition Documentation

DUMP_EDGE

#define DUMP_EDGE   0

Definition at line 332 of file SkDistanceFieldGen.cpp.

Enumeration Type Documentation

NeighborFlags

enum NeighborFlags

Enumerator
kLeft_NeighborFlag
kRight_NeighborFlag
kTopLeft_NeighborFlag
kTop_NeighborFlag
kTopRight_NeighborFlag
kBottomLeft_NeighborFlag
kBottom_NeighborFlag
kBottomRight_NeighborFlag
kAll_NeighborFlags
kNeighborFlagCount

Definition at line 33 of file SkDistanceFieldGen.cpp.

                   {
    kLeft_NeighborFlag        = 0x01,
    kRight_NeighborFlag       = 0x02,
    kTopLeft_NeighborFlag     = 0x04,
    kTop_NeighborFlag         = 0x08,
    kTopRight_NeighborFlag    = 0x10,
    kBottomLeft_NeighborFlag  = 0x20,
    kBottom_NeighborFlag      = 0x40,
    kBottomRight_NeighborFlag = 0x80,
    kAll_NeighborFlags        = 0xff,
 
    kNeighborFlagCount        = 8
};

Function Documentation

B1()

static void B1 ( DFData *  curr, int  width  )

static

Definition at line 273 of file SkDistanceFieldGen.cpp.

                                        {
    // left
    DFData* check = curr - 1;
    SkPoint distVec = check->fDistVector;
    float distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f;
    if (distSq < curr->fDistSq) {
        distVec.fX -= 1.0f;
        curr->fDistSq = distSq;
        curr->fDistVector = distVec;
    }
}

B2()

static void B2 ( DFData *  curr, int  width  )

static

Definition at line 287 of file SkDistanceFieldGen.cpp.

                                        {
    // right
    DFData* check = curr + 1;
    SkPoint distVec = check->fDistVector;
    float distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f;
    if (distSq < curr->fDistSq) {
        distVec.fX += 1.0f;
        curr->fDistSq = distSq;
        curr->fDistVector = distVec;
    }
 
    // bottom left
    check = curr + width-1;
    distVec = check->fDistVector;
    distSq = check->fDistSq - 2.0f*(distVec.fX - distVec.fY - 1.0f);
    if (distSq < curr->fDistSq) {
        distVec.fX -= 1.0f;
        distVec.fY += 1.0f;
        curr->fDistSq = distSq;
        curr->fDistVector = distVec;
    }
 
    // bottom
    check = curr + width;
    distVec = check->fDistVector;
    distSq = check->fDistSq + 2.0f*distVec.fY + 1.0f;
    if (distSq < curr->fDistSq) {
        distVec.fY += 1.0f;
        curr->fDistSq = distSq;
        curr->fDistVector = distVec;
    }
 
    // bottom right
    check = curr + width+1;
    distVec = check->fDistVector;
    distSq = check->fDistSq + 2.0f*(distVec.fX + distVec.fY + 1.0f);
    if (distSq < curr->fDistSq) {
        distVec.fX += 1.0f;
        distVec.fY += 1.0f;
        curr->fDistSq = distSq;
        curr->fDistVector = distVec;
    }
}

edge_distance()

static float edge_distance ( const SkPoint &  direction, float  alpha  )

static

Definition at line 125 of file SkDistanceFieldGen.cpp.

                                                                  {
    float dx = direction.fX;
    float dy = direction.fY;
    float distance;
    if (SkScalarNearlyZero(dx) || SkScalarNearlyZero(dy)) {
        distance = 0.5f - alpha;
    } else {
        // this is easier if we treat the direction as being in the first octant
        // (other octants are symmetrical)
        dx = SkScalarAbs(dx);
        dy = SkScalarAbs(dy);
        if (dx < dy) {
            using std::swap;
            swap(dx, dy);
        }
 
        // a1 = 0.5*dy/dx is the smaller fractional area chopped off by the edge
        // to avoid the divide, we just consider the numerator
        float a1num = 0.5f*dy;
 
        // we now compute the approximate distance, depending where the alpha falls
        // relative to the edge fractional area
 
        // if 0 <= alpha < a1
        if (alpha*dx < a1num) {
            // TODO: find a way to do this without square roots?
            distance = 0.5f*(dx + dy) - SkScalarSqrt(2.0f*dx*dy*alpha);
        // if a1 <= alpha <= 1 - a1
        } else if (alpha*dx < (dx - a1num)) {
            distance = (0.5f - alpha)*dx;
        // if 1 - a1 < alpha <= 1
        } else {
            // TODO: find a way to do this without square roots?
            distance = -0.5f*(dx + dy) + SkScalarSqrt(2.0f*dx*dy*(1.0f - alpha));
        }
    }
 
    return distance;
}

F1()

static void F1 ( DFData *  curr, int  width  )

static

Definition at line 213 of file SkDistanceFieldGen.cpp.

                                        {
    // upper left
    DFData* check = curr - width-1;
    SkPoint distVec = check->fDistVector;
    float distSq = check->fDistSq - 2.0f*(distVec.fX + distVec.fY - 1.0f);
    if (distSq < curr->fDistSq) {
        distVec.fX -= 1.0f;
        distVec.fY -= 1.0f;
        curr->fDistSq = distSq;
        curr->fDistVector = distVec;
    }
 
    // up
    check = curr - width;
    distVec = check->fDistVector;
    distSq = check->fDistSq - 2.0f*distVec.fY + 1.0f;
    if (distSq < curr->fDistSq) {
        distVec.fY -= 1.0f;
        curr->fDistSq = distSq;
        curr->fDistVector = distVec;
    }
 
    // upper right
    check = curr - width+1;
    distVec = check->fDistVector;
    distSq = check->fDistSq + 2.0f*(distVec.fX - distVec.fY + 1.0f);
    if (distSq < curr->fDistSq) {
        distVec.fX += 1.0f;
        distVec.fY -= 1.0f;
        curr->fDistSq = distSq;
        curr->fDistVector = distVec;
    }
 
    // left
    check = curr - 1;
    distVec = check->fDistVector;
    distSq = check->fDistSq - 2.0f*distVec.fX + 1.0f;
    if (distSq < curr->fDistSq) {
        distVec.fX -= 1.0f;
        curr->fDistSq = distSq;
        curr->fDistVector = distVec;
    }
}

F2()

static void F2 ( DFData *  curr, int  width  )

static

Definition at line 259 of file SkDistanceFieldGen.cpp.

                                        {
    // right
    DFData* check = curr + 1;
    SkPoint distVec = check->fDistVector;
    float distSq = check->fDistSq + 2.0f*distVec.fX + 1.0f;
    if (distSq < curr->fDistSq) {
        distVec.fX += 1.0f;
        curr->fDistSq = distSq;
        curr->fDistVector = distVec;
    }
}

found_edge()

static bool found_edge ( const unsigned char *  imagePtr, int  width, int  neighborFlags  )

static

Definition at line 51 of file SkDistanceFieldGen.cpp.

                                                                                    {
    // the order of these should match the neighbor flags above
    const int kNum8ConnectedNeighbors = 8;
    const int offsets[8] = {-1, 1, -width-1, -width, -width+1, width-1, width, width+1 };
    SkASSERT(kNum8ConnectedNeighbors == kNeighborFlagCount);
 
    // search for an edge
    unsigned char currVal = *imagePtr;
    unsigned char currCheck = (currVal >> 7);
    for (int i = 0; i < kNum8ConnectedNeighbors; ++i) {
        unsigned char neighborVal;
        if ((1 << i) & neighborFlags) {
            const unsigned char* checkPtr = imagePtr + offsets[i];
            neighborVal = *checkPtr;
        } else {
            neighborVal = 0;
        }
        unsigned char neighborCheck = (neighborVal >> 7);
        SkASSERT(currCheck == 0 || currCheck == 1);
        SkASSERT(neighborCheck == 0 || neighborCheck == 1);
        // if sharp transition
        if (currCheck != neighborCheck ||
            // or both <128 and >0
            (!currCheck && !neighborCheck && currVal && neighborVal)) {
            return true;
        }
    }
 
    return false;
}

generate_distance_field_from_image()

static bool generate_distance_field_from_image ( unsigned char *  distanceField, const unsigned char *  copyPtr, int  width, int  height  )

static

Definition at line 354 of file SkDistanceFieldGen.cpp.

                                                                      {
    SkASSERT(distanceField);
    SkASSERT(copyPtr);
 
    // we expand our temp data by one more on each side to simplify
    // the scanning code -- will always be treated as infinitely far away
    int pad = SK_DistanceFieldPad + 1;
 
    // set params for distance field data
    int dataWidth = width + 2*pad;
    int dataHeight = height + 2*pad;
 
    // create zeroed temp DFData+edge storage
    UniqueVoidPtr storage(sk_calloc_throw(dataWidth*dataHeight*(sizeof(DFData) + 1)));
    DFData*        dataPtr = (DFData*)storage.get();
    unsigned char* edgePtr = (unsigned char*)storage.get() + dataWidth*dataHeight*sizeof(DFData);
 
    // copy glyph into distance field storage
    init_glyph_data(dataPtr, edgePtr, copyPtr,
                    dataWidth, dataHeight,
                    width+2, height+2, SK_DistanceFieldPad);
 
    // create initial distance data, particularly at edges
    init_distances(dataPtr, edgePtr, dataWidth, dataHeight);
 
    // now perform Euclidean distance transform to propagate distances
 
    // forwards in y
    DFData* currData = dataPtr+dataWidth+1; // skip outer buffer
    unsigned char* currEdge = edgePtr+dataWidth+1;
    for (int j = 1; j < dataHeight-1; ++j) {
        // forwards in x
        for (int i = 1; i < dataWidth-1; ++i) {
            // don't need to calculate distance for edge pixels
            if (!*currEdge) {
                F1(currData, dataWidth);
            }
            ++currData;
            ++currEdge;
        }
 
        // backwards in x
        --currData; // reset to end
        --currEdge;
        for (int i = 1; i < dataWidth-1; ++i) {
            // don't need to calculate distance for edge pixels
            if (!*currEdge) {
                F2(currData, dataWidth);
            }
            --currData;
            --currEdge;
        }
 
        currData += dataWidth+1;
        currEdge += dataWidth+1;
    }
 
    // backwards in y
    currData = dataPtr+dataWidth*(dataHeight-2) - 1; // skip outer buffer
    currEdge = edgePtr+dataWidth*(dataHeight-2) - 1;
    for (int j = 1; j < dataHeight-1; ++j) {
        // forwards in x
        for (int i = 1; i < dataWidth-1; ++i) {
            // don't need to calculate distance for edge pixels
            if (!*currEdge) {
                B1(currData, dataWidth);
            }
            ++currData;
            ++currEdge;
        }
 
        // backwards in x
        --currData; // reset to end
        --currEdge;
        for (int i = 1; i < dataWidth-1; ++i) {
            // don't need to calculate distance for edge pixels
            if (!*currEdge) {
                B2(currData, dataWidth);
            }
            --currData;
            --currEdge;
        }
 
        currData -= dataWidth-1;
        currEdge -= dataWidth-1;
    }
 
    // copy results to final distance field data
    currData = dataPtr + dataWidth+1;
    currEdge = edgePtr + dataWidth+1;
    unsigned char *dfPtr = distanceField;
    for (int j = 1; j < dataHeight-1; ++j) {
        for (int i = 1; i < dataWidth-1; ++i) {
#if DUMP_EDGE
            float alpha = currData->fAlpha;
            float edge = 0.0f;
            if (*currEdge) {
                edge = 0.25f;
            }
            // blend with original image
            float result = alpha + (1.0f-alpha)*edge;
            unsigned char val = sk_float_round2int(255*result);
            *dfPtr++ = val;
#else
            float dist;
            if (currData->fAlpha > 0.5f) {
                dist = -SkScalarSqrt(currData->fDistSq);
            } else {
                dist = SkScalarSqrt(currData->fDistSq);
            }
            *dfPtr++ = pack_distance_field_val<SK_DistanceFieldMagnitude>(dist);
#endif
            ++currData;
            ++currEdge;
        }
        currData += 2;
        currEdge += 2;
    }
 
    return true;
}

init_distances()

static void init_distances ( DFData *  data, unsigned char *  edges, int  width, int  height  )

static

Definition at line 165 of file SkDistanceFieldGen.cpp.

                                                                                      {
    // skip one pixel border
    DFData* currData = data;
    DFData* prevData = data - width;
    DFData* nextData = data + width;
 
    for (int j = 0; j < height; ++j) {
        for (int i = 0; i < width; ++i) {
            if (*edges) {
                // we should not be in the one-pixel outside band
                SkASSERT(i > 0 && i < width-1 && j > 0 && j < height-1);
                // gradient will point from low to high
                // +y is down in this case
                // i.e., if you're outside, gradient points towards edge
                // if you're inside, gradient points away from edge
                SkPoint currGrad;
                currGrad.fX = (prevData+1)->fAlpha - (prevData-1)->fAlpha
                             + SK_ScalarSqrt2*(currData+1)->fAlpha
                             - SK_ScalarSqrt2*(currData-1)->fAlpha
                             + (nextData+1)->fAlpha - (nextData-1)->fAlpha;
                currGrad.fY = (nextData-1)->fAlpha - (prevData-1)->fAlpha
                             + SK_ScalarSqrt2*nextData->fAlpha
                             - SK_ScalarSqrt2*prevData->fAlpha
                             + (nextData+1)->fAlpha - (prevData+1)->fAlpha;
                SkPointPriv::SetLengthFast(&currGrad, 1.0f);
 
                // init squared distance to edge and distance vector
                float dist = edge_distance(currGrad, currData->fAlpha);
                currGrad.scale(dist, &currData->fDistVector);
                currData->fDistSq = dist*dist;
            } else {
                // init distance to "far away"
                currData->fDistSq = 2000000.f;
                currData->fDistVector.fX = 1000.f;
                currData->fDistVector.fY = 1000.f;
            }
            ++currData;
            ++prevData;
            ++nextData;
            ++edges;
        }
    }
}

init_glyph_data()

static void init_glyph_data ( DFData *  data, unsigned char *  edges, const unsigned char *  image, int  dataWidth, int  dataHeight, int  imageWidth, int  imageHeight, int  pad  )

static

Definition at line 82 of file SkDistanceFieldGen.cpp.

                                     {
    data += pad*dataWidth;
    data += pad;
    edges += (pad*dataWidth + pad);
 
    for (int j = 0; j < imageHeight; ++j) {
        for (int i = 0; i < imageWidth; ++i) {
            if (255 == *image) {
                data->fAlpha = 1.0f;
            } else {
                data->fAlpha = (*image)*0.00392156862f;  // 1/255
            }
            int checkMask = kAll_NeighborFlags;
            if (i == 0) {
                checkMask &= ~(kLeft_NeighborFlag|kTopLeft_NeighborFlag|kBottomLeft_NeighborFlag);
            }
            if (i == imageWidth-1) {
                checkMask &= ~(kRight_NeighborFlag|kTopRight_NeighborFlag|kBottomRight_NeighborFlag);
            }
            if (j == 0) {
                checkMask &= ~(kTopLeft_NeighborFlag|kTop_NeighborFlag|kTopRight_NeighborFlag);
            }
            if (j == imageHeight-1) {
                checkMask &= ~(kBottomLeft_NeighborFlag|kBottom_NeighborFlag|kBottomRight_NeighborFlag);
            }
            if (found_edge(image, imageWidth, checkMask)) {
                *edges = 255;  // using 255 makes for convenient debug rendering
            }
            ++data;
            ++image;
            ++edges;
        }
        data += 2*pad;
        edges += 2*pad;
    }
}

pack_distance_field_val()

template<int distanceMagnitude>

static unsigned char pack_distance_field_val ( float  dist )

static

Definition at line 336 of file SkDistanceFieldGen.cpp.

                                                         {
    // The distance field is constructed as unsigned char values, so that the zero value is at 128,
    // Beside 128, we have 128 values in range [0, 128), but only 127 values in range (128, 255].
    // So we multiply distanceMagnitude by 127/128 at the latter range to avoid overflow.
    dist = SkTPin<float>(-dist, -distanceMagnitude, distanceMagnitude * 127.0f / 128.0f);
 
    // Scale into the positive range for unsigned distance.
    dist += distanceMagnitude;
 
    // Scale into unsigned char range.
    // Round to place negative and positive values as equally as possible around 128
    // (which represents zero).
    return (unsigned char)SkScalarRoundToInt(dist / (2 * distanceMagnitude) * 256.0f);
}

SkGenerateDistanceFieldFromA8Image()

bool SkGenerateDistanceFieldFromA8Image	(	unsigned char *	distanceField,
		const unsigned char *	image,
		int	w,
		int	h,
		size_t	rowBytes
	)

Given 8-bit mask data, generate the associated distance field

Parameters

distanceField	The distance field to be generated. Should already be allocated by the client with the padding above.
image	8-bit mask we're using to generate the distance field.
w	Width of the original image.
h	Height of the original image.
rowBytes	Size of each row in the image, in bytes

Definition at line 479 of file SkDistanceFieldGen.cpp.

                                                                                {
    SkASSERT(distanceField);
    SkASSERT(image);
 
    // create temp data
    SkAutoSMalloc<1024> copyStorage((width+2)*(height+2)*sizeof(char));
    unsigned char* copyPtr = (unsigned char*) copyStorage.get();
 
    // we copy our source image into a padded copy to ensure we catch edge transitions
    // around the outside
    const unsigned char* currSrcScanLine = image;
    sk_bzero(copyPtr, (width+2)*sizeof(char));
    unsigned char* currDestPtr = copyPtr + width + 2;
    for (int i = 0; i < height; ++i) {
        *currDestPtr++ = 0;
        memcpy(currDestPtr, currSrcScanLine, width);
        currSrcScanLine += rowBytes;
        currDestPtr += width;
        *currDestPtr++ = 0;
    }
    sk_bzero(currDestPtr, (width+2)*sizeof(char));
 
    return generate_distance_field_from_image(distanceField, copyPtr, width, height);
}

SkGenerateDistanceFieldFromBWImage()

bool SkGenerateDistanceFieldFromBWImage	(	unsigned char *	distanceField,
		const unsigned char *	image,
		int	w,
		int	h,
		size_t	rowBytes
	)

Given 1-bit mask data, generate the associated distance field

Parameters

distanceField	The distance field to be generated. Should already be allocated by the client with the padding above.
image	1-bit mask we're using to generate the distance field.
w	Width of the original image.
h	Height of the original image.
rowBytes	Size of each row in the image, in bytes

Definition at line 537 of file SkDistanceFieldGen.cpp.

                                                                                {
    SkASSERT(distanceField);
    SkASSERT(image);
 
    // create temp data
    SkAutoSMalloc<1024> copyStorage((width+2)*(height+2)*sizeof(char));
    unsigned char* copyPtr = (unsigned char*) copyStorage.get();
 
    // we copy our source image into a padded copy to ensure we catch edge transitions
    // around the outside
    const unsigned char* currSrcScanLine = image;
    sk_bzero(copyPtr, (width+2)*sizeof(char));
    unsigned char* currDestPtr = copyPtr + width + 2;
    for (int i = 0; i < height; ++i) {
        *currDestPtr++ = 0;
 
        int rowWritesLeft = width;
        const unsigned char *maskPtr = currSrcScanLine;
        while (rowWritesLeft > 0) {
            unsigned mask = *maskPtr++;
            for (int j = 7; j >= 0 && rowWritesLeft; --j, --rowWritesLeft) {
                *currDestPtr++ = (mask & (1 << j)) ? 0xff : 0;
            }
        }
        currSrcScanLine += rowBytes;
 
        *currDestPtr++ = 0;
    }
    sk_bzero(currDestPtr, (width+2)*sizeof(char));
 
    return generate_distance_field_from_image(distanceField, copyPtr, width, height);
}

SkGenerateDistanceFieldFromLCD16Mask()

bool SkGenerateDistanceFieldFromLCD16Mask	(	unsigned char *	distanceField,
		const unsigned char *	image,
		int	w,
		int	h,
		size_t	rowBytes
	)

Given LCD16 mask data (not a 16-bit image), generate the associated distance field

Parameters

distanceField	The distance field to be generated. Should already be allocated by the client with the padding above.
image	16-bit LCD data we're using to generate the distance field.
w	Width of the original image.
h	Height of the original image.
rowBytes	Size of each row in the image, in bytes

Definition at line 507 of file SkDistanceFieldGen.cpp.

                                                                          {
    SkASSERT(distanceField);
    SkASSERT(image);
 
    // create temp data
    SkAutoSMalloc<1024> copyStorage((w+2)*(h+2)*sizeof(char));
    unsigned char* copyPtr = (unsigned char*) copyStorage.get();
 
    // we copy our source image into a padded copy to ensure we catch edge transitions
    // around the outside
    const uint16_t* start = reinterpret_cast<const uint16_t*>(image);
    auto currSrcScanline = SkMask::AlphaIter<SkMask::kLCD16_Format>(start);
    auto endSrcScanline = SkMask::AlphaIter<SkMask::kLCD16_Format>(start + w);
    sk_bzero(copyPtr, (w+2)*sizeof(char));
    unsigned char* currDestPtr = copyPtr + w + 2;
    for (int i = 0; i < h; ++i, currSrcScanline >>= rowBytes, endSrcScanline >>= rowBytes) {
        *currDestPtr++ = 0;
        for (auto src = currSrcScanline; src < endSrcScanline; ++src) {
            *currDestPtr++ = *src;
        }
        *currDestPtr++ = 0;
    }
    sk_bzero(currDestPtr, (w+2)*sizeof(char));
 
    return generate_distance_field_from_image(distanceField, copyPtr, w, h);
}