Weiler-Atherton Algorithm in 3D
5.00/5 (10 votes)
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.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...