s2dbpath.c

Go to the documentation of this file.

#include "s2dbpath.h"

enum{UP,DOWN,LEFT,RIGHT};

#ifdef DEBUG
BOOL DebugInside(
 LPBYTE *rows,
 RECT *rc,
 LONG x,
 LONG y,
 int target,
 int line
){
 ASSERT(x>=rc->left);
 ASSERT(y>=rc->top);
 ASSERT(x<rc->right);
 ASSERT(y<rc->bottom);
 if(x<rc->left||x>=rc->right
  ||y<rc->top||y>=rc->bottom){
  DebugOut("assertion violated at line %d",line);
 }
 return DibGetPixel1(rows,x,y)==target;
}

#define INSIDE(x,y) DebugInside(rows,rc,x,y,target,__LINE__)
#else
#define INSIDE(x,y) (DibGetPixel1(rows,x,y)==target)
#endif

static void TraceShape(
 LPBYTE *rows,
 RECT *rc,
 LONG x,
 LONG y,
 int target,
 PRTL_BITMAP bits,
 ITEMARRAY *path
){
 // Start from the right, then go clockwise around
 // the path
 int direction=RIGHT;
 LONG xBegin=x;
 LONG yBegin=y;
 LONG xLast=x;
 LONG yLast=y;
 LONG right1=rc->right-1;
 LONG bottom1=rc->bottom-1;
 PathMoveTo(path,x,y);
 do{
  ASSERT(x>=rc->left);
  ASSERT(y>=rc->top);
  ASSERT(x<=rc->right);
  ASSERT(y<=rc->bottom);
//  DebugOut("%d | %d %d [%d %d]",direction,xLast,yLast,xBegin,yBegin);
  switch(direction){
   case RIGHT:
    xLast=x+1;
    ASSERT(x<rc->right);
    if(x!=right1&&INSIDE(x+1,y)){
     if(y!=rc->top&&INSIDE(x+1,y-1)){
      PathLineTo(path,xLast,yLast);
      direction=UP;        
     }
    } else {
     PathLineTo(path,xLast,yLast);
     direction=DOWN;
    }
    x++;
    break;
   case LEFT:
    xLast=x-1;
    ASSERT(x>rc->left);
    if(x>rc->left+1&&
       y!=rc->top&&INSIDE(x-2,y-1)){
     if(y!=rc->bottom&&INSIDE(x-2,y)){
      PathLineTo(path,xLast,yLast);
      direction=DOWN;
     }
    } else {
     PathLineTo(path,xLast,yLast);
     direction=UP;
    }
    x--;
    break;
   case DOWN:
    yLast=y+1;
    ASSERT(x>rc->left);
    if(y!=bottom1&&INSIDE(x-1,y+1)){
     if(x!=rc->right&&INSIDE(x,y+1)){
      PathLineTo(path,xLast,yLast);
      direction=RIGHT;
     }
    } else {
     PathLineTo(path,xLast,yLast);
     direction=LEFT;
    }
    y++;
    break;
   case UP:
    yLast=y-1;
    ASSERT(x<rc->right);
    if(y>rc->top+1&&INSIDE(x,y-2)){
     if(x!=rc->left&&INSIDE(x-1,y-2)){
      PathLineTo(path,xLast,yLast);
      direction=LEFT;
     }
    } else {
     PathLineTo(path,xLast,yLast);
     direction=RIGHT;
    }
    y--;
    break;
  }
 } while(x!=xBegin||y!=yBegin);
 PathClose(path);
}

