Weiler-Atherton Algorithm in MFC

• Download project - 59.3 KB
• Download demo - 34.3 KB

Introduction

The Weiler-Atherton algorithm of polygons clipping has been cited in a lot of tutorials. The idea seemed fine and simple but as for coding implementation, it is not so easy. And in all the tutorials above in the best case, just common flour-charts may be found. In this article, the completed code of anyhow polygons clipping in MFC has been provided.

Background

The demo project WeilerMFC has been created with the standard MFC Appwizard. Polygon performance is the same as class Polygon_2D in my former CodeProject article, "Your Own Quadrics in OpenGL MFC". The polygons are randomly created using technology of Lesson 42 from my former CodeProject article "50 OpenGL MFC Projects in One".

Before you start building the project provided, it is highly recommended to have a look to the demo presentation enclosed in order to get an idea of the output expected.

Demo Explanations

The executable WeilerMFC.exe has been built with MSVS-2015 pro using the instruments of MSVS-2010. Therefore, the WeilerMFC.exe is valid even for Windows-XP (differs from my former CodeProject articles where no special *.dll files are required because only the ram memory is used).

Some menu and some special Accelerator keys arranged in order to demonstrate the WeilerMFC project implementation:

• Menu File->Play - play/stop object rotation (also Ctrl+P click)
• Menu Edit->Reset Scene - two somehow polygons with the random rotation rates created (also Space Bar click)
• Menu Edit->Start Clipping - stop polygons rotation and start clipping (also Enter click)
• Menu Edit->Next Scene - next scene of performance (if play stopped; also Right Arrow click)
• Menu Help->Help - show Help Dialog (also F1 click)

The Help Dialog is non-modal therefore you can use as menu and accelerator commands directly or press OK button in the Help Dialog (or double click the item correspondence):

Building Notes

Solution configuration must be installed as Release and the platform to be x86.

The project provided has been developed with MSVS-2015 pro using the instruments of MSVS-2010. Therefore the EXE files are valid even for Windows-XP. If you do not need to run the application in Windows-XP, just change the instruments to MSVS-2015 .

The default coding property is UNICODE; nevertheless MBCS coding is also available, just change the property.

Even if you are working for the first time with MSVS, just select menu Debug->Start without debugging and the program GLPlane.exe should start building and working.

Project Source and Data Storage

Standard Source codes in WeilerMFCproj path have been created with the standard MFC Application Wizard:

• WeilerMFC.cpp - defines the standard class behaviors for the application
• MainFrm.cpp - implementation of the standard CMainFrame class
• CChildView.cpp - implementation of the standard CWnd class; messages handling procedures created by the author using standard MFC Application Wizard procedures
• DlgHelp.cpp - non-modal implementation of the standard CDialogEx class; messages handling procedures created by the author using standard MFC Application Wizard procedures
• WeilerMFC.rc and resource.h - menu, dialog, accelerator resources created by the author using the standard Resource Wizard procedures

Special source code in WeilerMFCProj\GlobUse path have been developed by the author based on the standard graphics and geometry routine procedures:

• Vector_2D.cpp, Poligon_2D.cpp - 2D object handling

Code Explanation

All the following Menu and Accelerator Commands have been done with standard MFC AppWizard technologies.

1. Init Application

CChildView class variables have been declared in CChildView.h:

CDC m_dcMem;          //memory device context
CBitmap m_memBmp;     //memory bitmap
CBitmap * m_pMemBmp;  //reference to device memory bitmap
BOOL m_bPlay;         //Flag of the scene to play
CDlgHelp * m_pDlgHelp;//reference to non-modal Help Dialog

Global variables have been declared in CChildView.cpp:

CChildView * m_pView = NULL;  //reference this CChildView window
CObList m_polygonList;        // object list of polygons to draw

The initialization of the variables occurred during CChildView class creation:

int CChildView::OnCreate(LPCREATESTRUCT lpCreateStruct)
{
 if (CWnd::OnCreate(lpCreateStruct) == -1)
  return -1;
 m_pView = this;                              //reference to this CChidView window
 srand((unsigned)time(NULL));                 //set random seed 
 m_dcMem.CreateCompatibleDC(GetDC());         //create memory device context
 //create memory device bitmap:
 m_memBmp.CreateCompatibleBitmap(GetDC(),m_dcMem.GetDeviceCaps(HORZRES),
                                m_dcMem.GetDeviceCaps(VERTRES));
 m_pMemBmp = m_dcMem.SelectObject(&m_memBmp); //select memory device bitmap object 
 SetTimer(ID_TIMER_PLAY, 50, NULL);           //start timer for 20 scenes per second
 m_pDlgHelp = new CDlgHelp;                   //non-modal Help Dialog initialization
 return 0;
}   

