revfit.c

[Game.Programming].Academic - Graphics Gems (6 books source code)

       else {
        tmp= dy*b.lx;   exact= (dy==0 || tmp%b.ly==0);
        Ex = tmp/b.ly + Sx + (b.ly>0 ? (b.lx>0 ? -exact : -1   )
                                     : (b.lx>0 ? 1      : exact));
       }
       EndptOK = Pretest || WithinBound(Ey-Sy,Ex-Sx,b);
      }
      else if (!slopecmp(b.uy,b.ux,dy,dx)) {
       /*
        * dy dx is equal or above the upper limit.
        * i.e. the slope just below the upper limit should be taken.
        * if the upper gradient limit hits exactly on a sub-pixel res point,
        *  the truncation of the integer division has done part of the job.
        */
       if (Is_Horizontal(maindir)) {
        tmp= dx*b.uy;   exact= (tmp%b.ux==0);
        Ey = tmp/b.ux + Sy + (b.ux>0 ? (b.uy>0 ? -exact :-1    )
                                     : (b.uy>0 ? 1      : exact));
       }
       else {
        tmp= dy*b.ux;   exact= (tmp%b.uy==0);
        Ex = tmp/b.uy + Sx + (b.uy>0 ? (b.ux>0 ? 1      : exact)
                                     : (b.ux>0 ? -exact :-1    ));
       }
       EndptOK = Pretest || WithinBound(Ey-Sy,Ex-Sx,b);
      }
      else       /* dy,dx is within the limits. i.e. mid-point is taken. */
      EndptOK=1;
     } /* if (TryAllEndPts)..else.. */

     if (EndptOK) break;    /* if Pretest is TRUE, EndptOK always TRUE */
     else  {    /* no valid end-point can be found, step back one edge */
      backward(el);
      last = Pedgehistory[--NPedges-2];
      Nbound--;
     }
    } /* for (;;) */                    /* until a valid end pt is found */
    breaktrace=TRUE;                    /* one line segment found.       */
   }
   else {                               /* limits not crossed over yet   */
    Nbound++;                           /* one more new valid bound      */
    continue;                           /* continue to get another Pedge */
   } /* if (various trace breaking conditions) */
  } /* if (nextp==NULL || ndir==ESTABLISHED) */
  else {  /* i.e. dominant and trnsvrse direction not yet established */
    breaktrace = FALSE;
    if (ndir<3) {
     for (i=0;i<ndir;i++) {             /* compare with previous dir's   */
      if (against(dnow,dir[i])) {       /* there is a `U' turn ...       */
       breaktrace = TRUE;               /* therefore an early stop       */
       Ex=MidX(last);  Ey=MidY(last);
       if (TryAllEndPts) {
         endlist[0].x=Ex; endlist[0].y=Ey;
         Nendpt=1;
       } /* if (TryAllEndPts) */
      } /* for () */
     }
     if (ndir<2 || dnow!=dir[1] || dir[0]!=dir[1]) {
      dir[ndir]=dnow;
      ndir++;
     }
    }

    if (ndir==3)                /* now we can establish the directions... */
    {                           /*   _       | */
     if (dir[0]!=dir[1]) {      /* _|   or  _| */
      maindir=dir[2];                                             /*    | */
      if (dir[1]==dir[2]) {                                       /*   _| */
       trnsvrse=dir[0];         /* the 1st dir is the trnsvrse dir        */
       if (Is_Horizontal(maindir)) {
        Ux = Lx = MidX(e) - Sx;
        Uy = (Ly = e.y1-Sy-HalfSUBPIXRES) +SUBPIXRES;
       }
       else {
        Uy = Ly = MidY(e) - Sy;
        Ux = (Lx = e.x1-Sx-HalfSUBPIXRES) +SUBPIXRES;
       }
      }
      else {                                                      /*   _  */
       trnsvrse=dir[1];                                           /* _|   */
       if (Is_Horizontal(maindir)) {
        Lx = Ux = MidX(e)-Sx;
        Ly = (Uy = MidY(e)+HalfSUBPIXRES-Sy) -SUBPIXRES;
       }
       else {
        Ly = Uy = MidY(e)-Sy;
        Lx = (Ux = MidX(e)+HalfSUBPIXRES-Sx) -SUBPIXRES;
       }
      }
     }
     else {                                                   /* __.....| */
      maindir=dir[0];
      trnsvrse=dir[2];
      if (Is_Horizontal(maindir)) {
       Lx = e.x1 + (maindir>0 ? -HalfSUBPIXRES : HalfSUBPIXRES) - Sx;
       Ux = Lx + (maindir>0 ? SUBPIXRES : -SUBPIXRES);
       Uy = Ly = MidY(e) - Sy;
      }
      else {
       Ly = e.y1 + (maindir>0 ? -HalfSUBPIXRES : HalfSUBPIXRES) - Sy ;
       Uy = Ly + (maindir>0 ? SUBPIXRES : -SUBPIXRES);
       Ux = Lx = MidX(e) - Sx;
      }
     }
     if (slopecmp(Ly,Lx,Uy,Ux)) {       /* swap the grad limits if necessary */
      bound[0].uy=Ly; bound[0].ux=Lx;   /* Ly Lx larger */
      bound[0].ly=Uy; bound[0].lx=Ux;
     }
     else {
      bound[0].uy=Uy; bound[0].ux=Ux;   /* Uy Ux larger */
      bound[0].ly=Ly; bound[0].lx=Lx;
     }
     Nbound=1;                          /* first bound established */
     ndir = ESTABLISHED;
    } /* if (ndir==3) */
  } /* if (ndir==ESTABLISHED)...else... */
                                                 /*--------------------------*/
  if (breaktrace) {                              /*     one line ended       */
                                                 /*--------------------------*/
   backward(el);    /* last pixel edge shall be the start of another line.   */

   if (TryAllEndPts) {
    if (maxlen < (el.current-currentsave))  {    /* longer than the longest  */
     maxlen = el.current-currentsave;            /* longest distance so far  */
     bestpt_last=last;                           /* save the last edge       */
     bestpt=startp;                              /* update the best pt so far*/
     bestpt_currentsave=el.current;              /* save the cursor for el   */
     for (i=0; i<Nendpt; i++) bestpt_endlist[i]=endlist[i]; /* save end pts  */
     bestpt_Nendpt=Nendpt;                       /* save the no. of end pts  */
    }
    startp++;                            /* next starting pt in startpts[]   */
    if (startp >= Nstartpt) {            /* all starting pts have been tried */
     currentsave=el.current=bestpt_currentsave;     /* save the ending pos   */
     estartsave=e=bestpt_last;                      /* save the ending Pedge */
     lines[linescount++] = startpts[bestpt];        /* record the best pt    */
     if (linescount>=MaxNLine) return -1;           /* too many lines        */
     if (bestpt_currentsave>=el.Nedges-1) {         /* no more Pixel edges ? */
      lines[linescount++]=bestpt_endlist[0];        /* record end pt as well */
      return linescount>=MaxNLine ? -1 : linescount;/* done                  */
     }

     Nstartpt=bestpt_Nendpt;      /* use the list of end pts as starting pts */
     for (i=0; i<bestpt_Nendpt; i++) startpts[i]=bestpt_endlist[i];

     startp=0;                    /* consider the first one in the new list  */
     Sx=startpts[0].x; Sy=startpts[0].y;
     maxlen=bestpt=-1;            /* reset maxlen and bestpt to undefined    */
    }
    else { /* i.e. startp<Nstartpt.  try next starting point                 */
     Sx=startpts[startp].x; Sy=startpts[startp].y; /* next starting pt       */
                                                   /* rewind and start again */
     el.current=currentsave;
     e=last=estartsave;
    } /* if (startp>=Nstartpt) ... else ... */
   }
   else { /* i.e. TryAllEndPts==FALSE.  simply start at the end pt again     */
    Sx=Ex; Sy=Ey; e=last;
    lines[linescount].x=Ex; lines[linescount++].y=Ey;
    if (linescount>=MaxNLine) return -1;           /* too many lines         */
    if (el.current>=el.Nedges-1) return linescount;/* no more Pedges, done   */
   }
   starttrace=TRUE;                                /* start again            */
  } /* if (breaktrace) */
 } /* for (starttrace=TRUE;;) infinite loop */
} /* fitlines() */

