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

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