home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_10_08 / qcreg.cpp < prev    next >
C/C++ Source or Header  |  1992-07-12  |  20KB  |  645 lines
  1. ///////////////////////////////////////////////////////
  2. //  Listing 2 - QCREG.CPP: Quadcode region support
  3. //  Written by:
  4. //    Kenneth Van Camp
  5. //    RR #1 Box 1255
  6. //    East Stroudsburg, PA  18301
  7. //    (717)223-8620
  8. //
  9. //  Functions -
  10. //    Region::Region            construct from outline
  11. //    Region::ScanOutAET        create qc's in row
  12. //    Region::AddRow            add a row of qc's
  13. //    Region::AddQC             add a single qc
  14. //    Region::~Region           destructor
  15. //    Region::Compress          compress the region
  16. //    Region::InRegion          is qc within region?
  17. //    Region::MaxQuits          find max #quits
  18. //    Region::NumQC             find # qc's in region
  19. //    operator<<                region "put to" stream
  20. //    BuildGET                  build global edge table
  21. //    MoveJSortedToAET          move row GET to AET
  22. //    JSortAET                  sort AET by column
  23. //    AdvanceAET                advance edges in AET
  24. //    SetRegionYieldFunc        set appl. yield func
  25. //    DefaultRegionYieldFunc    the default yield func
  26. //
  27. ///////////////////////////////////////////////////////
  28.  
  29. #include <stdio.h>
  30. #include <stdlib.h>
  31. #include <string.h>
  32. #include <limits.h>
  33. #include <assert.h>
  34. #ifdef __TURBOC__
  35. #include <iostream.h>
  36. #else
  37. #include <stream.hpp>
  38. #endif
  39. #include "qc.h"
  40.  
  41. #define SWAP(a,b) { temp = a; a = b; b = temp; }
  42.  
  43. // Following class and globals are used locally,
  44. // for construction of regions:
  45.  
  46. // struct EdgeState: Holds data on edges of one row of
  47. // the polygon (region) during construction.
  48. struct EdgeState
  49. {
  50.   struct EdgeState  *next_edge;
  51.   COORD j,
  52.         start_i;
  53.   int   whole_pixel_jmove,
  54.         jdirection;
  55.   COORD error_term,
  56.         error_term_adj_up,
  57.         error_term_adj_down,
  58.         count;
  59. };
  60.  
  61. static EdgeState  *GETptr,      // Global edge table
  62.                   *AETptr;      // Active edge table
  63.  
  64. // This sets up the yield function, to allow yielding
  65. // to the user or another application:
  66. int DefaultRegionYieldFunc (int pct_complete);
  67. static int (*RegionYieldFunc) (int) = DefaultRegionYieldFunc;
  68.  
  69. // Local function prototypes:
  70. static void BuildGET (PointListHeader &vertex_list,
  71.     EdgeState *next_free_edge, COORD &min_i, COORD &max_i);
  72. static void MoveJSortedToAET (COORD i_to_move);
  73. static void JSortAET (void);
  74. static void AdvanceAET (void);
  75.  
  76. ///////////////////////////////////////////////////////
  77. // Region::Region: Constructor for region given a
  78. // perimeter list.  The following code is based on a
  79. // complex polygon fill routine by Michael Abrash, as
  80. // published in his Graphics Programming column in
  81. // Dr. Dobb's Journal, June 1991, pp. 139-143, 154-157.
  82. //   This function will periodically yield control to the
  83. // designated yield function.  If the yield function
  84. // returns TRUE, then region building is aborted and a
  85. // flag is set so that subsequent calls to NumQC() will
  86. // return a 0.
  87.  
  88. Region::Region (PointListHeader &vertex_list)
  89. // vertex_list  is an array of points describing the
  90. //              outline of the region.  The path is
  91. //              automatically closed from the last to
  92. //              the first point.
  93. {
  94.   first_qcnode = NULL;
  95.   aborted = FALSE;
  96.  
  97.   ndiv = vertex_list.ndiv;
  98.   int nquits = MaxQuits();
  99.   assert (nquits > 0);
  100.   // Reject polygons that are invisible.
  101.   assert (vertex_list.length >= 3);
  102.  
  103.   // Get enough memory to store entire edge table:
  104.   EdgeState *edge_table_buf;
  105.   edge_table_buf = new EdgeState[vertex_list.length];
  106.   assert (edge_table_buf != NULL);
  107.  
  108.   // Build the global edge table:
  109.   BuildGET (vertex_list, edge_table_buf, min_i, max_i);
  110.  
  111.   // Scan down through polygon edges, one scan line at
  112.   // a time, so long as at least one edge remains in
  113.   // either the GET or AET.
  114.   // Initialize the active edge table to empty:
  115.   AETptr = NULL;
  116.   // Start at the top polygon vertex.
  117.   current_i = GETptr->start_i;
  118.   int nqc_compress = 0; // qc's added since compression
  119.   while ((GETptr != NULL) || (AETptr != NULL))
  120.   {
  121.     // Update AET for this scan line.
  122.     MoveJSortedToAET (current_i);
  123.     // Add quadcodes for this scan line.
  124.     ScanOutAET (current_i, nqc_compress, nquits);
  125.     // Advance AET edges one scan line.
  126.     AdvanceAET();
  127.     // Re-sort on J.
  128.     JSortAET();
  129.     // Advance to next scan line.
  130.     current_i--;
  131.  
  132.     // Single compression pass after 100 quadcodes
  133.     if (nqc_compress > 100)
  134.     {
  135.       nqc_compress = 0;
  136.       (void)Compress();
  137.     }
  138.  
  139.     // Yield to the user or another application after each
  140.     // scan line:
  141.     if (RegionYieldFunc (PctComplete()))
  142.     {
  143.       // The process has been aborted.
  144.       // Set a flag, release dynamic memory, and return.
  145.       aborted = TRUE;
  146.       delete edge_table_buf;
  147.       return;
  148.     }
  149.  
  150.   }
  151.  
  152.   // Release dynamic memory
  153.   delete edge_table_buf;
  154.  
  155.   // Final compression, until nothing more to compress:
  156.   while (Compress())
  157.     ;
  158.  
  159. } // Region::Region
  160.  
  161. ///////////////////////////////////////////////////////
  162. // Region::ScanOutAET: Create quadcodes along an entire
  163. // row, using the odd/even fill rule.
  164.  
  165. void Region::ScanOutAET
  166.     (COORD i_to_scan, int &nqc_compress, int nquits)
  167. // i_to_scan    is the row # to scan
  168. // nqc_compress is the # qc's added since last compress
  169. // nquits       is the # of quits to use in each qc
  170. {
  171.   // Scan through AET, filling areas along current row
  172.   // as each pair of edge crossings is encountered.
  173.   // Nearest pixel on or to the right of left edges is
  174.   // drawn, and nearest pixel to the left of but not on
  175.   // the right edges is drawn.
  176.   EdgeState *current_edge = AETptr;
  177.   while (current_edge != NULL)
  178.   {
  179.     COORD left_j = current_edge->j;
  180.     current_edge = current_edge->next_edge;
  181.     AddRow (i_to_scan, left_j, current_edge->j - 1,
  182.         nquits);
  183.     nqc_compress += abs (current_edge->j - left_j);
  184.     current_edge = current_edge->next_edge;
  185.   }
  186. } // Region::ScanOutAET
  187.  
  188. ///////////////////////////////////////////////////////
  189. // Region::AddRow: Add an entire row of quadcodes.
  190.  
  191. void Region::AddRow
  192.     (COORD i, COORD j1, COORD j2, int nquits)
  193. // i        is the I coordinate of the row
  194. // j1       is the J coordinate at one end of the row
  195. // j2       is the J coordinate at other end of the row
  196. // nquits   is the # quits in the quadcode to add
  197. {
  198.   COORD j;
  199.   COORD jmin = min (j1, j2);
  200.   COORD jmax = max (j1, j2);
  201.  
  202.   for (j = jmax; j >= jmin; j--)
  203.     AddQC (i, j, nquits);
  204. } // Region::AddRow
  205.  
  206. ///////////////////////////////////////////////////////
  207. // Region::AddQC: Add a single quadcode to a region.
  208.  
  209. void Region::AddQC (COORD i, COORD j, int nquits)
  210. // i        is the I coordinate of the quadcode
  211. // j        is the J coordinate of the quadcode
  212. // nquits   is the # quits in the quadcode to add
  213. {
  214.   QCNode  *new_qcn = new QCNode (i, j, nquits);
  215.   assert (new_qcn != NULL);
  216.  
  217.   // Insert into linked list in sorted order.
  218.   QCNode  *qcn,
  219.           *prev = NULL;
  220.  
  221.   for (qcn = first_qcnode; qcn; qcn = qcn->next)
  222.   {
  223.     if (*new_qcn <= *qcn)
  224.     {
  225.       // Found insertion point
  226.       if (*new_qcn == *qcn)
  227.       {
  228.         // Quadcode already in list - don't add again.
  229.         delete new_qcn;
  230.         return;
  231.       }
  232.       break;
  233.     }
  234.     prev = qcn;
  235.   } // for qcn
  236.  
  237.   new_qcn->next = qcn;
  238.   if (prev)
  239.     prev->next = new_qcn;
  240.   else
  241.     // Add to head of list
  242.     first_qcnode = new_qcn;
  243.  
  244. } // Region::AddQC
  245.  
  246. ///////////////////////////////////////////////////////
  247. // Region::~Region: Region destructor
  248.  
  249. Region::~Region (void)
  250. {
  251.   QCNode  *qcn,
  252.           *nextqcn;
  253.  
  254.   // Release the linked list of quadcode nodes
  255.   for (qcn = first_qcnode; qcn; qcn = nextqcn)
  256.   {
  257.     nextqcn = qcn->next;
  258.     delete qcn;
  259.   }
  260.   first_qcnode = NULL;
  261. } // Region::~Region
  262.  
  263. ///////////////////////////////////////////////////////
  264. // Region::Compress: This function makes a single pass
  265. // at compressing a region, by finding any four consec-
  266. // utive quadcodes that are siblings and replacing them
  267. // with their parent.  Return TRUE if any compression
  268. // took place, or FALSE if the region is unchanged.
  269. // To fully compress the region, this function should
  270. // be called repeatedly until FALSE is returned.
  271.  
  272. int Region::Compress (void)
  273. {
  274.   int changed = FALSE;    // has region been changed?
  275.   QCNode *qcn;
  276.  
  277.   for (qcn = first_qcnode; qcn; qcn = qcn->next)
  278.   {
  279.     // Don't compare any top-level qc's because they
  280.     // can't be compressed out.
  281.     if (qcn->nquits < 2)
  282.       continue;
  283.     // Are next four qc's in a row all siblings?
  284.     if (qcn->Sibling (qcn->next) &&
  285.         qcn->next->Sibling (qcn->next->next)
  286.         && qcn->next->next->Sibling (qcn->next->next->next))
  287.     {
  288.       // Yes - One sibling is replaced with its parent,
  289.       // the other 3 are dropped.
  290.       changed = TRUE;
  291.       QCNode *save_next = qcn->next->next->next->next;
  292.       qcn->MakeParent();
  293.       delete qcn->next->next->next;
  294.       delete qcn->next->next;
  295.       delete qcn->next;
  296.       qcn->next = save_next;
  297.     }
  298.   } // for qcn
  299.  
  300.   return (changed);
  301. } // Region::Compress
  302.  
  303. ///////////////////////////////////////////////////////
  304. // Region::InRegion: Return TRUE if the supplied qc is
  305. // within the region boundaries, or FALSE if not.
  306.  
  307. int Region::InRegion (QuadCode &qc)
  308. // qc   is the quadcode to compare
  309. {
  310.   QCNode  *qcn;
  311.  
  312.   for (qcn = first_qcnode; qcn; qcn = qcn->next)
  313.   {
  314.     if (qcn->Contains (qc))
  315.       return (TRUE);
  316.     // If past our quadcode, then done.
  317.     if (*qcn > qc)
  318.       return (FALSE);
  319.   }
  320.  
  321.   return (FALSE);
  322. } // Region::InRegion
  323.  
  324. ///////////////////////////////////////////////////////
  325. // Region::MaxQuits: Compute the max # quits in a qc
  326. // in this region, from the # of (I,J) divisions in the
  327. // entire grid.
  328.  
  329. int Region::MaxQuits (void)
  330. {
  331.   int nq;
  332.   for (nq = 0; nq < MAXQUITS; nq++)
  333.     if (1 << nq >= ndiv)
  334.       break;
  335.   assert (nq != MAXQUITS);
  336.   return (nq);
  337. } // Region::MaxQuits
  338.  
  339. ///////////////////////////////////////////////////////
  340. // Region::NumQC: Count the # quadcodes in the region.
  341.  
  342. int Region::NumQC (void)
  343. {
  344.   int     n;
  345.   QCNode  *qcn;
  346.  
  347.   if (aborted)
  348.     // The region build was aborted.
  349.     return(0);
  350.  
  351.   for (n = 0, qcn = first_qcnode; qcn;
  352.       qcn = qcn->next, n++)
  353.     ;
  354.   return (n);
  355. } // Region::NumQC
  356.  
  357. ///////////////////////////////////////////////////////
  358. // Region::PctComplete: Return the percentage of the
  359. // region that has been built (0 - 100).
  360.  
  361. int Region::PctComplete (void)
  362. {
  363.   if (min_i >= max_i)
  364.     // Haven't started to build region yet.
  365.     return (0);
  366.  
  367.   // The following assumes the region is built from
  368.   // highest I to lowest.
  369.   return ((int) (100.0 * (max_i - current_i) /
  370.         (max_i - min_i)));
  371. } // Region::PctComplete
  372.  
  373. ///////////////////////////////////////////////////////
  374. // operator<<: Overload the "Put to" operator for
  375. // Region output to stream.
  376.  
  377. ostream &operator<< (ostream &stream, Region ®)
  378. // stream     is the stream to print to
  379. // reg        is the region to print
  380. {
  381.   QCNode  *qcn;
  382.  
  383.   if (reg.first_qcnode == NULL)
  384.   {
  385.     stream << "(empty)";
  386.     return (stream);
  387.   }
  388.   for (qcn = reg.first_qcnode; qcn; qcn = qcn->next)
  389.     stream << *qcn << ' ';
  390.   return (stream);
  391. } // operator<<
  392.  
  393. ///////////////////////////////////////////////////////
  394. // BuildGET: Build the global edge table from the
  395. // vertex list.
  396.  
  397. static void BuildGET (PointListHeader &vertex_list,
  398.     EdgeState *next_free_edge, COORD &min_i, COORD &max_i)
  399. // vertex_list    is a list of pts defining perimeter
  400. // next_free_edge is a ptr to array of edge states
  401. {
  402.   // Scan thru vertex list & put all non-zero-height
  403.   // edges into the GET, sorted by decreasing i start
  404.   // coordinate
  405.   Point *vertex_ptr = vertex_list.pointptr;
  406.   GETptr = NULL;
  407.   min_i = LONG_MAX;
  408.   max_i = LONG_MIN;
  409.   int i;
  410.   for (i = 0; i < vertex_list.length; i++)
  411.   {
  412.     // Calculate edge height & width
  413.     COORD start_i = vertex_ptr[i].i;
  414.     COORD start_j = vertex_ptr[i].j;
  415.     COORD end_i, end_j, temp;
  416.  
  417.     // The edge runs from current pt to the prev one.
  418.     if (i == 0)
  419.     {
  420.       // Wrap back around to the end of the list.
  421.       end_i = vertex_ptr[vertex_list.length - 1].i;
  422.       end_j = vertex_ptr[vertex_list.length - 1].j;
  423.     }
  424.     else
  425.     {
  426.       end_i = vertex_ptr[i-1].i;
  427.       end_j = vertex_ptr[i-1].j;
  428.     }
  429.     // Make sure the edge runs bottom to top
  430.     if (end_i > start_i)
  431.     {
  432.       SWAP (start_i, end_i);
  433.       SWAP (start_j, end_j);
  434.     }
  435.  
  436.     // Establish limits of the region
  437.     min_i = min (min_i, end_i);
  438.     max_i = max (max_i, start_i);
  439.  
  440.     // Skip if can't ever be an active edge (0 height).
  441.     COORD delta_i, delta_j;
  442.     if ((delta_i = start_i - end_i) != 0)
  443.     {
  444.       // Allocate space for edge's info, fill in struct
  445.       EdgeState *new_edge_ptr = next_free_edge++;
  446.       // Find direction in which J moves:
  447.       new_edge_ptr->jdirection =
  448.           ((delta_j = end_j - start_j) > 0) ? 1 : -1;
  449.       COORD width = abs(delta_j);
  450.       new_edge_ptr->j = start_j;
  451.       new_edge_ptr->start_i = start_i;
  452.       new_edge_ptr->count = delta_i;
  453.       new_edge_ptr->error_term_adj_down = delta_i;
  454.       if (delta_j >= 0)
  455.         // Initial error term going L->R
  456.         new_edge_ptr->error_term = 0;
  457.       else
  458.         // Initial error term going R->L
  459.         new_edge_ptr->error_term = -delta_i + 1;
  460.       if (delta_i >= width)
  461.       {
  462.         // I-major edge
  463.         new_edge_ptr->whole_pixel_jmove = 0;
  464.         new_edge_ptr->error_term_adj_up = width;
  465.       }
  466.       else
  467.       {
  468.         // J-major edge
  469.         new_edge_ptr->whole_pixel_jmove =
  470.             (width / delta_i) *
  471.             new_edge_ptr->jdirection;
  472.         new_edge_ptr->error_term_adj_up =
  473.             width % delta_i;
  474.       }
  475.  
  476.       // Link new edge into the GET so the edge list is
  477.       // still sorted by I, and by J for all edges with
  478.       // same I.
  479.       EdgeState **following_edge_link = &GETptr;
  480.       EdgeState *following_edge;
  481.       for ( ; ; )
  482.       {
  483.         following_edge = *following_edge_link;
  484.         if ((following_edge == NULL) ||
  485.             (following_edge->start_i < start_i) ||
  486.             ((following_edge->start_i == start_i) &&
  487.              (following_edge->j >= start_j)))
  488.         {
  489.           new_edge_ptr->next_edge = following_edge;
  490.           *following_edge_link = new_edge_ptr;
  491.           break;
  492.         }
  493.         following_edge_link =
  494.             &following_edge->next_edge;
  495.       } // for
  496.     } // if delta_i
  497.   } // for i
  498.  
  499. } // BuildGET
  500.  
  501. ///////////////////////////////////////////////////////
  502. // MoveJSortedToAET: Move all edges that start at
  503. // specified row from the GET to the AET, maintaining J
  504. // sorting of the AET.
  505.  
  506. static void MoveJSortedToAET (COORD i_to_move)
  507. {
  508.   // The GET is I sorted.  Any edges that start at the
  509.   // desired row will be first in the GET, so move
  510.   // edges from the GET to AET until first edge left in
  511.   // the GET is no longer at the desired row.  Also,
  512.   // the GET is J sorted within each row, so each
  513.   // successive edge added to the AET is guaranteed to
  514.   // belong later in the AET than the one just added.
  515.   EdgeState **AET_edge_ptr = &AETptr;
  516.   while ((GETptr != NULL) &&
  517.       (GETptr->start_i == i_to_move))
  518.   {
  519.     int current_j = GETptr->j;
  520.     // Link new edge into the AET so the AET is still
  521.     // sorted by J coordinate.
  522.     for ( ; ; )
  523.     {
  524.       EdgeState *AET_edge = *AET_edge_ptr;
  525.       if ((AET_edge == NULL) ||
  526.           (AET_edge->j >= current_j))
  527.       {
  528.         EdgeState *temp_edge = GETptr->next_edge;
  529.         *AET_edge_ptr = GETptr;   // link edge into AET
  530.         GETptr->next_edge = AET_edge;
  531.         AET_edge_ptr = &GETptr->next_edge;
  532.         GETptr = temp_edge;     // unlink edge from AET
  533.         break;
  534.       }
  535.       else
  536.         AET_edge_ptr = &AET_edge->next_edge;
  537.     } // for
  538.   } // while
  539.  
  540. } // MoveJSortedToAET
  541.  
  542. ///////////////////////////////////////////////////////
  543. // JSortAET: Sort all edges currently in active edge
  544. // table into ascending order of current J.
  545.  
  546. static void JSortAET (void)
  547. {
  548.   // Scan through AET and swap any adjacent edges for
  549.   // which the second edge is at a lower current J
  550.   // coord than the first edge.  Repeat until no
  551.   // further swapping is needed.
  552.   if (AETptr != NULL)
  553.   {
  554.     int swap_occurred;
  555.     do
  556.     {
  557.       swap_occurred = FALSE;
  558.       EdgeState **current_edge_ptr = &AETptr;
  559.       EdgeState *current_edge;
  560.       while ((current_edge =
  561.           *current_edge_ptr)->next_edge != NULL)
  562.       {
  563.         if (current_edge->j >
  564.             current_edge->next_edge->j)
  565.         {
  566.           // The second edge has lower J than first.
  567.           // Swap them in the AET.
  568.           EdgeState *temp_edge =
  569.               current_edge->next_edge->next_edge;
  570.           *current_edge_ptr = current_edge->next_edge;
  571.           current_edge->next_edge->next_edge =
  572.               current_edge;
  573.           current_edge->next_edge = temp_edge;
  574.           swap_occurred = TRUE;
  575.         }
  576.         current_edge_ptr =
  577.             &(*current_edge_ptr)->next_edge;
  578.       } // while
  579.     } while (swap_occurred);
  580.   } // if AETptr
  581. } // JSortAET
  582.  
  583. ///////////////////////////////////////////////////////
  584. // AdvanceAET: Advances each edge in the AET by one
  585. // scan line. Removes edges that are fully scanned.
  586.  
  587. static void AdvanceAET (void)
  588. {
  589.   // Count down and remove or advance each edge in AET.
  590.   EdgeState **current_edge_ptr = &AETptr;
  591.   EdgeState *current_edge;
  592.   while ((current_edge = *current_edge_ptr) != NULL)
  593.   {
  594.     // Count off one scan line for this edge.
  595.     if ((--(current_edge->count)) == 0)
  596.       // This edge is finished, so remove from the AET.
  597.       *current_edge_ptr = current_edge->next_edge;
  598.     else
  599.     {
  600.       // Advance the edge's J coord by minimum move.
  601.       current_edge->j +=
  602.           current_edge->whole_pixel_jmove;
  603.       // Determine whether it's time for J to advance
  604.       // one extra.
  605.       if ((current_edge->error_term +=
  606.           current_edge->error_term_adj_up) > 0)
  607.       {
  608.         current_edge->j += current_edge->jdirection;
  609.         current_edge->error_term -=
  610.             current_edge->error_term_adj_down;
  611.       }
  612.       current_edge_ptr = ¤t_edge->next_edge;
  613.     }
  614.   } // while
  615. } // AdvanceAET
  616.  
  617. ///////////////////////////////////////////////////////
  618. // SetRegionYieldFunc: Set the address of a "yield"
  619. // function.  This function will be called repeatedly
  620. // during region building, to allow the application to
  621. // yield control to the user or another application.
  622. // The percentage complete is passed so the user may be
  623. // kept up to date on the progress of region building.
  624.  
  625. void SetRegionYieldFunc (int (*yield_func) (int pct_complete))
  626. // yield_func       is a pointer to the application's
  627. //                  yield function
  628. {
  629.   RegionYieldFunc = yield_func;
  630. } // SetRegionYieldFunc
  631.  
  632. ///////////////////////////////////////////////////////
  633. // DefaultRegionYieldFunc: The yield function should
  634. // return TRUE if region building should be aborted,
  635. // or FALSE otherwise.
  636.  
  637. int DefaultRegionYieldFunc (int pct_complete)
  638. // pct_complete     is the percent of the region that
  639. //                  has been built (0 - 100)
  640.  
  641. {
  642.   // The default yield function does nothing.
  643.   return (FALSE);
  644. } // DefaultRegionYieldFunc
  645.