edge_table

Go to the documentation of this file.

// Copyright (C) 2010, Guy Barrand. All rights reserved.
// See the file tools.license for terms.
 
#ifndef tools_zb_edge_table
#define tools_zb_edge_table
 
#include "line"
#include "point"
 
#include "../cmemT"
#include <cstdio> //NULL
 
namespace tools {
namespace zb {
 
/***************************************************************************/
inline void InsertEdgeInET (
 EdgeTable* ET
,EdgeTableEntry* ETE
,int scanline
,ScanLineListBlock** SLLBlock
,int* iSLLBlock
)
/***************************************************************************/
/*
 *     InsertEdgeInET
 *
 *     Insert the given edge into the edge table.
 *     First we must find the correct bucket in the
 *     Edge table, then find the right slot in the
 *     bucket.  Finally, we can insert it.
 *
 */
{
  EdgeTableEntry *start, *prev;
  ScanLineList *pSLL, *pPrevSLL;
  ScanLineListBlock *tmpSLLBlock;
/*.........................................................................*/
 
    /*
     * find the right bucket to put the edge into
     */
    pPrevSLL = &ET->scanlines;
    pSLL = pPrevSLL->next;
    while (pSLL && (pSLL->scanline < scanline))
    {
        pPrevSLL = pSLL;
        pSLL = pSLL->next;
    }
 
    /*
     * reassign pSLL (pointer to ScanLineList) if necessary
     */
    if ( (pSLL==NULL) || (pSLL->scanline > scanline))
    {
        if (*iSLLBlock > SLLSPERBLOCK-1)
        {
            tmpSLLBlock = cmem_alloc<ScanLineListBlock>(1);
            (*SLLBlock)->next = tmpSLLBlock;
            tmpSLLBlock->next = (ScanLineListBlock *)NULL;
            *SLLBlock = tmpSLLBlock;
            *iSLLBlock = 0;
        }
        pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
 
        pSLL->next = pPrevSLL->next;
        pSLL->edgelist = (EdgeTableEntry *)NULL;
        pPrevSLL->next = pSLL;
    }
    pSLL->scanline = scanline;
 
    /*
     * now insert the edge in the right bucket
     */
    prev = (EdgeTableEntry *)NULL;
    start = pSLL->edgelist;
    while (start && (start->bres.minor_axis < ETE->bres.minor_axis))
    {
        prev = start;
        start = start->next;
    }
    ETE->next = start;
 
    if (prev!=NULL)
        prev->next = ETE;
    else
        pSLL->edgelist = ETE;
}
 
/***************************************************************************/
inline void CreateETandAET (
 int count
,point* pts
,EdgeTable* ET
,EdgeTableEntry* AET
,EdgeTableEntry* pETEs
,ScanLineListBlock* pSLLBlock
)
/***************************************************************************/
/*
 *     CreateEdgeTable
 *
 *     This routine creates the edge table for
 *     scan converting polygons.
 *     The Edge Table (ET) looks like:
 *
 *    EdgeTable
 *     --------
 *    |  ymax  |        ScanLineLists
 *    |scanline|-->------------>-------------->...
 *     --------   |scanline|   |scanline|
 *                |edgelist|   |edgelist|
 *                ---------    ---------
 *                    |             |
 *                    |             |
 *                    V             V
 *              list of ETEs   list of ETEs
 *
 *     where ETE is an EdgeTableEntry data structure,
 *     and there is one ScanLineList per scanline at
 *     which an edge is initially entered.
 *
 */
{
  point *top, *bottom;
  point *PrevPt, *CurrPt;
  int iSLLBlock = 0;
  int dy;
/*.........................................................................*/
 
    if (count < 2)  return;
 
    /*
     *  initialize the Active Edge Table
     */
    AET->next = (EdgeTableEntry *)NULL;
    AET->back = (EdgeTableEntry *)NULL;
    AET->nextWETE = (EdgeTableEntry *)NULL;
    AET->bres.minor_axis = SMALL_COORDINATE;
 
    /*
     *  initialize the Edge Table.
     */
    ET->scanlines.next = (ScanLineList *)NULL;
    ET->ymax = SMALL_COORDINATE;
    ET->ymin = LARGE_COORDINATE;
    pSLLBlock->next = (ScanLineListBlock *)NULL;
 
    PrevPt = &pts[count-1];
 
    /*
     *  for each vertex in the array of points.
     *  In this loop we are dealing with two vertices at
     *  a time -- these make up one edge of the polygon.
     */
    while (count--)
    {
        CurrPt = pts++;
 
        /*
         *  find out which point is above and which is below.
         */
        if (PrevPt->y > CurrPt->y)
        {
            bottom = PrevPt, top = CurrPt;
            pETEs->ClockWise = 0;
        }
        else
        {
            bottom = CurrPt, top = PrevPt;
            pETEs->ClockWise = 1;
        }
 
        /*
         * don't add horizontal edges to the Edge table.
         */
        if (bottom->y != top->y)
        {
            pETEs->ymax = (int)(bottom->y-1);  /* -1 so we don't get last scanline */
 
            /*
             *  initialize integer edge algorithm
             */
            dy = (int)(bottom->y - top->y);
            BRESINITPGONSTRUCT (dy,(int)top->x,(int)bottom->x, pETEs->bres)
 
            InsertEdgeInET (ET, pETEs, (int)top->y, &pSLLBlock, &iSLLBlock);
 
        if (PrevPt->y > ET->ymax) ET->ymax = (int) PrevPt->y;
        if (PrevPt->y < ET->ymin) ET->ymin = (int) PrevPt->y;
            pETEs++;
        }
 
        PrevPt = CurrPt;
    }
}
 
inline void LoadAET(EdgeTableEntry* AET,EdgeTableEntry* ETEs) {
/*
 *     LoadAET
 *
 *     This routine moves EdgeTableEntries from the
 *     EdgeTable into the Active Edge Table,
 *     leaving them sorted by smaller x coordinate.
 *
 */
  EdgeTableEntry *pPrevAET;
  EdgeTableEntry *tmp;
 
  pPrevAET = AET;
  AET = AET->next;
  while(ETEs) {
        while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis))
        {
            pPrevAET = AET;
            AET = AET->next;
        }
        tmp = ETEs->next;
        ETEs->next = AET;
        if (AET!=NULL)
            AET->back = ETEs;
        ETEs->back = pPrevAET;
        pPrevAET->next = ETEs;
        pPrevAET = ETEs;
 
