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

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