Error in ScanPoly - Grx

27 Apr 2001


      I have found an error in the scanpoly.c (scan fill an arbitrary
polygon) which is a part of the GRX graphics library.
Under certain conditions a clipped polygon is not shown.
This mistake appears with an example-triangle.
It has the coordinates {{120, 0}, {120,90}, {0,60}} and is clipped
by a rectangle {{50,50}, {270,150}} (with GrSetClipBox).
The changed part of the fill algorithm can display this triangle.
My changes are recognizable by the define NOERROR.
The original source code can be found in directory shape.
/**
 ** scanpoly.c ---- scan fill an arbitrary polygon
 **
 ** Copyright (c) 1995 Csaba Biegl, 820 Stirrup Dr, Nashville, TN 37221
 ** [e-mail: csaba@vuse.vanderbilt.edu]
 **
 ** This file is part of the GRX graphics library.
 **
 ** The GRX graphics library is free software; you can redistribute it
 ** and/or modify it under some conditions; see the "copying.grx" file
 ** for details.
 **
 ** This library is distributed in the hope that it will be useful,
 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 **
 **/
#define NOERROR
void _GrScanPolygon(int n, int pt[][2], GrColor color)
{
  edge *edges, *ep;
  scan *scans, *sp, *points, *segments;
  int xmin, xmax, ymin, ymax;
  int ypos, nedges;
  int prevx;
  int prevy;
  int i;
if ((n > 1) && (pt[0][0] == pt[n-1][0]) && (pt[0][1] == pt[n-1][1])) {
n--;
  }
  if (n < 1) {
    return;
  }
  edges = (edge *)malloc(sizeof(edge) * (n + 2));
  scans = (scan *)malloc(sizeof(scan) * (n + 8));
  if (edges && scans) {
    /*
     * Build the edge table. Store only those edges which are in the
     * valid Y region. Clip them in Y if necessary. Store them with
     * the endpoints ordered by Y in the edge table.
     */
    prevx = xmin = xmax = pt[0][0];
    prevy = ymin = ymax = pt[0][1];
    nedges = 0;
    ep     = edges;
    while (--n >= 0) {
      if (pt[n][1] >= prevy) {
 ep->e.x     = prevx;
 ep->e.y     = prevy;
 ep->e.xlast = prevx = pt[n][0];
 ep->e.ylast = prevy = pt[n][1];
      } else {
 ep->e.xlast = prevx;
 ep->e.ylast = prevy;
 ep->e.x     = prevx = pt[n][0];
 ep->e.y     = prevy = pt[n][1];
      }
#ifndef NOERROR
      if ((ep->e.y > GrHighY()) || (ep->e.ylast < GrLowY())) continue;
      clip_line_ymin(CURC, ep->e.x, ep->e.y, ep->e.xlast, ep->e.ylast);
#endif
if (ymin > ep->e.y)     ymin = ep->e.y;
      if (ymax < ep->e.ylast) ymax = ep->e.ylast;
      if (xmin > ep->e.x)     xmin = ep->e.x;
      if (xmax < ep->e.xlast) xmax = ep->e.xlast;
      setup_edge(&ep->e);
      ep->status = inactive;
      nedges++;
      ep++;
    }
#ifndef NOERROR
    if ((nedges > 0) && (xmin <= GrHighX()) && (xmax >= GrLowX())) {
      if (xmin < GrLowX()) xmin = GrLowX();
      if (ymin < GrLowY()) ymin = GrLowY();
      if (xmax > GrHighX()) xmax = GrHighX();
      if (ymax > GrHighY()) ymax = GrHighY();
#else
    if ((nedges > 0)) {
#endif
/*
       * Scan for every row between ymin and ymax.
       * Build a linked list of disjoint segments to fill. Rules:
       *   (1) a horizontal edge in the row contributes a segment
       *   (2) any other edge crossing the row contributes a point
       *   (3) every segment between even and odd points is filled
       */
      for (ypos = ymin; ypos <= ymax; ypos++) {
#ifdef NOERROR
 if (ypos > GrHighY()) continue;
 if (ypos < GrLowY()) continue;
#endif
sp       = scans;
 points   = NULL;
 segments = NULL;
 for (n = nedges, ep = edges; --n >= 0; ep++) {
   switch (ep->status) {
     case inactive:
       if (ep->e.y != ypos) break;
       if (ep->e.dy == 0) {
  ep->status = passed;
  xmin = ep->e.x;
  xmax = ep->e.xlast;
  isort(xmin, xmax);
  add_scansegment(&segments, sp, xmin, xmax);
  sp++;
  break;
       }
       ep->status = active;
     case active:
       xmin = xmax = ep->e.x;
       if (ep->e.ylast == ypos) {
  ep->status = passed;
  xmax = ep->e.xlast;
  isort(xmin, xmax);
  add_scanpoint(&points, sp, xmin, xmax);
  sp++;
       } else if (ep->e.xmajor) {
  xstep_edge(&ep->e);
  xmax = ep->e.x - ep->e.xstep;
  isort(xmin, xmax);
       } else {
  ystep_edge(&ep->e);
       }
       add_scanpoint(&points, sp, xmin, xmax);
       sp++;
       break;
     default:
       break;
   }
 }
 while (points != NULL) {
   scan *nextpt = points->next;
   if (!nextpt) break;
   xmin   = points->x1;
   xmax   = nextpt->x2;
   points = nextpt->next;
   add_scansegment(&segments, nextpt, xmin, xmax);
 }
while (segments != NULL) {
   xmin     = segments->x1;
   xmax     = segments->x2;
   segments = segments->next;
clip_ordxrange_(CURC, xmin, xmax, continue,
CLIP_EMPTY_MACRO_ARG);
drawhline(xmin, ypos, xmax-xmin+1, color);
 }
      }
    }
  }
  if (edges) free(edges);
  if (scans) free(scans);
}
int left = 50;
int top = 50;
int right = 270;
int bottom = 150;
int n = 4;
GrColor color = YELLOW;
int pt[4][2];
int main()
{
  GrSetClipBox(left, top, right, bottom);
pt[0][0] = 120; pt[0][1] =  0;
  pt[1][0] = 120; pt[1][1] = 90;
  pt[2][0] =   0; pt[2][1] = 60;
  pt[3][0] = 120; pt[3][1] =  0;
_GrScanPolygon(n, pt, color);
}