revfit.c

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

/*
 *  revfit.c : edge reconstruction and the inverse process.
 */
#include <stdio.h>
#include "revfit.h"

#ifndef abs
#define abs(a)	((a)>=0 ? (a) : -(a) )
#endif

#define HalfSUBPIXRES   (SUBPIXRES/2)
#define ESTABLISHED     127
#define MAXRUN          2000          /* max no of pixel edges in a line */

extern DrawPixelEdge(int x, int y, int V_H); /* a user supplied function */
                                             /* for drawing a PixelEdge  */

/**********************************************************************\
 * typedef's for sub-pixel resolution pixel edges and gradient bounds *
\**********************************************************************/
typedef struct {
   int x1,y1;   /* from (coordinates multiplied by sub-pixel resolution) */
   int x2,y2;   /* to   (coordinates multiplied by sub-pixel resolution) */
} Pedge;

typedef struct {
   int ly,lx;   /* lower limit */
   int uy,ux;   /* upper limit */
} Bound;

#define MidX(e) (((e).x1+(e).x2)/2)     /* midpt coordinates of a Pedge    */
#define MidY(e) (((e).y1+(e).y2)/2)
#define Is_Horizontal(d) (abs(d)==HRZ)  /* a horizontal direction? (1, -1) */
#define Is_Vertical(d)   (abs(d)==VRT)  /* a vertical direction?  (2, -2)  */
#define against(a,b) (!((a)+(b)))       /* whether two directions are opp. */
#define Bound_OK(b) (slopecmp((b).uy,(b).ux,(b).ly,(b).lx))
#define WithinBound(dy,dx,b) (slopecmp((dy),(dx),(b).ly,(b).lx) &&\
                              slopecmp((b).uy,(b).ux,(dy),(dx)))

/***************************************************************************
 *   Get_Pedge(): Returns a pointer to the current Pedge from the list el. *
 *                 The position of the cursor of list is not modified.     *
 *                 Returns NULL if no more edges in the list.              *
 *                 Coordinates multiplied by sub-pixel resolution.         *
 ***************************************************************************/
static Pedge *Get_Pedge(Edgelist el) {
 static Pedge e;
 int dir;
   if (el.current>=el.Nedges) return NULL;
   if (Is_Horizontal(dir=(el.list[el.current].dir))) {
    e.y1=e.y2=el.list[el.current].y*SUBPIXRES + HalfSUBPIXRES;
    e.x1=el.list[el.current].x*SUBPIXRES
          - (dir>0 ? HalfSUBPIXRES : -HalfSUBPIXRES);
    e.x2=e.x1 + (dir>0 ? SUBPIXRES : -SUBPIXRES);
 }
 else {
    e.x1=e.x2=el.list[el.current].x*SUBPIXRES + HalfSUBPIXRES;
    e.y1=el.list[el.current].y*SUBPIXRES
        - (dir>0 ? HalfSUBPIXRES : -HalfSUBPIXRES);
    e.y2=e.y1 + (dir>0 ? SUBPIXRES : -SUBPIXRES);
 }
 return &e;
} /* Get_Pedge() */

/************************************************************************
 *      forward(): Update the cursor of the list to the next edge.      *
 ************************************************************************/
#define forward(el) (((el).current)++)

/*************************************************************************
 *      backward(): Move back the cursor of the list one place so that   *
 *                  the previous edge can be visited again.              *
 *************************************************************************/
#define backward(el) (((el).current)--)

/************************************************\
 *      wayof(): return a direction.            *
\************************************************/
/* the directions no.s are chosen s.t. d1==-d2 if d1,d2 are opp. */
static int wayof(Pedge e)  {
 int d=e.x2-e.x1;
   return d ? d/SUBPIXRES                  /* 1 or -1 for horizontal edge */
            : (e.y2 - e.y1)/HalfSUBPIXRES; /* 2 or -2 for vertical edge   */
} /* wayof() */

/**************************************************************************
 * slopecmp(): True if grad vector of the 1st is on the counter-clockwise *
 *             side of the 2nd one                                        *
 **************************************************************************/
static int slopecmp(int dy1,int dx1, int dy2,int dx2)  {
   return (long)dx2*dy1 > (long)dx1*dy2;
} /* slopecmp() */