2. Draw Scene Procedure

The drawing procedure to be called by virtual procedure OnPaint:

void CChildView::OnPaint() 
{
CPaintDC dc(this); // device context for painting
DrawMyScene(&dc);
}
void CChildView::DrawMyScene(CDC * pDC)
{
 CRect rect;                       //this window rectangle
 GetClientRect(&rect);             //get rect sizes
 DrawScene(&m_dcMem, rect);        //draw scene into memory device context
 //copy scene from memory device context into target context pDC;
 pDC->BitBlt(rect.left, rect.top, rect.Width(), rect.Height(), &m_dcMem, 0, 0, SRCCOPY);
}
void DrawScene(CDC * pDC, CRect rect)
{
 pDC->FillRect(rect, &CBrush(RGB(255, 245, 221)));                   //install background colour
 for (POSITION pos = m_polygonList.GetHeadPosition(); pos != NULL;)  //for all the polygons:
 {
  Polygon_2D * ppl = (Polygon_2D *)m_polygonList.GetNext(pos);       //get next polygon 
  ppl->DrawSolidStroke(pDC, Vector_2D(1), 0, 
      ppl->turnPoint, 0., 1., 1., FALSE, TRUE); //draw polygon
 }
}

The idea is that Polygon_2 class has a fractal structure that contains the Object List m_PlaneList with the child Polygon_2D calling the same DrawSolidStroke procedure for drawing:

BOOL Polygon_2D::DrawSolidStroke(CDC * pDC, Vector_2D scl, int prrt, Vector_2D parentCenter,
 double parentAngle, double parentCoefX, double parentCoefY)
{
 Vector_2D myCenter = parentCenter;
 double myAngle = parentAngle + angle;
 double csn = cos(myAngle);
 double sns = sin(myAngle);
 double myCoefX = coefX * parentCoefX;
 double myCoefY = coefY * parentCoefY;
  ............................................................    
 for (POSITION pos = m_PlaneList.GetHeadPosition(); pos != NULL;)
 {
    Polygon_2D * pl = (Polygon_2D *)m_PlaneList.GetNext(pos);
    pl->DrawSolidStroke(pDC, scl, prrt, myCenter, myAngle, myCoefX, myCoefY);
 }
	return TRUE;
}

3. Random Polygon Objects Creation

With the Menu Edit->Reset Scene command (also Space Bar click), all previous polygons are deleted and new two somehow polygons with the random rotation rates are created:

The polygons are randomly created using technology of Lesson 42 from my former CodeProject article "50 OpenGL MFC Projects in One":

void CreateRandomPoly(void)
{
 CRect rect(50, 50, 600, 480);
 int marg = 50;
 Polygon_2D * pNew = new Polygon_2D;
 pNew->CreateRandomPoly(CRect(rect.left + marg, rect.top + marg, 
      rect.right - marg, rect.bottom - marg));
 m_polygonList.AddTail(pNew);
 CRect rct;
 m_pView->GetClientRect(&rct);
 pNew->turnPoint = Vector_2D((rct.left + rct.right) / 2, (rct.top + rct.bottom) / 2);
}

4. Polygons Clipping

With the Menu Edit->Start Clipping command (also Enter click), the polygons rotation is stopped and clipping procedure commenced:

In the figure above, the classic Weiler-Atherton demo is performed: magenta colour segments show the points and segments of the red polygon inside the blue one; lightblue colour segments show the points and segments of the blue polygon inside the red one.

The key procedure for the points and segments inside the polygon:

