C/C++ Users Group Library 1996 July/C-C++ Users Group Library July 1996.iso/listings/v_10_08/qcreg.cpp

C/C++ Source or Header | 1992-07-11 | 19.2 KB | 645 lines

///////////////////////////////////////////////////////
//  Listing 2 - QCREG.CPP: Quadcode region support
//  Written by:
//    Kenneth Van Camp
//    RR #1 Box 1255
//    East Stroudsburg, PA  18301
//    [phone]
//
//  Functions -
//    Region::Region            construct from outline
//    Region::ScanOutAET        create qc's in row
//    Region::AddRow            add a row of qc's
//    Region::AddQC             add a single qc
//    Region::~Region           destructor
//    Region::Compress          compress the region
//    Region::InRegion          is qc within region?
//    Region::MaxQuits          find max #quits
//    Region::NumQC             find # qc's in region
//    operator<<                region "put to" stream
//    BuildGET                  build global edge table
//    MoveJSortedToAET          move row GET to AET
//    JSortAET                  sort AET by column
//    AdvanceAET                advance edges in AET
//    SetRegionYieldFunc        set appl. yield func
//    DefaultRegionYieldFunc    the default yield func
//
///////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <assert.h>
#ifdef __TURBOC__
#include <iostream.h>
#else
#include <stream.hpp>
#endif
#include "qc.h"

#define SWAP(a,b) { temp = a; a = b; b = temp; }

// Following class and globals are used locally,
// for construction of regions:

// struct EdgeState: Holds data on edges of one row of
// the polygon (region) during construction.
struct EdgeState
{
  struct EdgeState  *next_edge;
  COORD j,
        start_i;
  int   whole_pixel_jmove,
        jdirection;
  COORD error_term,
        error_term_adj_up,
        error_term_adj_down,
        count;
};

static EdgeState  *GETptr,      // Global edge table
                  *AETptr;      // Active edge table

// This sets up the yield function, to allow yielding
// to the user or another application:
int DefaultRegionYieldFunc (int pct_complete);
static int (*RegionYieldFunc) (int) = DefaultRegionYieldFunc;

// Local function prototypes:
static void BuildGET (PointListHeader &vertex_list,
    EdgeState *next_free_edge, COORD &min_i, COORD &max_i);
static void MoveJSortedToAET (COORD i_to_move);
static void JSortAET (void);
static void AdvanceAET (void);

///////////////////////////////////////////////////////
// Region::Region: Constructor for region given a
// perimeter list.  The following code is based on a
// complex polygon fill routine by Michael Abrash, as
// published in his Graphics Programming column in
// Dr. Dobb's Journal, June 1991, pp. 139-143, 154-157.
//   This function will periodically yield control to the
// designated yield function.  If the yield function
// returns TRUE, then region building is aborted and a
// flag is set so that subsequent calls to NumQC() will
// return a 0.

Region::Region (PointListHeader &vertex_list)
// vertex_list  is an array of points describing the
//              outline of the region.  The path is
//              automatically closed from the last to
//              the first point.
{
  first_qcnode = NULL;
  aborted = FALSE;

  ndiv = vertex_list.ndiv;
  int nquits = MaxQuits();
  assert (nquits > 0);
  // Reject polygons that are invisible.
  assert (vertex_list.length >= 3);

  // Get enough memory to store entire edge table:
  EdgeState *edge_table_buf;
  edge_table_buf = new EdgeState[vertex_list.length];
  assert (edge_table_buf != NULL);

  // Build the global edge table:
  BuildGET (vertex_list, edge_table_buf, min_i, max_i);

  // Scan down through polygon edges, one scan line at
  // a time, so long as at least one edge remains in
  // either the GET or AET.
  // Initialize the active edge table to empty:
  AETptr = NULL;
  // Start at the top polygon vertex.
  current_i = GETptr->start_i;
  int nqc_compress = 0; // qc's added since compression
  while ((GETptr != NULL) || (AETptr != NULL))
  {
    // Update AET for this scan line.
    MoveJSortedToAET (current_i);
    // Add quadcodes for this scan line.
    ScanOutAET (current_i, nqc_compress, nquits);
    // Advance AET edges one scan line.
    AdvanceAET();
    // Re-sort on J.
    JSortAET();
    // Advance to next scan line.
    current_i--;

    // Single compression pass after 100 quadcodes
    if (nqc_compress > 100)
    {
      nqc_compress = 0;
      (void)Compress();
    }

    // Yield to the user or another application after each
    // scan line:
    if (RegionYieldFunc (PctComplete()))
    {
      // The process has been aborted.
      // Set a flag, release dynamic memory, and return.
      aborted = TRUE;
      delete edge_table_buf;
      return;
    }

  }

  // Release dynamic memory
  delete edge_table_buf;

  // Final compression, until nothing more to compress:
  while (Compress())
    ;

} // Region::Region

