Weiler-Atherton in 3D

Published April 12, 2013 by Petrov Vladimir, posted by Petrov_VA
Do you see issues with this article? Let us know.
Advertisement

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:

  1. 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.
  2. 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.
  3. 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.

fig_1_1.JPG

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.

fig_1_2.JPG

In fig 1.3 The sets of Magenta and Aqua segments are moved aside for the demonstration purposes.

fig_1_3.JPG

In fig 1.4 The sets of Magenta and Aqua segments are moved together to create clipping polygons.

fig_1_4.JPG

In fig 1.5 the the Yellow clipped polygons are shown together with the original Red and Blue polygons.

fig_1_5.JPG

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)

FIG_1_6.jpg

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:

  1. 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.
  2. 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.
  3. 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.

fig_01.JPG

In fig 2.2 the Red and Blue polyhedrons moved into random position to start clipping.

fig_02.jpg

In fig 2.3 the Red and Blue polyhedrons in random position are shown in blending mode as semi-transparent.

fig_03.jpg

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.

fig_04.jpg

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.

fig_05.jpg

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)

FIG_06.png

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)

Description of the 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.

Cancel Save
0 Likes 8 Comments

Comments

swiftcoder

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.

May 28, 2015 04:10 PM
Dave Hunt

I agree with swiftcoder. Without implementation details, there's not much point to the article.

May 28, 2015 06:30 PM
TangentZ

Maybe even some pseudo-code of the algorithm will help explain what the demo is doing exactly.

The most useful part I got out of this article is the name of the algorithm, the Weiler-Atherton Algorithm, but not much more than that.

The Wikipedia page doesn't have much information there either (http://en.wikipedia.org/wiki/Weiler%E2%80%93Atherton_clipping_algorithm)

May 28, 2015 07:45 PM
Gaiiden

my bad, I didn't think to check the download for source and just assumed it was included. Assumptions. Fail

May 29, 2015 01:19 AM
Khatharr

Honestly I'm not sure that I like the idea of distributing binaries this way either. It could lead to bad things happening in the future. Rather than distributing binaries, maybe some links to YouTube videos would be more appropriate.

I really think the best thing here would be to walk through the algorithm and explain how you implemented it. If you wanted to attach source code to such an article then that would be fine, but only as a bonus, not as a substitute for an explanation within the article itself.

May 29, 2015 06:54 AM
Gaiiden

article has been re-published with pseudocode and links for further reference

June 05, 2015 11:42 AM
Buckeye

If the intent of the article is merely to announce that an algorithm that has been implemented in 2D also works in 3D - perhaps "My Announcements" is a better location for the information.

I.e., this article falls short (from what I as a reviewer expect a gamedev article to provide) in the following areas:

a. the benefits and disadvantages of an algorithm in the world of graphics programming. With regard to using the algorithm, the author provides only:

It seemed worth to use the Weiler-Atherton Algorithm of clipping in 3D simple applications

If the algorithm is applicable only to "simple" applications, define what "simple" means and some explanation of why it's worth using.

b. details for implemenation of the algorithm. The pseudo-code provides a loop setup but specifically and intentionally leaves out details regarding the article-titled algorithm. An article claiming that extension of an algorithm for 2D to 3D is possible and/or useful needs to provide technical information that the claim is, in fact, true. IMHO, "Run this program and see" does not comprise support for the claim.

c. I heartily agree with Khatarr with regard to distributing binaries. Yeah, I've got Norton, etc., but downloading and blindly running executables?? No thanks. For me: downloaded the zip, looked at the contents, deleted the zip.

@author: To improve the article, you need to add a clear description of the intent of the article. Tell readers what benefit they may gain from reading it. Provide a description of the scope of the article - how much or how little information is provided regarding the subject. E.g., as the article stands, you should be kind to readers and let them know very early in the article, if they become interested in implementing the algorithm, googling, other research and trial-and-error coding will be required.

My opinion - without a minimum of the suggested improvements, and resolution of the areas mentioned as a,b,c above, the value of this article appearing on this site is marginal.

June 05, 2015 05:16 PM
Dave Hunt

I have to agree with @Buckeye on this. While the addition of the pseudo-code is welcome, it is still vague and lacks any accompanying text to explain how the thing works.

As it is, we have some pictures, a bit of pseudo-code, a demo with no source code, and a comment that, if we're actually interested in this stuff, then Google is your friend.

June 05, 2015 06:36 PM
You must log in to join the conversation.
Don't have a GameDev.net account? Sign up!

The Presentation of 2D and 3D Weiler-Atherton Algorithm provided with an executable demo

Advertisement
Advertisement