Fast Algorithm for Polygon Clipping with 3D Windows

Abstract

Many applications which use 3D graphics, need 3D geometric modeling and hence polygon clipping against 3D Windows or general volumes. The disadvantages of existing clipping algorithms are that they are 2D, slow or produce incorrect results. This paper describes a new 3D clipping algorithm for concave polygons with one contour. The new algorithm is an extension to the algorithm of Liang and Barsky: The necessary condition for the appearance of a corner of the clipping rectangle in the output polygon is replaced by a necessary and sufficient condition and then extended to the three dimensional case. Another advantage of the presented algorithm is the the removal of degenerated edges. The algorithm is useful for implementing the draft international standards GKS-3D and PHIGS and also for 3D Window Systems.