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 >
Wrap
C/C++ Source or Header
|
1992-07-12
|
20KB
|
645 lines
///////////////////////////////////////////////////////
// Listing 2 - QCREG.CPP: Quadcode region support
// Written by:
// Kenneth Van Camp
// RR #1 Box 1255
// East Stroudsburg, PA 18301
// (717)223-8620
//
// 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