static void TraceShapeInner(
 LPBYTE *rows,
 RECT *rc,
 LONG x,
 LONG y,
 int target,
 PRTL_BITMAP bits,
 ITEMARRAY *path
){
 // Start down, then go clockwise around
 // the path
 int direction=DOWN;
 LONG xBegin=x;
 LONG yBegin=y;
 LONG xLast=x;
 LONG yLast=y;
 LONG right1=rc->right-1;
 LONG bottom1=rc->bottom-1;
 PathMoveTo(path,x,y);
 do{
  ASSERT(x>=rc->left);
  ASSERT(y>=rc->top);
  ASSERT(x<=rc->right);
  ASSERT(y<=rc->bottom);
  switch(direction){
   case RIGHT:
    xLast=x+1;
    ASSERT(x<rc->right);
    if(x!=right1&&y!=rc->top&&INSIDE(x+1,y-1)){
     if(y!=rc->bottom&&INSIDE(x+1,y)){
      PathLineTo(path,xLast,yLast);
      direction=DOWN;        
     }
    } else {
     PathLineTo(path,xLast,yLast);
     direction=UP;
    }
    x++;
    break;
   case LEFT:
    xLast=x-1;
    ASSERT(x>rc->left);
    if(x>rc->left+1&&y!=rc->bottom&&INSIDE(x-2,y)){
     if(y!=rc->top&&INSIDE(x-2,y-1)){
      PathLineTo(path,xLast,yLast);
      direction=UP;
     }
    } else {
     PathLineTo(path,xLast,yLast);
     direction=DOWN;
    }
    x--;
    break;
   case DOWN://done
    yLast=y+1;
    ASSERT(x<rc->right);
    if(y!=bottom1&&x!=rc->right&&INSIDE(x,y+1)){
     if(x!=rc->left&&INSIDE(x-1,y+1)){
      PathLineTo(path,xLast,yLast);
      direction=LEFT;
     }
    } else {
     PathLineTo(path,xLast,yLast);
     direction=RIGHT;
    }
    y++;
    break;
   case UP:
    yLast=y-1;
    ASSERT(x>rc->left);
    if(y>rc->top+1&&x!=rc->left&&INSIDE(x-1,y-2)){
     if(x!=rc->right&&INSIDE(x,y-2)){
      PathLineTo(path,xLast,yLast);
      direction=RIGHT;
     }
    } else {
     PathLineTo(path,xLast,yLast);
     direction=LEFT;
    }
    y--;
    break;
  }
 } while(x!=xBegin||y!=yBegin);
 PathClose(path);
}


static void FloodFillOuter(
 LPBYTE *rows,
 RECT *rc,
 LONG x,
 LONG y,
 int target,
 PRTL_BITMAP bits,
 PRTL_BITMAP fillbits
){
 // four-neighbor flood fill
 LONG w=RectWidth(rc);
 LONG xLeft=x;
 LONG xRight=x;
 LONG i;
 LONG yFromOrg=y-rc->top;
 LONG xFromOrg=x-rc->left;
 LONG curpos=yFromOrg*w+xFromOrg;
 do{
//  DebugOut("set lbit at %d %d",xLeft,y);
  SETBIT(bits->Buffer,curpos);
  SETBIT(fillbits->Buffer,curpos);
  curpos--;
  xLeft--;
 } while(xLeft>=rc->left
       &&INSIDE(xLeft,y)
       &&!TESTBIT(fillbits->Buffer,curpos));
 xLeft++;
 curpos=yFromOrg*w+xFromOrg;
 do{
//  DebugOut("set rbit at %d %d",xRight,y);
  SETBIT(bits->Buffer,curpos);
  SETBIT(fillbits->Buffer,curpos);
  curpos++;
  xRight++;
 } while(xRight<rc->right
       &&INSIDE(xRight,y)
       &&!TESTBIT(fillbits->Buffer,curpos));
 xRight--;
 curpos=yFromOrg-w+(xLeft-rc->left);
 for(i=xLeft;i<=xRight;i++){
  LONG above=(yFromOrg-1)*w+(i-rc->left);
  LONG below=(yFromOrg+1)*w+(i-rc->left);
  if(y> rc->top      &&INSIDE(i,y-1)
        &&!TESTBIT(fillbits->Buffer,above))
   FloodFillOuter(rows,rc,i,y-1,target,bits,fillbits);
  if(y<(rc->bottom-1)&&INSIDE(i,y+1)
                     &&!TESTBIT(fillbits->Buffer,below))
   FloodFillOuter(rows,rc,i,y+1,target,bits,fillbits);
 }
}

