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   std::vector<int> parabolas(length);    // Locations of parabolas in lower envelope
  88   std::vector<float> edge(length + 1);   // Locations of boundaries between parabolas
  89
  90   int rightmost(0);         // Index of rightmost parabola in lower envelope
  91
  92   parabolas[0] = 0;
  93   edge[0] = -MAX_DISTANCE;
  94   edge[1] = +MAX_DISTANCE;
  95   for( unsigned int i = 1; i <= length - 1; i++ )
  96   {
  97     const float initialDistance( source[i] + SQUARE( i ) );
  98     int parabola = parabolas[rightmost];
  99     float newDistance( (initialDistance - (source[parabola] + SQUARE( parabola ))) / (2 * i - 2 * parabola) );
 100     while( rightmost > 0 && newDistance <= edge[rightmost] )
 101     {
 102       rightmost--;
 103       parabola = parabolas[rightmost];
 104       newDistance = (initialDistance - (source[parabola] + SQUARE( parabola ))) / (2 * i - 2 * parabola);
 105     }
 106
 107     rightmost++;
 108     parabolas[rightmost] = i;
 109     edge[rightmost] = newDistance;
 110     edge[rightmost + 1] = MAX_DISTANCE;
 111   }
 112
 113   rightmost = 0;
 114   for( unsigned int i = 0; i <= length - 1; ++i )
 115   {
 116     while( edge[rightmost + 1] < i )
 117     {
 118       ++rightmost;
 119     }
 120     dest[i] = SQUARE( static_cast< int >( i ) - parabolas[rightmost] ) + source[parabolas[rightmost]];
 121   }
 122 }
 123
 124 /**
 125  * Distance transform of 2D function using squared distance
 126  */
 127 void DistanceTransform( float* data, unsigned int width, unsigned int height, float* sourceBuffer, float* destBuffer )
 128 {
 129   // transform along columns
 130   for( unsigned int x = 0; x < width; ++x )
 131   {
 132     for( unsigned int y = 0; y < height; ++y )
 133     {
 134       sourceBuffer[y] = data[ y * width + x ];
 135     }
 136
 137     DistanceTransform( sourceBuffer, destBuffer, height );
 138
 139     for( unsigned int y = 0; y < height; y++ )
 140     {
 141       data[y * width + x] = destBuffer[y];
 142     }
 143   }
 144
 145   // transform along rows
 146   for( unsigned int y = 0; y < height; ++y )
 147   {
 148     for( unsigned int x = 0; x < width; ++x )
 149     {
 150       sourceBuffer[x] = data[ y * width + x ];
 151     }
 152
 153     DistanceTransform( sourceBuffer, destBuffer, width );
 154
 155     for( unsigned int x = 0; x < width; x++ )
 156     {
 157       data[y * width + x] = destBuffer[x];
 158     }
 159   }
 160 }
 161
 162 } // namespace
 163
 164 void GenerateDistanceFieldMap(const unsigned char* const imagePixels, const Size& imageSize,
 165                               unsigned char* const distanceMap, const Size& distanceMapSize,
 166                               const float fieldRadius, const unsigned int fieldBorder, bool highQuality)
 167 {
 168   GenerateDistanceFieldMap( imagePixels, imageSize, distanceMap, distanceMapSize, fieldBorder, imageSize, highQuality );
 169 }
 170
 171 void GenerateDistanceFieldMap(const unsigned char* const imagePixels, const Size& imageSize,
 172                               unsigned char* const distanceMap, const Size& distanceMapSize,
 173                               const unsigned int fieldBorder,
 174                               const Vector2& maxSize,
 175                               bool highQuality)
 176 {
 177   // constants to reduce redundant calculations
 178   const int originalWidth( static_cast<int>(imageSize.width) );
 179   const int originalHeight( static_cast<int>(imageSize.height) );
 180   const int paddedWidth( originalWidth + (fieldBorder * 2 ) );
 181   const int paddedHeight( originalHeight + (fieldBorder * 2 ) );
 182   const int scaledWidth( static_cast<int>(distanceMapSize.width) );
 183   const int scaledHeight( static_cast<int>(distanceMapSize.height) );
 184   const int maxWidth( static_cast<int>(maxSize.width) + (fieldBorder * 2 ));
 185   const int maxHeight( static_cast<int>(maxSize.height) + (fieldBorder * 2 ) );
 186
 187   const int bufferLength( std::max( maxWidth, std::max(paddedWidth, scaledWidth) ) *
 188                           std::max( maxHeight, std::max(paddedHeight, scaledHeight) ) );
 189
 190   std::vector<float> outsidePixels( bufferLength, 0.0f );
 191   std::vector<float> insidePixels( bufferLength, 0.0f );
 192
 193   float* outside( outsidePixels.data() );
 194   float* inside( insidePixels.data() );
 195
 196   for( int y = 0; y < paddedHeight; ++y )
 197   {
 198     for ( int x = 0; x < paddedWidth; ++x)
 199     {
 200       if( y < static_cast< int >( fieldBorder ) || y >= ( paddedHeight - static_cast< int >( fieldBorder ) ) ||
 201           x < static_cast< int >( fieldBorder ) || x >= ( paddedWidth - static_cast< int >( fieldBorder ) ) )
 202       {
 203         outside[ y * paddedWidth + x ] = MAX_DISTANCE;
 204         inside[ y * paddedWidth + x ] = 0.0f;
 205       }
 206       else
 207       {
 208         unsigned int pixel( imagePixels[ (y - fieldBorder) * originalWidth + (x - fieldBorder) ] );
 209         outside[ y * paddedWidth + x ] = (pixel == 0) ? MAX_DISTANCE : SQUARE((255 - pixel) / 255.0f);
 210         inside[ y * paddedWidth + x ] = (pixel == 255) ? MAX_DISTANCE : SQUARE(pixel / 255.0f);
 211       }
 212     }
 213   }
 214
 215   // perform distance transform if high quality requested, else use original figure
 216   if( highQuality )
 217   {
 218     // create temporary buffers for DistanceTransform()
 219     const int tempBufferLength( std::max(paddedWidth, paddedHeight) );
 220     std::vector<float> tempSourceBuffer( tempBufferLength, 0.0f );
 221     std::vector<float> tempDestBuffer( tempBufferLength, 0.0f );
 222
 223     // Perform distance transform for pixels 'outside' the figure
 224     DistanceTransform( outside, paddedWidth, paddedHeight, tempSourceBuffer.data(), tempDestBuffer.data() );
 225
 226     // Perform distance transform for pixels 'inside' the figure
 227     DistanceTransform( inside, paddedWidth, paddedHeight, tempSourceBuffer.data(), tempDestBuffer.data() );
 228   }
 229
 230   // distmap = outside - inside; % Bipolar distance field
 231   for( int y = 0; y < paddedHeight; ++y)
 232   {
 233     for( int x = 0; x < paddedWidth; ++x )
 234     {
 235       const int offset( y * paddedWidth + x );
 236       float pixel( sqrtf(outside[offset]) - sqrtf(inside[offset]) );
 237       pixel = 128.0f + pixel * 16.0f;
 238       pixel = Clamp( pixel, 0.0f, 255.0f );
 239       outside[offset] = (255.0f - pixel) / 255.0f;
 240     }
 241   }
 242
 243   // scale the figure to the distance field tile size
 244   ScaleField( paddedWidth, paddedHeight, outside, scaledWidth, scaledHeight, inside );
 245
 246   // convert from floats to integers
 247   for( int y = 0; y < scaledHeight; ++y )
 248   {
 249     for( int x = 0; x < scaledWidth; ++x )
 250     {
 251       float pixel( inside[ y * scaledWidth + x ] );
 252       distanceMap[y * scaledWidth + x ] = static_cast< unsigned char >(pixel * 255.0f);
 253     }
 254   }
 255 }
 256
 257 } // namespace Dali