dali/devel-api/images/distance-field.cpp

   1 /*
   2  * Copyright (c) 2020 Samsung Electronics Co., Ltd.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  *
  16  */
  17
  18 // CLASS HEADER
  19 #include <dali/devel-api/images/distance-field.h>
  20
  21 // EXTERNAL INCLUDES
  22 #include <math.h>
  23 #include <stdio.h>
  24 #include <time.h>
  25 #include <algorithm>
  26
  27 // INTERNAL INCLUDES
  28 #include <dali/public-api/common/constants.h>
  29 #include <dali/public-api/common/vector-wrapper.h>
  30 #include <dali/public-api/math/math-utils.h>
  31 #include <dali/public-api/math/vector2.h>
  32
  33 namespace Dali
  34 {
  35 namespace
  36 {
  37 float Interpolate(float a, float b, float factor)
  38 {
  39   return a * (1.0f - factor) + b * factor;
  40 }
  41
  42 float Bilinear(float a, float b, float c, float d, float dx, float dy)
  43 {
  44   return Interpolate(Interpolate(a, b, dx), Interpolate(c, d, dx), dy);
  45 }
  46
  47 void ScaleField(int width, int height, float* in, uint32_t targetWidth, uint32_t targetHeight, float* out)
  48 {
  49   float xScale = static_cast<float>(width) / static_cast<float>(targetWidth);
  50   float yScale = static_cast<float>(height) / static_cast<float>(targetHeight);
  51
  52   // for each row in target
  53   for(uint32_t y = 0; y < targetHeight; ++y)
  54   {
  55     const int32_t sampleY = static_cast<int32_t>(yScale * static_cast<float>(y));
  56     const int32_t otherY  = std::min(sampleY + 1, height - 1);
  57     const float   dy      = (yScale * static_cast<float>(y)) - static_cast<float>(sampleY);
  58
  59     // for each column in target
  60     for(uint32_t x = 0; x < targetWidth; ++x)
  61     {
  62       const int32_t sampleX = static_cast<int32_t>(xScale * static_cast<float>(x));
  63       const int32_t otherX  = std::min(sampleX + 1, width - 1);
  64       const float   dx      = (xScale * static_cast<float>(x)) - static_cast<float>(sampleX);
  65
  66       float value = Bilinear(in[sampleY * width + sampleX],
  67                              in[sampleY * width + otherX],
  68                              in[otherY * width + sampleX],
  69                              in[otherY * width + otherX],
  70                              dx,
  71                              dy);
  72
  73       out[y * targetWidth + x] = std::min(value, 1.0f);
  74     }
  75   }
  76 }
  77
  78 #define SQUARE(a) ((a) * (a))
  79 const float MAX_DISTANCE = static_cast<float>(1e20);
  80
  81 /**
  82  * Distance transform of 1D function using squared distance
  83  */
  84 void DistanceTransform(float* source, float* dest, uint32_t length)
  85 {
  86   std::vector<int32_t> parabolas(length); // Locations of parabolas in lower envelope
  87   std::vector<float>   edge(length + 1);  // Locations of boundaries between parabolas
  88
  89   int32_t rightmost(0); // Index of rightmost parabola in lower envelope
  90
  91   parabolas[0] = 0;
  92   edge[0]      = -MAX_DISTANCE;
  93   edge[1]      = +MAX_DISTANCE;
  94   for(uint32_t i = 1; i <= length - 1; i++)
  95   {
  96     const float initialDistance(source[i] + static_cast<float>(i * i));
  97     int32_t     parabola = parabolas[rightmost];
  98
  99     float newDistance((initialDistance - (source[parabola] + static_cast<float>(parabola * parabola))) / static_cast<float>(2 * i - 2 * parabola));
 100
 101     while(rightmost > 0 && newDistance <= edge[rightmost])
 102     {
 103       rightmost--;
 104       parabola    = parabolas[rightmost];
 105       newDistance = (initialDistance - (source[parabola] + static_cast<float>(parabola * parabola))) / static_cast<float>(2 * i - 2 * parabola);
 106     }
 107
 108     rightmost++;
 109     parabolas[rightmost] = i;
 110     edge[rightmost]      = newDistance;
 111     edge[rightmost + 1]  = MAX_DISTANCE;
 112   }
 113
 114   rightmost = 0;
 115   for(uint32_t i = 0; i <= length - 1; ++i)
 116   {
 117     while(edge[rightmost + 1] < static_cast<float>(i))
 118     {
 119       ++rightmost;
 120     }
 121     dest[i] = static_cast<float>(SQUARE(static_cast<int32_t>(i) - parabolas[rightmost])) + source[parabolas[rightmost]];
 122   }
 123 }
 124
 125 /**
 126  * Distance transform of 2D function using squared distance
 127  */
 128 void DistanceTransform(float* data, uint32_t width, uint32_t height, float* sourceBuffer, float* destBuffer)
 129 {
 130   // transform along columns
 131   for(uint32_t x = 0; x < width; ++x)
 132   {
 133     for(uint32_t y = 0; y < height; ++y)
 134     {
 135       sourceBuffer[y] = data[y * width + x];
 136     }
 137
 138     DistanceTransform(sourceBuffer, destBuffer, height);
 139
 140     for(uint32_t y = 0; y < height; y++)
 141     {
 142       data[y * width + x] = destBuffer[y];
 143     }
 144   }
 145
 146   // transform along rows
 147   for(uint32_t y = 0; y < height; ++y)
 148   {
 149     for(uint32_t x = 0; x < width; ++x)
 150     {
 151       sourceBuffer[x] = data[y * width + x];
 152     }
 153
 154     DistanceTransform(sourceBuffer, destBuffer, width);
 155
 156     for(uint32_t x = 0; x < width; x++)
 157     {
 158       data[y * width + x] = destBuffer[x];
 159     }
 160   }
 161 }
 162
 163 } // namespace
 164
 165 void GenerateDistanceFieldMap(const uint8_t* const imagePixels, const Size& imageSize, uint8_t* const distanceMap, const Size& distanceMapSize, const float fieldRadius, const uint32_t fieldBorder, bool highQuality)
 166 {
 167   GenerateDistanceFieldMap(imagePixels, imageSize, distanceMap, distanceMapSize, fieldBorder, imageSize, highQuality);
 168 }
 169
 170 void GenerateDistanceFieldMap(const uint8_t* const imagePixels, const Size& imageSize, uint8_t* const distanceMap, const Size& distanceMapSize, const uint32_t fieldBorder, const Vector2& maxSize, bool highQuality)
 171 {
 172   // constants to reduce redundant calculations
 173   const uint32_t originalWidth(static_cast<int32_t>(imageSize.width));
 174   const uint32_t originalHeight(static_cast<int32_t>(imageSize.height));
 175   const uint32_t paddedWidth(originalWidth + (fieldBorder * 2));
 176   const uint32_t paddedHeight(originalHeight + (fieldBorder * 2));
 177   const uint32_t scaledWidth(static_cast<int32_t>(distanceMapSize.width));
 178   const uint32_t scaledHeight(static_cast<int32_t>(distanceMapSize.height));
 179   const uint32_t maxWidth(static_cast<int32_t>(maxSize.width) + (fieldBorder * 2));
 180   const uint32_t maxHeight(static_cast<int32_t>(maxSize.height) + (fieldBorder * 2));
 181
 182   const uint32_t bufferLength(std::max(maxWidth, std::max(paddedWidth, scaledWidth)) *
 183                               std::max(maxHeight, std::max(paddedHeight, scaledHeight)));
 184
 185   std::vector<float> outsidePixels(bufferLength, 0.0f);
 186   std::vector<float> insidePixels(bufferLength, 0.0f);
 187
 188   float* outside(outsidePixels.data());
 189   float* inside(insidePixels.data());
 190
 191   for(uint32_t y = 0; y < paddedHeight; ++y)
 192   {
 193     for(uint32_t x = 0; x < paddedWidth; ++x)
 194     {
 195       if(y < static_cast<uint32_t>(fieldBorder) ||
 196          y >= (paddedHeight - static_cast<uint32_t>(fieldBorder)) ||
 197          x < static_cast<uint32_t>(fieldBorder) ||
 198          x >= (paddedWidth - static_cast<uint32_t>(fieldBorder)))
 199       {
 200         outside[y * paddedWidth + x] = MAX_DISTANCE;
 201         inside[y * paddedWidth + x]  = 0.0f;
 202       }
 203       else
 204       {
 205         uint32_t pixel(imagePixels[(y - fieldBorder) * originalWidth + (x - fieldBorder)]);
 206         outside[y * paddedWidth + x] = (pixel == 0) ? MAX_DISTANCE : SQUARE(static_cast<float>(255 - pixel) / 255.0f);
 207         inside[y * paddedWidth + x]  = (pixel == 255) ? MAX_DISTANCE : SQUARE(static_cast<float>(pixel) / 255.0f);
 208       }
 209     }
 210   }
 211
 212   // perform distance transform if high quality requested, else use original figure
 213   if(highQuality)
 214   {
 215     // create temporary buffers for DistanceTransform()
 216     const uint32_t     tempBufferLength(std::max(paddedWidth, paddedHeight));
 217     std::vector<float> tempSourceBuffer(tempBufferLength, 0.0f);
 218     std::vector<float> tempDestBuffer(tempBufferLength, 0.0f);
 219
 220     // Perform distance transform for pixels 'outside' the figure
 221     DistanceTransform(outside, paddedWidth, paddedHeight, tempSourceBuffer.data(), tempDestBuffer.data());
 222
 223     // Perform distance transform for pixels 'inside' the figure
 224     DistanceTransform(inside, paddedWidth, paddedHeight, tempSourceBuffer.data(), tempDestBuffer.data());
 225   }
 226
 227   // distmap = outside - inside; % Bipolar distance field
 228   for(uint32_t y = 0; y < paddedHeight; ++y)
 229   {
 230     for(uint32_t x = 0; x < paddedWidth; ++x)
 231     {
 232       const int32_t offset(y * paddedWidth + x);
 233       float         pixel(sqrtf(outside[offset]) - sqrtf(inside[offset]));
 234       pixel           = 128.0f + pixel * 16.0f;
 235       pixel           = Clamp(pixel, 0.0f, 255.0f);
 236       outside[offset] = (255.0f - pixel) / 255.0f;
 237     }
 238   }
 239
 240   // scale the figure to the distance field tile size
 241   ScaleField(paddedWidth, paddedHeight, outside, scaledWidth, scaledHeight, inside);
 242
 243   // convert from floats to integers
 244   for(uint32_t y = 0; y < scaledHeight; ++y)
 245   {
 246     for(uint32_t x = 0; x < scaledWidth; ++x)
 247     {
 248       float pixel(inside[y * scaledWidth + x]);
 249       distanceMap[y * scaledWidth + x] = static_cast<uint8_t>(pixel * 255.0f);
 250     }
 251   }
 252 }
 253
 254 } // namespace Dali