static void FloodFillInnerCheck(
 LPBYTE *rows,
 RECT *rc,
 LONG x,
 LONG y,
 int target,
 PRTL_BITMAP fillbits,
 LONG *px,
 LONG *py,
 LONG *mnx,
 LONG *mny
){
 // eight-neighbor flood fill
 LONG w=RectWidth(rc);
 LONG xLeft=x;
 LONG xRight=x;
 LONG i;
 LONG yFromOrg=y-rc->top;
 LONG xFromOrg=x-rc->left;
 LONG curpos=yFromOrg*w+xFromOrg;
 do{
  SETBIT(fillbits->Buffer,curpos);
  *px=max(*px,xLeft);
  *py=max(*py,y);
  *mnx=min(*mnx,xLeft);
  *mny=min(*mny,y);
  curpos--;
  xLeft--;
 } while(xLeft>=rc->left
       &&INSIDE(xLeft,y)
       &&!TESTBIT(fillbits->Buffer,curpos));
 xLeft++;
 curpos=yFromOrg*w+xFromOrg;
 do{
  SETBIT(fillbits->Buffer,curpos);
  *px=max(*px,xRight);
  *py=max(*py,y);
  *mnx=min(*mnx,xRight);
  *mny=min(*mny,y);
  curpos++;
  xRight++;
 } while(xRight<rc->right
       &&INSIDE(xRight,y)
       &&!TESTBIT(fillbits->Buffer,curpos));
 xRight--;
 curpos=yFromOrg-w+(xLeft-rc->left);
 for(i=xLeft;i<=xRight;i++){
  LONG above=(yFromOrg-1)*w+(i-rc->left);
  LONG below=(yFromOrg+1)*w+(i-rc->left);
  if(y> rc->top){
   if(   INSIDE(i,y-1)
      &&!TESTBIT(fillbits->Buffer,above))
    FloodFillInnerCheck(rows,rc,i  ,y-1,target,fillbits,px,py,mnx,mny);
   if(i>rc->left
      && INSIDE(i-1,y-1)
      &&!TESTBIT(fillbits->Buffer,above-1))
    FloodFillInnerCheck(rows,rc,i-1,y-1,target,fillbits,px,py,mnx,mny);
   if(i<rc->right-1
      && INSIDE(i+1,y-1)
      &&!TESTBIT(fillbits->Buffer,above+1))
    FloodFillInnerCheck(rows,rc,i+1,y-1,target,fillbits,px,py,mnx,mny);
  }
  if(y<(rc->bottom-1)){
   if(   INSIDE(i,y+1)
      &&!TESTBIT(fillbits->Buffer,below))
    FloodFillInnerCheck(rows,rc,i  ,y+1,target,fillbits,px,py,mnx,mny);
   if(i>rc->left
      && INSIDE(i-1,y+1)
      &&!TESTBIT(fillbits->Buffer,below-1))
    FloodFillInnerCheck(rows,rc,i-1,y+1,target,fillbits,px,py,mnx,mny);
   if(i<rc->right-1
      && INSIDE(i+1,y+1)
      &&!TESTBIT(fillbits->Buffer,below+1))
    FloodFillInnerCheck(rows,rc,i+1,y+1,target,fillbits,px,py,mnx,mny);
  }
 }
}
/*
#include "ionative.h"
void SaveRtlBitmap(PRTL_BITMAP bits, DWORD cx, DWORD cy, int count, int line){
 IMAGEBUFFERINFO *ibi=DibImageBufferInfoAlloc(cx,cy,1);
 int x,y;
 char bmp[200];
 for(y=0;y<cy;y++){
  for(x=0;x<cx;x++){
   int pixel=TESTBIT(bits->Buffer,y*cx+x) ? 0 : 1;
   DibSetPixel1(ibi->rows,x,y,pixel);
  }
 }
 sprintf(bmp,"bpath%03d_%03d.bmp",count,line);
 DibImageBufferInfoSave(bmp,GetNativeIo(),ibi);
 DibImageBufferInfoFree(ibi);
}
*/
#define SAVE ;/*SaveRtlBitmap(&bits,w,h,bmpcount++,__LINE__)*/

