2 * Copyright (c) 2017 Samsung Electronics Co., Ltd.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 #include <dali/devel-api/images/distance-field.h>
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>
39 float Interpolate( float a, float b, float factor )
41 return a * (1.0f - factor) + b * factor;
44 float Bilinear( float a, float b, float c, float d, float dx, float dy )
46 return Interpolate( Interpolate( a, b, dx), Interpolate( c, d, dx ), dy );
49 void ScaleField( int width, int height, float* in, int targetWidth, int targetHeight, float* out )
51 float xScale = static_cast< float >(width) / targetWidth;
52 float yScale = static_cast< float >(height) / targetHeight;
54 // for each row in target
55 for(int y = 0; y < targetHeight; ++y)
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;
61 // for each column in target
62 for (int x = 0; x < targetWidth; ++x)
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;
68 float value = Bilinear( in[ sampleY * width + sampleX ],
69 in[ sampleY * width + otherX ],
70 in[ otherY * width + sampleX ],
71 in[ otherY * width + otherX ],
74 out[y * targetWidth + x] = std::min( value, 1.0f );
79 #define SQUARE(a) ((a) * (a))
80 const float MAX_DISTANCE( 1e20 );
83 * Distance transform of 1D function using squared distance
85 void DistanceTransform( float *source, float* dest, unsigned int length )
87 std::vector<int> parabolas(length); // Locations of parabolas in lower envelope
88 std::vector<float> edge(length + 1); // Locations of boundaries between parabolas
90 int rightmost(0); // Index of rightmost parabola in lower envelope
93 edge[0] = -MAX_DISTANCE;
94 edge[1] = +MAX_DISTANCE;
95 for( unsigned int i = 1; i <= length - 1; i++ )
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] )
103 parabola = parabolas[rightmost];
104 newDistance = (initialDistance - (source[parabola] + SQUARE( parabola ))) / (2 * i - 2 * parabola);
108 parabolas[rightmost] = i;
109 edge[rightmost] = newDistance;
110 edge[rightmost + 1] = MAX_DISTANCE;
114 for( unsigned int i = 0; i <= length - 1; ++i )
116 while( edge[rightmost + 1] < i )
120 dest[i] = SQUARE( static_cast< int >( i ) - parabolas[rightmost] ) + source[parabolas[rightmost]];
125 * Distance transform of 2D function using squared distance
127 void DistanceTransform( float* data, unsigned int width, unsigned int height, float* sourceBuffer, float* destBuffer )
129 // transform along columns
130 for( unsigned int x = 0; x < width; ++x )
132 for( unsigned int y = 0; y < height; ++y )
134 sourceBuffer[y] = data[ y * width + x ];
137 DistanceTransform( sourceBuffer, destBuffer, height );
139 for( unsigned int y = 0; y < height; y++ )
141 data[y * width + x] = destBuffer[y];
145 // transform along rows
146 for( unsigned int y = 0; y < height; ++y )
148 for( unsigned int x = 0; x < width; ++x )
150 sourceBuffer[x] = data[ y * width + x ];
153 DistanceTransform( sourceBuffer, destBuffer, width );
155 for( unsigned int x = 0; x < width; x++ )
157 data[y * width + x] = destBuffer[x];
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)
168 GenerateDistanceFieldMap( imagePixels, imageSize, distanceMap, distanceMapSize, fieldBorder, imageSize, highQuality );
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,
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 ) );
187 const int bufferLength( std::max( maxWidth, std::max(paddedWidth, scaledWidth) ) *
188 std::max( maxHeight, std::max(paddedHeight, scaledHeight) ) );
190 std::vector<float> outsidePixels( bufferLength, 0.0f );
191 std::vector<float> insidePixels( bufferLength, 0.0f );
193 float* outside( outsidePixels.data() );
194 float* inside( insidePixels.data() );
196 for( int y = 0; y < paddedHeight; ++y )
198 for ( int x = 0; x < paddedWidth; ++x)
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 ) ) )
203 outside[ y * paddedWidth + x ] = MAX_DISTANCE;
204 inside[ y * paddedWidth + x ] = 0.0f;
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);
215 // perform distance transform if high quality requested, else use original figure
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 );
223 // Perform distance transform for pixels 'outside' the figure
224 DistanceTransform( outside, paddedWidth, paddedHeight, tempSourceBuffer.data(), tempDestBuffer.data() );
226 // Perform distance transform for pixels 'inside' the figure
227 DistanceTransform( inside, paddedWidth, paddedHeight, tempSourceBuffer.data(), tempDestBuffer.data() );
230 // distmap = outside - inside; % Bipolar distance field
231 for( int y = 0; y < paddedHeight; ++y)
233 for( int x = 0; x < paddedWidth; ++x )
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;
243 // scale the figure to the distance field tile size
244 ScaleField( paddedWidth, paddedHeight, outside, scaledWidth, scaledHeight, inside );
246 // convert from floats to integers
247 for( int y = 0; y < scaledHeight; ++y )
249 for( int x = 0; x < scaledWidth; ++x )
251 float pixel( inside[ y * scaledWidth + x ] );
252 distanceMap[y * scaledWidth + x ] = static_cast< unsigned char >(pixel * 255.0f);