/***********************************************************************\
*               T H E    I N V E R S E    P R O C E S S                 *
\***********************************************************************/
#define divisible(a,b) ((a)%(b)==0)
#define ishori(x,y) (divisible(x,SUBPIXRES)||\
                     divisible(y+HalfSUBPIXRES,SUBPIXRES))
#define isvert(x,y) (divisible(y,SUBPIXRES)||\
                     divisible(x+HalfSUBPIXRES,SUBPIXRES))
#define sign(x) ((x)>=0 ? 1 : -1)
#define Trunc(n) ((n)/SUBPIXRES*SUBPIXRES)
static int lastx,lasty,lastdir;            /* to avoid duplicated pixel edges */

static void drawHPedge(int x, int y) {     /* draw a horizontal pixel edge    */
 if (lastx==x && lasty==y && lastdir==HRZ) /* starting edge==last ending edge */
   return;
 lastx=x; lasty=y; lastdir=HRZ;
 DrawPixelEdge(x/SUBPIXRES, y/SUBPIXRES, HRZ);    /* call the user function   */
} /* drawHPedge() */

static void drawVPedge(int x, int y) {     /* draw a vertical pixel edge      */
 if (lastx==x && lasty==y && lastdir==VRT) /* starting edge==last ending edge */
   return;
 lastx=x; lasty=y; lastdir=VRT;
 DrawPixelEdge(x/SUBPIXRES, y/SUBPIXRES, VRT);   /* call the user function    */
} /* drawVPedge() */