static BOOL PathFromBitmapIntersectRect(
 RECT *dst, RECT *src1, RECT *src2
){
 RECT tmp;
 if(!src1||!src2)
  return 0;
 tmp.left=max(src1->left,src2->left);
 tmp.top=max(src1->top,src2->top);
 tmp.right=min(src1->right,src2->right);
 tmp.bottom=min(src1->bottom,src2->bottom);
 if(dst)*dst=tmp;
 return (tmp.left<tmp.right&&tmp.top<tmp.bottom);
}

BOOL PathFromBitmap(
 IMAGEBUFFERINFO *ibi,
 RECT *rcExtent,
 int target,
 ITEMARRAY *path
){
 RTL_BITMAP bits;
 RTL_BITMAP fillbits;
 LPBYTE *rows;
 RECT rcClip;
 RECT ext;
 RECT *rc;
 DWORD x,y;
 DWORD w,h;
 DWORD bitindex;
 int bmpcount=0;
 int notTarget;
 if(!ISARRAY(path,PATHSEGMENT))return FALSE;
 if(!ibi||ibi->bpp!=1)return FALSE;
 target=(target)?1:0;
 notTarget=(target)?0:1;
 rows=ibi->rows;
 if(rcExtent){
  SetRect(&rcClip,0,0,ibi->width,ibi->height);
  PathFromBitmapIntersectRect(rcExtent,&rcClip,rcExtent);
  rc=rcExtent;
 } else {
  SetRect(&ext,0,0,ibi->width,ibi->height);
  rc=&ext;
 }
 w=RectWidth(rc);
 h=RectHeight(rc);
 INITBITS(&bits,w*h);
 INITBITS(&fillbits,w*h);
 bitindex=0;
 for(y=rc->top;y<rc->bottom;y++){
  for(x=rc->left;x<rc->right;x++,bitindex++){
   if(!TESTBIT(bits.Buffer,bitindex)){
    if(!INSIDE(x,y)){
     if(x==rc->left
      ||x==rc->right-1
      ||y==rc->top
      ||y==rc->bottom-1
     ){
      CLEARBITS(&fillbits);
      FloodFillOuter(rows,rc,x,y,notTarget,&bits,&fillbits);SAVE;
     }
    }
   }
  }
 }
 bitindex=0;
 for(y=rc->top;y<rc->bottom;y++){
  for(x=rc->left;x<rc->right;x++,bitindex++){
   if(!TESTBIT(bits.Buffer,bitindex)){
    if(INSIDE(x,y)){
     TraceShape(rows,rc,x,y,target,&bits,path);SAVE;
     CLEARBITS(&fillbits);
     FloodFillOuter(rows,rc,x,y,target,&bits,&fillbits);SAVE;
    } else {
     if(x==rc->left
      ||x==rc->right-1
      ||y==rc->top
      ||y==rc->bottom-1
     ){
      CLEARBITS(&fillbits);
      FloodFillOuter(rows,rc,x,y,notTarget,&bits,&fillbits);SAVE;
     } else {
      LONG px=-1,py=-1;
      LONG mnx=w,mny=h;
      CLEARBITS(&fillbits);
      FloodFillInnerCheck(rows,rc,x,y,notTarget,&fillbits,&px,&py,&mnx,&mny);
      if(px!=rc->right-1&&py!=rc->bottom-1&&mnx!=0&&mny!=0){
       TraceShapeInner(rows,rc,x,y,notTarget,&bits,path);SAVE;
      }
      CLEARBITS(&fillbits);
      // must use four-neighbor (outer) flood fill because of TraceShapeInner's behavior
      FloodFillOuter(rows,rc,x,y,notTarget,&bits,&fillbits);SAVE;
     }
    }
   }
  }
 }
 free(bits.Buffer);
 free(fillbits.Buffer);
 return TRUE;
}

---