61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncCopyright 1987, 1998 The Open Group
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncPermission to use, copy, modify, distribute, and sell this software and its
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncdocumentation for any purpose is hereby granted without fee, provided that
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncthe above copyright notice appear in all copies and that both that
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsynccopyright notice and this permission notice appear in supporting
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncdocumentation.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncThe above copyright notice and this permission notice shall be included
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncin all copies or substantial portions of the Software.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncTHE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncOR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncMERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncIN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncOTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncOTHER DEALINGS IN THE SOFTWARE.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncExcept as contained in this notice, the name of The Open Group shall
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncnot be used in advertising or otherwise to promote the sale, use or
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncother dealings in this Software without prior written authorization
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncfrom The Open Group.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * Created by Brian Kelleher; Oct 1985
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * Include file for filled polygon routines.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * These are the data structures needed to scan
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * convert regions. Two different scan conversion
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * methods are available -- the even-odd method, and
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * the winding number method.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * The even-odd rule states that a point is inside
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * the polygon if a ray drawn from that point in any
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * direction will pass through an odd number of
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * path segments.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * By the winding number rule, a point is decided
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * to be inside the polygon if a ray drawn from that
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * point in any direction passes through a different
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * number of clockwise and counter-clockwise path
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * segments.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * These data structures are adapted somewhat from
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * the algorithm in (Foley/Van Dam) for scan converting
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * polygons.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * The basic algorithm is to start at the top (smallest y)
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * of the polygon, stepping down to the bottom of
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * the polygon by incrementing the y coordinate. We
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * keep a list of edges which the current scanline crosses,
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * sorted by x. This list is called the Active Edge Table (AET)
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * As we change the y-coordinate, we update each entry in
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * in the active edge table to reflect the edges new xcoord.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * This list must be sorted at each scanline in case
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * two edges intersect.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * We also keep a data structure known as the Edge Table (ET),
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * which keeps track of all the edges which the current
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * scanline has not yet reached. The ET is basically a
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * list of ScanLineList structures containing a list of
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * edges which are entered at a given scanline. There is one
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * ScanLineList per scanline at which an edge is entered.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * When we enter a new edge, we move it from the ET to the AET.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * From the AET, we can implement the even-odd rule as in
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * The winding number rule is a little trickier. We also
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * keep the EdgeTableEntries in the AET linked by the
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * nextWETE (winding EdgeTableEntry) link. This allows
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * the edges to be linked just as before for updating
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * purposes, but only uses the edges linked by the nextWETE
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * link as edges representing spans of the polygon to
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * drawn (as with the even-odd rule).
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * for the winding number rule
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync BRESINFO bres; /* Bresenham info to run the edge */
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync struct _EdgeTableEntry *next; /* next in the list */
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync struct _EdgeTableEntry *back; /* for insertion sort */
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync struct _EdgeTableEntry *nextWETE; /* for winding num rule */
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsynctypedef struct {
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * Here is a struct to help with storage allocation
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * so we can allocate a big chunk at a time, and then take
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * pieces from this heap when we need to.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * number of points to buffer before sending them off
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * to scanlines() : Must be an even number
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * a few macros for the inner loops of the fill code where
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * performance considerations don't allow a procedure call.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * Evaluate the given edge at the given scanline.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * If the edge has expired, then we leave it and fix up
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * the active edge table; otherwise, we increment the
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * x value to be ready for the next scanline.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * The winding number rule is in effect, so we must notify
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * the caller when the edge has been removed so he
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * can reorder the Winding Active Edge Table.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * Evaluate the given edge at the given scanline.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * If the edge has expired, then we leave it and fix up
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * the active edge table; otherwise, we increment the
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * x value to be ready for the next scanline.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsync * The even-odd rule is in effect.
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncextern _X_EXPORT Bool miCreateETandAET(int /*count */ ,
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncextern _X_EXPORT void miloadAET(EdgeTableEntry * /*AET*/, EdgeTableEntry * /*ETEs */
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncextern _X_EXPORT void micomputeWAET(EdgeTableEntry * /*AET*/);
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncextern _X_EXPORT int miInsertionSort(EdgeTableEntry * /*AET*/);
61cb83a8ccd1dd7f671f31fa93c9d8b7be09b4ccvboxsyncextern _X_EXPORT void miFreeStorage(ScanLineListBlock * /*pSLLBlock */