/*
|
/*
|
* Portions Copyright (c) 2000 Greg Haerr <greg@censoft.com>
|
* Portions Copyright (c) 2000 Greg Haerr <greg@censoft.com>
|
* Somewhat less shamelessly ripped from the Wine distribution
|
* Somewhat less shamelessly ripped from the Wine distribution
|
* and the X Window System.
|
* and the X Window System.
|
*
|
*
|
* Device-independent Microwindows polygon regions, implemented using
|
* Device-independent Microwindows polygon regions, implemented using
|
* multiple rectangles.
|
* multiple rectangles.
|
*
|
*
|
* Shamelessly ripped out from the X11 distribution
|
* Shamelessly ripped out from the X11 distribution
|
* Thanks for the nice licence.
|
* Thanks for the nice licence.
|
*
|
*
|
* Copyright 1993, 1994, 1995 Alexandre Julliard
|
* Copyright 1993, 1994, 1995 Alexandre Julliard
|
* Modifications and additions: Copyright 1998 Huw Davies
|
* Modifications and additions: Copyright 1998 Huw Davies
|
*/
|
*/
|
|
|
/************************************************************************
|
/************************************************************************
|
|
|
Copyright (c) 1987, 1988 X Consortium
|
Copyright (c) 1987, 1988 X Consortium
|
|
|
Permission is hereby granted, free of charge, to any person obtaining a copy
|
Permission is hereby granted, free of charge, to any person obtaining a copy
|
of this software and associated documentation files (the "Software"), to deal
|
of this software and associated documentation files (the "Software"), to deal
|
in the Software without restriction, including without limitation the rights
|
in the Software without restriction, including without limitation the rights
|
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
copies of the Software, and to permit persons to whom the Software is
|
copies of the Software, and to permit persons to whom the Software is
|
furnished to do so, subject to the following conditions:
|
furnished to do so, subject to the following conditions:
|
|
|
The above copyright notice and this permission notice shall be included in
|
The above copyright notice and this permission notice shall be included in
|
all copies or substantial portions of the Software.
|
all copies or substantial portions of the Software.
|
|
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
|
X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
|
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
|
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
|
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
|
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
|
|
|
Except as contained in this notice, the name of the X Consortium shall not be
|
Except as contained in this notice, the name of the X Consortium shall not be
|
used in advertising or otherwise to promote the sale, use or other dealings
|
used in advertising or otherwise to promote the sale, use or other dealings
|
in this Software without prior written authorization from the X Consortium.
|
in this Software without prior written authorization from the X Consortium.
|
|
|
|
|
Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
|
Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
|
|
|
All Rights Reserved
|
All Rights Reserved
|
|
|
Permission to use, copy, modify, and distribute this software and its
|
Permission to use, copy, modify, and distribute this software and its
|
documentation for any purpose and without fee is hereby granted,
|
documentation for any purpose and without fee is hereby granted,
|
provided that the above copyright notice appear in all copies and that
|
provided that the above copyright notice appear in all copies and that
|
both that copyright notice and this permission notice appear in
|
both that copyright notice and this permission notice appear in
|
supporting documentation, and that the name of Digital not be
|
supporting documentation, and that the name of Digital not be
|
used in advertising or publicity pertaining to distribution of the
|
used in advertising or publicity pertaining to distribution of the
|
software without specific, written prior permission.
|
software without specific, written prior permission.
|
|
|
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
|
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
|
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
|
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
|
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
|
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
|
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
|
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
|
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
|
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
|
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
|
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
|
SOFTWARE.
|
SOFTWARE.
|
|
|
************************************************************************/
|
************************************************************************/
|
|
|
#include <stdio.h>
|
#include <stdio.h>
|
#include <stdlib.h>
|
#include <stdlib.h>
|
#include "device.h"
|
#include "device.h"
|
|
|
#if POLYREGIONS
|
#if POLYREGIONS
|
|
|
/*
|
/*
|
* number of points to buffer before sending them off
|
* number of points to buffer before sending them off
|
* to scanlines() : Must be an even number
|
* to scanlines() : Must be an even number
|
*/
|
*/
|
#define NUMPTSTOBUFFER 200
|
#define NUMPTSTOBUFFER 200
|
|
|
/*
|
/*
|
* used to allocate buffers for points and link
|
* used to allocate buffers for points and link
|
* the buffers together
|
* the buffers together
|
*/
|
*/
|
|
|
typedef struct _POINTBLOCK {
|
typedef struct _POINTBLOCK {
|
MWPOINT pts[NUMPTSTOBUFFER];
|
MWPOINT pts[NUMPTSTOBUFFER];
|
struct _POINTBLOCK *next;
|
struct _POINTBLOCK *next;
|
} POINTBLOCK;
|
} POINTBLOCK;
|
|
|
/*
|
/*
|
* This file contains a few macros to help track
|
* This file contains a few macros to help track
|
* the edge of a filled object. The object is assumed
|
* the edge of a filled object. The object is assumed
|
* to be filled in scanline order, and thus the
|
* to be filled in scanline order, and thus the
|
* algorithm used is an extension of Bresenham's line
|
* algorithm used is an extension of Bresenham's line
|
* drawing algorithm which assumes that y is always the
|
* drawing algorithm which assumes that y is always the
|
* major axis.
|
* major axis.
|
* Since these pieces of code are the same for any filled shape,
|
* Since these pieces of code are the same for any filled shape,
|
* it is more convenient to gather the library in one
|
* it is more convenient to gather the library in one
|
* place, but since these pieces of code are also in
|
* place, but since these pieces of code are also in
|
* the inner loops of output primitives, procedure call
|
* the inner loops of output primitives, procedure call
|
* overhead is out of the question.
|
* overhead is out of the question.
|
* See the author for a derivation if needed.
|
* See the author for a derivation if needed.
|
*/
|
*/
|
|
|
/*
|
/*
|
* In scan converting polygons, we want to choose those pixels
|
* In scan converting polygons, we want to choose those pixels
|
* which are inside the polygon. Thus, we add .5 to the starting
|
* which are inside the polygon. Thus, we add .5 to the starting
|
* x coordinate for both left and right edges. Now we choose the
|
* x coordinate for both left and right edges. Now we choose the
|
* first pixel which is inside the pgon for the left edge and the
|
* first pixel which is inside the pgon for the left edge and the
|
* first pixel which is outside the pgon for the right edge.
|
* first pixel which is outside the pgon for the right edge.
|
* Draw the left pixel, but not the right.
|
* Draw the left pixel, but not the right.
|
*
|
*
|
* How to add .5 to the starting x coordinate:
|
* How to add .5 to the starting x coordinate:
|
* If the edge is moving to the right, then subtract dy from the
|
* If the edge is moving to the right, then subtract dy from the
|
* error term from the general form of the algorithm.
|
* error term from the general form of the algorithm.
|
* If the edge is moving to the left, then add dy to the error term.
|
* If the edge is moving to the left, then add dy to the error term.
|
*
|
*
|
* The reason for the difference between edges moving to the left
|
* The reason for the difference between edges moving to the left
|
* and edges moving to the right is simple: If an edge is moving
|
* and edges moving to the right is simple: If an edge is moving
|
* to the right, then we want the algorithm to flip immediately.
|
* to the right, then we want the algorithm to flip immediately.
|
* If it is moving to the left, then we don't want it to flip until
|
* If it is moving to the left, then we don't want it to flip until
|
* we traverse an entire pixel.
|
* we traverse an entire pixel.
|
*/
|
*/
|
|
|
#define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
|
#define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
|
int dx; /* local storage */ \
|
int dx; /* local storage */ \
|
\
|
\
|
/* \
|
/* \
|
* if the edge is horizontal, then it is ignored \
|
* if the edge is horizontal, then it is ignored \
|
* and assumed not to be processed. Otherwise, do this stuff. \
|
* and assumed not to be processed. Otherwise, do this stuff. \
|
*/ \
|
*/ \
|
if ((dy) != 0) { \
|
if ((dy) != 0) { \
|
xStart = (x1); \
|
xStart = (x1); \
|
dx = (x2) - xStart; \
|
dx = (x2) - xStart; \
|
if (dx < 0) { \
|
if (dx < 0) { \
|
m = dx / (dy); \
|
m = dx / (dy); \
|
m1 = m - 1; \
|
m1 = m - 1; \
|
incr1 = (-2) * (dx) + 2 * (dy) * (m1); \
|
incr1 = (-2) * (dx) + 2 * (dy) * (m1); \
|
incr2 = (-2) * (dx) + 2 * (dy) * (m); \
|
incr2 = (-2) * (dx) + 2 * (dy) * (m); \
|
d = 2 * (m) * (dy) - 2 * (dx) - 2 * (dy); \
|
d = 2 * (m) * (dy) - 2 * (dx) - 2 * (dy); \
|
} else { \
|
} else { \
|
m = dx / (dy); \
|
m = dx / (dy); \
|
m1 = m + 1; \
|
m1 = m + 1; \
|
incr1 = (2 * dx) - 2 * (dy) * m1; \
|
incr1 = (2 * dx) - 2 * (dy) * m1; \
|
incr2 = (2 * dx) - 2 * (dy) * m; \
|
incr2 = (2 * dx) - 2 * (dy) * m; \
|
d = (-2) * m * (dy) + 2 * dx; \
|
d = (-2) * m * (dy) + 2 * dx; \
|
} \
|
} \
|
} \
|
} \
|
}
|
}
|
|
|
#define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
|
#define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
|
if (m1 > 0) { \
|
if (m1 > 0) { \
|
if (d > 0) { \
|
if (d > 0) { \
|
minval += m1; \
|
minval += m1; \
|
d += incr1; \
|
d += incr1; \
|
} \
|
} \
|
else { \
|
else { \
|
minval += m; \
|
minval += m; \
|
d += incr2; \
|
d += incr2; \
|
} \
|
} \
|
} else {\
|
} else {\
|
if (d >= 0) { \
|
if (d >= 0) { \
|
minval += m1; \
|
minval += m1; \
|
d += incr1; \
|
d += incr1; \
|
} \
|
} \
|
else { \
|
else { \
|
minval += m; \
|
minval += m; \
|
d += incr2; \
|
d += incr2; \
|
} \
|
} \
|
} \
|
} \
|
}
|
}
|
|
|
|
|
/*
|
/*
|
* This structure contains all of the information needed
|
* This structure contains all of the information needed
|
* to run the bresenham algorithm.
|
* to run the bresenham algorithm.
|
* The variables may be hardcoded into the declarations
|
* The variables may be hardcoded into the declarations
|
* instead of using this structure to make use of
|
* instead of using this structure to make use of
|
* register declarations.
|
* register declarations.
|
*/
|
*/
|
typedef struct {
|
typedef struct {
|
MWCOORD minor_axis; /* minor axis */
|
MWCOORD minor_axis; /* minor axis */
|
int d; /* decision variable */
|
int d; /* decision variable */
|
int m, m1; /* slope and slope+1 */
|
int m, m1; /* slope and slope+1 */
|
int incr1, incr2; /* error increments */
|
int incr1, incr2; /* error increments */
|
} BRESINFO;
|
} BRESINFO;
|
|
|
#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
|
#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
|
BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
|
BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
|
bres.m, bres.m1, bres.incr1, bres.incr2)
|
bres.m, bres.m1, bres.incr1, bres.incr2)
|
|
|
#define BRESINCRPGONSTRUCT(bres) \
|
#define BRESINCRPGONSTRUCT(bres) \
|
BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
|
BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
|
|
|
|
|
/*
|
/*
|
* These are the data structures needed to scan
|
* These are the data structures needed to scan
|
* convert regions. Two different scan conversion
|
* convert regions. Two different scan conversion
|
* methods are available -- the even-odd method, and
|
* methods are available -- the even-odd method, and
|
* the winding number method.
|
* the winding number method.
|
* The even-odd rule states that a point is inside
|
* The even-odd rule states that a point is inside
|
* the polygon if a ray drawn from that point in any
|
* the polygon if a ray drawn from that point in any
|
* direction will pass through an odd number of
|
* direction will pass through an odd number of
|
* path segments.
|
* path segments.
|
* By the winding number rule, a point is decided
|
* By the winding number rule, a point is decided
|
* to be inside the polygon if a ray drawn from that
|
* to be inside the polygon if a ray drawn from that
|
* point in any direction passes through a different
|
* point in any direction passes through a different
|
* number of clockwise and counter-clockwise path
|
* number of clockwise and counter-clockwise path
|
* segments.
|
* segments.
|
*
|
*
|
* These data structures are adapted somewhat from
|
* These data structures are adapted somewhat from
|
* the algorithm in (Foley/Van Dam) for scan converting
|
* the algorithm in (Foley/Van Dam) for scan converting
|
* polygons.
|
* polygons.
|
* The basic algorithm is to start at the top (smallest y)
|
* The basic algorithm is to start at the top (smallest y)
|
* of the polygon, stepping down to the bottom of
|
* of the polygon, stepping down to the bottom of
|
* the polygon by incrementing the y coordinate. We
|
* the polygon by incrementing the y coordinate. We
|
* keep a list of edges which the current scanline crosses,
|
* keep a list of edges which the current scanline crosses,
|
* sorted by x. This list is called the Active Edge Table (AET)
|
* sorted by x. This list is called the Active Edge Table (AET)
|
* As we change the y-coordinate, we update each entry in
|
* As we change the y-coordinate, we update each entry in
|
* in the active edge table to reflect the edges new xcoord.
|
* in the active edge table to reflect the edges new xcoord.
|
* This list must be sorted at each scanline in case
|
* This list must be sorted at each scanline in case
|
* two edges intersect.
|
* two edges intersect.
|
* We also keep a data structure known as the Edge Table (ET),
|
* We also keep a data structure known as the Edge Table (ET),
|
* which keeps track of all the edges which the current
|
* which keeps track of all the edges which the current
|
* scanline has not yet reached. The ET is basically a
|
* scanline has not yet reached. The ET is basically a
|
* list of ScanLineList structures containing a list of
|
* list of ScanLineList structures containing a list of
|
* edges which are entered at a given scanline. There is one
|
* edges which are entered at a given scanline. There is one
|
* ScanLineList per scanline at which an edge is entered.
|
* ScanLineList per scanline at which an edge is entered.
|
* When we enter a new edge, we move it from the ET to the AET.
|
* When we enter a new edge, we move it from the ET to the AET.
|
*
|
*
|
* From the AET, we can implement the even-odd rule as in
|
* From the AET, we can implement the even-odd rule as in
|
* (Foley/Van Dam).
|
* (Foley/Van Dam).
|
* The winding number rule is a little trickier. We also
|
* The winding number rule is a little trickier. We also
|
* keep the EdgeTableEntries in the AET linked by the
|
* keep the EdgeTableEntries in the AET linked by the
|
* nextWETE (winding EdgeTableEntry) link. This allows
|
* nextWETE (winding EdgeTableEntry) link. This allows
|
* the edges to be linked just as before for updating
|
* the edges to be linked just as before for updating
|
* purposes, but only uses the edges linked by the nextWETE
|
* purposes, but only uses the edges linked by the nextWETE
|
* link as edges representing spans of the polygon to
|
* link as edges representing spans of the polygon to
|
* drawn (as with the even-odd rule).
|
* drawn (as with the even-odd rule).
|
*/
|
*/
|
|
|
/*
|
/*
|
* for the winding number rule
|
* for the winding number rule
|
*/
|
*/
|
#define CLOCKWISE 1
|
#define CLOCKWISE 1
|
#define COUNTERCLOCKWISE -1
|
#define COUNTERCLOCKWISE -1
|
|
|
typedef struct _EdgeTableEntry {
|
typedef struct _EdgeTableEntry {
|
MWCOORD ymax; /* ycoord at which we exit this edge. */
|
MWCOORD ymax; /* ycoord at which we exit this edge. */
|
BRESINFO bres; /* Bresenham info to run the edge */
|
BRESINFO bres; /* Bresenham info to run the edge */
|
struct _EdgeTableEntry *next; /* next in the list */
|
struct _EdgeTableEntry *next; /* next in the list */
|
struct _EdgeTableEntry *back; /* for insertion sort */
|
struct _EdgeTableEntry *back; /* for insertion sort */
|
struct _EdgeTableEntry *nextWETE; /* for winding num rule */
|
struct _EdgeTableEntry *nextWETE; /* for winding num rule */
|
int ClockWise; /* flag for winding number rule */
|
int ClockWise; /* flag for winding number rule */
|
} EdgeTableEntry;
|
} EdgeTableEntry;
|
|
|
|
|
typedef struct _ScanLineList{
|
typedef struct _ScanLineList{
|
int scanline; /* the scanline represented */
|
int scanline; /* the scanline represented */
|
EdgeTableEntry *edgelist; /* header node */
|
EdgeTableEntry *edgelist; /* header node */
|
struct _ScanLineList *next; /* next in the list */
|
struct _ScanLineList *next; /* next in the list */
|
} ScanLineList;
|
} ScanLineList;
|
|
|
|
|
typedef struct {
|
typedef struct {
|
MWCOORD ymax; /* ymax for the polygon */
|
MWCOORD ymax; /* ymax for the polygon */
|
MWCOORD ymin; /* ymin for the polygon */
|
MWCOORD ymin; /* ymin for the polygon */
|
ScanLineList scanlines; /* header node */
|
ScanLineList scanlines; /* header node */
|
} EdgeTable;
|
} EdgeTable;
|
|
|
|
|
/*
|
/*
|
* Here is a struct to help with storage allocation
|
* Here is a struct to help with storage allocation
|
* so we can allocate a big chunk at a time, and then take
|
* so we can allocate a big chunk at a time, and then take
|
* pieces from this heap when we need to.
|
* pieces from this heap when we need to.
|
*/
|
*/
|
#define SLLSPERBLOCK 25
|
#define SLLSPERBLOCK 25
|
|
|
typedef struct _ScanLineListBlock {
|
typedef struct _ScanLineListBlock {
|
ScanLineList SLLs[SLLSPERBLOCK];
|
ScanLineList SLLs[SLLSPERBLOCK];
|
struct _ScanLineListBlock *next;
|
struct _ScanLineListBlock *next;
|
} ScanLineListBlock;
|
} ScanLineListBlock;
|
|
|
/*
|
/*
|
*
|
*
|
* a few macros for the inner loops of the fill code where
|
* a few macros for the inner loops of the fill code where
|
* performance considerations don't allow a procedure call.
|
* performance considerations don't allow a procedure call.
|
*
|
*
|
* Evaluate the given edge at the given scanline.
|
* Evaluate the given edge at the given scanline.
|
* If the edge has expired, then we leave it and fix up
|
* If the edge has expired, then we leave it and fix up
|
* the active edge table; otherwise, we increment the
|
* the active edge table; otherwise, we increment the
|
* x value to be ready for the next scanline.
|
* x value to be ready for the next scanline.
|
* The winding number rule is in effect, so we must notify
|
* The winding number rule is in effect, so we must notify
|
* the caller when the edge has been removed so he
|
* the caller when the edge has been removed so he
|
* can reorder the Winding Active Edge Table.
|
* can reorder the Winding Active Edge Table.
|
*/
|
*/
|
#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
|
#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
|
if (pAET->ymax == y) { /* leaving this edge */ \
|
if (pAET->ymax == y) { /* leaving this edge */ \
|
pPrevAET->next = pAET->next; \
|
pPrevAET->next = pAET->next; \
|
pAET = pPrevAET->next; \
|
pAET = pPrevAET->next; \
|
fixWAET = 1; \
|
fixWAET = 1; \
|
if (pAET) \
|
if (pAET) \
|
pAET->back = pPrevAET; \
|
pAET->back = pPrevAET; \
|
} \
|
} \
|
else { \
|
else { \
|
BRESINCRPGONSTRUCT(pAET->bres); \
|
BRESINCRPGONSTRUCT(pAET->bres); \
|
pPrevAET = pAET; \
|
pPrevAET = pAET; \
|
pAET = pAET->next; \
|
pAET = pAET->next; \
|
} \
|
} \
|
}
|
}
|
|
|
|
|
/*
|
/*
|
* Evaluate the given edge at the given scanline.
|
* Evaluate the given edge at the given scanline.
|
* If the edge has expired, then we leave it and fix up
|
* If the edge has expired, then we leave it and fix up
|
* the active edge table; otherwise, we increment the
|
* the active edge table; otherwise, we increment the
|
* x value to be ready for the next scanline.
|
* x value to be ready for the next scanline.
|
* The even-odd rule is in effect.
|
* The even-odd rule is in effect.
|
*/
|
*/
|
#define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
|
#define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
|
if (pAET->ymax == y) { /* leaving this edge */ \
|
if (pAET->ymax == y) { /* leaving this edge */ \
|
pPrevAET->next = pAET->next; \
|
pPrevAET->next = pAET->next; \
|
pAET = pPrevAET->next; \
|
pAET = pPrevAET->next; \
|
if (pAET) \
|
if (pAET) \
|
pAET->back = pPrevAET; \
|
pAET->back = pPrevAET; \
|
} \
|
} \
|
else { \
|
else { \
|
BRESINCRPGONSTRUCT(pAET->bres); \
|
BRESINCRPGONSTRUCT(pAET->bres); \
|
pPrevAET = pAET; \
|
pPrevAET = pAET; \
|
pAET = pAET->next; \
|
pAET = pAET->next; \
|
} \
|
} \
|
}
|
}
|
|
|
|
|
|
|
#define LARGE_COORDINATE 0x7fffffff /* FIXME */
|
#define LARGE_COORDINATE 0x7fffffff /* FIXME */
|
#define SMALL_COORDINATE 0x80000000
|
#define SMALL_COORDINATE 0x80000000
|
|
|
/*
|
/*
|
* REGION_InsertEdgeInET
|
* REGION_InsertEdgeInET
|
*
|
*
|
* Insert the given edge into the edge table.
|
* Insert the given edge into the edge table.
|
* First we must find the correct bucket in the
|
* First we must find the correct bucket in the
|
* Edge table, then find the right slot in the
|
* Edge table, then find the right slot in the
|
* bucket. Finally, we can insert it.
|
* bucket. Finally, we can insert it.
|
*
|
*
|
*/
|
*/
|
static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
|
static void REGION_InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE,
|
int scanline, ScanLineListBlock **SLLBlock, int *iSLLBlock)
|
int scanline, ScanLineListBlock **SLLBlock, int *iSLLBlock)
|
|
|
{
|
{
|
EdgeTableEntry *start, *prev;
|
EdgeTableEntry *start, *prev;
|
ScanLineList *pSLL, *pPrevSLL;
|
ScanLineList *pSLL, *pPrevSLL;
|
ScanLineListBlock *tmpSLLBlock;
|
ScanLineListBlock *tmpSLLBlock;
|
|
|
/*
|
/*
|
* find the right bucket to put the edge into
|
* find the right bucket to put the edge into
|
*/
|
*/
|
pPrevSLL = &ET->scanlines;
|
pPrevSLL = &ET->scanlines;
|
pSLL = pPrevSLL->next;
|
pSLL = pPrevSLL->next;
|
while (pSLL && (pSLL->scanline < scanline))
|
while (pSLL && (pSLL->scanline < scanline))
|
{
|
{
|
pPrevSLL = pSLL;
|
pPrevSLL = pSLL;
|
pSLL = pSLL->next;
|
pSLL = pSLL->next;
|
}
|
}
|
|
|
/*
|
/*
|
* reassign pSLL (pointer to ScanLineList) if necessary
|
* reassign pSLL (pointer to ScanLineList) if necessary
|
*/
|
*/
|
if ((!pSLL) || (pSLL->scanline > scanline))
|
if ((!pSLL) || (pSLL->scanline > scanline))
|
{
|
{
|
if (*iSLLBlock > SLLSPERBLOCK-1)
|
if (*iSLLBlock > SLLSPERBLOCK-1)
|
{
|
{
|
tmpSLLBlock = malloc( sizeof(ScanLineListBlock));
|
tmpSLLBlock = malloc( sizeof(ScanLineListBlock));
|
if(!tmpSLLBlock)
|
if(!tmpSLLBlock)
|
{
|
{
|
return;
|
return;
|
}
|
}
|
(*SLLBlock)->next = tmpSLLBlock;
|
(*SLLBlock)->next = tmpSLLBlock;
|
tmpSLLBlock->next = (ScanLineListBlock *)NULL;
|
tmpSLLBlock->next = (ScanLineListBlock *)NULL;
|
*SLLBlock = tmpSLLBlock;
|
*SLLBlock = tmpSLLBlock;
|
*iSLLBlock = 0;
|
*iSLLBlock = 0;
|
}
|
}
|
pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
|
pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
|
|
|
pSLL->next = pPrevSLL->next;
|
pSLL->next = pPrevSLL->next;
|
pSLL->edgelist = (EdgeTableEntry *)NULL;
|
pSLL->edgelist = (EdgeTableEntry *)NULL;
|
pPrevSLL->next = pSLL;
|
pPrevSLL->next = pSLL;
|
}
|
}
|
pSLL->scanline = scanline;
|
pSLL->scanline = scanline;
|
|
|
/*
|
/*
|
* now insert the edge in the right bucket
|
* now insert the edge in the right bucket
|
*/
|
*/
|
prev = (EdgeTableEntry *)NULL;
|
prev = (EdgeTableEntry *)NULL;
|
start = pSLL->edgelist;
|
start = pSLL->edgelist;
|
while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
|
while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
|
{
|
{
|
prev = start;
|
prev = start;
|
start = start->next;
|
start = start->next;
|
}
|
}
|
ETE->next = start;
|
ETE->next = start;
|
|
|
if (prev)
|
if (prev)
|
prev->next = ETE;
|
prev->next = ETE;
|
else
|
else
|
pSLL->edgelist = ETE;
|
pSLL->edgelist = ETE;
|
}
|
}
|
|
|
|
|
/*
|
/*
|
* REGION_CreateEdgeTable
|
* REGION_CreateEdgeTable
|
*
|
*
|
* This routine creates the edge table for
|
* This routine creates the edge table for
|
* scan converting polygons.
|
* scan converting polygons.
|
* The Edge Table (ET) looks like:
|
* The Edge Table (ET) looks like:
|
*
|
*
|
* EdgeTable
|
* EdgeTable
|
* --------
|
* --------
|
* | ymax | ScanLineLists
|
* | ymax | ScanLineLists
|
* |scanline|-->------------>-------------->...
|
* |scanline|-->------------>-------------->...
|
* -------- |scanline| |scanline|
|
* -------- |scanline| |scanline|
|
* |edgelist| |edgelist|
|
* |edgelist| |edgelist|
|
* --------- ---------
|
* --------- ---------
|
* | |
|
* | |
|
* | |
|
* | |
|
* V V
|
* V V
|
* list of ETEs list of ETEs
|
* list of ETEs list of ETEs
|
*
|
*
|
* where ETE is an EdgeTableEntry data structure,
|
* where ETE is an EdgeTableEntry data structure,
|
* and there is one ScanLineList per scanline at
|
* and there is one ScanLineList per scanline at
|
* which an edge is initially entered.
|
* which an edge is initially entered.
|
*
|
*
|
*/
|
*/
|
static void REGION_CreateETandAET(int *Count, int nbpolygons,
|
static void REGION_CreateETandAET(int *Count, int nbpolygons,
|
MWPOINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
|
MWPOINT *pts, EdgeTable *ET, EdgeTableEntry *AET,
|
EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
|
EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
|
{
|
{
|
MWPOINT *top, *bottom;
|
MWPOINT *top, *bottom;
|
MWPOINT *PrevPt, *CurrPt, *EndPt;
|
MWPOINT *PrevPt, *CurrPt, *EndPt;
|
int poly, count;
|
int poly, count;
|
int iSLLBlock = 0;
|
int iSLLBlock = 0;
|
int dy;
|
int dy;
|
|
|
|
|
/*
|
/*
|
* initialize the Active Edge Table
|
* initialize the Active Edge Table
|
*/
|
*/
|
AET->next = (EdgeTableEntry *)NULL;
|
AET->next = (EdgeTableEntry *)NULL;
|
AET->back = (EdgeTableEntry *)NULL;
|
AET->back = (EdgeTableEntry *)NULL;
|
AET->nextWETE = (EdgeTableEntry *)NULL;
|
AET->nextWETE = (EdgeTableEntry *)NULL;
|
AET->bres.minor_axis = SMALL_COORDINATE;
|
AET->bres.minor_axis = SMALL_COORDINATE;
|
|
|
/*
|
/*
|
* initialize the Edge Table.
|
* initialize the Edge Table.
|
*/
|
*/
|
ET->scanlines.next = (ScanLineList *)NULL;
|
ET->scanlines.next = (ScanLineList *)NULL;
|
ET->ymax = SMALL_COORDINATE;
|
ET->ymax = SMALL_COORDINATE;
|
ET->ymin = LARGE_COORDINATE;
|
ET->ymin = LARGE_COORDINATE;
|
pSLLBlock->next = (ScanLineListBlock *)NULL;
|
pSLLBlock->next = (ScanLineListBlock *)NULL;
|
|
|
EndPt = pts - 1;
|
EndPt = pts - 1;
|
for(poly = 0; poly < nbpolygons; poly++)
|
for(poly = 0; poly < nbpolygons; poly++)
|
{
|
{
|
count = Count[poly];
|
count = Count[poly];
|
EndPt += count;
|
EndPt += count;
|
if(count < 2)
|
if(count < 2)
|
continue;
|
continue;
|
|
|
PrevPt = EndPt;
|
PrevPt = EndPt;
|
|
|
/*
|
/*
|
* for each vertex in the array of points.
|
* for each vertex in the array of points.
|
* In this loop we are dealing with two vertices at
|
* In this loop we are dealing with two vertices at
|
* a time -- these make up one edge of the polygon.
|
* a time -- these make up one edge of the polygon.
|
*/
|
*/
|
while (count--)
|
while (count--)
|
{
|
{
|
CurrPt = pts++;
|
CurrPt = pts++;
|
/*
|
/*
|
* find out which point is above and which is below.
|
* find out which point is above and which is below.
|
*/
|
*/
|
if (PrevPt->y > CurrPt->y)
|
if (PrevPt->y > CurrPt->y)
|
{
|
{
|
bottom = PrevPt, top = CurrPt;
|
bottom = PrevPt, top = CurrPt;
|
pETEs->ClockWise = 0;
|
pETEs->ClockWise = 0;
|
}
|
}
|
else
|
else
|
{
|
{
|
bottom = CurrPt, top = PrevPt;
|
bottom = CurrPt, top = PrevPt;
|
pETEs->ClockWise = 1;
|
pETEs->ClockWise = 1;
|
}
|
}
|
|
|
/*
|
/*
|
* don't add horizontal edges to the Edge table.
|
* don't add horizontal edges to the Edge table.
|
*/
|
*/
|
if (bottom->y != top->y)
|
if (bottom->y != top->y)
|
{
|
{
|
pETEs->ymax = bottom->y-1;
|
pETEs->ymax = bottom->y-1;
|
/* -1 so we don't get last scanline */
|
/* -1 so we don't get last scanline */
|
|
|
/*
|
/*
|
* initialize integer edge algorithm
|
* initialize integer edge algorithm
|
*/
|
*/
|
dy = bottom->y - top->y;
|
dy = bottom->y - top->y;
|
|
|
BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
|
BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
|
|
|
REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
|
REGION_InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock,
|
&iSLLBlock);
|
&iSLLBlock);
|
|
|
if (PrevPt->y > ET->ymax)
|
if (PrevPt->y > ET->ymax)
|
ET->ymax = PrevPt->y;
|
ET->ymax = PrevPt->y;
|
if (PrevPt->y < ET->ymin)
|
if (PrevPt->y < ET->ymin)
|
ET->ymin = PrevPt->y;
|
ET->ymin = PrevPt->y;
|
pETEs++;
|
pETEs++;
|
}
|
}
|
|
|
PrevPt = CurrPt;
|
PrevPt = CurrPt;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/*
|
/*
|
* REGION_loadAET
|
* REGION_loadAET
|
*
|
*
|
* This routine moves EdgeTableEntries from the
|
* This routine moves EdgeTableEntries from the
|
* EdgeTable into the Active Edge Table,
|
* EdgeTable into the Active Edge Table,
|
* leaving them sorted by smaller x coordinate.
|
* leaving them sorted by smaller x coordinate.
|
*
|
*
|
*/
|
*/
|
static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
|
static void REGION_loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
|
{
|
{
|
EdgeTableEntry *pPrevAET;
|
EdgeTableEntry *pPrevAET;
|
EdgeTableEntry *tmp;
|
EdgeTableEntry *tmp;
|
|
|
pPrevAET = AET;
|
pPrevAET = AET;
|
AET = AET->next;
|
AET = AET->next;
|
while (ETEs)
|
while (ETEs)
|
{
|
{
|
while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
|
while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
|
{
|
{
|
pPrevAET = AET;
|
pPrevAET = AET;
|
AET = AET->next;
|
AET = AET->next;
|
}
|
}
|
tmp = ETEs->next;
|
tmp = ETEs->next;
|
ETEs->next = AET;
|
ETEs->next = AET;
|
if (AET)
|
if (AET)
|
AET->back = ETEs;
|
AET->back = ETEs;
|
ETEs->back = pPrevAET;
|
ETEs->back = pPrevAET;
|
pPrevAET->next = ETEs;
|
pPrevAET->next = ETEs;
|
pPrevAET = ETEs;
|
pPrevAET = ETEs;
|
|
|
ETEs = tmp;
|
ETEs = tmp;
|
}
|
}
|
}
|
}
|
|
|
/*
|
/*
|
* REGION_computeWAET
|
* REGION_computeWAET
|
*
|
*
|
* This routine links the AET by the
|
* This routine links the AET by the
|
* nextWETE (winding EdgeTableEntry) link for
|
* nextWETE (winding EdgeTableEntry) link for
|
* use by the winding number rule. The final
|
* use by the winding number rule. The final
|
* Active Edge Table (AET) might look something
|
* Active Edge Table (AET) might look something
|
* like:
|
* like:
|
*
|
*
|
* AET
|
* AET
|
* ---------- --------- ---------
|
* ---------- --------- ---------
|
* |ymax | |ymax | |ymax |
|
* |ymax | |ymax | |ymax |
|
* | ... | |... | |... |
|
* | ... | |... | |... |
|
* |next |->|next |->|next |->...
|
* |next |->|next |->|next |->...
|
* |nextWETE| |nextWETE| |nextWETE|
|
* |nextWETE| |nextWETE| |nextWETE|
|
* --------- --------- ^--------
|
* --------- --------- ^--------
|
* | | |
|
* | | |
|
* V-------------------> V---> ...
|
* V-------------------> V---> ...
|
*
|
*
|
*/
|
*/
|
static void REGION_computeWAET(EdgeTableEntry *AET)
|
static void REGION_computeWAET(EdgeTableEntry *AET)
|
{
|
{
|
EdgeTableEntry *pWETE;
|
EdgeTableEntry *pWETE;
|
int inside = 1;
|
int inside = 1;
|
int isInside = 0;
|
int isInside = 0;
|
|
|
AET->nextWETE = (EdgeTableEntry *)NULL;
|
AET->nextWETE = (EdgeTableEntry *)NULL;
|
pWETE = AET;
|
pWETE = AET;
|
AET = AET->next;
|
AET = AET->next;
|
while (AET)
|
while (AET)
|
{
|
{
|
if (AET->ClockWise)
|
if (AET->ClockWise)
|
isInside++;
|
isInside++;
|
else
|
else
|
isInside--;
|
isInside--;
|
|
|
if ((!inside && !isInside) ||
|
if ((!inside && !isInside) ||
|
( inside && isInside))
|
( inside && isInside))
|
{
|
{
|
pWETE->nextWETE = AET;
|
pWETE->nextWETE = AET;
|
pWETE = AET;
|
pWETE = AET;
|
inside = !inside;
|
inside = !inside;
|
}
|
}
|
AET = AET->next;
|
AET = AET->next;
|
}
|
}
|
pWETE->nextWETE = (EdgeTableEntry *)NULL;
|
pWETE->nextWETE = (EdgeTableEntry *)NULL;
|
}
|
}
|
|
|
/*
|
/*
|
* REGION_InsertionSort
|
* REGION_InsertionSort
|
*
|
*
|
* Just a simple insertion sort using
|
* Just a simple insertion sort using
|
* pointers and back pointers to sort the Active
|
* pointers and back pointers to sort the Active
|
* Edge Table.
|
* Edge Table.
|
*
|
*
|
*/
|
*/
|
static MWBOOL REGION_InsertionSort(EdgeTableEntry *AET)
|
static MWBOOL REGION_InsertionSort(EdgeTableEntry *AET)
|
{
|
{
|
EdgeTableEntry *pETEchase;
|
EdgeTableEntry *pETEchase;
|
EdgeTableEntry *pETEinsert;
|
EdgeTableEntry *pETEinsert;
|
EdgeTableEntry *pETEchaseBackTMP;
|
EdgeTableEntry *pETEchaseBackTMP;
|
MWBOOL changed = FALSE;
|
MWBOOL changed = FALSE;
|
|
|
AET = AET->next;
|
AET = AET->next;
|
while (AET)
|
while (AET)
|
{
|
{
|
pETEinsert = AET;
|
pETEinsert = AET;
|
pETEchase = AET;
|
pETEchase = AET;
|
while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
|
while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
|
pETEchase = pETEchase->back;
|
pETEchase = pETEchase->back;
|
|
|
AET = AET->next;
|
AET = AET->next;
|
if (pETEchase != pETEinsert)
|
if (pETEchase != pETEinsert)
|
{
|
{
|
pETEchaseBackTMP = pETEchase->back;
|
pETEchaseBackTMP = pETEchase->back;
|
pETEinsert->back->next = AET;
|
pETEinsert->back->next = AET;
|
if (AET)
|
if (AET)
|
AET->back = pETEinsert->back;
|
AET->back = pETEinsert->back;
|
pETEinsert->next = pETEchase;
|
pETEinsert->next = pETEchase;
|
pETEchase->back->next = pETEinsert;
|
pETEchase->back->next = pETEinsert;
|
pETEchase->back = pETEinsert;
|
pETEchase->back = pETEinsert;
|
pETEinsert->back = pETEchaseBackTMP;
|
pETEinsert->back = pETEchaseBackTMP;
|
changed = TRUE;
|
changed = TRUE;
|
}
|
}
|
}
|
}
|
return changed;
|
return changed;
|
}
|
}
|
|
|
/*
|
/*
|
* REGION_FreeStorage
|
* REGION_FreeStorage
|
*
|
*
|
* Clean up our act.
|
* Clean up our act.
|
*/
|
*/
|
static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
|
static void REGION_FreeStorage(ScanLineListBlock *pSLLBlock)
|
{
|
{
|
ScanLineListBlock *tmpSLLBlock;
|
ScanLineListBlock *tmpSLLBlock;
|
|
|
while (pSLLBlock)
|
while (pSLLBlock)
|
{
|
{
|
tmpSLLBlock = pSLLBlock->next;
|
tmpSLLBlock = pSLLBlock->next;
|
free( pSLLBlock );
|
free( pSLLBlock );
|
pSLLBlock = tmpSLLBlock;
|
pSLLBlock = tmpSLLBlock;
|
}
|
}
|
}
|
}
|
|
|
|
|
/*
|
/*
|
* REGION_PtsToRegion
|
* REGION_PtsToRegion
|
*
|
*
|
* Create an array of rectangles from a list of points.
|
* Create an array of rectangles from a list of points.
|
*/
|
*/
|
static int REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
|
static int REGION_PtsToRegion(int numFullPtBlocks, int iCurPtBlock,
|
POINTBLOCK *FirstPtBlock, MWCLIPREGION *reg)
|
POINTBLOCK *FirstPtBlock, MWCLIPREGION *reg)
|
{
|
{
|
MWRECT *rects;
|
MWRECT *rects;
|
MWPOINT *pts;
|
MWPOINT *pts;
|
POINTBLOCK *CurPtBlock;
|
POINTBLOCK *CurPtBlock;
|
int i;
|
int i;
|
MWRECT *extents;
|
MWRECT *extents;
|
int numRects;
|
int numRects;
|
|
|
extents = ®->extents;
|
extents = ®->extents;
|
|
|
numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
|
numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
|
|
|
if (!(reg->rects = realloc( reg->rects, sizeof(MWRECT) * numRects )))
|
if (!(reg->rects = realloc( reg->rects, sizeof(MWRECT) * numRects )))
|
return(0);
|
return(0);
|
|
|
reg->size = numRects;
|
reg->size = numRects;
|
CurPtBlock = FirstPtBlock;
|
CurPtBlock = FirstPtBlock;
|
rects = reg->rects - 1;
|
rects = reg->rects - 1;
|
numRects = 0;
|
numRects = 0;
|
extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE;
|
extents->left = LARGE_COORDINATE, extents->right = SMALL_COORDINATE;
|
|
|
for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
|
for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
|
/* the loop uses 2 points per iteration */
|
/* the loop uses 2 points per iteration */
|
i = NUMPTSTOBUFFER >> 1;
|
i = NUMPTSTOBUFFER >> 1;
|
if (!numFullPtBlocks)
|
if (!numFullPtBlocks)
|
i = iCurPtBlock >> 1;
|
i = iCurPtBlock >> 1;
|
for (pts = CurPtBlock->pts; i--; pts += 2) {
|
for (pts = CurPtBlock->pts; i--; pts += 2) {
|
if (pts->x == pts[1].x)
|
if (pts->x == pts[1].x)
|
continue;
|
continue;
|
if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
|
if (numRects && pts->x == rects->left && pts->y == rects->bottom &&
|
pts[1].x == rects->right &&
|
pts[1].x == rects->right &&
|
(numRects == 1 || rects[-1].top != rects->top) &&
|
(numRects == 1 || rects[-1].top != rects->top) &&
|
(i && pts[2].y > pts[1].y)) {
|
(i && pts[2].y > pts[1].y)) {
|
rects->bottom = pts[1].y + 1;
|
rects->bottom = pts[1].y + 1;
|
continue;
|
continue;
|
}
|
}
|
numRects++;
|
numRects++;
|
rects++;
|
rects++;
|
rects->left = pts->x; rects->top = pts->y;
|
rects->left = pts->x; rects->top = pts->y;
|
rects->right = pts[1].x; rects->bottom = pts[1].y + 1;
|
rects->right = pts[1].x; rects->bottom = pts[1].y + 1;
|
if (rects->left < extents->left)
|
if (rects->left < extents->left)
|
extents->left = rects->left;
|
extents->left = rects->left;
|
if (rects->right > extents->right)
|
if (rects->right > extents->right)
|
extents->right = rects->right;
|
extents->right = rects->right;
|
}
|
}
|
CurPtBlock = CurPtBlock->next;
|
CurPtBlock = CurPtBlock->next;
|
}
|
}
|
|
|
if (numRects) {
|
if (numRects) {
|
extents->top = reg->rects->top;
|
extents->top = reg->rects->top;
|
extents->bottom = rects->bottom;
|
extents->bottom = rects->bottom;
|
} else {
|
} else {
|
extents->left = 0;
|
extents->left = 0;
|
extents->top = 0;
|
extents->top = 0;
|
extents->right = 0;
|
extents->right = 0;
|
extents->bottom = 0;
|
extents->bottom = 0;
|
}
|
}
|
reg->numRects = numRects;
|
reg->numRects = numRects;
|
|
|
return(TRUE);
|
return(TRUE);
|
}
|
}
|
|
|
/*
|
/*
|
* GdAllocPolygonRegion
|
* GdAllocPolygonRegion
|
*/
|
*/
|
MWCLIPREGION *
|
MWCLIPREGION *
|
GdAllocPolygonRegion(MWPOINT *points, int count, int mode)
|
GdAllocPolygonRegion(MWPOINT *points, int count, int mode)
|
{
|
{
|
return GdAllocPolyPolygonRegion(points, &count, 1, mode );
|
return GdAllocPolyPolygonRegion(points, &count, 1, mode );
|
}
|
}
|
|
|
/*
|
/*
|
* GdAllocPolyPolygonRegion
|
* GdAllocPolyPolygonRegion
|
*/
|
*/
|
MWCLIPREGION *
|
MWCLIPREGION *
|
GdAllocPolyPolygonRegion(MWPOINT *points, int *count, int nbpolygons, int mode)
|
GdAllocPolyPolygonRegion(MWPOINT *points, int *count, int nbpolygons, int mode)
|
{
|
{
|
MWCLIPREGION *rgn;
|
MWCLIPREGION *rgn;
|
EdgeTableEntry *pAET; /* Active Edge Table */
|
EdgeTableEntry *pAET; /* Active Edge Table */
|
int y; /* current scanline */
|
int y; /* current scanline */
|
int iPts = 0; /* number of pts in buffer */
|
int iPts = 0; /* number of pts in buffer */
|
EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
|
EdgeTableEntry *pWETE; /* Winding Edge Table Entry*/
|
ScanLineList *pSLL; /* current scanLineList */
|
ScanLineList *pSLL; /* current scanLineList */
|
MWPOINT *pts; /* output buffer */
|
MWPOINT *pts; /* output buffer */
|
EdgeTableEntry *pPrevAET; /* ptr to previous AET */
|
EdgeTableEntry *pPrevAET; /* ptr to previous AET */
|
EdgeTable ET; /* header node for ET */
|
EdgeTable ET; /* header node for ET */
|
EdgeTableEntry AET; /* header node for AET */
|
EdgeTableEntry AET; /* header node for AET */
|
EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
|
EdgeTableEntry *pETEs; /* EdgeTableEntries pool */
|
ScanLineListBlock SLLBlock; /* header for scanlinelist */
|
ScanLineListBlock SLLBlock; /* header for scanlinelist */
|
int fixWAET = FALSE;
|
int fixWAET = FALSE;
|
POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
|
POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers */
|
POINTBLOCK *tmpPtBlock;
|
POINTBLOCK *tmpPtBlock;
|
int numFullPtBlocks = 0;
|
int numFullPtBlocks = 0;
|
int poly, total;
|
int poly, total;
|
|
|
if(!(rgn = GdAllocRegion()))
|
if(!(rgn = GdAllocRegion()))
|
return NULL;
|
return NULL;
|
|
|
/* special case a rectangle */
|
/* special case a rectangle */
|
|
|
if (((nbpolygons == 1) && ((*count == 4) ||
|
if (((nbpolygons == 1) && ((*count == 4) ||
|
((*count == 5) && (points[4].x == points[0].x)
|
((*count == 5) && (points[4].x == points[0].x)
|
&& (points[4].y == points[0].y)))) &&
|
&& (points[4].y == points[0].y)))) &&
|
(((points[0].y == points[1].y) &&
|
(((points[0].y == points[1].y) &&
|
(points[1].x == points[2].x) &&
|
(points[1].x == points[2].x) &&
|
(points[2].y == points[3].y) &&
|
(points[2].y == points[3].y) &&
|
(points[3].x == points[0].x)) ||
|
(points[3].x == points[0].x)) ||
|
((points[0].x == points[1].x) &&
|
((points[0].x == points[1].x) &&
|
(points[1].y == points[2].y) &&
|
(points[1].y == points[2].y) &&
|
(points[2].x == points[3].x) &&
|
(points[2].x == points[3].x) &&
|
(points[3].y == points[0].y))))
|
(points[3].y == points[0].y))))
|
{
|
{
|
GdSetRectRegion( rgn,
|
GdSetRectRegion( rgn,
|
MWMIN(points[0].x, points[2].x), MWMIN(points[0].y, points[2].y),
|
MWMIN(points[0].x, points[2].x), MWMIN(points[0].y, points[2].y),
|
MWMAX(points[0].x, points[2].x), MWMAX(points[0].y, points[2].y) );
|
MWMAX(points[0].x, points[2].x), MWMAX(points[0].y, points[2].y) );
|
return rgn;
|
return rgn;
|
}
|
}
|
|
|
for(poly = total = 0; poly < nbpolygons; poly++)
|
for(poly = total = 0; poly < nbpolygons; poly++)
|
total += count[poly];
|
total += count[poly];
|
if (! (pETEs = malloc( sizeof(EdgeTableEntry) * total )))
|
if (! (pETEs = malloc( sizeof(EdgeTableEntry) * total )))
|
{
|
{
|
GdDestroyRegion( rgn );
|
GdDestroyRegion( rgn );
|
return 0;
|
return 0;
|
}
|
}
|
pts = FirstPtBlock.pts;
|
pts = FirstPtBlock.pts;
|
REGION_CreateETandAET(count, nbpolygons, points, &ET, &AET,
|
REGION_CreateETandAET(count, nbpolygons, points, &ET, &AET,
|
pETEs, &SLLBlock);
|
pETEs, &SLLBlock);
|
pSLL = ET.scanlines.next;
|
pSLL = ET.scanlines.next;
|
curPtBlock = &FirstPtBlock;
|
curPtBlock = &FirstPtBlock;
|
|
|
if (mode != MWPOLY_WINDING) {
|
if (mode != MWPOLY_WINDING) {
|
/*
|
/*
|
* for each scanline
|
* for each scanline
|
*/
|
*/
|
for (y = ET.ymin; y < ET.ymax; y++) {
|
for (y = ET.ymin; y < ET.ymax; y++) {
|
/*
|
/*
|
* Add a new edge to the active edge table when we
|
* Add a new edge to the active edge table when we
|
* get to the next edge.
|
* get to the next edge.
|
*/
|
*/
|
if (pSLL != NULL && y == pSLL->scanline) {
|
if (pSLL != NULL && y == pSLL->scanline) {
|
REGION_loadAET(&AET, pSLL->edgelist);
|
REGION_loadAET(&AET, pSLL->edgelist);
|
pSLL = pSLL->next;
|
pSLL = pSLL->next;
|
}
|
}
|
pPrevAET = &AET;
|
pPrevAET = &AET;
|
pAET = AET.next;
|
pAET = AET.next;
|
|
|
/*
|
/*
|
* for each active edge
|
* for each active edge
|
*/
|
*/
|
while (pAET) {
|
while (pAET) {
|
pts->x = pAET->bres.minor_axis, pts->y = y;
|
pts->x = pAET->bres.minor_axis, pts->y = y;
|
pts++, iPts++;
|
pts++, iPts++;
|
|
|
/*
|
/*
|
* send out the buffer
|
* send out the buffer
|
*/
|
*/
|
if (iPts == NUMPTSTOBUFFER) {
|
if (iPts == NUMPTSTOBUFFER) {
|
tmpPtBlock = malloc( sizeof(POINTBLOCK));
|
tmpPtBlock = malloc( sizeof(POINTBLOCK));
|
if(!tmpPtBlock) {
|
if(!tmpPtBlock) {
|
return 0;
|
return 0;
|
}
|
}
|
curPtBlock->next = tmpPtBlock;
|
curPtBlock->next = tmpPtBlock;
|
curPtBlock = tmpPtBlock;
|
curPtBlock = tmpPtBlock;
|
pts = curPtBlock->pts;
|
pts = curPtBlock->pts;
|
numFullPtBlocks++;
|
numFullPtBlocks++;
|
iPts = 0;
|
iPts = 0;
|
}
|
}
|
EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
|
EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
|
|
|
}
|
}
|
REGION_InsertionSort(&AET);
|
REGION_InsertionSort(&AET);
|
}
|
}
|
}
|
}
|
else {
|
else {
|
/*
|
/*
|
* for each scanline
|
* for each scanline
|
*/
|
*/
|
for (y = ET.ymin; y < ET.ymax; y++) {
|
for (y = ET.ymin; y < ET.ymax; y++) {
|
/*
|
/*
|
* Add a new edge to the active edge table when we
|
* Add a new edge to the active edge table when we
|
* get to the next edge.
|
* get to the next edge.
|
*/
|
*/
|
if (pSLL != NULL && y == pSLL->scanline) {
|
if (pSLL != NULL && y == pSLL->scanline) {
|
REGION_loadAET(&AET, pSLL->edgelist);
|
REGION_loadAET(&AET, pSLL->edgelist);
|
REGION_computeWAET(&AET);
|
REGION_computeWAET(&AET);
|
pSLL = pSLL->next;
|
pSLL = pSLL->next;
|
}
|
}
|
pPrevAET = &AET;
|
pPrevAET = &AET;
|
pAET = AET.next;
|
pAET = AET.next;
|
pWETE = pAET;
|
pWETE = pAET;
|
|
|
/*
|
/*
|
* for each active edge
|
* for each active edge
|
*/
|
*/
|
while (pAET) {
|
while (pAET) {
|
/*
|
/*
|
* add to the buffer only those edges that
|
* add to the buffer only those edges that
|
* are in the Winding active edge table.
|
* are in the Winding active edge table.
|
*/
|
*/
|
if (pWETE == pAET) {
|
if (pWETE == pAET) {
|
pts->x = pAET->bres.minor_axis, pts->y = y;
|
pts->x = pAET->bres.minor_axis, pts->y = y;
|
pts++, iPts++;
|
pts++, iPts++;
|
|
|
/*
|
/*
|
* send out the buffer
|
* send out the buffer
|
*/
|
*/
|
if (iPts == NUMPTSTOBUFFER) {
|
if (iPts == NUMPTSTOBUFFER) {
|
tmpPtBlock = malloc( sizeof(POINTBLOCK) );
|
tmpPtBlock = malloc( sizeof(POINTBLOCK) );
|
if(!tmpPtBlock) {
|
if(!tmpPtBlock) {
|
return 0;
|
return 0;
|
}
|
}
|
curPtBlock->next = tmpPtBlock;
|
curPtBlock->next = tmpPtBlock;
|
curPtBlock = tmpPtBlock;
|
curPtBlock = tmpPtBlock;
|
pts = curPtBlock->pts;
|
pts = curPtBlock->pts;
|
numFullPtBlocks++; iPts = 0;
|
numFullPtBlocks++; iPts = 0;
|
}
|
}
|
pWETE = pWETE->nextWETE;
|
pWETE = pWETE->nextWETE;
|
}
|
}
|
EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
|
EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
|
}
|
}
|
|
|
/*
|
/*
|
* recompute the winding active edge table if
|
* recompute the winding active edge table if
|
* we just resorted or have exited an edge.
|
* we just resorted or have exited an edge.
|
*/
|
*/
|
if (REGION_InsertionSort(&AET) || fixWAET) {
|
if (REGION_InsertionSort(&AET) || fixWAET) {
|
REGION_computeWAET(&AET);
|
REGION_computeWAET(&AET);
|
fixWAET = FALSE;
|
fixWAET = FALSE;
|
}
|
}
|
}
|
}
|
}
|
}
|
REGION_FreeStorage(SLLBlock.next);
|
REGION_FreeStorage(SLLBlock.next);
|
REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, rgn);
|
REGION_PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, rgn);
|
for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
|
for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
|
tmpPtBlock = curPtBlock->next;
|
tmpPtBlock = curPtBlock->next;
|
free( curPtBlock );
|
free( curPtBlock );
|
curPtBlock = tmpPtBlock;
|
curPtBlock = tmpPtBlock;
|
}
|
}
|
free( pETEs );
|
free( pETEs );
|
return rgn;
|
return rgn;
|
}
|
}
|
|
|
#endif /* POLYREGIONS*/
|
#endif /* POLYREGIONS*/
|
|
|
