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