mi/mipolyutil.c

   1 /***********************************************************
   2
   3 Copyright 1987, 1998  The Open Group
   4
   5 Permission to use, copy, modify, distribute, and sell this software and its
   6 documentation for any purpose is hereby granted without fee, provided that
   7 the above copyright notice appear in all copies and that both that
   8 copyright notice and this permission notice appear in supporting
   9 documentation.
  10
  11 The above copyright notice and this permission notice shall be included in
  12 all copies or substantial portions of the Software.
  13
  14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  17 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  18 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  19 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  20
  21 Except as contained in this notice, the name of The Open Group shall not be
  22 used in advertising or otherwise to promote the sale, use or other dealings
  23 in this Software without prior written authorization from The Open Group.
  24
  25 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
  26
  27                         All Rights Reserved
  28
  29 Permission to use, copy, modify, and distribute this software and its
  30 documentation for any purpose and without fee is hereby granted,
  31 provided that the above copyright notice appear in all copies and that
  32 both that copyright notice and this permission notice appear in
  33 supporting documentation, and that the name of Digital not be
  34 used in advertising or publicity pertaining to distribution of the
  35 software without specific, written prior permission.
  36
  37 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  38 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  39 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  40 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  41 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  42 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  43 SOFTWARE.
  44
  45 ******************************************************************/
  46 #ifdef HAVE_DIX_CONFIG_H
  47 #include <dix-config.h>
  48 #endif
  49
  50 #include "regionstr.h"
  51 #include "gc.h"
  52 #include "miscanfill.h"
  53 #include "mipoly.h"
  54 #include "misc.h"               /* MAXINT */
  55
  56 /*
  57  *     fillUtils.c
  58  *
  59  *     Written by Brian Kelleher;  Oct. 1985
  60  *
  61  *     This module contains all of the utility functions
  62  *     needed to scan convert a polygon.
  63  *
  64  */
  65 \f
  66 /*
  67  *     InsertEdgeInET
  68  *
  69  *     Insert the given edge into the edge table.
  70  *     First we must find the correct bucket in the
  71  *     Edge table, then find the right slot in the
  72  *     bucket.  Finally, we can insert it.
  73  *
  74  */
  75 static Bool
  76 miInsertEdgeInET(EdgeTable * ET, EdgeTableEntry * ETE, int scanline,
  77                  ScanLineListBlock ** SLLBlock, int *iSLLBlock)
  78 {
  79     EdgeTableEntry *start, *prev;
  80     ScanLineList *pSLL, *pPrevSLL;
  81     ScanLineListBlock *tmpSLLBlock;
  82
  83     /*
  84      * find the right bucket to put the edge into
  85      */
  86     pPrevSLL = &ET->scanlines;
  87     pSLL = pPrevSLL->next;
  88     while (pSLL && (pSLL->scanline < scanline)) {
  89         pPrevSLL = pSLL;
  90         pSLL = pSLL->next;
  91     }
  92
  93     /*
  94      * reassign pSLL (pointer to ScanLineList) if necessary
  95      */
  96     if ((!pSLL) || (pSLL->scanline > scanline)) {
  97         if (*iSLLBlock > SLLSPERBLOCK - 1) {
  98             tmpSLLBlock = malloc(sizeof(ScanLineListBlock));
  99             if (!tmpSLLBlock)
 100                 return FALSE;
 101             (*SLLBlock)->next = tmpSLLBlock;
 102             tmpSLLBlock->next = NULL;
 103             *SLLBlock = tmpSLLBlock;
 104             *iSLLBlock = 0;
 105         }
 106         pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
 107
 108         pSLL->next = pPrevSLL->next;
 109         pSLL->edgelist = NULL;
 110         pPrevSLL->next = pSLL;
 111     }
 112     pSLL->scanline = scanline;
 113
 114     /*
 115      * now insert the edge in the right bucket
 116      */
 117     prev = NULL;
 118     start = pSLL->edgelist;
 119     while (start && (start->bres.minor < ETE->bres.minor)) {
 120         prev = start;
 121         start = start->next;
 122     }
 123     ETE->next = start;
 124
 125     if (prev)
 126         prev->next = ETE;
 127     else
 128         pSLL->edgelist = ETE;
 129     return TRUE;
 130 }
 131 \f
 132 /*
 133  *     CreateEdgeTable
 134  *
 135  *     This routine creates the edge table for
 136  *     scan converting polygons.
 137  *     The Edge Table (ET) looks like:
 138  *
 139  *    EdgeTable
 140  *     --------
 141  *    |  ymax  |        ScanLineLists
 142  *    |scanline|-->------------>-------------->...
 143  *     --------   |scanline|   |scanline|
 144  *                |edgelist|   |edgelist|
 145  *                ---------    ---------
 146  *                    |             |
 147  *                    |             |
 148  *                    V             V
 149  *              list of ETEs   list of ETEs
 150  *
 151  *     where ETE is an EdgeTableEntry data structure,
 152  *     and there is one ScanLineList per scanline at
 153  *     which an edge is initially entered.
 154  *
 155  */
 156
 157 Bool
 158 miCreateETandAET(int count, DDXPointPtr pts, EdgeTable * ET,
 159                  EdgeTableEntry * AET, EdgeTableEntry * pETEs,
 160                  ScanLineListBlock * pSLLBlock)
 161 {
 162     DDXPointPtr top, bottom;
 163     DDXPointPtr PrevPt, CurrPt;
 164     int iSLLBlock = 0;
 165
 166     int dy;
 167
 168     if (count < 2)
 169         return TRUE;
 170
 171     /*
 172      *  initialize the Active Edge Table
 173      */
 174     AET->next = NULL;
 175     AET->back = NULL;
 176     AET->nextWETE = NULL;
 177     AET->bres.minor = MININT;
 178
 179     /*
 180      *  initialize the Edge Table.
 181      */
 182     ET->scanlines.next = NULL;
 183     ET->ymax = MININT;
 184     ET->ymin = MAXINT;
 185     pSLLBlock->next = NULL;
 186
 187     PrevPt = &pts[count - 1];
 188
 189     /*
 190      *  for each vertex in the array of points.
 191      *  In this loop we are dealing with two vertices at
 192      *  a time -- these make up one edge of the polygon.
 193      */
 194     while (count--) {
 195         CurrPt = pts++;
 196
 197         /*
 198          *  find out which point is above and which is below.
 199          */
 200         if (PrevPt->y > CurrPt->y) {
 201             bottom = PrevPt, top = CurrPt;
 202             pETEs->ClockWise = 0;
 203         }
 204         else {
 205             bottom = CurrPt, top = PrevPt;
 206             pETEs->ClockWise = 1;
 207         }
 208
 209         /*
 210          * don't add horizontal edges to the Edge table.
 211          */
 212         if (bottom->y != top->y) {
 213             pETEs->ymax = bottom->y - 1;        /* -1 so we don't get last scanline */
 214
 215             /*
 216              *  initialize integer edge algorithm
 217              */
 218             dy = bottom->y - top->y;
 219             BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
 220
 221             if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock)) {
 222                 miFreeStorage(pSLLBlock->next);
 223                 return FALSE;
 224             }
 225
 226             ET->ymax = max(ET->ymax, PrevPt->y);
 227             ET->ymin = min(ET->ymin, PrevPt->y);
 228             pETEs++;
 229         }
 230
 231         PrevPt = CurrPt;
 232     }
 233     return TRUE;
 234 }
 235 \f
 236 /*
 237  *     loadAET
 238  *
 239  *     This routine moves EdgeTableEntries from the
 240  *     EdgeTable into the Active Edge Table,
 241  *     leaving them sorted by smaller x coordinate.
 242  *
 243  */
 244
 245 void
 246 miloadAET(EdgeTableEntry * AET, EdgeTableEntry * ETEs)
 247 {
 248     EdgeTableEntry *pPrevAET;
 249     EdgeTableEntry *tmp;
 250
 251     pPrevAET = AET;
 252     AET = AET->next;
 253     while (ETEs) {
 254         while (AET && (AET->bres.minor < ETEs->bres.minor)) {
 255             pPrevAET = AET;
 256             AET = AET->next;
 257         }
 258         tmp = ETEs->next;
 259         ETEs->next = AET;
 260         if (AET)
 261             AET->back = ETEs;
 262         ETEs->back = pPrevAET;
 263         pPrevAET->next = ETEs;
 264         pPrevAET = ETEs;
 265
 266         ETEs = tmp;
 267     }
 268 }
 269 \f
 270 /*
 271  *     computeWAET
 272  *
 273  *     This routine links the AET by the
 274  *     nextWETE (winding EdgeTableEntry) link for
 275  *     use by the winding number rule.  The final
 276  *     Active Edge Table (AET) might look something
 277  *     like:
 278  *
 279  *     AET
 280  *     ----------  ---------   ---------
 281  *     |ymax    |  |ymax    |  |ymax    |
 282  *     | ...    |  |...     |  |...     |
 283  *     |next    |->|next    |->|next    |->...
 284  *     |nextWETE|  |nextWETE|  |nextWETE|
 285  *     ---------   ---------   ^--------
 286  *         |                   |       |
 287  *         V------------------->       V---> ...
 288  *
 289  */
 290 void
 291 micomputeWAET(EdgeTableEntry * AET)
 292 {
 293     EdgeTableEntry *pWETE;
 294     int inside = 1;
 295     int isInside = 0;
 296
 297     AET->nextWETE = NULL;
 298     pWETE = AET;
 299     AET = AET->next;
 300     while (AET) {
 301         if (AET->ClockWise)
 302             isInside++;
 303         else
 304             isInside--;
 305
 306         if ((!inside && !isInside) || (inside && isInside)) {
 307             pWETE->nextWETE = AET;
 308             pWETE = AET;
 309             inside = !inside;
 310         }
 311         AET = AET->next;
 312     }
 313     pWETE->nextWETE = NULL;
 314 }
 315 \f
 316 /*
 317  *     InsertionSort
 318  *
 319  *     Just a simple insertion sort using
 320  *     pointers and back pointers to sort the Active
 321  *     Edge Table.
 322  *
 323  */
 324
 325 int
 326 miInsertionSort(EdgeTableEntry * AET)
 327 {
 328     EdgeTableEntry *pETEchase;
 329     EdgeTableEntry *pETEinsert;
 330     EdgeTableEntry *pETEchaseBackTMP;
 331     int changed = 0;
 332
 333     AET = AET->next;
 334     while (AET) {
 335         pETEinsert = AET;
 336         pETEchase = AET;
 337         while (pETEchase->back->bres.minor > AET->bres.minor)
 338             pETEchase = pETEchase->back;
 339
 340         AET = AET->next;
 341         if (pETEchase != pETEinsert) {
 342             pETEchaseBackTMP = pETEchase->back;
 343             pETEinsert->back->next = AET;
 344             if (AET)
 345                 AET->back = pETEinsert->back;
 346             pETEinsert->next = pETEchase;
 347             pETEchase->back->next = pETEinsert;
 348             pETEchase->back = pETEinsert;
 349             pETEinsert->back = pETEchaseBackTMP;
 350             changed = 1;
 351         }
 352     }
 353     return changed;
 354 }
 355 \f
 356 /*
 357  *     Clean up our act.
 358  */
 359 void
 360 miFreeStorage(ScanLineListBlock * pSLLBlock)
 361 {
 362     ScanLineListBlock *tmpSLLBlock;
 363
 364     while (pSLLBlock) {
 365         tmpSLLBlock = pSLLBlock->next;
 366         free(pSLLBlock);
 367         pSLLBlock = tmpSLLBlock;
 368     }
 369 }