Weiler-Atherton Algorithm in 3D

• Download demo - 53.4 KB
• Download project - 105.4 KB

Introduction

 The Weiler-Atherton algorithm of polygons clipping in 2D may be briefly described as follows:

• to find all the points and segments of the first polygon inside the second one
• to find all the points and segments of the second polygon inside the first one
• to join the segments chains beginnings with the ends as clipping result polygons

The Weiler-Atherton algorithm of objects clipping in 3D on the analogy with the 2D one may be briefly described as follows:

• to find all the points and polygons of the first 3D object inside the second one
• to find all the points and polygons of the second 3D object inside the first one
• to superimpose the polygons with the common edges as clipping result 3D object

The idea proved to be working. In this article, the completed codes of anyhow 3D semi-quadric objects clipping  in MFC provided.

Background

The demo project Weiler3D has been created  with the standard MFC Appwizard. 3D semi-quadric object performance is the same as class CPlaneObject in my former CodeProject article "Your Own Quadrics in OpenGL MFC". The 3D semi-quadric objects are randomly created using technology of the article above.

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 Weiler3D.exe has been built  with MSVS-2015 pro using the instruments of MSVS-2010. Therefore, the Weiler3D.exe is valid even for Windows-XP (differs from my former CodeProject articles, no special *.dll files required because only the RAM memory is used).

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

• Menu File->Play - play/stop object rotation (also Ctrl+P click)
• Menu Edit->Reset Scene - two somehow objects with the random rotation rates and  constant velocity created  (also Space Bar click)
• Menu Edit->Start Clipping - if the objects intersected - stop objects rotation and moving 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)
• Mouse Move with the Left Button pressed - rotate the scene around vertical and horizontal axes
• Mouse Right Button pressed - restore default scene position

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 Weiler3D.exe should start building and working.

Project Source Storage

Standard source code in Weiler3Dproj path has been created with the standard MFC Application Wizard:

• Weiler3D.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
• Weiler3D.rc and resource.h - menu, dialog, accelerator resources created by the author using the standard Resource Wizard procedures

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

• Vector_2D.cpp, Poligon_2D.cpp - 2D object  handling
• Material.cpp - colour performance of the object
• GLObject.cpp, BoxObject.cpp, Vector_3D.cpp, Plane.cpp , PlaneArea.cpp, PlaneObject.cpp - 3D object  handling

Codes Explanation

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

1. Init Application

CChildView class variables declared in CChildView.h:

BOOL m_bPlay;         //Flag of the scene to play
CDlgHelp * m_pDlgHelp;//reference to non-modal Help Dialog
int mouse_x0;         //mouse x pos fixed with L button down
int mouse_y0;         //mouse y pos fixed with L button down
float  m_AngleY;      //angle scene Y potation
float  m_AngleX;      //angle scene X potation
float  m_AngleZ;      //angle scene Z potation
float  m_z;           //camera z pos

Global variables declared in CChildView.cpp:

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

and in CLObject.cpp:

CGLObject * m_pRedObj = NULL;  //Reference to red object
CGLObject * m_pBlueObj = NULL; //Reference to blue object
CGLObject * m_pRedCut = NULL;  //Reference to red object clipped inside blue
CGLObject * m_pBlueCut = NULL; //Reference to blue object clipped inside red
Vector_3D vRed(0);             //Vector of red object start clipping
Vector_3D vBlue(0);            //Vector of blue object start clipping 

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 
	Init();                    // initialize OpenGL borrowed from Standard Cube Sample
	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();
}
BOOL CChildView::DrawMyScene(void)
{
 static BOOL     bBusy = FALSE;                       //Draw Scene busy flag
 if (bBusy)                                            //If Drawing going on return
  return FALSE;
 glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);  //Indicate the buffers to be cleared
 glLoadIdentity();                                    //Reset matrix
 glColor3f(1.0f, 1.0f, 1.0f);

 glTranslatef(0.0f, 0.0f, -m_z);                      //move object far-near
 glRotatef(m_AngleX, 1.0f, 0.0f, 0.0f);                //rotate object    
 glRotatef(m_AngleY, 0.0f, 1.0f, 0.0f);                //around the axe
 glRotatef(m_AngleZ, 0.0f, 0.0f, 1.0f);                //specified
 

 for (POSITION pos = m_glObjList.GetHeadPosition(); pos != NULL;) //for all 3D objects
 {
  CGLObject * pGL = (CGLObject *)m_glObjList.GetNext(pos);     //get recurrent object
  pGL->DrawGLObjectScene();                                    //Draw recurrent object
 }//for(POSITION pos = m_glObjList.GetHeadPosition(); pos != NULL;)

 glFinish();                                           //Blocks until all 
                                                       //OpenGL execution is complete
 SwapBuffers(wglGetCurrentDC());                       //Exchanges the front and back buffers 
 bBusy = FALSE;

 return TRUE;
} 

