Clipping a Convex Polygon Against a Plane

The following code clips an arbitrary convex polygon against a given plane. The vertex parameter points to an array containing the number of vertices specified by the vertexCount parameter, wound in counterclockwise order. The plane parameter specifies the plane against which the polygon is clipped. The location array is used for internal processing and must be large enough to hold vertexCount values. The result array is where the clipped polygon is returned and must generally be large enough to hold vertexCount + 1 vertices. The return value of the function is the number of vertices in the clipped polygon.

#include "Vector4D.h"


enum
{
    polygonInterior = 1,
    polygonBoundary = 0,
    polygonExterior = -1
};


const float boundaryEpsilon = 1.0e-3F;


long ClipPolygonAgainstPlane(long vertexCount, const Point3D *vertex,
        const Vector4D& plane, signed char *location, Point3D *result)
{
    long positive = 0;
    long negative = 0;
    
    for (long a = 0; a < vertexCount; a++)
    {
        float d = plane * vertex[a];
        if (d > boundaryEpsilon)
        {
            location[a] = polygonInterior;
            positive++;
        }
        else
        {
            if (d < -boundaryEpsilon)
            {
                location[a] = polygonExterior;
                negative++;
            }
            else
            {
                location[a] = polygonBoundary;
            }
        }
    }
    
    if (negative == 0)
    {
        for (long a = 0; a < vertexCount; a++) result[a] = vertex[a];
        return (vertexCount);
    }
    else if (positive == 0)
    {
        return (0);
    }
    
    long count = 0;
    long previous = vertexCount - 1;
    for (long index = 0; index < vertexCount; index++)
    {
        long loc = location[index];
        if (loc == polygonExterior)
        {
            if (location[previous] == polygonInterior)
            {
                const Point3D& v1 = vertex[previous];
                const Point3D& v2 = vertex[index];
                Vector3D dv = v2 - v1;
                
                float t = plane * v2 / (plane * dv);
                result[count++] = v2 - dv * t;
            }
        }
        else
        {
            const Point3D& v1 = vertex[index];
            if ((loc == polygonInterior) && (location[previous] == polygonExterior))
            {
                const Point3D& v2 = vertex[previous];
                Vector3D dv = v2 - v1;
                
                float t = plane * v2 / (plane * dv);
                result[count++] = v2 - dv * t;
            }
            
            result[count++] = v1;
        }
        
        previous = index;
    }
    
    return (count);
}

How to cite this article

Lengyel, Eric. “Clipping a Convex Polygon Against a Plane”. Terathon Software 3D Graphics Library, 2001. http://www.terathon.com/code/clipping.html