void Polygon_2D::IntersectSegmentList(Polygon_2D * pT, Polygon_2D * pRslt)
{
 //Polygon_2D * pT - target polygon
 //Polygon_2D * pRslt - result set of polygons consisted of points 
 //and segments of this polygon inside the target
 if (pT == NULL)
  return;
 Polygon_2D * pStroke = NULL;          //polygon of points and lines of pT inside this  polygon 
 BOOL bChain = FALSE;                  //flag of is current chain polygon continue
 for (POSITION pos = m_PointList.GetHeadPosition(); pos != NULL;)
 {
  Vector_2D * pti = (Vector_2D *)m_PointList.GetNext(pos);//current point
  Vector_2D * ptiN = GetNextPoint(pti, TRUE);             //next point
  if (dist2(pti, ptiN)< GeomTreshold)     //if current == next skip
   continue;
  Polygon_2D sCross;                      //polygon of intersection 
                                          //segment(pti, ptiN) with target polygon pT
  pT->IsCrossStroke(pti, ptiN, &sCross);  //if segment intersect target
  if (pT->IsPointInside(pti))             //if current point inside target
  {
   if (!bChain)                           //if chain broken
    if (sCross.m_PointList.GetCount() || pT->IsPointInside(ptiN))//if segment intersect target 
    {
     pStroke = new Polygon_2D;            //start new polygon chain
     pStroke->fillStyle = HS_TRANSPARENT;
     pStroke->penWidth = 3;
     pStroke->fgColor = pRslt->fgColor;
     pStroke->m_bClosed = FALSE;
     pRslt->m_PlaneList.AddTail(pStroke); //new polygon chain appended to result polygon
     bChain = TRUE;
    }//if(!bChain)
   if (bChain)
    pStroke->AppendNewPoint(pti);         //current point append to current polygon chain
  }//if(pT->IsPointInside(pti))
  else
   bChain = FALSE;

  while (sCross.m_PointList.GetCount())   //check all intersection points
  {
   Vector_2D * pN = (Vector_2D *)sCross.m_PointList.GetHead();
   sCross.m_PointList.RemoveHead();
   if (pN->dist(*pti) < GeomTreshold)
    continue;
   if (pStroke != NULL)
    if (pStroke->m_PointList.GetCount())
    {
     Vector_2D * pvl = (Vector_2D *)pStroke->m_PointList.GetTail();
     Vector_2D vd = (*pvl + *pN)*0.5;
     if (bChain)
      bChain = pT->IsPointInside(&vd);
    }

   if (!bChain)   //if chain broken
   {
    pStroke = new Polygon_2D;             //start new polygon chain
    pStroke->fillStyle = HS_TRANSPARENT;
    pStroke->penWidth = 3;
    pStroke->fgColor = pRslt->fgColor;
    pStroke->m_bClosed = FALSE;
    pRslt->m_PlaneList.AddTail(pStroke);  //new polygon chain appended to result polygon
    bChain = TRUE;
   }//if(!bChain)

   pStroke->AppendNewPoint(pN);           //intersection point append to current polygon chain
  }//while(sCross.m_PointList.GetCount())

  if (pT->IsPointInside(ptiN))            //if next point inside target
  {
   if (!bChain)
   {
    pStroke = new Polygon_2D;             //start new polygon chain    
    pStroke->fillStyle = HS_TRANSPARENT;
    pStroke->penWidth = 3;
    pStroke->fgColor = pRslt->fgColor;
    pStroke->m_bClosed = FALSE;

    pRslt->m_PlaneList.AddTail(pStroke);  //new polygon chain appended to result polygon
    bChain = TRUE;
   }
   pStroke->AppendNewPoint(ptiN);         //next point append to current polygon chain
  }
  else
   bChain = FALSE;
 }//for (POSITION pos = m_PointList.GetHeadPosition(); pos != NULL;)
}

In the next figure, the set of chains polygons slightly moved one from another for demo purposes:

The beginning and the ends of this set of chains polygons found each other with the Polygon_2D::MergeChains(Polygon_2D * pPl) procedure as shown at the next figure:

And the result is the set of yellow polygons in the title picture of this article.

Your Own Applications Development Using the Project Provided

You may pick up all this project, rename it with the project of my former Code Project article "MFC Project from Existing Code in One Click" and combine and improve the code as you like.

Or you may pick up the GlobUse directory from this project and include the special procedures contained in any of your Own graphics project with menu Project->Existing Item.

Your references to my code, if any, should be highly appreciated.

Points of Interest

I believe that this demo and code should be helpful for software people for polygons clipping.

The project has been developed in MFC platform. Nevertheless, everything developed in MFC may be converted to Win32 and vice versa.

History

All my previous CodeProject articles were the precursors to the present article.

And I believe that the present article is a precursor to my forthcoming articles.

The job to be continued...