home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsv / ch6_5 / revfit.c next >
Encoding:
C/C++ Source or Header  |  1995-04-04  |  23.9 KB  |  554 lines
  1. /*
  2.  *  revfit.c : edge reconstruction and the inverse process.
  3.  */
  4. #include <stdio.h>
  5. #include "revfit.h"
  6.  
  7. #ifndef abs
  8. #define abs(a)    ((a)>=0 ? (a) : -(a) )
  9. #endif
  10.  
  11. #define HalfSUBPIXRES   (SUBPIXRES/2)
  12. #define ESTABLISHED     127
  13. #define MAXRUN          2000          /* max no of pixel edges in a line */
  14.  
  15. extern DrawPixelEdge(int x, int y, int V_H); /* a user supplied function */
  16.                                              /* for drawing a PixelEdge  */
  17.  
  18. /**********************************************************************\
  19.  * typedef's for sub-pixel resolution pixel edges and gradient bounds *
  20. \**********************************************************************/
  21. typedef struct {
  22.    int x1,y1;   /* from (coordinates multiplied by sub-pixel resolution) */
  23.    int x2,y2;   /* to   (coordinates multiplied by sub-pixel resolution) */
  24. } Pedge;
  25.  
  26. typedef struct {
  27.    int ly,lx;   /* lower limit */
  28.    int uy,ux;   /* upper limit */
  29. } Bound;
  30.  
  31. #define MidX(e) (((e).x1+(e).x2)/2)     /* midpt coordinates of a Pedge    */
  32. #define MidY(e) (((e).y1+(e).y2)/2)
  33. #define Is_Horizontal(d) (abs(d)==HRZ)  /* a horizontal direction? (1, -1) */
  34. #define Is_Vertical(d)   (abs(d)==VRT)  /* a vertical direction?  (2, -2)  */
  35. #define against(a,b) (!((a)+(b)))       /* whether two directions are opp. */
  36. #define Bound_OK(b) (slopecmp((b).uy,(b).ux,(b).ly,(b).lx))
  37. #define WithinBound(dy,dx,b) (slopecmp((dy),(dx),(b).ly,(b).lx) &&\
  38.                               slopecmp((b).uy,(b).ux,(dy),(dx)))
  39.  
  40. /***************************************************************************
  41.  *   Get_Pedge(): Returns a pointer to the current Pedge from the list el. *
  42.  *                 The position of the cursor of list is not modified.     *
  43.  *                 Returns NULL if no more edges in the list.              *
  44.  *                 Coordinates multiplied by sub-pixel resolution.         *
  45.  ***************************************************************************/
  46. static Pedge *Get_Pedge(Edgelist el) {
  47.  static Pedge e;
  48.  int dir;
  49.    if (el.current>=el.Nedges) return NULL;
  50.    if (Is_Horizontal(dir=(el.list[el.current].dir))) {
  51.     e.y1=e.y2=el.list[el.current].y*SUBPIXRES + HalfSUBPIXRES;
  52.     e.x1=el.list[el.current].x*SUBPIXRES
  53.           - (dir>0 ? HalfSUBPIXRES : -HalfSUBPIXRES);
  54.     e.x2=e.x1 + (dir>0 ? SUBPIXRES : -SUBPIXRES);
  55.  }
  56.  else {
  57.     e.x1=e.x2=el.list[el.current].x*SUBPIXRES + HalfSUBPIXRES;
  58.     e.y1=el.list[el.current].y*SUBPIXRES
  59.         - (dir>0 ? HalfSUBPIXRES : -HalfSUBPIXRES);
  60.     e.y2=e.y1 + (dir>0 ? SUBPIXRES : -SUBPIXRES);
  61.  }
  62.  return &e;
  63. } /* Get_Pedge() */
  64.  
  65. /************************************************************************
  66.  *      forward(): Update the cursor of the list to the next edge.      *
  67.  ************************************************************************/
  68. #define forward(el) (((el).current)++)
  69.  
  70. /*************************************************************************
  71.  *      backward(): Move back the cursor of the list one place so that   *
  72.  *                  the previous edge can be visited again.              *
  73.  *************************************************************************/
  74. #define backward(el) (((el).current)--)
  75.  
  76. /************************************************\
  77.  *      wayof(): return a direction.            *
  78. \************************************************/
  79. /* the directions no.s are chosen s.t. d1==-d2 if d1,d2 are opp. */
  80. static int wayof(Pedge e)  {
  81.  int d=e.x2-e.x1;
  82.    return d ? d/SUBPIXRES                  /* 1 or -1 for horizontal edge */
  83.             : (e.y2 - e.y1)/HalfSUBPIXRES; /* 2 or -2 for vertical edge   */
  84. } /* wayof() */
  85.  
  86. /**************************************************************************
  87.  * slopecmp(): True if grad vector of the 1st is on the counter-clockwise *
  88.  *             side of the 2nd one                                        *
  89.  **************************************************************************/
  90. static int slopecmp(int dy1,int dx1, int dy2,int dx2)  {
  91.    return (long)dx2*dy1 > (long)dx1*dy2;
  92. } /* slopecmp() */
  93.  
  94. /***************************************************************************\
  95. * calcbound(): calc the bounds (the pair of gradient limits) for the Pedge  *
  96. \***************************************************************************/
  97. void calcbound(int dominantdir, Pedge e, int Sx, int Sy,
  98.                Bound* b, IntPoint2 *gradU, IntPoint2 *gradL) {
  99. /* gradU and gradL shall be filled with the gradients just within the limits */
  100.  int dy,dx;
  101.    if (Is_Horizontal(dominantdir)) { /* horizontal dominant direction */
  102.       b->uy = (e.y1+e.y2+SUBPIXRES)/2-Sy;
  103.       b->ux = (e.x1+e.x2)/2          -Sx;
  104.       b->ly = (e.y1+e.y2-SUBPIXRES)/2-Sy;
  105.       gradU->x = gradL->x = b->lx = b->ux;
  106.       gradU->y = b->uy-1; gradL->y = b->ly+1;
  107.    }
  108.    else { /* up or down dominant direction */
  109.       b->uy = (e.y1+e.y2)/2          -Sy;
  110.       b->ux = (e.x1+e.x2+SUBPIXRES)/2-Sx;
  111.       gradU->y = gradL->y = b->ly = b->uy;
  112.       b->lx = (e.x1+e.x2-SUBPIXRES)/2-Sx;
  113.       gradU->x = b->ux-1; gradL->x = b->lx+1;
  114.    }
  115.    if (!Bound_OK(*b)) {    /* swaps the bounds if necessary */
  116.     IntPoint2 p;
  117.       dx=b->ux;    dy=b->uy;
  118.       b->ux=b->lx; b->uy=b->ly;
  119.       b->lx=dx;    b->ly=dy;
  120.       p=*gradU; *gradU=*gradL; *gradL=p;
  121.    }
  122. } /* calcbound() */
  123.  
  124. /******************************************************************************
  125.  * fitlines() : The reversible straight line edge reconstruction routine      *
  126.  ******************************************************************************/
  127. int fitlines(Edgelist el, boolean Pretest, boolean TryAllEndPts,
  128.              IntPoint2 *lines, int MaxNLine) {
  129. /*----------------------------------------------------------------------------*
  130.  * el          : The supplied list of PixelEdges.
  131.  * Pretest     : 1=perform pre-test on each pixel edge, i.e., stop as soon as
  132.  *                 a valid end pt cannot be found on a pixel edge.
  133.  *               0=Allows stepping back.
  134.  * TryAllEndPts: 1=Try all possible end-pts, 0=Use the one closest to mid-pt.
  135.  * lines[]     : A preallocated array to be filled with end pts of fitted lines
  136.  *               Note: Coordinates of the end pts are multiplied by SUBPIXRES.
  137.  * MaxNLine    : The size of the lines[] array.
  138.  *----------------------------------------------------------------------------*/
  139.  int i,linescount,startp,Nendpt,Nstartpt,NPedges,Nbound;          /* counters */
  140.  int Sx,Sy,Ex,Ey,  Ux,Uy,Lx,Ly,  maindir,trnsvrse,dnow,  ndir,dir[3];
  141.  flag breaktrace, starttrace;                                     /* flags    */
  142.  int currentsave, bestpt, maxlen, bestpt_currentsave, bestpt_Nendpt;
  143.  IntPoint2 startpts[SUBPIXRES],endlist[SUBPIXRES],bestpt_endlist[SUBPIXRES];
  144.  Pedge Pedgehistory[MAXRUN],e,last,*nextp,estartsave,bestpt_last;
  145.  Bound bound[MAXRUN];
  146.  
  147.  el.current=0;                          /* set cursor to the first edge */
  148.  e = *Get_Pedge(el);                    /* first edge                   */
  149.  Sx = MidX(e);
  150.  Sy = MidY(e);
  151.  
  152.  if (!TryAllEndPts)  {
  153.    lines[0].x = Sx;                     /* record the 1st starting pt.  */
  154.    lines[0].y = Sy;
  155.    linescount=1;
  156.  }
  157.  else  {
  158.   flag hori = Is_Horizontal(wayof(e));
  159.    Nstartpt=0;
  160.    startpts[0].x = Sx;
  161.    startpts[0].y = Sy;
  162.    for (i=1;i<HalfSUBPIXRES;i++) { /* the list of possible init. starting pts */
  163.      startpts[Nstartpt  ].x =  hori ? Sx-i : Sx;
  164.      startpts[Nstartpt++].y = !hori ? Sy+i : Sy;
  165.      startpts[Nstartpt  ].x =  hori ? Sx-i : Sx;
  166.      startpts[Nstartpt++].y = !hori ? Sy+i : Sy;
  167.    }
  168.    startp=0;  /* counter for the list of possible starting pts (startpts[]) */
  169.    bestpt_currentsave=currentsave=el.current;   /* save these for rewinding */
  170.    estartsave=e;
  171.    maxlen=bestpt=-1;                    /* no best starting pt (bestpt) yet */
  172.    linescount=0;
  173.  } /* if (!TryAllEndPts) .. else .. */
  174.  
  175.  for (starttrace=TRUE;;) {              /* loop for all PixelEdges */
  176.   if (starttrace) {                     /* beginning of a new line segment  */
  177.    dir[0]=wayof(e);   ndir=1;           /* no.of distinct directions so far */
  178.    starttrace=0;  breaktrace=0;
  179.    Pedgehistory[0]=e;                   /* the first Pedge traced */
  180.    NPedges=1;                           /* reset the counters     */
  181.    Nbound=0; 
  182.   } /* if (starttrace) */
  183.  
  184.   last=e;
  185.   forward(el);                          /* go on to the next PixelEdge */
  186.   if ((nextp=Get_Pedge(el))!=NULL) {    /* get a new Pedge             */
  187.    Pedgehistory[NPedges++]=*nextp;
  188.    e=*nextp;
  189.    dnow=wayof(e);                       /* direction of the current edge     */
  190.   }
  191.  
  192.   if (nextp==NULL || ndir==ESTABLISHED){ /* maindir and trnsvrse established */
  193.    Bound b;
  194.    IntPoint2 gradU,gradL;
  195.    flag lowerupdated, upperupdated;
  196.  
  197.    if (nextp!=NULL) {
  198.     calcbound(maindir,e,Sx,Sy,&b,&gradU,&gradL);
  199.  
  200.     bound[Nbound]=bound[Nbound-1];
  201.  
  202.     lowerupdated=upperupdated=FALSE;
  203.     if (slopecmp(bound[Nbound-1].uy,bound[Nbound-1].ux,
  204.                  b.uy,b.ux)) {          /* update the upper limit */
  205.      bound[Nbound].uy=b.uy;
  206.      bound[Nbound].ux=b.ux;
  207.      upperupdated=TRUE;
  208.     }
  209.     if (slopecmp(b.ly,b.lx,
  210.                  bound[Nbound-1].ly,
  211.                  bound[Nbound-1].lx)) { /* update the lower limit */
  212.      bound[Nbound].ly=b.ly;
  213.      bound[Nbound].lx=b.lx;
  214.      lowerupdated=TRUE;
  215.     }
  216.    } /* if (nextp!=NULL) */
  217.  
  218.    if (nextp==NULL ||                                 /* no more PixelEdge */
  219.        (dnow!=trnsvrse && dnow!=maindir)    ||        /* U-turn            */
  220.        (dnow==trnsvrse && dnow==wayof(last)) ||       /* 2 trnsvrse edges  */
  221.        !Bound_OK(bound[Nbound]) ||                    /* not within limits */
  222.        (Pretest &&   /* if Pretest, check if there is any pt within limits */
  223.         ((lowerupdated && !WithinBound(gradU.y,gradU.x,bound[Nbound])) ||
  224.          (upperupdated && !WithinBound(gradL.y,gradL.x,bound[Nbound]))))) {
  225.               /* now we shall calculate the starting pt for the next trace */
  226.     for (;;) {/* loop until the end-point lies within the gradient limits  */
  227.      int dx,dy,tmp;        flag exact,EndptOK;
  228.  
  229.      Ex=MidX(last); Ey=MidY(last);
  230.      if (Nbound==0) { /* i.e. first few PixelEdges. therefore mid-pt is ok  */
  231.       if (TryAllEndPts){
  232.        endlist[0].x=Ex; endlist[0].y=Ey;
  233.        Nendpt=1;
  234.       }
  235.       break;          /* end pt found */
  236.      }
  237.  
  238.      b = bound[Nbound-1];
  239.  
  240.      dx= Ex - Sx;             /* the slope of the mid-pt of the last Pedge  */
  241.      dy= Ey - Sy;
  242.  
  243.      if (TryAllEndPts && el.current-currentsave>maxlen) {
  244.      /* find all possible end pts only if length longer than maxlen so far  */
  245.        int h,addy,addx;
  246.  
  247.        if (abs(maindir)==1) { addy=1; addx=0; } else {addy=0; addx=1;}
  248.        if (WithinBound(dy,dx,b))  {                  /* check mid-pt first  */
  249.         endlist[0].x=Ex; endlist[0].y=Ey; Nendpt=1;
  250.        }
  251.        else Nendpt=0;
  252.        for (h=1; h<SUBPIXRES/2; h++) {               /* offset from mid-pt  */
  253.         if (WithinBound(dy+addy*h,dx+addx*h,b)) {
  254.          endlist[Nendpt  ].x = Ex + addx*h;
  255.          endlist[Nendpt++].y = Ey + addy*h;
  256.         }
  257.         else if (WithinBound(dy-addy*h,dx-addx*h,b)) {
  258.          endlist[Nendpt  ].x = Ex - addx*h;
  259.          endlist[Nendpt++].y = Ey - addy*h;
  260.         }
  261.        } /* for (h) */
  262.        Ex=endlist[0].x; Ey=endlist[0].y;
  263.        EndptOK = Nendpt>0;
  264.      }
  265.      else { /* TryAllEndPts==FALSE. just calc the pt closest to the mid-pt  */
  266.       if (!slopecmp(dy,dx,b.ly,b.lx)) {
  267.        /*
  268.         * dy dx is equal or below the lower limit.
  269.         * i.e. the slope just above the lower limit should be taken.
  270.         * if the lower gradient limit hits exactly on a sub-pixel res point,
  271.         *  the truncation of the integer division has done part of the job.
  272.         */
  273.        if (Is_Horizontal(maindir)) {
  274.         tmp= dx*b.ly;   exact= (dx==0 || tmp%b.lx==0);
  275.         Ey = tmp/b.lx + Sy + (b.lx>0 ? (b.ly>0 ? 1      : exact)
  276.                                      : (b.ly>0 ? -exact : -1   ));
  277.        }
  278.        else {
  279.         tmp= dy*b.lx;   exact= (dy==0 || tmp%b.ly==0);
  280.         Ex = tmp/b.ly + Sx + (b.ly>0 ? (b.lx>0 ? -exact : -1   )
  281.                                      : (b.lx>0 ? 1      : exact));
  282.        }
  283.        EndptOK = Pretest || WithinBound(Ey-Sy,Ex-Sx,b);
  284.       }
  285.       else if (!slopecmp(b.uy,b.ux,dy,dx)) {
  286.        /*
  287.         * dy dx is equal or above the upper limit.
  288.         * i.e. the slope just below the upper limit should be taken.
  289.         * if the upper gradient limit hits exactly on a sub-pixel res point,
  290.         *  the truncation of the integer division has done part of the job.
  291.         */
  292.        if (Is_Horizontal(maindir)) {
  293.         tmp= dx*b.uy;   exact= (tmp%b.ux==0);
  294.         Ey = tmp/b.ux + Sy + (b.ux>0 ? (b.uy>0 ? -exact :-1    )
  295.                                      : (b.uy>0 ? 1      : exact));
  296.        }
  297.        else {
  298.         tmp= dy*b.ux;   exact= (tmp%b.uy==0);
  299.         Ex = tmp/b.uy + Sx + (b.uy>0 ? (b.ux>0 ? 1      : exact)
  300.                                      : (b.ux>0 ? -exact :-1    ));
  301.        }
  302.        EndptOK = Pretest || WithinBound(Ey-Sy,Ex-Sx,b);
  303.       }
  304.       else       /* dy,dx is within the limits. i.e. mid-point is taken. */
  305.       EndptOK=1;
  306.      } /* if (TryAllEndPts)..else.. */
  307.  
  308.      if (EndptOK) break;    /* if Pretest is TRUE, EndptOK always TRUE */
  309.      else  {    /* no valid end-point can be found, step back one edge */
  310.       backward(el);
  311.       last = Pedgehistory[--NPedges-2];
  312.       Nbound--;
  313.      }
  314.     } /* for (;;) */                    /* until a valid end pt is found */
  315.     breaktrace=TRUE;                    /* one line segment found.       */
  316.    }
  317.    else {                               /* limits not crossed over yet   */
  318.     Nbound++;                           /* one more new valid bound      */
  319.     continue;                           /* continue to get another Pedge */
  320.    } /* if (various trace breaking conditions) */
  321.   } /* if (nextp==NULL || ndir==ESTABLISHED) */
  322.   else {  /* i.e. dominant and trnsvrse direction not yet established */
  323.     breaktrace = FALSE;
  324.     if (ndir<3) {
  325.      for (i=0;i<ndir;i++) {             /* compare with previous dir's   */
  326.       if (against(dnow,dir[i])) {       /* there is a `U' turn ...       */
  327.        breaktrace = TRUE;               /* therefore an early stop       */
  328.        Ex=MidX(last);  Ey=MidY(last);
  329.        if (TryAllEndPts) {
  330.          endlist[0].x=Ex; endlist[0].y=Ey;
  331.          Nendpt=1;
  332.        } /* if (TryAllEndPts) */
  333.       } /* for () */
  334.      }
  335.      if (ndir<2 || dnow!=dir[1] || dir[0]!=dir[1]) {
  336.       dir[ndir]=dnow;
  337.       ndir++;
  338.      }
  339.     }
  340.  
  341.     if (ndir==3)                /* now we can establish the directions... */
  342.     {                           /*   _       | */
  343.      if (dir[0]!=dir[1]) {      /* _|   or  _| */
  344.       maindir=dir[2];                                             /*    | */
  345.       if (dir[1]==dir[2]) {                                       /*   _| */
  346.        trnsvrse=dir[0];         /* the 1st dir is the trnsvrse dir        */
  347.        if (Is_Horizontal(maindir)) {
  348.         Ux = Lx = MidX(e) - Sx;
  349.         Uy = (Ly = e.y1-Sy-HalfSUBPIXRES) +SUBPIXRES;
  350.        }
  351.        else {
  352.         Uy = Ly = MidY(e) - Sy;
  353.         Ux = (Lx = e.x1-Sx-HalfSUBPIXRES) +SUBPIXRES;
  354.        }
  355.       }
  356.       else {                                                      /*   _  */
  357.        trnsvrse=dir[1];                                           /* _|   */
  358.        if (Is_Horizontal(maindir)) {
  359.         Lx = Ux = MidX(e)-Sx;
  360.         Ly = (Uy = MidY(e)+HalfSUBPIXRES-Sy) -SUBPIXRES;
  361.        }
  362.        else {
  363.         Ly = Uy = MidY(e)-Sy;
  364.         Lx = (Ux = MidX(e)+HalfSUBPIXRES-Sx) -SUBPIXRES;
  365.        }
  366.       }
  367.      }
  368.      else {                                                   /* __.....| */
  369.       maindir=dir[0];
  370.       trnsvrse=dir[2];
  371.       if (Is_Horizontal(maindir)) {
  372.        Lx = e.x1 + (maindir>0 ? -HalfSUBPIXRES : HalfSUBPIXRES) - Sx;
  373.        Ux = Lx + (maindir>0 ? SUBPIXRES : -SUBPIXRES);
  374.        Uy = Ly = MidY(e) - Sy;
  375.       }
  376.       else {
  377.        Ly = e.y1 + (maindir>0 ? -HalfSUBPIXRES : HalfSUBPIXRES) - Sy ;
  378.        Uy = Ly + (maindir>0 ? SUBPIXRES : -SUBPIXRES);
  379.        Ux = Lx = MidX(e) - Sx;
  380.       }
  381.      }
  382.      if (slopecmp(Ly,Lx,Uy,Ux)) {       /* swap the grad limits if necessary */
  383.       bound[0].uy=Ly; bound[0].ux=Lx;   /* Ly Lx larger */
  384.       bound[0].ly=Uy; bound[0].lx=Ux;
  385.      }
  386.      else {
  387.       bound[0].uy=Uy; bound[0].ux=Ux;   /* Uy Ux larger */
  388.       bound[0].ly=Ly; bound[0].lx=Lx;
  389.      }
  390.      Nbound=1;                          /* first bound established */
  391.      ndir = ESTABLISHED;
  392.     } /* if (ndir==3) */
  393.   } /* if (ndir==ESTABLISHED)...else... */
  394.                                                  /*--------------------------*/
  395.   if (breaktrace) {                              /*     one line ended       */
  396.                                                  /*--------------------------*/
  397.    backward(el);    /* last pixel edge shall be the start of another line.   */
  398.  
  399.    if (TryAllEndPts) {
  400.     if (maxlen < (el.current-currentsave))  {    /* longer than the longest  */
  401.      maxlen = el.current-currentsave;            /* longest distance so far  */
  402.      bestpt_last=last;                           /* save the last edge       */
  403.      bestpt=startp;                              /* update the best pt so far*/
  404.      bestpt_currentsave=el.current;              /* save the cursor for el   */
  405.      for (i=0; i<Nendpt; i++) bestpt_endlist[i]=endlist[i]; /* save end pts  */
  406.      bestpt_Nendpt=Nendpt;                       /* save the no. of end pts  */
  407.     }
  408.     startp++;                            /* next starting pt in startpts[]   */
  409.     if (startp >= Nstartpt) {            /* all starting pts have been tried */
  410.      currentsave=el.current=bestpt_currentsave;     /* save the ending pos   */
  411.      estartsave=e=bestpt_last;                      /* save the ending Pedge */
  412.      lines[linescount++] = startpts[bestpt];        /* record the best pt    */
  413.      if (linescount>=MaxNLine) return -1;           /* too many lines        */
  414.      if (bestpt_currentsave>=el.Nedges-1) {         /* no more Pixel edges ? */
  415.       lines[linescount++]=bestpt_endlist[0];        /* record end pt as well */
  416.       return linescount>=MaxNLine ? -1 : linescount;/* done                  */
  417.      }
  418.  
  419.      Nstartpt=bestpt_Nendpt;      /* use the list of end pts as starting pts */
  420.      for (i=0; i<bestpt_Nendpt; i++) startpts[i]=bestpt_endlist[i];
  421.  
  422.      startp=0;                    /* consider the first one in the new list  */
  423.      Sx=startpts[0].x; Sy=startpts[0].y;
  424.      maxlen=bestpt=-1;            /* reset maxlen and bestpt to undefined    */
  425.     }
  426.     else { /* i.e. startp<Nstartpt.  try next starting point                 */
  427.      Sx=startpts[startp].x; Sy=startpts[startp].y; /* next starting pt       */
  428.                                                    /* rewind and start again */
  429.      el.current=currentsave;
  430.      e=last=estartsave;
  431.     } /* if (startp>=Nstartpt) ... else ... */
  432.    }
  433.    else { /* i.e. TryAllEndPts==FALSE.  simply start at the end pt again     */
  434.     Sx=Ex; Sy=Ey; e=last;
  435.     lines[linescount].x=Ex; lines[linescount++].y=Ey;
  436.     if (linescount>=MaxNLine) return -1;           /* too many lines         */
  437.     if (el.current>=el.Nedges-1) return linescount;/* no more Pedges, done   */
  438.    }
  439.    starttrace=TRUE;                                /* start again            */
  440.   } /* if (breaktrace) */
  441.  } /* for (starttrace=TRUE;;) infinite loop */
  442. } /* fitlines() */
  443.  
  444. /***********************************************************************\
  445. *               T H E    I N V E R S E    P R O C E S S                 *
  446. \***********************************************************************/
  447. #define divisible(a,b) ((a)%(b)==0)
  448. #define ishori(x,y) (divisible(x,SUBPIXRES)||\
  449.                      divisible(y+HalfSUBPIXRES,SUBPIXRES))
  450. #define isvert(x,y) (divisible(y,SUBPIXRES)||\
  451.                      divisible(x+HalfSUBPIXRES,SUBPIXRES))
  452. #define sign(x) ((x)>=0 ? 1 : -1)
  453. #define Trunc(n) ((n)/SUBPIXRES*SUBPIXRES)
  454. static int lastx,lasty,lastdir;            /* to avoid duplicated pixel edges */
  455.  
  456. static void drawHPedge(int x, int y) {     /* draw a horizontal pixel edge    */
  457.  if (lastx==x && lasty==y && lastdir==HRZ) /* starting edge==last ending edge */
  458.    return;
  459.  lastx=x; lasty=y; lastdir=HRZ;
  460.  DrawPixelEdge(x/SUBPIXRES, y/SUBPIXRES, HRZ);    /* call the user function   */
  461. } /* drawHPedge() */
  462.  
  463. static void drawVPedge(int x, int y) {     /* draw a vertical pixel edge      */
  464.  if (lastx==x && lasty==y && lastdir==VRT) /* starting edge==last ending edge */
  465.    return;
  466.  lastx=x; lasty=y; lastdir=VRT;
  467.  DrawPixelEdge(x/SUBPIXRES, y/SUBPIXRES, VRT);   /* call the user function    */
  468. } /* drawVPedge() */
  469.  
  470. /**************************************************************************
  471.  * makejaggedline(): A modified Bresenham's mid-point algorithm. Based on *
  472.  *    the code from the original Graphics Gem.  Neither the starting pt   *
  473.  *    nor the ending pt need to be at the mid-pt of a pixel edge.          *
  474.  *    The decision variable has been scaled by SUBPIXRES and preloaded    *
  475.  *    with the offset from a `proper' starting pt, i.e. the mid-pt of the  *
  476.  *    first pixel edge pointing to the dominant direction.                *
  477.  **************************************************************************/
  478. static makejaggedline(int x1, int y1, int x2, int y2) {
  479.  int d, x, y, ax, ay, sx, sy, dx, dy, finaltrnsvrse;
  480.  
  481.  dx = x2-x1;  ax = abs(dx)*SUBPIXRES;  sx = sign(dx)*SUBPIXRES;
  482.  dy = y2-y1;  ay = abs(dy)*SUBPIXRES;  sy = sign(dy)*SUBPIXRES;
  483.                                                            /*============*/
  484.  if (ax>ay)                                                /* x dominant */
  485.  {                                                         /*============*/
  486.   if (isvert(x1,y1)) /* 1st edge is trnsvrse. skip to the mid-pt  */
  487.   {                  /* of the next dominant dir edge.            */
  488.    y=Trunc(y1 + HalfSUBPIXRES) + sy/2;
  489.    x=Trunc(x1) + HalfSUBPIXRES + sx/2;
  490.    drawVPedge(x-sx/2,y-sy/2);            /* draw the skipped edge */
  491.   }
  492.   else { /* 1st edge is dominant. shift to the mid-pt */
  493.    x=Trunc(x1 + HalfSUBPIXRES);
  494.    y=Trunc(y1) + HalfSUBPIXRES;
  495.   }
  496.   /* preload decision var `d' with offset x-x1, y-y1. (if any) */
  497.   d = ay - (ax>>1) + ay*(x-x1)/sx - ax*(y-y1)/sy;
  498.   for (;;)   {
  499.    drawHPedge(x,y);
  500.    if (abs(x-x2) < HalfSUBPIXRES) return; /* final edge is a dominant one */
  501.    x += sx;
  502.    finaltrnsvrse = dx>0 ? x>x2: x<x2;
  503.    if (d>0 || finaltrnsvrse)  {        /* if the final edge is a trnsvrse */
  504.     drawVPedge(x-sx/2,y+sy/2);         /* one, draw it before stopping    */
  505.     y += sy;
  506.     d -= ax;
  507.    }
  508.    if (finaltrnsvrse) return;
  509.    d += ay;
  510.   } /* for (;;) */
  511.  }                                                 /*============*/
  512.  else                                              /* y dominant */
  513.  {                                                 /*============*/
  514.   if (ishori(x1,y1)) /* 1st edge trnsvrse. skip to the mid-pt  */
  515.   {                  /* of the next dominant dir edge          */
  516.    x=Trunc(x1 + HalfSUBPIXRES) + sx/2;
  517.    y=Trunc(y1) + HalfSUBPIXRES + sy/2;
  518.    drawHPedge(x-sx/2, y-sy/2);        /* draw the skipped edge */
  519.   }
  520.   else { /* 1st edge is dominant. shift to the mid-pt */
  521.    x=Trunc(x1) + HalfSUBPIXRES;
  522.    y=Trunc(y1 + HalfSUBPIXRES);
  523.   }
  524.   /* preload decision var `d' with offset x-x1, y-y1 (if any) */
  525.   d = ax - (ay>>1) + ax*(y-y1)/sy - ay*(x-x1)/sx;
  526.   for (;;) {
  527.    drawVPedge(x,y);
  528.    if (abs(y-y2) < HalfSUBPIXRES) return; /* final edge is a dominant one */
  529.    y += sy;
  530.    finaltrnsvrse = dy>0 ? y>y2 : y<y2;
  531.    if (d>0 || finaltrnsvrse)  {         /* if the final one is a trnsvrse */
  532.     drawHPedge(x+sx/2, y-sy/2);         /* one, draw it before stopping.  */
  533.     x += sx;
  534.     d -= ay;
  535.    }
  536.    if (finaltrnsvrse) return;
  537.    d += ax;
  538.   } /* for (;;) */
  539.  } /* if (ax>ay)... else ...*/
  540. } /* makejaggedline() */
  541.  
  542. /***************************************************************************
  543.  * linestojagged(): reconstruct a sequence of pixel edges from given lines *
  544.  *                by calling the makejaggedline() function.                *
  545.  ***************************************************************************/
  546. void linestojagged(int Nlines, IntPoint2 *lines) {
  547.  int from_x, from_y, i;
  548.  lastdir=0;
  549.  for (from_x=lines[0].x, from_y=lines[0].y, i=1; i<Nlines; i++) {
  550.   makejaggedline(from_x,from_y,lines[i].x,lines[i].y);
  551.   from_x=lines[i].x;    from_y=lines[i].y;
  552.  }
  553. } /* linetojagged() */
  554.