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 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
92 edge[0] = -MAX_DISTANCE;
93 edge[1] = +MAX_DISTANCE;
94 for( unsigned int i = 1; i <= length - 1; i++ )
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] )
102 parabola = parabolas[rightmost];
103 newDistance = (initialDistance - (source[parabola] + SQUARE( parabola ))) / (2 * i - 2 * parabola);
107 parabolas[rightmost] = i;
108 edge[rightmost] = newDistance;
109 edge[rightmost + 1] = MAX_DISTANCE;
113 for( unsigned int i = 0; i <= length - 1; ++i )
115 while( edge[rightmost + 1] < i )
119 dest[i] = SQUARE( static_cast< int >( i ) - parabolas[rightmost] ) + source[parabolas[rightmost]];
124 * Distance transform of 2D function using squared distance
126 void DistanceTransform( float* data, unsigned int width, unsigned int height, float* sourceBuffer, float* destBuffer )
128 // transform along columns
129 for( unsigned int x = 0; x < width; ++x )
131 for( unsigned int y = 0; y < height; ++y )
133 sourceBuffer[y] = data[ y * width + x ];
136 DistanceTransform( sourceBuffer, destBuffer, height );
138 for( unsigned int y = 0; y < height; y++ )
140 data[y * width + x] = destBuffer[y];
144 // transform along rows
145 for( unsigned int y = 0; y < height; ++y )
147 for( unsigned int x = 0; x < width; ++x )
149 sourceBuffer[x] = data[ y * width + x ];
152 DistanceTransform( sourceBuffer, destBuffer, width );
154 for( unsigned int x = 0; x < width; x++ )
156 data[y * width + x] = destBuffer[x];
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)
167 GenerateDistanceFieldMap( imagePixels, imageSize, distanceMap, distanceMapSize, fieldBorder, imageSize, highQuality );
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,
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 ) );
186 const int bufferLength( std::max( maxWidth, std::max(paddedWidth, scaledWidth) ) *
187 std::max( maxHeight, std::max(paddedHeight, scaledHeight) ) );
189 std::vector<float> outsidePixels( bufferLength, 0.0f );
190 std::vector<float> insidePixels( bufferLength, 0.0f );
192 float* outside( outsidePixels.data() );
193 float* inside( insidePixels.data() );
195 for( int y = 0; y < paddedHeight; ++y )
197 for ( int x = 0; x < paddedWidth; ++x)
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 ) ) )
202 outside[ y * paddedWidth + x ] = MAX_DISTANCE;
203 inside[ y * paddedWidth + x ] = 0.0f;
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);
214 // perform distance transform if high quality requested, else use original figure
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 );
222 // Perform distance transform for pixels 'outside' the figure
223 DistanceTransform( outside, paddedWidth, paddedHeight, tempSourceBuffer.data(), tempDestBuffer.data() );
225 // Perform distance transform for pixels 'inside' the figure
226 DistanceTransform( inside, paddedWidth, paddedHeight, tempSourceBuffer.data(), tempDestBuffer.data() );
229 // distmap = outside - inside; % Bipolar distance field
230 for( int y = 0; y < paddedHeight; ++y)
232 for( int x = 0; x < paddedWidth; ++x )
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;
242 // scale the figure to the distance field tile size
243 ScaleField( paddedWidth, paddedHeight, outside, scaledWidth, scaledHeight, inside );
245 // convert from floats to integers
246 for( int y = 0; y < scaledHeight; ++y )
248 for( int x = 0; x < scaledWidth; ++x )
250 float pixel( inside[ y * scaledWidth + x ] );
251 distanceMap[y * scaledWidth + x ] = static_cast< unsigned char >(pixel * 255.0f);