///////////////////////////////////////////////////////
// Region::ScanOutAET: Create quadcodes along an entire
// row, using the odd/even fill rule.

void Region::ScanOutAET
    (COORD i_to_scan, int &nqc_compress, int nquits)
// i_to_scan    is the row # to scan
// nqc_compress is the # qc's added since last compress
// nquits       is the # of quits to use in each qc
{
  // Scan through AET, filling areas along current row
  // as each pair of edge crossings is encountered.
  // Nearest pixel on or to the right of left edges is
  // drawn, and nearest pixel to the left of but not on
  // the right edges is drawn.
  EdgeState *current_edge = AETptr;
  while (current_edge != NULL)
  {
    COORD left_j = current_edge->j;
    current_edge = current_edge->next_edge;
    AddRow (i_to_scan, left_j, current_edge->j - 1,
        nquits);
    nqc_compress += abs (current_edge->j - left_j);
    current_edge = current_edge->next_edge;
  }
} // Region::ScanOutAET

///////////////////////////////////////////////////////
// Region::AddRow: Add an entire row of quadcodes.

void Region::AddRow
    (COORD i, COORD j1, COORD j2, int nquits)
// i        is the I coordinate of the row
// j1       is the J coordinate at one end of the row
// j2       is the J coordinate at other end of the row
// nquits   is the # quits in the quadcode to add
{
  COORD j;
  COORD jmin = min (j1, j2);
  COORD jmax = max (j1, j2);

  for (j = jmax; j >= jmin; j--)
    AddQC (i, j, nquits);
} // Region::AddRow

///////////////////////////////////////////////////////
// Region::AddQC: Add a single quadcode to a region.

void Region::AddQC (COORD i, COORD j, int nquits)
// i        is the I coordinate of the quadcode
// j        is the J coordinate of the quadcode
// nquits   is the # quits in the quadcode to add
{
  QCNode  *new_qcn = new QCNode (i, j, nquits);
  assert (new_qcn != NULL);

  // Insert into linked list in sorted order.
  QCNode  *qcn,
          *prev = NULL;

  for (qcn = first_qcnode; qcn; qcn = qcn->next)
  {
    if (*new_qcn <= *qcn)
    {
      // Found insertion point
      if (*new_qcn == *qcn)
      {
        // Quadcode already in list - don't add again.
        delete new_qcn;
        return;
      }
      break;
    }
    prev = qcn;
  } // for qcn

  new_qcn->next = qcn;
  if (prev)
    prev->next = new_qcn;
  else
    // Add to head of list
    first_qcnode = new_qcn;

} // Region::AddQC

///////////////////////////////////////////////////////
// Region::~Region: Region destructor

Region::~Region (void)
{
  QCNode  *qcn,
          *nextqcn;

  // Release the linked list of quadcode nodes
  for (qcn = first_qcnode; qcn; qcn = nextqcn)
  {
    nextqcn = qcn->next;
    delete qcn;
  }
  first_qcnode = NULL;
} // Region::~Region