3. Random 3D Objects Creation

With the Menu Edit->Reset Scene command (also Space Bar click), all previous objects deleted and new two somehow 3D objects with the random rotation rates and moving towards each other created as in figure below:

The 3D objects are randomly created using technology of my former CodeProject article "Your Own Quadrics in OpenGL MFC":

void ResetScene(void)
{
 while (m_glObjList.GetCount())                         //while any object exists
 {
  CGLObject * pGl = (CGLObject *)m_glObjList.GetTail(); //get the last object   
  m_glObjList.RemoveTail();                             //remove the last object 
  pGl->DeleteContents();                                //clear the last object
 }

 CreateRandomObj();                                      //create random object
 CGLObject * pGl = (CGLObject *)m_glObjList.GetTail();   //get the object created
 pGl->cntrPt.y -= 3;                                     //move object left
 pGl->m_NameGL = _T("RED_UNIT");                         //assign unit name
 pGl->m_pPlaneObject->SetColor(RGB(255, 0, 0));          //assign unit color
 pGl->vel.y = 0.05f;                                     //set moving right

 CreateRandomObj();                                      //create random object
 CGLObject * pGlt = (CGLObject *)m_glObjList.GetTail();  //get the object created
 pGlt->cntrPt.y += 3;                                    //move object left
 pGlt->m_NameGL = _T("BLUE_UNIT");                       //assign unit name
 pGlt->m_pPlaneObject->SetColor(RGB(0, 0, 255));         //assign unit color
 pGlt->vel.y = -0.05f;                                   //set moving right

 m_pRedObj = pGl; m_pBlueObj = pGlt;                  //assign references to objects created
 }

4. 3D Objects Clipping

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

void CChildView::OnVkReturn()
{
 if (m_glObjList.GetCount() != 2)     //if not two objects do nothing
  return;
 m_pBlueObj->m_bBlend = TRUE;         //set Blue object semi-transparent in demo purpose

 BOOL bRemPlay = m_bPlay;             //remember play flag status
 m_bPlay = FALSE;                     //stop play

 DrawMyScene();                       //Draw intersected scene
 Sleep(500);                          //wait half second to observe

 CPlaneObject * pljRed = m_pRedObj->CreateTruePlaneObject();   //fix red object as it is
 CPlaneObject * pljBlue = m_pBlueObj->CreateTruePlaneObject(); //fix blue object as it is
 CPlaneObject plObj;

 //find all the points and polygons of the red object inside the blue one:
 //find all the points and polygons of the blue object inside the red one:
 plObj.IntersectPlaneObjectDemo(pljBlue, pljRed);             

 if (m_pRedCut == NULL || m_pBlueCut == NULL)  //if no intersection
 {
  m_bPlay = bRemPlay;                          //restore play flag
  return;                                      //do nothing
 }
 m_pRedCut->m_NameGL = m_pRedObj->m_NameGL;    //assign the name red truncated object
 m_pBlueCut->m_NameGL = m_pBlueObj->m_NameGL;  //assign the name blue truncated object

 m_pRedCut->vel = m_pRedObj->vel;              //the velocity and 
 m_pRedCut->rot = m_pRedObj->rot;              //rotation rate

 m_pBlueCut->vel = m_pBlueObj->vel;           //of the truncated objects 
 m_pBlueCut->rot = m_pBlueObj->rot;           //the same as origin

 vRed = m_pRedCut->cntrPt;                    //remember vector of red object
 vBlue = m_pBlueCut->cntrPt;                  //remember vector of blue object

 m_pRedCut->cntrPt += m_pRedCut->vel;         //start moving 
 m_pBlueCut->cntrPt += m_pBlueCut->vel;       //truncated objects 

 m_pRedObj->vel = m_pBlueObj->vel = 0;        //original objects stopped
 m_pRedObj->rot = m_pBlueObj->rot = 0;

 m_bPlay = bRemPlay;                         //restore play flag

 pljRed->DeleteContents();                   //clear temporary plane objects
 pljBlue->DeleteContents();
 delete pljRed;
 delete pljBlue;
 pljRed = pljBlue = NULL;
}

In the next figure, the Blue object has been set as semi-transparent for demo purposes:

After half a second, the truncated objects start moving aside and rotate in demo purposes as demonstrated in the title picture of this article.

Next truncated objects return to the clipping  place and the result is the superposed object in the figure above.

Your Own Applications Development Using the Project Provided

You may pick up all of this project, rename it with the project of my former CodeProject 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 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 3D objects clipping.

And I'm sure that the Weiler-Atherton algorithm should work in 4D and 5D as well if required.

The project has been developed in MFC platform. Nevertheless, everything developed in MFC may be converted to Win32 and vise 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 next forthcoming articles.

The job will be continued...