/***************************************************************************\
* calcbound(): calc the bounds (the pair of gradient limits) for the Pedge  *
\***************************************************************************/
void calcbound(int dominantdir, Pedge e, int Sx, int Sy,
               Bound* b, IntPoint2 *gradU, IntPoint2 *gradL) {
/* gradU and gradL shall be filled with the gradients just within the limits */
 int dy,dx;
   if (Is_Horizontal(dominantdir)) { /* horizontal dominant direction */
      b->uy = (e.y1+e.y2+SUBPIXRES)/2-Sy;
      b->ux = (e.x1+e.x2)/2          -Sx;
      b->ly = (e.y1+e.y2-SUBPIXRES)/2-Sy;
      gradU->x = gradL->x = b->lx = b->ux;
      gradU->y = b->uy-1; gradL->y = b->ly+1;
   }
   else { /* up or down dominant direction */
      b->uy = (e.y1+e.y2)/2          -Sy;
      b->ux = (e.x1+e.x2+SUBPIXRES)/2-Sx;
      gradU->y = gradL->y = b->ly = b->uy;
      b->lx = (e.x1+e.x2-SUBPIXRES)/2-Sx;
      gradU->x = b->ux-1; gradL->x = b->lx+1;
   }
   if (!Bound_OK(*b)) {    /* swaps the bounds if necessary */
    IntPoint2 p;
      dx=b->ux;    dy=b->uy;
      b->ux=b->lx; b->uy=b->ly;
      b->lx=dx;    b->ly=dy;
      p=*gradU; *gradU=*gradL; *gradL=p;
   }
} /* calcbound() */

/******************************************************************************
 * fitlines() : The reversible straight line edge reconstruction routine      *
 ******************************************************************************/