///////////////////////////////////////////////////////
// Region::Compress: This function makes a single pass
// at compressing a region, by finding any four consec-
// utive quadcodes that are siblings and replacing them
// with their parent.  Return TRUE if any compression
// took place, or FALSE if the region is unchanged.
// To fully compress the region, this function should
// be called repeatedly until FALSE is returned.

int Region::Compress (void)
{
  int changed = FALSE;    // has region been changed?
  QCNode *qcn;

  for (qcn = first_qcnode; qcn; qcn = qcn->next)
  {
    // Don't compare any top-level qc's because they
    // can't be compressed out.
    if (qcn->nquits < 2)
      continue;
    // Are next four qc's in a row all siblings?
    if (qcn->Sibling (qcn->next) &&
        qcn->next->Sibling (qcn->next->next)
        && qcn->next->next->Sibling (qcn->next->next->next))
    {
      // Yes - One sibling is replaced with its parent,
      // the other 3 are dropped.
      changed = TRUE;
      QCNode *save_next = qcn->next->next->next->next;
      qcn->MakeParent();
      delete qcn->next->next->next;
      delete qcn->next->next;
      delete qcn->next;
      qcn->next = save_next;
    }
  } // for qcn

  return (changed);
} // Region::Compress

///////////////////////////////////////////////////////
// Region::InRegion: Return TRUE if the supplied qc is
// within the region boundaries, or FALSE if not.

int Region::InRegion (QuadCode &qc)
// qc   is the quadcode to compare
{
  QCNode  *qcn;

  for (qcn = first_qcnode; qcn; qcn = qcn->next)
  {
    if (qcn->Contains (qc))
      return (TRUE);
    // If past our quadcode, then done.
    if (*qcn > qc)
      return (FALSE);
  }

  return (FALSE);
} // Region::InRegion

///////////////////////////////////////////////////////
// Region::MaxQuits: Compute the max # quits in a qc
// in this region, from the # of (I,J) divisions in the
// entire grid.

int Region::MaxQuits (void)
{
  int nq;
  for (nq = 0; nq < MAXQUITS; nq++)
    if (1 << nq >= ndiv)
      break;
  assert (nq != MAXQUITS);
  return (nq);
} // Region::MaxQuits

///////////////////////////////////////////////////////
// Region::NumQC: Count the # quadcodes in the region.

int Region::NumQC (void)
{
  int     n;
  QCNode  *qcn;

  if (aborted)
    // The region build was aborted.
    return(0);

  for (n = 0, qcn = first_qcnode; qcn;
      qcn = qcn->next, n++)
    ;
  return (n);
} // Region::NumQC

///////////////////////////////////////////////////////
// Region::PctComplete: Return the percentage of the
// region that has been built (0 - 100).

int Region::PctComplete (void)
{
  if (min_i >= max_i)
    // Haven't started to build region yet.
    return (0);

  // The following assumes the region is built from
  // highest I to lowest.
  return ((int) (100.0 * (max_i - current_i) /
        (max_i - min_i)));
} // Region::PctComplete

///////////////////////////////////////////////////////
// operator<<: Overload the "Put to" operator for
// Region output to stream.

ostream &operator<< (ostream &stream, Region ®)
// stream     is the stream to print to
// reg        is the region to print
{
  QCNode  *qcn;

  if (reg.first_qcnode == NULL)
  {
    stream << "(empty)";
    return (stream);
  }
  for (qcn = reg.first_qcnode; qcn; qcn = qcn->next)
    stream << *qcn << ' ';
  return (stream);
} // operator<<

///////////////////////////////////////////////////////
// BuildGET: Build the global edge table from the
// vertex list.

static void BuildGET (PointListHeader &vertex_list,
    EdgeState *next_free_edge, COORD &min_i, COORD &max_i)
