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

   1 /*
   2  * Copyright (c) 2014 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/public-api/images/distance-field.h>
  20
  21 // EXTERNAL INCLUDES
  22 #include <algorithm>
  23 #include <math.h>
  24 #include <stdio.h>
  25 #include <time.h>
  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/vector2.h>
  31
  32 namespace Dali
  33 {
  34
  35 namespace
  36 {
  37
  38 float Interpolate( float a, float b, float factor )
  39 {
  40   return a * (1.0f - factor) + b * factor;
  41 }
  42
  43 float Bilinear( float a, float b, float c, float d, float dx, float dy )
  44 {
  45   return Interpolate( Interpolate( a, b, dx), Interpolate( c, d, dx ), dy );
  46 }
  47
  48 void ScaleField( int width, int height, float* in, int targetWidth, int targetHeight, float* out )
  49 {
  50   float xScale = static_cast< float >(width) / targetWidth;
  51   float yScale = static_cast< float >(height) / targetHeight;
  52
  53   // for each row in target
  54   for(int y = 0; y < targetHeight; ++y)
  55   {
  56     const int sampleY = static_cast< int >( yScale * y );
  57     const int otherY = std::min( sampleY + 1, height - 1 );
  58     const float dy = (yScale * y ) - sampleY;
  59
  60     // for each column in target
  61     for (int x = 0; x < targetWidth; ++x)
  62     {
  63       const int sampleX = static_cast< int >( xScale * x );
  64       const int otherX = std::min( sampleX + 1, width - 1 );
  65       const float dx = (xScale * x) - sampleX;
  66
  67       float value = Bilinear( in[ sampleY * width + sampleX ],
  68                               in[ sampleY * width + otherX ],
  69                               in[ otherY * width + sampleX ],
  70                               in[ otherY * width + otherX ],
  71                               dx, 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( 1e20 );
  80
  81 /**
  82  * Distance transform of 1D function using squared distance
  83  */
  84 void DistanceTransform( float *source, float* dest, unsigned int length )
  85 {
  86   int parabolas[length];    // Locations of parabolas in lower envelope
  87   float edge[length + 1];   // Locations of boundaries between parabolas
  88   int rightmost(0);         // Index of rightmost parabola in lower envelope
  89
  90   parabolas[0] = 0;
  91   edge[0] = -MAX_DISTANCE;
  92   edge[1] = +MAX_DISTANCE;
  93   for( unsigned int i = 1; i <= length - 1; i++ )
  94   {
  95     const float initialDistance( source[i] + SQUARE( i ) );
  96     int parabola = parabolas[rightmost];
  97     float newDistance( (initialDistance - (source[parabola] + SQUARE( parabola ))) / (2 * i - 2 * parabola) );
  98     while( newDistance <= edge[rightmost] )
  99     {
 100       rightmost--;
 101       parabola = parabolas[rightmost];
 102       newDistance = (initialDistance - (source[parabola] + SQUARE( parabola ))) / (2 * i - 2 * parabola);
 103     }
 104
 105     rightmost++;
 106     parabolas[rightmost] = i;
 107     edge[rightmost] = newDistance;
 108     edge[rightmost + 1] = MAX_DISTANCE;
 109   }
 110
 111   rightmost = 0;
 112   for( unsigned int i = 0; i <= length - 1; ++i )
 113   {
 114     while( edge[rightmost + 1] < i )
 115     {
 116       ++rightmost;
 117     }
 118     dest[i] = SQUARE( i - parabolas[rightmost] ) + source[parabolas[rightmost]];
 119   }
 120 }
 121
 122 /**
 123  * Distance transform of 2D function using squared distance
 124  */
 125 void DistanceTransform( float* data, unsigned int width, unsigned int height, float* sourceBuffer, float* destBuffer )
 126 {
 127   // transform along columns
 128   for( unsigned int x = 0; x < width; ++x )
 129   {
 130     for( unsigned int y = 0; y < height; ++y )
 131     {
 132       sourceBuffer[y] = data[ y * width + x ];
 133     }
 134
 135     DistanceTransform( sourceBuffer, destBuffer, height );
 136
 137     for( unsigned int y = 0; y < height; y++ )
 138     {
 139       data[y * width + x] = destBuffer[y];
 140     }
 141   }
 142
 143   // transform along rows
 144   for( unsigned int y = 0; y < height; ++y )
 145   {
 146     for( unsigned int x = 0; x < width; ++x )
 147     {
 148       sourceBuffer[x] = data[ y * width + x ];
 149     }
 150
 151     DistanceTransform( sourceBuffer, destBuffer, width );
 152
 153     for( unsigned int x = 0; x < width; x++ )
 154     {
 155       data[y * width + x] = destBuffer[x];
 156     }
 157   }
 158 }
 159
 160 } // namespace
 161
 162 void GenerateDistanceFieldMap(const unsigned char* const imagePixels, const Size& imageSize,
 163                               unsigned char* const distanceMap, const Size& distanceMapSize,
 164                               const float fieldRadius, const unsigned int fieldBorder, bool highQuality)
 165 {
 166   GenerateDistanceFieldMap( imagePixels, imageSize, distanceMap, distanceMapSize, fieldBorder, imageSize, highQuality );
 167 }
 168
 169 void GenerateDistanceFieldMap(const unsigned char* const imagePixels, const Size& imageSize,
 170                               unsigned char* const distanceMap, const Size& distanceMapSize,
 171                               const unsigned int fieldBorder,
 172                               const Vector2& maxSize,
 173                               bool highQuality)
 174 {
 175   // constants to reduce redundant calculations
 176   const int originalWidth( static_cast<int>(imageSize.width) );
 177   const int originalHeight( static_cast<int>(imageSize.height) );
 178   const int paddedWidth( originalWidth + (fieldBorder * 2 ) );
 179   const int paddedHeight( originalHeight + (fieldBorder * 2 ) );
 180   const int scaledWidth( static_cast<int>(distanceMapSize.width) );
 181   const int scaledHeight( static_cast<int>(distanceMapSize.height) );
 182   const int maxWidth( static_cast<int>(maxSize.width) + (fieldBorder * 2 ));
 183   const int maxHeight( static_cast<int>(maxSize.height) + (fieldBorder * 2 ) );
 184
 185   const int bufferLength( std::max( maxWidth, std::max(paddedWidth, scaledWidth) ) *
 186                           std::max( maxHeight, std::max(paddedHeight, scaledHeight) ) );
 187
 188   std::vector<float> outsidePixels( bufferLength, 0.0f );
 189   std::vector<float> insidePixels( bufferLength, 0.0f );
 190
 191   float* outside( outsidePixels.data() );
 192   float* inside( insidePixels.data() );
 193
 194   for( int y = 0; y < paddedHeight; ++y )
 195   {
 196     for ( int x = 0; x < paddedWidth; ++x)
 197     {
 198       if( y < (int)fieldBorder || y >= (paddedHeight - (int)fieldBorder) ||
 199           x < (int)fieldBorder || x >= (paddedWidth - (int)fieldBorder) )
 200       {
 201         outside[ y * paddedWidth + x ] = MAX_DISTANCE;
 202         inside[ y * paddedWidth + x ] = 0.0f;
 203       }
 204       else
 205       {
 206         unsigned int pixel( imagePixels[ (y - fieldBorder) * originalWidth + (x - fieldBorder) ] );
 207         outside[ y * paddedWidth + x ] = (pixel == 0) ? MAX_DISTANCE : SQUARE((255 - pixel) / 255.0f);
 208         inside[ y * paddedWidth + x ] = (pixel == 255) ? MAX_DISTANCE : SQUARE(pixel / 255.0f);
 209       }
 210     }
 211   }
 212
 213   // perform distance transform if high quality requested, else use original figure
 214   if( highQuality )
 215   {
 216     // create temporary buffers for DistanceTransform()
 217     const int tempBufferLength( std::max(paddedWidth, paddedHeight) );
 218     std::vector<float> tempSourceBuffer( tempBufferLength, 0.0f );
 219     std::vector<float> tempDestBuffer( tempBufferLength, 0.0f );
 220
 221     // Perform distance transform for pixels 'outside' the figure
 222     DistanceTransform( outside, paddedWidth, paddedHeight, tempSourceBuffer.data(), tempDestBuffer.data() );
 223
 224     // Perform distance transform for pixels 'inside' the figure
 225     DistanceTransform( inside, paddedWidth, paddedHeight, tempSourceBuffer.data(), tempDestBuffer.data() );
 226   }
 227
 228   // distmap = outside - inside; % Bipolar distance field
 229   for( int y = 0; y < paddedHeight; ++y)
 230   {
 231     for( int x = 0; x < paddedWidth; ++x )
 232     {
 233       const int offset( y * paddedWidth + x );
 234       float pixel( sqrtf(outside[offset]) - sqrtf(inside[offset]) );
 235       pixel = 128.0f + pixel * 16.0f;
 236       pixel = Clamp( pixel, 0.0f, 255.0f );
 237       outside[offset] = (255.0f - pixel) / 255.0f;
 238     }
 239   }
 240
 241   // scale the figure to the distance field tile size
 242   ScaleField( paddedWidth, paddedHeight, outside, scaledWidth, scaledHeight, inside );
 243
 244   // convert from floats to integers
 245   for( int y = 0; y < scaledHeight; ++y )
 246   {
 247     for( int x = 0; x < scaledWidth; ++x )
 248     {
 249       float pixel( inside[ y * scaledWidth + x ] );
 250       distanceMap[y * scaledWidth + x ] = static_cast< unsigned char >(pixel * 255.0f);
 251     }
 252   }
 253 }
 254
 255 } // namespace Dali