The Ecere SDK - sdk/blob - ecere/src/gfx/imgDistMap.ec

   1 import "instance"
   2
   3 #include <math.h>
   4
   5 // Based on The ‘‘dead reckoning’’ signed distance transform
   6 // by George J. Grevera
   7
   8 struct MapDistMapPoint
   9 {
  10   float distance;
  11   float x, y;
  12   float bias;
  13 };
  14
  15 #define IMGDISTMAP_SQRT2 (1.41421356237f)
  16 #define IMGDISTMAP_SQRT5 (2.2360679775f)
  17 #define IMGDISTMAP_SQRT10 (3.16227766017f)
  18 #define IMGDISTMAP_SQRT13 (3.60555127546f)
  19
  20
  21 #if defined(__GNUC__)
  22  #define ALWAYS_INLINE __attribute__((always_inline))
  23 #else
  24  #define ALWAYS_INLINE
  25 #endif
  26
  27
  28 static inline ALWAYS_INLINE void imgDistMapCheck( MapDistMapPoint pt, float fx, float fy, MapDistMapPoint ptref, float delta )
  29 {
  30   float dx, dy;
  31   if( ( ptref.distance + delta ) < pt.distance )
  32   {
  33     pt.x = ptref.x;
  34     pt.y = ptref.y;
  35     dx = ptref.x - fx;
  36     dy = ptref.y - fy;
  37     pt.distance = sqrtf( ( dx * dx ) + ( dy * dy ) ) + ptref.bias;
  38     pt.bias = ptref.bias;
  39   }
  40 }
  41
  42 #define IMGDIST_OPFLAGS_XP1_SHIFT (0)
  43 #define IMGDIST_OPFLAGS_XP2_SHIFT (1)
  44 #define IMGDIST_OPFLAGS_XP3_SHIFT (2)
  45 #define IMGDIST_OPFLAGS_XM1_SHIFT (3)
  46 #define IMGDIST_OPFLAGS_XM2_SHIFT (4)
  47 #define IMGDIST_OPFLAGS_XM3_SHIFT (5)
  48 #define IMGDIST_OPFLAGS_YP1_SHIFT (6)
  49 #define IMGDIST_OPFLAGS_YP2_SHIFT (7)
  50 #define IMGDIST_OPFLAGS_YP3_SHIFT (8)
  51 #define IMGDIST_OPFLAGS_YM1_SHIFT (9)
  52 #define IMGDIST_OPFLAGS_YM2_SHIFT (10)
  53 #define IMGDIST_OPFLAGS_YM3_SHIFT (11)
  54
  55 #define IMGDIST_OPFLAGS_XP1 (1<<IMGDIST_OPFLAGS_XP1_SHIFT)
  56 #define IMGDIST_OPFLAGS_XP2 (1<<IMGDIST_OPFLAGS_XP2_SHIFT)
  57 #define IMGDIST_OPFLAGS_XP3 (1<<IMGDIST_OPFLAGS_XP3_SHIFT)
  58 #define IMGDIST_OPFLAGS_XM1 (1<<IMGDIST_OPFLAGS_XM1_SHIFT)
  59 #define IMGDIST_OPFLAGS_XM2 (1<<IMGDIST_OPFLAGS_XM2_SHIFT)
  60 #define IMGDIST_OPFLAGS_XM3 (1<<IMGDIST_OPFLAGS_XM3_SHIFT)
  61 #define IMGDIST_OPFLAGS_YP1 (1<<IMGDIST_OPFLAGS_YP1_SHIFT)
  62 #define IMGDIST_OPFLAGS_YP2 (1<<IMGDIST_OPFLAGS_YP2_SHIFT)
  63 #define IMGDIST_OPFLAGS_YP3 (1<<IMGDIST_OPFLAGS_YP3_SHIFT)
  64 #define IMGDIST_OPFLAGS_YM1 (1<<IMGDIST_OPFLAGS_YM1_SHIFT)
  65 #define IMGDIST_OPFLAGS_YM2 (1<<IMGDIST_OPFLAGS_YM2_SHIFT)
  66 #define IMGDIST_OPFLAGS_YM3 (1<<IMGDIST_OPFLAGS_YM3_SHIFT)
  67
  68
  69 static inline ALWAYS_INLINE int imgDistMapForwardOpFlags( int x, int y, int sizex, int sizey )
  70 {
  71   int opflags;
  72   opflags = 0;
  73   opflags |= ( x >= 1 ) << IMGDIST_OPFLAGS_XM1_SHIFT;
  74   opflags |= ( x >= 2 ) << IMGDIST_OPFLAGS_XM2_SHIFT;
  75   opflags |= ( x >= 3 ) << IMGDIST_OPFLAGS_XM3_SHIFT;
  76   opflags |= ( y >= 1 ) << IMGDIST_OPFLAGS_YM1_SHIFT;
  77   opflags |= ( y >= 2 ) << IMGDIST_OPFLAGS_YM2_SHIFT;
  78   opflags |= ( y >= 3 ) << IMGDIST_OPFLAGS_YM3_SHIFT;
  79   opflags |= ( x < (sizex-1) ) << IMGDIST_OPFLAGS_XP1_SHIFT;
  80   opflags |= ( x < (sizex-2) ) << IMGDIST_OPFLAGS_XP2_SHIFT;
  81   opflags |= ( x < (sizex-3) ) << IMGDIST_OPFLAGS_XP3_SHIFT;
  82   return opflags;
  83 }
  84
  85 static void imgDistMapForwardClamp( MapDistMapPoint *p, float fx, float fy, int x, int y, int sizex, int opflags )
  86 {
  87   if( opflags & IMGDIST_OPFLAGS_XM1 )
  88     imgDistMapCheck( p, fx, fy, p+( 0*sizex)+(-1), 1.0f );
  89   if( opflags & IMGDIST_OPFLAGS_YM1 )
  90   {
  91     imgDistMapCheck( p, fx, fy, p+(-1*sizex)+( 0), 1.0f );
  92     if( opflags & IMGDIST_OPFLAGS_XM1 )
  93       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+(-1), IMGDISTMAP_SQRT2 );
  94     if( opflags & IMGDIST_OPFLAGS_XP1 )
  95       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+( 1), IMGDISTMAP_SQRT2 );
  96     if( opflags & IMGDIST_OPFLAGS_XM2 )
  97       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+(-2), IMGDISTMAP_SQRT5 );
  98     if( opflags & IMGDIST_OPFLAGS_XP2 )
  99       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+( 2), IMGDISTMAP_SQRT5 );
 100     if( opflags & IMGDIST_OPFLAGS_XM3 )
 101       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+(-3), IMGDISTMAP_SQRT10 );
 102     if( opflags & IMGDIST_OPFLAGS_XP3 )
 103       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+( 3), IMGDISTMAP_SQRT10 );
 104   }
 105   if( opflags & IMGDIST_OPFLAGS_YM2 )
 106   {
 107     if( opflags & IMGDIST_OPFLAGS_XM1 )
 108       imgDistMapCheck( p, fx, fy, p+(-2*sizex)+(-1), IMGDISTMAP_SQRT5 );
 109     if( opflags & IMGDIST_OPFLAGS_XP1 )
 110       imgDistMapCheck( p, fx, fy, p+(-2*sizex)+( 1), IMGDISTMAP_SQRT5 );
 111     if( opflags & IMGDIST_OPFLAGS_XM3 )
 112       imgDistMapCheck( p, fx, fy, p+(-2*sizex)+(-3), IMGDISTMAP_SQRT13 );
 113     if( opflags & IMGDIST_OPFLAGS_XP3 )
 114       imgDistMapCheck( p, fx, fy, p+(-2*sizex)+( 3), IMGDISTMAP_SQRT13 );
 115   }
 116   if( opflags & IMGDIST_OPFLAGS_YM3 )
 117   {
 118     if( opflags & IMGDIST_OPFLAGS_XM1 )
 119       imgDistMapCheck( p, fx, fy, p+(-3*sizex)+(-1), IMGDISTMAP_SQRT10 );
 120     if( opflags & IMGDIST_OPFLAGS_XP1 )
 121       imgDistMapCheck( p, fx, fy, p+(-3*sizex)+( 1), IMGDISTMAP_SQRT10 );
 122     if( opflags & IMGDIST_OPFLAGS_XM2 )
 123       imgDistMapCheck( p, fx, fy, p+(-3*sizex)+(-2), IMGDISTMAP_SQRT13 );
 124     if( opflags & IMGDIST_OPFLAGS_XP2 )
 125       imgDistMapCheck( p, fx, fy, p+(-3*sizex)+( 2), IMGDISTMAP_SQRT13 );
 126   }
 127 }
 128
 129 static inline ALWAYS_INLINE int imgDistMapBackwardOpFlags( int x, int y, int sizex, int sizey )
 130 {
 131   int opflags;
 132   opflags = 0;
 133   opflags |= ( x >= 1 ) << IMGDIST_OPFLAGS_XM1_SHIFT;
 134   opflags |= ( x >= 2 ) << IMGDIST_OPFLAGS_XM2_SHIFT;
 135   opflags |= ( x >= 3 ) << IMGDIST_OPFLAGS_XM3_SHIFT;
 136   opflags |= ( x < (sizex-1) ) << IMGDIST_OPFLAGS_XP1_SHIFT;
 137   opflags |= ( x < (sizex-2) ) << IMGDIST_OPFLAGS_XP2_SHIFT;
 138   opflags |= ( x < (sizex-3) ) << IMGDIST_OPFLAGS_XP3_SHIFT;
 139   opflags |= ( y < (sizey-1) ) << IMGDIST_OPFLAGS_YP1_SHIFT;
 140   opflags |= ( y < (sizey-2) ) << IMGDIST_OPFLAGS_YP2_SHIFT;
 141   opflags |= ( y < (sizey-3) ) << IMGDIST_OPFLAGS_YP3_SHIFT;
 142   return opflags;
 143 }
 144
 145 static void imgDistMapBackwardClamp( MapDistMapPoint *p, float fx, float fy, int x, int y, int sizex, int opflags )
 146 {
 147   if( opflags & IMGDIST_OPFLAGS_XP1 )
 148     imgDistMapCheck( p, fx, fy, p+( 0*sizex)+( 1), 1.0f );
 149   if( opflags & IMGDIST_OPFLAGS_YP1 )
 150   {
 151     imgDistMapCheck( p, fx, fy, p+( 1*sizex)+( 0), 1.0f );
 152     if( opflags & IMGDIST_OPFLAGS_XM1 )
 153       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+(-1), IMGDISTMAP_SQRT2 );
 154     if( opflags & IMGDIST_OPFLAGS_XP1 )
 155       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+( 1), IMGDISTMAP_SQRT2 );
 156     if( opflags & IMGDIST_OPFLAGS_XM2 )
 157       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+(-2), IMGDISTMAP_SQRT5 );
 158     if( opflags & IMGDIST_OPFLAGS_XP2 )
 159       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+( 2), IMGDISTMAP_SQRT5 );
 160     if( opflags & IMGDIST_OPFLAGS_XM3 )
 161       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+(-3), IMGDISTMAP_SQRT10 );
 162     if( opflags & IMGDIST_OPFLAGS_XP3 )
 163       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+( 3), IMGDISTMAP_SQRT10 );
 164   }
 165   if( opflags & IMGDIST_OPFLAGS_YP2 )
 166   {
 167     if( opflags & IMGDIST_OPFLAGS_XM1 )
 168       imgDistMapCheck( p, fx, fy, p+( 2*sizex)+(-1), IMGDISTMAP_SQRT5 );
 169     if( opflags & IMGDIST_OPFLAGS_XP1 )
 170       imgDistMapCheck( p, fx, fy, p+( 2*sizex)+( 1), IMGDISTMAP_SQRT5 );
 171     if( opflags & IMGDIST_OPFLAGS_XM3 )
 172       imgDistMapCheck( p, fx, fy, p+( 2*sizex)+(-3), IMGDISTMAP_SQRT13 );
 173     if( opflags & IMGDIST_OPFLAGS_XP3 )
 174       imgDistMapCheck( p, fx, fy, p+( 2*sizex)+( 3), IMGDISTMAP_SQRT13 );
 175   }
 176   if( opflags & IMGDIST_OPFLAGS_YP3 )
 177   {
 178     if( opflags & IMGDIST_OPFLAGS_XM1 )
 179       imgDistMapCheck( p, fx, fy, p+( 3*sizex)+(-1), IMGDISTMAP_SQRT10 );
 180     if( opflags & IMGDIST_OPFLAGS_XP1 )
 181       imgDistMapCheck( p, fx, fy, p+( 3*sizex)+( 1), IMGDISTMAP_SQRT10 );
 182     if( opflags & IMGDIST_OPFLAGS_XM2 )
 183       imgDistMapCheck( p, fx, fy, p+( 3*sizex)+(-2), IMGDISTMAP_SQRT13 );
 184     if( opflags & IMGDIST_OPFLAGS_XP2 )
 185       imgDistMapCheck( p, fx, fy, p+( 3*sizex)+( 2), IMGDISTMAP_SQRT13 );
 186   }
 187 }
 188
 189
 190 // The outer edge must be all zeroes
 191 void imgDistMapBuild( float *distancemap, byte *src, int sizex, int sizey, int srcbytesperpixel, int srcbytesperline )
 192 {
 193   int x, y, mapindex, srcindex;
 194   byte pixel;
 195   float fx, fy, bias, maxdistance;
 196   MapDistMapPoint *ptmap;
 197   MapDistMapPoint *p;
 198
 199   if( ( sizex < 4 ) || ( sizey < 4 ) )
 200     return;
 201
 202   ptmap = new MapDistMapPoint[sizex * sizey];
 203
 204   maxdistance = sizex + sizey;
 205   mapindex = 0;
 206   for( y = 0 ; y < sizey ; y++ )
 207   {
 208     srcindex = y * srcbytesperline;
 209     for( x = 0 ; x < sizex ; x++ )
 210     {
 211       pixel = src[ srcindex ];
 212       if( pixel )
 213       {
 214         fx = (float)x;
 215         fy = (float)y;
 216         bias = 1.0f - ( (float)pixel * (1.0f/255.0f) );
 217         ptmap[mapindex].distance = bias;
 218         ptmap[mapindex].x = fx;
 219         ptmap[mapindex].y = fy;
 220         ptmap[mapindex].bias = bias;
 221       }
 222       else
 223       {
 224         ptmap[mapindex].distance = maxdistance;
 225         ptmap[mapindex].x = -1.0f;
 226         ptmap[mapindex].y = -1.0f;
 227         ptmap[mapindex].bias = 0.0f;
 228       }
 229       mapindex++;
 230       srcindex += srcbytesperpixel;
 231     }
 232   }
 233
 234   // Forward pass
 235   for( y = 0 ; y < 3 ; y++ )
 236   {
 237     mapindex = y * sizex;
 238     for( x = 0 ; x < sizex ; x++ )
 239     {
 240       p = &ptmap[mapindex];
 241       fx = (float)x;
 242       fy = (float)y;
 243       imgDistMapForwardClamp( p, fx, fy, x, y, sizex, imgDistMapForwardOpFlags( x, y, sizex, sizey ) );
 244       mapindex++;
 245     }
 246   }
 247   for( ; y < sizey - 3 ; y++ )
 248   {
 249     mapindex = y * sizex;
 250     for( x = 0 ; x < 3 ; x++ )
 251     {
 252       p = &ptmap[mapindex];
 253       fx = (float)x;
 254       fy = (float)y;
 255       imgDistMapForwardClamp( p, fx, fy, x, y, sizex, imgDistMapForwardOpFlags( x, y, sizex, sizey ) );
 256       mapindex++;
 257     }
 258     for( x = 3 ; x < sizex - 3 ; x++ )
 259     {
 260       p = &ptmap[mapindex];
 261       fx = (float)x;
 262       fy = (float)y;
 263
 264       imgDistMapCheck( p, fx, fy, p+( 0*sizex)+(-1), 1.0f );
 265       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+( 0), 1.0f );
 266       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+(-1), IMGDISTMAP_SQRT2 );
 267       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+( 1), IMGDISTMAP_SQRT2 );
 268
 269       imgDistMapCheck( p, fx, fy, p+(-2*sizex)+(-1), IMGDISTMAP_SQRT5 );
 270       imgDistMapCheck( p, fx, fy, p+(-2*sizex)+( 1), IMGDISTMAP_SQRT5 );
 271       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+(-2), IMGDISTMAP_SQRT5 );
 272       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+( 2), IMGDISTMAP_SQRT5 );
 273
 274       imgDistMapCheck( p, fx, fy, p+(-3*sizex)+(-1), IMGDISTMAP_SQRT10 );
 275       imgDistMapCheck( p, fx, fy, p+(-3*sizex)+( 1), IMGDISTMAP_SQRT10 );
 276       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+(-3), IMGDISTMAP_SQRT10 );
 277       imgDistMapCheck( p, fx, fy, p+(-1*sizex)+( 3), IMGDISTMAP_SQRT10 );
 278
 279       imgDistMapCheck( p, fx, fy, p+(-3*sizex)+(-2), IMGDISTMAP_SQRT13 );
 280       imgDistMapCheck( p, fx, fy, p+(-3*sizex)+( 2), IMGDISTMAP_SQRT13 );
 281       imgDistMapCheck( p, fx, fy, p+(-2*sizex)+(-3), IMGDISTMAP_SQRT13 );
 282       imgDistMapCheck( p, fx, fy, p+(-2*sizex)+( 3), IMGDISTMAP_SQRT13 );
 283       mapindex++;
 284     }
 285     for( ; x < sizex ; x++ )
 286     {
 287       p = &ptmap[mapindex];
 288       fx = (float)x;
 289       fy = (float)y;
 290       imgDistMapForwardClamp( p, fx, fy, x, y, sizex, imgDistMapForwardOpFlags( x, y, sizex, sizey ) );
 291       mapindex++;
 292     }
 293   }
 294   for( ; y < sizey ; y++ )
 295   {
 296     mapindex = y * sizex;
 297     for( x = 0 ; x < sizex ; x++ )
 298     {
 299       p = &ptmap[mapindex];
 300       fx = (float)x;
 301       fy = (float)y;
 302       imgDistMapForwardClamp( p, fx, fy, x, y, sizex, imgDistMapForwardOpFlags( x, y, sizex, sizey ) );
 303       mapindex++;
 304     }
 305   }
 306
 307   // Backward pass
 308   for( y = sizey - 1 ; y >= sizey - 3 ; y-- )
 309   {
 310     mapindex = ( y * sizex ) + ( sizex - 1 );
 311     for( x = sizex - 1 ; x >= 0 ; x-- )
 312     {
 313       p = &ptmap[mapindex];
 314       fx = (float)x;
 315       fy = (float)y;
 316       imgDistMapBackwardClamp( p, fx, fy, x, y, sizex, imgDistMapBackwardOpFlags( x, y, sizex, sizey ) );
 317       distancemap[ mapindex ] = p->distance;
 318       mapindex--;
 319     }
 320   }
 321   for( ; y >= 3 ; y-- )
 322   {
 323     mapindex = ( y * sizex ) + ( sizex - 1 );
 324     for( x = sizex - 1 ; x >= sizex - 3 ; x-- )
 325     {
 326       p = &ptmap[mapindex];
 327       fx = (float)x;
 328       fy = (float)y;
 329       imgDistMapBackwardClamp( p, fx, fy, x, y, sizex, imgDistMapBackwardOpFlags( x, y, sizex, sizey ) );
 330       distancemap[ mapindex ] = p->distance;
 331       mapindex--;
 332     }
 333     for( ; x >= 3 ; x-- )
 334     {
 335       p = &ptmap[mapindex];
 336       fx = (float)x;
 337       fy = (float)y;
 338
 339       imgDistMapCheck( p, fx, fy, p+( 0*sizex)+( 1), 1.0f );
 340       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+( 0), 1.0f );
 341       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+(-1), IMGDISTMAP_SQRT2 );
 342       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+( 1), IMGDISTMAP_SQRT2 );
 343
 344       imgDistMapCheck( p, fx, fy, p+( 2*sizex)+(-1), IMGDISTMAP_SQRT5 );
 345       imgDistMapCheck( p, fx, fy, p+( 2*sizex)+( 1), IMGDISTMAP_SQRT5 );
 346       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+(-2), IMGDISTMAP_SQRT5 );
 347       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+( 2), IMGDISTMAP_SQRT5 );
 348
 349       imgDistMapCheck( p, fx, fy, p+( 3*sizex)+(-1), IMGDISTMAP_SQRT10 );
 350       imgDistMapCheck( p, fx, fy, p+( 3*sizex)+( 1), IMGDISTMAP_SQRT10 );
 351       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+(-3), IMGDISTMAP_SQRT10 );
 352       imgDistMapCheck( p, fx, fy, p+( 1*sizex)+( 3), IMGDISTMAP_SQRT10 );
 353
 354       imgDistMapCheck( p, fx, fy, p+( 3*sizex)+(-2), IMGDISTMAP_SQRT13 );
 355       imgDistMapCheck( p, fx, fy, p+( 3*sizex)+( 2), IMGDISTMAP_SQRT13 );
 356       imgDistMapCheck( p, fx, fy, p+( 2*sizex)+(-3), IMGDISTMAP_SQRT13 );
 357       imgDistMapCheck( p, fx, fy, p+( 2*sizex)+( 3), IMGDISTMAP_SQRT13 );
 358
 359       distancemap[ mapindex ] = p->distance;
 360       mapindex--;
 361     }
 362     for( ; x >= 0 ; x-- )
 363     {
 364       p = &ptmap[mapindex];
 365       fx = (float)x;
 366       fy = (float)y;
 367       imgDistMapBackwardClamp( p, fx, fy, x, y, sizex, imgDistMapBackwardOpFlags( x, y, sizex, sizey ) );
 368       distancemap[ mapindex ] = p->distance;
 369       mapindex--;
 370     }
 371   }
 372   for( ; y >= 0 ; y-- )
 373   {
 374     mapindex = ( y * sizex ) + ( sizex - 1 );
 375     for( x = sizex - 1 ; x >= 0 ; x-- )
 376     {
 377       p = &ptmap[mapindex];
 378       fx = (float)x;
 379       fy = (float)y;
 380       imgDistMapBackwardClamp( p, fx, fy, x, y, sizex, imgDistMapBackwardOpFlags( x, y, sizex, sizey ) );
 381       distancemap[ mapindex ] = p->distance;
 382       mapindex--;
 383     }
 384   }
 385
 386   delete ptmap;
 387 }