// vertex_list    is a list of pts defining perimeter
// next_free_edge is a ptr to array of edge states
{
  // Scan thru vertex list & put all non-zero-height
  // edges into the GET, sorted by decreasing i start
  // coordinate
  Point *vertex_ptr = vertex_list.pointptr;
  GETptr = NULL;
  min_i = LONG_MAX;
  max_i = LONG_MIN;
  int i;
  for (i = 0; i < vertex_list.length; i++)
  {
    // Calculate edge height & width
    COORD start_i = vertex_ptr[i].i;
    COORD start_j = vertex_ptr[i].j;
    COORD end_i, end_j, temp;

    // The edge runs from current pt to the prev one.
    if (i == 0)
    {
      // Wrap back around to the end of the list.
      end_i = vertex_ptr[vertex_list.length - 1].i;
      end_j = vertex_ptr[vertex_list.length - 1].j;
    }
    else
    {
      end_i = vertex_ptr[i-1].i;
      end_j = vertex_ptr[i-1].j;
    }
    // Make sure the edge runs bottom to top
    if (end_i > start_i)
    {
      SWAP (start_i, end_i);
      SWAP (start_j, end_j);
    }

    // Establish limits of the region
    min_i = min (min_i, end_i);
    max_i = max (max_i, start_i);

    // Skip if can't ever be an active edge (0 height).
    COORD delta_i, delta_j;
    if ((delta_i = start_i - end_i) != 0)
    {
      // Allocate space for edge's info, fill in struct
      EdgeState *new_edge_ptr = next_free_edge++;
      // Find direction in which J moves:
      new_edge_ptr->jdirection =
          ((delta_j = end_j - start_j) > 0) ? 1 : -1;
      COORD width = abs(delta_j);
      new_edge_ptr->j = start_j;
      new_edge_ptr->start_i = start_i;
      new_edge_ptr->count = delta_i;
      new_edge_ptr->error_term_adj_down = delta_i;
      if (delta_j >= 0)
        // Initial error term going L->R
        new_edge_ptr->error_term = 0;
      else
        // Initial error term going R->L
        new_edge_ptr->error_term = -delta_i + 1;
      if (delta_i >= width)
      {
        // I-major edge
        new_edge_ptr->whole_pixel_jmove = 0;
        new_edge_ptr->error_term_adj_up = width;
      }
      else
      {
        // J-major edge
        new_edge_ptr->whole_pixel_jmove =
            (width / delta_i) *
            new_edge_ptr->jdirection;
        new_edge_ptr->error_term_adj_up =
            width % delta_i;
      }

      // Link new edge into the GET so the edge list is
      // still sorted by I, and by J for all edges with
      // same I.
      EdgeState **following_edge_link = &GETptr;
      EdgeState *following_edge;
      for ( ; ; )
      {
        following_edge = *following_edge_link;
        if ((following_edge == NULL) ||
            (following_edge->start_i < start_i) ||
            ((following_edge->start_i == start_i) &&
             (following_edge->j >= start_j)))
        {
          new_edge_ptr->next_edge = following_edge;
          *following_edge_link = new_edge_ptr;
          break;
        }
        following_edge_link =
            &following_edge->next_edge;
      } // for
    } // if delta_i
  } // for i

} // BuildGET

///////////////////////////////////////////////////////
// MoveJSortedToAET: Move all edges that start at
// specified row from the GET to the AET, maintaining J
// sorting of the AET.