        ETEs = tmp;
  }
}
 
inline void ComputeWAET(EdgeTableEntry* AET) {
/*
 *     ComputeWAET
 *
 *     This routine links the AET by the
 *     nextWETE (winding EdgeTableEntry) link for
 *     use by the winding number rule.  The final
 *     Active Edge Table (AET) might look something
 *     like:
 *
 *     AET
 *     ----------  ---------   ---------
 *     |ymax    |  |ymax    |  |ymax    |
 *     | ...    |  |...     |  |...     |
 *     |next    |->|next    |->|next    |->...
 *     |nextWETE|  |nextWETE|  |nextWETE|
 *     ---------   ---------   ^--------
 *         |                   |       |
 *         V------------------->       V---> ...
 *
 */
  EdgeTableEntry *pWETE;
  int inside = 1;
  int isInside = 0;
 
  AET->nextWETE = (EdgeTableEntry *)NULL;
  pWETE = AET;
  AET = AET->next;
  while(AET) {
        if (AET->ClockWise!=0)
            isInside++;
        else
            isInside--;
 
        if (( (inside==0) && (isInside==0) ) ||
            ( (inside!=0) && (isInside!=0) ))
        {
            pWETE->nextWETE = AET;
            pWETE = AET;
            inside = !inside;
        }
        AET = AET->next;
  }
  pWETE->nextWETE = (EdgeTableEntry *)NULL;
}
 
inline int InsertAndSort(EdgeTableEntry* AET) {
  // InsertAndSort
  //   Just a simple insertion sort using
  //   pointers and back pointers to sort the Active
  //   Edge Table.
 
  EdgeTableEntry *pETEchase;
  EdgeTableEntry *pETEinsert;
  EdgeTableEntry *pETEchaseBackTMP;
  int changed = 0;
 
  AET = AET->next;
  while(AET) {
        pETEinsert = AET;
        pETEchase = AET;
        while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
            pETEchase = pETEchase->back;
 
        AET = AET->next;
        if (pETEchase != pETEinsert)
        {
            pETEchaseBackTMP = pETEchase->back;
            pETEinsert->back->next = AET;
            if (AET!=NULL)
                AET->back = pETEinsert->back;
            pETEinsert->next = pETEchase;
            pETEchase->back->next = pETEinsert;
            pETEchase->back = pETEinsert;
            pETEinsert->back = pETEchaseBackTMP;
            changed = 1;
        }
  }
  return(changed);
}
 
inline void FreeStorage(ScanLineListBlock* pSLLBlock){
  // Clean up our act.
  ScanLineListBlock* tmpSLLBlock;
  while(pSLLBlock) {
    tmpSLLBlock = pSLLBlock->next;
    cmem_free(pSLLBlock);
    pSLLBlock = tmpSLLBlock;
  }
}
 
}}
 
#endif