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

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