15,564,297 members
Articles / Desktop Programming / MFC
Article
Posted 11 Mar 2018

13.9K views
13 bookmarked

# Weiler-Atherton Algorithm in 3D

Rate me:
Weiler-Atherton algorithm in 3D codes demo implementation

## 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.cppPoligon_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:

C++
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:

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

and in CLObject.cpp:

C++
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:

C++
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
return 0;
}

### 2. Draw Scene Procedure

The drawing procedure to be called by virtual procedure OnPaint:

C++
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
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":

C++
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:

C++
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...

Written By
Russian Federation
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.