The well-known Weiler-Atherton Algorithm of the polygons clipping usualy is demonstrated in 2D performance. Nevertheless this idea also works in 3D. The demo programs concerned Weiler2D.exe and Weiler3D.exe are in the Weiler3D directory to be unpacked from the attached article resource archive.
1. Weiler-Atherton in 2D
The Weiler-Atherton Algorithm of the two 2D polygons may be performmed as 3 steps:
- To create the set of segments consisted of the vertexes of the 1st polygon contained inside the 2nd polygon the points of the ribs intersection included.
- To create the set of segments consisted of the vertexes of the 2nd polygon contained inside the 1st polygon the points of the ribs intersection included.
- To merge the sets of segments above with the intersection points.
The following illustrations have been created with the Demo Program Wailer2D.exe: In fig 1.1 two randomly created polygons Red and Blue to be clipped.
In fig 1.2 the set of Magenta segments of the the vertexes of the Red polygon are contained inside the Blue polygon and the set of Aqua segments of the the vertexes of the Blue polygon are contained inside the Red polygon.
In fig 1.3 The sets of Magenta and Aqua segments are moved aside for the demonstration purposes.
In fig 1.4 The sets of Magenta and Aqua segments are moved together to create clipping polygons.
In fig 1.5 the the Yellow clipped polygons are shown together with the original Red and Blue polygons.
You may create your own performance of the 2D Weiler-Atherton Algorithm with the program Wailer2D.exe. To watch step by step performance use the Right Arrow button while the Play timer is stopped. To start clipping press Enter button. All the commands for Weiler2D.exe available are shown in the Help Dialog (press F1 button to show)
To start the new scenario just press Space Bar. The polygons are randomly created and randomly oriented and randomly rotated.
2.Weiler-Atherton in 3D
The Weiler-Atherton Algorithm of the two polyhedrons clipping may be performmed as 3 steps:
- To create the set of polygons consisted of the vertexes of the 1st polyhedron contained inside the 2nd polyhedron the points of the polygons inertsection included.
- To create the set of polygons c consisted of the vertexes of the 2nd polyhedron contained inside the 1st polyhedron the points of the polygons inertsection included.
- To merge the sets of polygons above with the inersection points.
The next illustrations has been arranged with the Demo Program Wailer3D.exe: In fig 2.1 two randomly created Red and Blue polyhedrons randomly oriented to be clipped.
In fig 2.2 the Red and Blue polyhedrons moved into random position to start clipping.
In fig 2.3 the Red and Blue polyhedrons in random position are shown in blending mode as semi-transparent.
In fig 2.4 the sets of the Red polyhedron faces inside the Blue one and the sets of the Blue polyhedron faces inside the Red one the segments of intresection included are moved aside for the demonstration purposes.
In fig 2.5 the sets of the Red polyhedron faces inside the Blue one and the sets of the Blue polyhedron faces inside the Red one the segments of intresection included are moved together to obtain the clipped polyhedron.
You may select Play menu to watch the clipped polyhedron faces and/or you may use Mouse move with the left mouse button pressed. To watch step by step performance use the Right Arrow button while the Play timer is stopped. All the commands for Weiler3D.exe available are shown in the Help Dialog (press F1 button to show)
To start the new scenario just press Space Bar. The polyhedrons are randomly created and randomly oriented and randomly rotated. The programs above have been developed on the MFC platform. Needless to say that it is not a problem to develop them in Win32 or any other platform. The pseudocode of the procedures used in Weiler3D are provided below:
declare:
Plane : space area determined with the normal vector and the distance of axis centre
Polygon: list of the vertices layed in one plane
Polyhedron: list of the polygons conected
//////////////////////////////////////////////////////////////////
Procedure main
begin
Polyhedron Red
Polyhedron Blue
Polyhedron Mixed
ClipPolyHedrons( Red, Blue, &Mixed)
end Proc
//////////////////////////////////////////////////////////////////
Procedure ClipPolyhedrons( Polyhedron p0, Polyhedron p1, Polyhedron * pRslt)
begin
ClipPolyhedronIn(Polyhedron p0, Polyhedron p1, Polyhedron * pRslt)
ClipPolyhedronIn(Polyhedron p1, Polyhedron p0, Polyhedron * pRslt)
end Proc
///////////////////////////////////////////////////////////////////
Procedure ClipPolyhedronIn( Polyhedron p0, Polyhedron p1, Polyhedron * pRslt)
//pRslt is a list of polygons of Polyhedron p1 contained inside
//the Polyhedron p0 intersected polygons including
begin
with Polyhedron p0 for every polygon Polygon
pCur = the current polygon;
Polygon pNew = the result of the intersection of the Polygon pCur and Polyhedron p1
IntersectPolygon(p1, pCur, &pNew)
if there are any vertices in the Polygon pNew
Polygon pNew is appended to the polygon list in Polyhedron * pRslt
end if
end for
end Proc
/////////////////////////////////////////////////////////////////////////////
Procedure IntersectPolygon(Polyhedron phdr, Polygon plgn, Polygon * pRslt)
//pRslt is a list of vertises of Polygon plgn contained inside
//the Polyhedron phdr vertises of the intersection including
begin
if Polygon plgn is completely inside of the Polyhedron phdr
make Polygon * pPslt as copy of Polygon plgn;
return;
end if
Plane pA //The Plane of the Polygon plgn vertices
Polygon pT //The Polygon obtained with the intersection of the Polyhedron phdr by the Plane pA
IntersectPlane(phdr, pA, pT);
if Polygon pT has no vertices
return;
end if
ClipPolygons(plgn, pT, pRslt);
end Proc
//////////////////////////////////////////////////////////////////////////
Procedure IntersectPlane(Polyhedron phdr, Plane pA, Polygon * pRslt)
//pRslt is a list of vertises of the intersection Polyhedron phdr by the Plane pA
begin
with Polyhedron phdr for every polygon Polygon pCur = the current polygon;
if all the vertices of the Polygon pCur layed in the Plane pA
make Polygon * pPslt as copy of Polygon pCur;
return;
end if
let plt - the list of vertices of the intersection of the Polygon pCur with the Plane pA
IntersectByFlat(pCur, pA, &plt);
with the list of vertices plt for all the vertices
if current vertice is not in the list of the Polygon * pRslt
append current vertice to the list of the Polygon * pRslt
end if
end for
end for
end Proc
//////////////////////////////////////////////////////////////////////////
Procedure IntersectByFlat(Polygon plgn, Plane pA, list of intersection vertices &plt)
begin
with Polygon plgn for all the vertexes let pV = the current vertex;
let pVn = the next vertex in the list Polygon plgn
double d0 = Distance of pV to Plane pA;
double d1 = Distance of pVn to Plane pA;
if(d0 > 0 && d1 >= 0 || d0 < 0 && d1<=0)
continue;
end if
Intersection vertex pU:
Vector * pU = new Vector(* pV -(* pVn - * pV)*d0/(d1 - d0));
Append vertex pU to the list of vertices plt
end for
end Proc
///////////////////////////////////////////////////////////////////////////////////
The pseudocode of the ClipPolygons procedure has been ommited because it is a standard Weiler-Atherton algorithm in 2D. A lot of links concerning this algorithm can be found just by typing "Weiler-Atherton" in a search box (e.g. Weiler-Atherton Algorithm)
Conclusion
The Demo above shows that the Weiler-Atherton Algorithm of clipping is working in 3D as well. The Weiler3D.exe has been created on the basis of NeHe's OpenGL Lessons mentioned in my former article. It seemed worth to use the Weiler-Atherton Algorithm of clipping in 3D simple applications and I believe it will work in 4D and 5D as required.
It's an interesting topic, but the interesting part would be the implementation. I'd rather you provided source code to the demo applications, but if you aren't able/willing to do that, then the article needs to go into a lot more depth as to how each of the 2d/3d cases is implemented.
As is, this is more of a "look at this cool thing I've done", than an informative article.