int fitlines(Edgelist el, boolean Pretest, boolean TryAllEndPts,
             IntPoint2 *lines, int MaxNLine) {
/*----------------------------------------------------------------------------*
 * el          : The supplied list of PixelEdges.
 * Pretest     : 1=perform pre-test on each pixel edge, i.e., stop as soon as
 *                 a valid end pt cannot be found on a pixel edge.
 *               0=Allows stepping back.
 * TryAllEndPts: 1=Try all possible end-pts, 0=Use the one closest to mid-pt.
 * lines[]     : A preallocated array to be filled with end pts of fitted lines
 *               Note: Coordinates of the end pts are multiplied by SUBPIXRES.
 * MaxNLine    : The size of the lines[] array.
 *----------------------------------------------------------------------------*/
 int i,linescount,startp,Nendpt,Nstartpt,NPedges,Nbound;          /* counters */
 int Sx,Sy,Ex,Ey,  Ux,Uy,Lx,Ly,  maindir,trnsvrse,dnow,  ndir,dir[3];
 flag breaktrace, starttrace;                                     /* flags    */
 int currentsave, bestpt, maxlen, bestpt_currentsave, bestpt_Nendpt;
 IntPoint2 startpts[SUBPIXRES],endlist[SUBPIXRES],bestpt_endlist[SUBPIXRES];
 Pedge Pedgehistory[MAXRUN],e,last,*nextp,estartsave,bestpt_last;
 Bound bound[MAXRUN];

 el.current=0;                          /* set cursor to the first edge */
 e = *Get_Pedge(el);                    /* first edge                   */
 Sx = MidX(e);
 Sy = MidY(e);

 if (!TryAllEndPts)  {
   lines[0].x = Sx;                     /* record the 1st starting pt.  */
   lines[0].y = Sy;
   linescount=1;
 }
 else  {
  flag hori = Is_Horizontal(wayof(e));
   Nstartpt=0;
   startpts[0].x = Sx;
   startpts[0].y = Sy;
   for (i=1;i<HalfSUBPIXRES;i++) { /* the list of possible init. starting pts */
     startpts[Nstartpt  ].x =  hori ? Sx-i : Sx;
     startpts[Nstartpt++].y = !hori ? Sy+i : Sy;
     startpts[Nstartpt  ].x =  hori ? Sx-i : Sx;
     startpts[Nstartpt++].y = !hori ? Sy+i : Sy;
   }
   startp=0;  /* counter for the list of possible starting pts (startpts[]) */
   bestpt_currentsave=currentsave=el.current;   /* save these for rewinding */
   estartsave=e;
   maxlen=bestpt=-1;                    /* no best starting pt (bestpt) yet */
   linescount=0;
 } /* if (!TryAllEndPts) .. else .. */

 for (starttrace=TRUE;;) {              /* loop for all PixelEdges */
  if (starttrace) {                     /* beginning of a new line segment  */
   dir[0]=wayof(e);   ndir=1;           /* no.of distinct directions so far */
   starttrace=0;  breaktrace=0;
   Pedgehistory[0]=e;                   /* the first Pedge traced */
   NPedges=1;                           /* reset the counters     */
   Nbound=0; 
  } /* if (starttrace) */

  last=e;
  forward(el);                          /* go on to the next PixelEdge */
  if ((nextp=Get_Pedge(el))!=NULL) {    /* get a new Pedge             */
   Pedgehistory[NPedges++]=*nextp;
   e=*nextp;
   dnow=wayof(e);                       /* direction of the current edge     */
  }

  if (nextp==NULL || ndir==ESTABLISHED){ /* maindir and trnsvrse established */
   Bound b;
   IntPoint2 gradU,gradL;
   flag lowerupdated, upperupdated;

   if (nextp!=NULL) {
    calcbound(maindir,e,Sx,Sy,&b,&gradU,&gradL);

    bound[Nbound]=bound[Nbound-1];

    lowerupdated=upperupdated=FALSE;
    if (slopecmp(bound[Nbound-1].uy,bound[Nbound-1].ux,
                 b.uy,b.ux)) {          /* update the upper limit */
     bound[Nbound].uy=b.uy;
     bound[Nbound].ux=b.ux;
     upperupdated=TRUE;
    }
    if (slopecmp(b.ly,b.lx,
                 bound[Nbound-1].ly,
                 bound[Nbound-1].lx)) { /* update the lower limit */
     bound[Nbound].ly=b.ly;
     bound[Nbound].lx=b.lx;
     lowerupdated=TRUE;
    }
   } /* if (nextp!=NULL) */

   if (nextp==NULL ||                                 /* no more PixelEdge */
       (dnow!=trnsvrse && dnow!=maindir)    ||        /* U-turn            */
       (dnow==trnsvrse && dnow==wayof(last)) ||       /* 2 trnsvrse edges  */
       !Bound_OK(bound[Nbound]) ||                    /* not within limits */
       (Pretest &&   /* if Pretest, check if there is any pt within limits */
        ((lowerupdated && !WithinBound(gradU.y,gradU.x,bound[Nbound])) ||
         (upperupdated && !WithinBound(gradL.y,gradL.x,bound[Nbound]))))) {
              /* now we shall calculate the starting pt for the next trace */
    for (;;) {/* loop until the end-point lies within the gradient limits  */
     int dx,dy,tmp;        flag exact,EndptOK;

     Ex=MidX(last); Ey=MidY(last);
     if (Nbound==0) { /* i.e. first few PixelEdges. therefore mid-pt is ok  */
      if (TryAllEndPts){
       endlist[0].x=Ex; endlist[0].y=Ey;
       Nendpt=1;
      }
      break;          /* end pt found */
     }

     b = bound[Nbound-1];

     dx= Ex - Sx;             /* the slope of the mid-pt of the last Pedge  */
     dy= Ey - Sy;

     if (TryAllEndPts && el.current-currentsave>maxlen) {
     /* find all possible end pts only if length longer than maxlen so far  */
       int h,addy,addx;

       if (abs(maindir)==1) { addy=1; addx=0; } else {addy=0; addx=1;}
       if (WithinBound(dy,dx,b))  {                  /* check mid-pt first  */
        endlist[0].x=Ex; endlist[0].y=Ey; Nendpt=1;
       }
       else Nendpt=0;
       for (h=1; h<SUBPIXRES/2; h++) {               /* offset from mid-pt  */
        if (WithinBound(dy+addy*h,dx+addx*h,b)) {
         endlist[Nendpt  ].x = Ex + addx*h;
         endlist[Nendpt++].y = Ey + addy*h;
        }
        else if (WithinBound(dy-addy*h,dx-addx*h,b)) {
         endlist[Nendpt  ].x = Ex - addx*h;
         endlist[Nendpt++].y = Ey - addy*h;
        }
       } /* for (h) */
       Ex=endlist[0].x; Ey=endlist[0].y;
       EndptOK = Nendpt>0;
     }
     else { /* TryAllEndPts==FALSE. just calc the pt closest to the mid-pt  */
      if (!slopecmp(dy,dx,b.ly,b.lx)) {
       /*
        * dy dx is equal or below the lower limit.
        * i.e. the slope just above the lower limit should be taken.
        * if the lower 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.ly;   exact= (dx==0 || tmp%b.lx==0);
        Ey = tmp/b.lx + Sy + (b.lx>0 ? (b.ly>0 ? 1      : exact)
                                     : (b.ly>0 ? -exact : -1   ));
       }