home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / X / mit / lib / X / XPolyReg.c.orig < prev    next >
Encoding:
Text File  |  1991-06-08  |  16.7 KB  |  606 lines
  1. /* $XConsortium: XPolyReg.c,v 11.20 91/06/08 11:31:09 rws Exp $ */
  2. /************************************************************************
  3. Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
  4. and the Massachusetts Institute of Technology, Cambridge, Massachusetts.
  5.  
  6.                         All Rights Reserved
  7.  
  8. Permission to use, copy, modify, and distribute this software and its 
  9. documentation for any purpose and without fee is hereby granted, 
  10. provided that the above copyright notice appear in all copies and that
  11. both that copyright notice and this permission notice appear in 
  12. supporting documentation, and that the names of Digital or MIT not be
  13. used in advertising or publicity pertaining to distribution of the
  14. software without specific, written prior permission.  
  15.  
  16. DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  17. ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  18. DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  19. ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  20. WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  21. ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  22. SOFTWARE.
  23.  
  24. ************************************************************************/
  25.  
  26. #define LARGE_COORDINATE 1000000
  27. #define SMALL_COORDINATE -LARGE_COORDINATE
  28.  
  29. #include "Xlibint.h"
  30. #include "Xutil.h"
  31. #include "region.h"
  32. #include "poly.h"
  33.  
  34. /*
  35.  *     InsertEdgeInET
  36.  *
  37.  *     Insert the given edge into the edge table.
  38.  *     First we must find the correct bucket in the
  39.  *     Edge table, then find the right slot in the
  40.  *     bucket.  Finally, we can insert it.
  41.  *
  42.  */
  43. static void
  44. InsertEdgeInET(ET, ETE, scanline, SLLBlock, iSLLBlock)
  45.     EdgeTable *ET;
  46.     EdgeTableEntry *ETE;
  47.     int scanline;
  48.     ScanLineListBlock **SLLBlock;
  49.     int *iSLLBlock;
  50. {
  51.     register EdgeTableEntry *start, *prev;
  52.     register ScanLineList *pSLL, *pPrevSLL;
  53.     ScanLineListBlock *tmpSLLBlock;
  54.  
  55.     /*
  56.      * find the right bucket to put the edge into
  57.      */
  58.     pPrevSLL = &ET->scanlines;
  59.     pSLL = pPrevSLL->next;
  60.     while (pSLL && (pSLL->scanline < scanline)) 
  61.     {
  62.         pPrevSLL = pSLL;
  63.         pSLL = pSLL->next;
  64.     }
  65.  
  66.     /*
  67.      * reassign pSLL (pointer to ScanLineList) if necessary
  68.      */
  69.     if ((!pSLL) || (pSLL->scanline > scanline)) 
  70.     {
  71.         if (*iSLLBlock > SLLSPERBLOCK-1) 
  72.         {
  73.             tmpSLLBlock = 
  74.           (ScanLineListBlock *)Xmalloc(sizeof(ScanLineListBlock));
  75.             (*SLLBlock)->next = tmpSLLBlock;
  76.             tmpSLLBlock->next = (ScanLineListBlock *)NULL;
  77.             *SLLBlock = tmpSLLBlock;
  78.             *iSLLBlock = 0;
  79.         }
  80.         pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
  81.  
  82.         pSLL->next = pPrevSLL->next;
  83.         pSLL->edgelist = (EdgeTableEntry *)NULL;
  84.         pPrevSLL->next = pSLL;
  85.     }
  86.     pSLL->scanline = scanline;
  87.  
  88.     /*
  89.      * now insert the edge in the right bucket
  90.      */
  91.     prev = (EdgeTableEntry *)NULL;
  92.     start = pSLL->edgelist;
  93.     while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) 
  94.     {
  95.         prev = start;
  96.         start = start->next;
  97.     }
  98.     ETE->next = start;
  99.  
  100.     if (prev)
  101.         prev->next = ETE;
  102.     else
  103.         pSLL->edgelist = ETE;
  104. }
  105.  
  106. /*
  107.  *     CreateEdgeTable
  108.  *
  109.  *     This routine creates the edge table for
  110.  *     scan converting polygons. 
  111.  *     The Edge Table (ET) looks like:
  112.  *
  113.  *    EdgeTable
  114.  *     --------
  115.  *    |  ymax  |        ScanLineLists
  116.  *    |scanline|-->------------>-------------->...
  117.  *     --------   |scanline|   |scanline|
  118.  *                |edgelist|   |edgelist|
  119.  *                ---------    ---------
  120.  *                    |             |
  121.  *                    |             |
  122.  *                    V             V
  123.  *              list of ETEs   list of ETEs
  124.  *
  125.  *     where ETE is an EdgeTableEntry data structure,
  126.  *     and there is one ScanLineList per scanline at
  127.  *     which an edge is initially entered.
  128.  *
  129.  */
  130.  
  131. static void
  132. CreateETandAET(count, pts, ET, AET, pETEs, pSLLBlock)
  133.     register int count;
  134.     register XPoint *pts;
  135.     EdgeTable *ET;
  136.     EdgeTableEntry *AET;
  137.     register EdgeTableEntry *pETEs;
  138.     ScanLineListBlock   *pSLLBlock;
  139. {
  140.     register XPoint *top, *bottom;
  141.     register XPoint *PrevPt, *CurrPt;
  142.     int iSLLBlock = 0;
  143.     int dy;
  144.  
  145.     if (count < 2)  return;
  146.  
  147.     /*
  148.      *  initialize the Active Edge Table
  149.      */
  150.     AET->next = (EdgeTableEntry *)NULL;
  151.     AET->back = (EdgeTableEntry *)NULL;
  152.     AET->nextWETE = (EdgeTableEntry *)NULL;
  153.     AET->bres.minor_axis = SMALL_COORDINATE;
  154.  
  155.     /*
  156.      *  initialize the Edge Table.
  157.      */
  158.     ET->scanlines.next = (ScanLineList *)NULL;
  159.     ET->ymax = SMALL_COORDINATE;
  160.     ET->ymin = LARGE_COORDINATE;
  161.     pSLLBlock->next = (ScanLineListBlock *)NULL;
  162.  
  163.     PrevPt = &pts[count-1];
  164.  
  165.     /*
  166.      *  for each vertex in the array of points.
  167.      *  In this loop we are dealing with two vertices at
  168.      *  a time -- these make up one edge of the polygon.
  169.      */
  170.     while (count--) 
  171.     {
  172.         CurrPt = pts++;
  173.  
  174.         /*
  175.          *  find out which point is above and which is below.
  176.          */
  177.         if (PrevPt->y > CurrPt->y) 
  178.         {
  179.             bottom = PrevPt, top = CurrPt;
  180.             pETEs->ClockWise = 0;
  181.         }
  182.         else 
  183.         {
  184.             bottom = CurrPt, top = PrevPt;
  185.             pETEs->ClockWise = 1;
  186.         }
  187.  
  188.         /*
  189.          * don't add horizontal edges to the Edge table.
  190.          */
  191.         if (bottom->y != top->y) 
  192.         {
  193.             pETEs->ymax = bottom->y-1;  /* -1 so we don't get last scanline */
  194.  
  195.             /*
  196.              *  initialize integer edge algorithm
  197.              */
  198.             dy = bottom->y - top->y;
  199.             BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
  200.  
  201.             InsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock);
  202.  
  203.         if (PrevPt->y > ET->ymax)
  204.         ET->ymax = PrevPt->y;
  205.         if (PrevPt->y < ET->ymin)
  206.         ET->ymin = PrevPt->y;
  207.             pETEs++;
  208.         }
  209.  
  210.         PrevPt = CurrPt;
  211.     }
  212. }
  213.  
  214. /*
  215.  *     loadAET
  216.  *
  217.  *     This routine moves EdgeTableEntries from the
  218.  *     EdgeTable into the Active Edge Table,
  219.  *     leaving them sorted by smaller x coordinate.
  220.  *
  221.  */
  222.  
  223. static void
  224. loadAET(AET, ETEs)
  225.     register EdgeTableEntry *AET, *ETEs;
  226. {
  227.     register EdgeTableEntry *pPrevAET;
  228.     register EdgeTableEntry *tmp;
  229.  
  230.     pPrevAET = AET;
  231.     AET = AET->next;
  232.     while (ETEs) 
  233.     {
  234.         while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis)) 
  235.         {
  236.             pPrevAET = AET;
  237.             AET = AET->next;
  238.         }
  239.         tmp = ETEs->next;
  240.         ETEs->next = AET;
  241.         if (AET)
  242.             AET->back = ETEs;
  243.         ETEs->back = pPrevAET;
  244.         pPrevAET->next = ETEs;
  245.         pPrevAET = ETEs;
  246.  
  247.         ETEs = tmp;
  248.     }
  249. }
  250.  
  251. /*
  252.  *     computeWAET
  253.  *
  254.  *     This routine links the AET by the
  255.  *     nextWETE (winding EdgeTableEntry) link for
  256.  *     use by the winding number rule.  The final 
  257.  *     Active Edge Table (AET) might look something
  258.  *     like:
  259.  *
  260.  *     AET
  261.  *     ----------  ---------   ---------
  262.  *     |ymax    |  |ymax    |  |ymax    | 
  263.  *     | ...    |  |...     |  |...     |
  264.  *     |next    |->|next    |->|next    |->...
  265.  *     |nextWETE|  |nextWETE|  |nextWETE|
  266.  *     ---------   ---------   ^--------
  267.  *         |                   |       |
  268.  *         V------------------->       V---> ...
  269.  *
  270.  */
  271. static void
  272. computeWAET(AET)
  273.     register EdgeTableEntry *AET;
  274. {
  275.     register EdgeTableEntry *pWETE;
  276.     register int inside = 1;
  277.     register int isInside = 0;
  278.  
  279.     AET->nextWETE = (EdgeTableEntry *)NULL;
  280.     pWETE = AET;
  281.     AET = AET->next;
  282.     while (AET) 
  283.     {
  284.         if (AET->ClockWise)
  285.             isInside++;
  286.         else
  287.             isInside--;
  288.  
  289.         if ((!inside && !isInside) ||
  290.             ( inside &&  isInside)) 
  291.         {
  292.             pWETE->nextWETE = AET;
  293.             pWETE = AET;
  294.             inside = !inside;
  295.         }
  296.         AET = AET->next;
  297.     }
  298.     pWETE->nextWETE = (EdgeTableEntry *)NULL;
  299. }
  300.  
  301. /*
  302.  *     InsertionSort
  303.  *
  304.  *     Just a simple insertion sort using
  305.  *     pointers and back pointers to sort the Active
  306.  *     Edge Table.
  307.  *
  308.  */
  309.  
  310. static int
  311. InsertionSort(AET)
  312.     register EdgeTableEntry *AET;
  313. {
  314.     register EdgeTableEntry *pETEchase;
  315.     register EdgeTableEntry *pETEinsert;
  316.     register EdgeTableEntry *pETEchaseBackTMP;
  317.     register int changed = 0;
  318.  
  319.     AET = AET->next;
  320.     while (AET) 
  321.     {
  322.         pETEinsert = AET;
  323.         pETEchase = AET;
  324.         while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
  325.             pETEchase = pETEchase->back;
  326.  
  327.         AET = AET->next;
  328.         if (pETEchase != pETEinsert) 
  329.         {
  330.             pETEchaseBackTMP = pETEchase->back;
  331.             pETEinsert->back->next = AET;
  332.             if (AET)
  333.                 AET->back = pETEinsert->back;
  334.             pETEinsert->next = pETEchase;
  335.             pETEchase->back->next = pETEinsert;
  336.             pETEchase->back = pETEinsert;
  337.             pETEinsert->back = pETEchaseBackTMP;
  338.             changed = 1;
  339.         }
  340.     }
  341.     return(changed);
  342. }
  343.  
  344. /*
  345.  *     Clean up our act.
  346.  */
  347. static void
  348. FreeStorage(pSLLBlock)
  349.     register ScanLineListBlock   *pSLLBlock;
  350. {
  351.     register ScanLineListBlock   *tmpSLLBlock;
  352.  
  353.     while (pSLLBlock) 
  354.     {
  355.         tmpSLLBlock = pSLLBlock->next;
  356.         Xfree((char *)pSLLBlock);
  357.         pSLLBlock = tmpSLLBlock;
  358.     }
  359. }
  360.  
  361. /*
  362.  *     Create an array of rectangles from a list of points.
  363.  *     If indeed these things (POINTS, RECTS) are the same,
  364.  *     then this proc is still needed, because it allocates
  365.  *     storage for the array, which was allocated on the
  366.  *     stack by the calling procedure.
  367.  *
  368.  */
  369. static int PtsToRegion(numFullPtBlocks, iCurPtBlock, FirstPtBlock, reg)
  370.     register int  numFullPtBlocks, iCurPtBlock;
  371.     POINTBLOCK *FirstPtBlock;
  372.     REGION *reg;
  373. {
  374.     register BOX  *rects;
  375.     register XPoint *pts;
  376.     register POINTBLOCK *CurPtBlock;
  377.     register int i;
  378.     register BOX *extents;
  379.     int numRects;
  380.     Bool first;
  381.  
  382.     extents = ®->extents;
  383.  
  384.     numRects = ((numFullPtBlocks * NUMPTSTOBUFFER) + iCurPtBlock) >> 1;
  385.  
  386.     if (!(reg->rects = (BOX *)Xrealloc((char *)reg->rects, 
  387.         (unsigned) (sizeof(BOX) * numRects))))       return(0);
  388.  
  389.     reg->size = numRects;
  390.     CurPtBlock = FirstPtBlock;
  391.     rects = reg->rects - 1;
  392.     first = True;
  393.     extents->x1 = MAXSHORT,  extents->x2 = MINSHORT;
  394.  
  395.     for ( ; numFullPtBlocks >= 0; numFullPtBlocks--) {
  396.     /* the loop uses 2 points per iteration */
  397.     i = NUMPTSTOBUFFER >> 1;
  398.     if (!numFullPtBlocks)
  399.         i = iCurPtBlock >> 1;
  400.     for (pts = CurPtBlock->pts; i--; pts += 2) {
  401.         if (pts->x == pts[1].x) {
  402.         numRects--;
  403.         continue;
  404.         }
  405.         if (!first && pts->x == rects->x1 && pts->y == rects->y2 &&
  406.         pts[1].x == rects->x2) {
  407.         rects->y2 = pts[1].y + 1;
  408.         numRects--;
  409.         continue;
  410.         }
  411.         first = False;
  412.         rects++;
  413.         rects->x1 = pts->x;  rects->y1 = pts->y;
  414.         rects->x2 = pts[1].x;  rects->y2 = pts[1].y + 1;
  415.         if (rects->x1 < extents->x1)
  416.         extents->x1 = rects->x1;
  417.         if (rects->x2 > extents->x2)
  418.         extents->x2 = rects->x2;
  419.         }
  420.     CurPtBlock = CurPtBlock->next;
  421.     }
  422.  
  423.     if (numRects) {
  424.     extents->y1 = reg->rects->y1;
  425.     extents->y2 = rects->y2;
  426.     } else {
  427.     extents->x1 = 0;
  428.     extents->y1 = 0;
  429.     extents->x2 = 0;
  430.     extents->y2 = 0;
  431.     }
  432.     reg->numRects = numRects;
  433.  
  434.     return(TRUE);
  435. }
  436.  
  437. /*
  438.  *     polytoregion
  439.  *
  440.  *     Scan converts a polygon by returning a run-length
  441.  *     encoding of the resultant bitmap -- the run-length
  442.  *     encoding is in the form of an array of rectangles.
  443.  */
  444. Region 
  445. XPolygonRegion(Pts, Count, rule)
  446.     int       Count;                 /* number of pts           */
  447.     XPoint     *Pts;             /* the pts                 */
  448.     int    rule;                 /* winding rule */
  449. {
  450.     Region region;
  451.     register EdgeTableEntry *pAET;   /* Active Edge Table       */
  452.     register int y;                  /* current scanline        */
  453.     register int iPts = 0;           /* number of pts in buffer */
  454.     register EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
  455.     register ScanLineList *pSLL;     /* current scanLineList    */
  456.     register XPoint *pts;             /* output buffer           */
  457.     EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
  458.     EdgeTable ET;                    /* header node for ET      */
  459.     EdgeTableEntry AET;              /* header node for AET     */
  460.     EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
  461.     ScanLineListBlock SLLBlock;      /* header for scanlinelist */
  462.     int fixWAET = FALSE;
  463.     POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
  464.     POINTBLOCK *tmpPtBlock;
  465.     int numFullPtBlocks = 0;
  466.  
  467.     if (! (region = XCreateRegion())) return (Region) NULL;
  468.  
  469.     /* special case a rectangle */
  470.     pts = Pts;
  471.     if (((Count == 4) ||
  472.      ((Count == 5) && (pts[4].x == pts[0].x) && (pts[4].y == pts[0].y))) &&
  473.     (((pts[0].y == pts[1].y) &&
  474.       (pts[1].x == pts[2].x) &&
  475.       (pts[2].y == pts[3].y) &&
  476.       (pts[3].x == pts[0].x)) ||
  477.      ((pts[0].x == pts[1].x) &&
  478.       (pts[1].y == pts[2].y) &&
  479.       (pts[2].x == pts[3].x) &&
  480.       (pts[3].y == pts[0].y)))) {
  481.     region->extents.x1 = min(pts[0].x, pts[2].x);
  482.     region->extents.y1 = min(pts[0].y, pts[2].y);
  483.     region->extents.x2 = max(pts[0].x, pts[2].x);
  484.     region->extents.y2 = max(pts[0].y, pts[2].y);
  485.     if ((region->extents.x1 != region->extents.x2) &&
  486.         (region->extents.y1 != region->extents.y2)) {
  487.         region->numRects = 1;
  488.         *(region->rects) = region->extents;
  489.     }
  490.     return(region);
  491.     }
  492.  
  493.     if (! (pETEs = (EdgeTableEntry *)
  494.        Xmalloc((unsigned) (sizeof(EdgeTableEntry) * Count))))
  495.     return (Region) NULL;
  496.  
  497.     pts = FirstPtBlock.pts;
  498.     CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
  499.     pSLL = ET.scanlines.next;
  500.     curPtBlock = &FirstPtBlock;
  501.  
  502.     if (rule == EvenOddRule) {
  503.         /*
  504.          *  for each scanline
  505.          */
  506.         for (y = ET.ymin; y < ET.ymax; y++) {
  507.             /*
  508.              *  Add a new edge to the active edge table when we
  509.              *  get to the next edge.
  510.              */
  511.             if (pSLL != NULL && y == pSLL->scanline) {
  512.                 loadAET(&AET, pSLL->edgelist);
  513.                 pSLL = pSLL->next;
  514.             }
  515.             pPrevAET = &AET;
  516.             pAET = AET.next;
  517.  
  518.             /*
  519.              *  for each active edge
  520.              */
  521.             while (pAET) {
  522.                 pts->x = pAET->bres.minor_axis,  pts->y = y;
  523.                 pts++, iPts++;
  524.  
  525.                 /*
  526.                  *  send out the buffer
  527.                  */
  528.                 if (iPts == NUMPTSTOBUFFER) {
  529.                     tmpPtBlock = (POINTBLOCK *)Xmalloc(sizeof(POINTBLOCK));
  530.                     curPtBlock->next = tmpPtBlock;
  531.                     curPtBlock = tmpPtBlock;
  532.                     pts = curPtBlock->pts;
  533.                     numFullPtBlocks++;
  534.                     iPts = 0;
  535.                 }
  536.                 EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
  537.             }
  538.             (void) InsertionSort(&AET);
  539.         }
  540.     }
  541.     else {
  542.         /*
  543.          *  for each scanline
  544.          */
  545.         for (y = ET.ymin; y < ET.ymax; y++) {
  546.             /*
  547.              *  Add a new edge to the active edge table when we
  548.              *  get to the next edge.
  549.              */
  550.             if (pSLL != NULL && y == pSLL->scanline) {
  551.                 loadAET(&AET, pSLL->edgelist);
  552.                 computeWAET(&AET);
  553.                 pSLL = pSLL->next;
  554.             }
  555.             pPrevAET = &AET;
  556.             pAET = AET.next;
  557.             pWETE = pAET;
  558.  
  559.             /*
  560.              *  for each active edge
  561.              */
  562.             while (pAET) {
  563.                 /*
  564.                  *  add to the buffer only those edges that
  565.                  *  are in the Winding active edge table.
  566.                  */
  567.                 if (pWETE == pAET) {
  568.                     pts->x = pAET->bres.minor_axis,  pts->y = y;
  569.                     pts++, iPts++;
  570.  
  571.                     /*
  572.                      *  send out the buffer
  573.                      */
  574.                     if (iPts == NUMPTSTOBUFFER) {
  575.                         tmpPtBlock = (POINTBLOCK *)Xmalloc(sizeof(POINTBLOCK));
  576.                         curPtBlock->next = tmpPtBlock;
  577.                         curPtBlock = tmpPtBlock;
  578.                         pts = curPtBlock->pts;
  579.                         numFullPtBlocks++;    iPts = 0;
  580.                     }
  581.                     pWETE = pWETE->nextWETE;
  582.                 }
  583.                 EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
  584.             }
  585.  
  586.             /*
  587.              *  recompute the winding active edge table if
  588.              *  we just resorted or have exited an edge.
  589.              */
  590.             if (InsertionSort(&AET) || fixWAET) {
  591.                 computeWAET(&AET);
  592.                 fixWAET = FALSE;
  593.             }
  594.         }
  595.     }
  596.     FreeStorage(SLLBlock.next);    
  597.     (void) PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
  598.     for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
  599.     tmpPtBlock = curPtBlock->next;
  600.     Xfree((char *)curPtBlock);
  601.     curPtBlock = tmpPtBlock;
  602.     }
  603.     Xfree((char *)pETEs);
  604.     return(region);
  605. }
  606.