static void MoveJSortedToAET (COORD i_to_move)
{
  // The GET is I sorted.  Any edges that start at the
  // desired row will be first in the GET, so move
  // edges from the GET to AET until first edge left in
  // the GET is no longer at the desired row.  Also,
  // the GET is J sorted within each row, so each
  // successive edge added to the AET is guaranteed to
  // belong later in the AET than the one just added.
  EdgeState **AET_edge_ptr = &AETptr;
  while ((GETptr != NULL) &&
      (GETptr->start_i == i_to_move))
  {
    int current_j = GETptr->j;
    // Link new edge into the AET so the AET is still
    // sorted by J coordinate.
    for ( ; ; )
    {
      EdgeState *AET_edge = *AET_edge_ptr;
      if ((AET_edge == NULL) ||
          (AET_edge->j >= current_j))
      {
        EdgeState *temp_edge = GETptr->next_edge;
        *AET_edge_ptr = GETptr;   // link edge into AET
        GETptr->next_edge = AET_edge;
        AET_edge_ptr = &GETptr->next_edge;
        GETptr = temp_edge;     // unlink edge from AET
        break;
      }
      else
        AET_edge_ptr = &AET_edge->next_edge;
    } // for
  } // while

} // MoveJSortedToAET

///////////////////////////////////////////////////////
// JSortAET: Sort all edges currently in active edge
// table into ascending order of current J.

static void JSortAET (void)
{
  // Scan through AET and swap any adjacent edges for
  // which the second edge is at a lower current J
  // coord than the first edge.  Repeat until no
  // further swapping is needed.
  if (AETptr != NULL)
  {
    int swap_occurred;
    do
    {
      swap_occurred = FALSE;
      EdgeState **current_edge_ptr = &AETptr;
      EdgeState *current_edge;
      while ((current_edge =
          *current_edge_ptr)->next_edge != NULL)
      {
        if (current_edge->j >
            current_edge->next_edge->j)
        {
          // The second edge has lower J than first.
          // Swap them in the AET.
          EdgeState *temp_edge =
              current_edge->next_edge->next_edge;
          *current_edge_ptr = current_edge->next_edge;
          current_edge->next_edge->next_edge =
              current_edge;
          current_edge->next_edge = temp_edge;
          swap_occurred = TRUE;
        }
        current_edge_ptr =
            &(*current_edge_ptr)->next_edge;
      } // while
    } while (swap_occurred);
  } // if AETptr
} // JSortAET

///////////////////////////////////////////////////////
// AdvanceAET: Advances each edge in the AET by one
// scan line. Removes edges that are fully scanned.

static void AdvanceAET (void)
{
  // Count down and remove or advance each edge in AET.
  EdgeState **current_edge_ptr = &AETptr;
  EdgeState *current_edge;
  while ((current_edge = *current_edge_ptr) != NULL)
  {
    // Count off one scan line for this edge.
    if ((--(current_edge->count)) == 0)
      // This edge is finished, so remove from the AET.
      *current_edge_ptr = current_edge->next_edge;
    else
    {
      // Advance the edge's J coord by minimum move.
      current_edge->j +=
          current_edge->whole_pixel_jmove;
      // Determine whether it's time for J to advance
      // one extra.
      if ((current_edge->error_term +=
          current_edge->error_term_adj_up) > 0)
      {
        current_edge->j += current_edge->jdirection;
        current_edge->error_term -=
            current_edge->error_term_adj_down;
      }
      current_edge_ptr = ¤t_edge->next_edge;
    }
  } // while
} // AdvanceAET

///////////////////////////////////////////////////////
// SetRegionYieldFunc: Set the address of a "yield"
// function.  This function will be called repeatedly
// during region building, to allow the application to
// yield control to the user or another application.
// The percentage complete is passed so the user may be
// kept up to date on the progress of region building.

void SetRegionYieldFunc (int (*yield_func) (int pct_complete))
// yield_func       is a pointer to the application's
//                  yield function
{
  RegionYieldFunc = yield_func;
} // SetRegionYieldFunc

///////////////////////////////////////////////////////
// DefaultRegionYieldFunc: The yield function should
// return TRUE if region building should be aborted,
// or FALSE otherwise.

int DefaultRegionYieldFunc (int pct_complete)
// pct_complete     is the percent of the region that
//                  has been built (0 - 100)

{
  // The default yield function does nothing.
  return (FALSE);
} // DefaultRegionYieldFunc