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