Dali 3D User Interface Engine
distance-field.cpp
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 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
20 
21 // EXTERNAL INCLUDES
22 #include <algorithm>
23 #include <math.h>
24 #include <stdio.h>
25 #include <time.h>
26 
27 // INTERNAL INCLUDES
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 
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( i - parabolas[rightmost] ) + source[parabolas[rightmost]];
120  }
121 }
122 
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 < (int)fieldBorder || y >= (paddedHeight - (int)fieldBorder) ||
200  x < (int)fieldBorder || x >= (paddedWidth - (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
Dali Docs Home
Read more about Dali