git.sesse.net Git - rdpsrv/blob - Xserver/programs/Xserver/mi/mipolyutil.c

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