/**************************************************************************
 * makejaggedline(): A modified Bresenham's mid-point algorithm. Based on *
 *    the code from the original Graphics Gem.  Neither the starting pt   *
 *    nor the ending pt need to be at the mid-pt of a pixel edge.          *
 *    The decision variable has been scaled by SUBPIXRES and preloaded    *
 *    with the offset from a `proper' starting pt, i.e. the mid-pt of the  *
 *    first pixel edge pointing to the dominant direction.                *
 **************************************************************************/
static makejaggedline(int x1, int y1, int x2, int y2) {
 int d, x, y, ax, ay, sx, sy, dx, dy, finaltrnsvrse;

 dx = x2-x1;  ax = abs(dx)*SUBPIXRES;  sx = sign(dx)*SUBPIXRES;
 dy = y2-y1;  ay = abs(dy)*SUBPIXRES;  sy = sign(dy)*SUBPIXRES;
                                                           /*============*/
 if (ax>ay)                                                /* x dominant */
 {                                                         /*============*/
  if (isvert(x1,y1)) /* 1st edge is trnsvrse. skip to the mid-pt  */
  {                  /* of the next dominant dir edge.            */
   y=Trunc(y1 + HalfSUBPIXRES) + sy/2;
   x=Trunc(x1) + HalfSUBPIXRES + sx/2;
   drawVPedge(x-sx/2,y-sy/2);            /* draw the skipped edge */
  }
  else { /* 1st edge is dominant. shift to the mid-pt */
   x=Trunc(x1 + HalfSUBPIXRES);
   y=Trunc(y1) + HalfSUBPIXRES;
  }
  /* preload decision var `d' with offset x-x1, y-y1. (if any) */
  d = ay - (ax>>1) + ay*(x-x1)/sx - ax*(y-y1)/sy;
  for (;;)   {
   drawHPedge(x,y);
   if (abs(x-x2) < HalfSUBPIXRES) return; /* final edge is a dominant one */
   x += sx;
   finaltrnsvrse = dx>0 ? x>x2: x<x2;
   if (d>0 || finaltrnsvrse)  {        /* if the final edge is a trnsvrse */
    drawVPedge(x-sx/2,y+sy/2);         /* one, draw it before stopping    */
    y += sy;
    d -= ax;
   }
   if (finaltrnsvrse) return;
   d += ay;
  } /* for (;;) */
 }                                                 /*============*/
 else                                              /* y dominant */
 {                                                 /*============*/
  if (ishori(x1,y1)) /* 1st edge trnsvrse. skip to the mid-pt  */
  {                  /* of the next dominant dir edge          */
   x=Trunc(x1 + HalfSUBPIXRES) + sx/2;
   y=Trunc(y1) + HalfSUBPIXRES + sy/2;
   drawHPedge(x-sx/2, y-sy/2);        /* draw the skipped edge */
  }
  else { /* 1st edge is dominant. shift to the mid-pt */
   x=Trunc(x1) + HalfSUBPIXRES;
   y=Trunc(y1 + HalfSUBPIXRES);
  }
  /* preload decision var `d' with offset x-x1, y-y1 (if any) */
  d = ax - (ay>>1) + ax*(y-y1)/sy - ay*(x-x1)/sx;
  for (;;) {
   drawVPedge(x,y);
   if (abs(y-y2) < HalfSUBPIXRES) return; /* final edge is a dominant one */
   y += sy;
   finaltrnsvrse = dy>0 ? y>y2 : y<y2;
   if (d>0 || finaltrnsvrse)  {         /* if the final one is a trnsvrse */
    drawHPedge(x+sx/2, y-sy/2);         /* one, draw it before stopping.  */
    x += sx;
    d -= ay;
   }
   if (finaltrnsvrse) return;
   d += ax;
  } /* for (;;) */
 } /* if (ax>ay)... else ...*/
} /* makejaggedline() */

/***************************************************************************
 * linestojagged(): reconstruct a sequence of pixel edges from given lines *
 *                by calling the makejaggedline() function.                *
 ***************************************************************************/
void linestojagged(int Nlines, IntPoint2 *lines) {
 int from_x, from_y, i;
 lastdir=0;
 for (from_x=lines[0].x, from_y=lines[0].y, i=1; i<Nlines; i++) {
  makejaggedline(from_x,from_y,lines[i].x,lines[i].y);
  from_x=lines[i].x;    from_y=lines[i].y;
 }
} /* linetojagged() */