Polygon Intersection Formula

OpenGL
1

I was wondering if there is a formula or function that can figure out the vertices of an intersection between two polygons on the same plane. Here’s a picture of what I’m talking about: http://filebox.vt.edu/users/rengle/RetroEngine/codeintersection.jpg One of the polygons will always be a square and the other will always be a triangle. Any information on this would help me a lot, thanks.

2

I was unable to view your picture, but that’s ok.

Here’s a brute force approach for 2 convex polygons, A and B.

For each edge in A, find the intersection of the edge with the plane of B. If there is an intersection, determine if the intersection point is inside the poly B. If contained, then save this point, as it will be an end point of the final line segment. Repeat this process for the remaing edges. There should be exactly 2 intersections constituting your line segment. If all this fails to produce 2 intersections, then repeat the entire process for B. If B fails, then there’s no intersection.

There is a caveat here, the case where a vertex of A falls on the plane of B, or vice versa. It could be that the edge of A is coplaner with B, or the vertex is simply touching, or the next vertex of A is on the other side of B, in which case you have a split. It’s up to you how you classify such points, but I would keep them around for later inspection, particularly for the split case.

You can, of course, use bounding boxes for trivial rejection cases. There’s also a separating axis theorem that can be employed to speed things up, along with AABB/OBB trees, etc.

Try a google for V-COLLIDE or RAPID if you want the real skinny in the area of collision detection.

edit:

It occurred to me that you maybe interested in the 2D case specifically. If this is the case, then you could simplify a few things:

for each edge in A
{
    for each edge of B
    {
       if( A's edge intersects B's edge ) 
           save intersection point  
    }
}

This would give you a list of all the intersections. With a triangle and a quad, you could have as many as 4 intersection points.

Note that you need to check for the case where A is completely contained in B, and vice versa. This case would generate no edge intersections.

One way to test for this situation is to treat the edges as hyper-planes, or walls coming out of the screen, and using a simple plane distance test for the points. You can create these hyper-planes by crossing an edge direction with the screen normal. With a clockwise winding, this will produce normals that point into the poly, forming a little room, if you like. To test containment, you simply test each point of A against all the hyper-planes of B. If every point is inside, then A is contained.

You didn’t say if you need winding information in the intersection points, so I’ll just leave it there.

3

The general method for finding the intersection of two convex conplanar polygons is to clip one of the polygons (doesn’t matter which) against the planes through the edges of the other. The following code will clip a polygon against one plane.

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);
}

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. For an edge of another polygon, this is given by {Nx, Ny, Nz, -N dot P}, where N is the inward facing normal of the edge and P is one of the edge’s endpoints. 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.

For a quad clipped against a triangle, you could possibly end up with a six-sided polygon. This method will automatically handle cases when one polygon is contained in the other.

I should point out that the product between a Vector4D V and a Point3D P is the dot product Vx * Px + Vy * Py + Vz * Pz + Vw, and the product between a Vector4D V and a Vector3D U is the dot product Vx * Ux + Vy * Uy + Vz * Uz.