# Calculate the Intersection of Two Volumes

If you've ever played The Swapper, you'll have a good idea of what I'm asking about.

I need to check for, and isolate, areas of a rectangle that may intersect with either a circle or another rectangle. These selected areas will receive special properties, and the areas will be non-static, since the intersecting shapes themselves will also be dynamic. My first thought was to use raycasting detection, though I've only seen that in use with circles, or even ellipses.

I'm curious if there's a method of using raycasting with a more rectangular approach, or if there's a totally different method already in use to accomplish this task. I would like something more exact than checking in large chunks, and since I'm using SDL2 with a logical renderer size of 1920x1080, checking if each pixel is intersecting is out of the question, as it would slow things down past a playable speed. I already have a multi-shape collision function-template in place, and I could use that, though it only checks if sides or corners are intersecting; it does not compute the overlapping area, or even find the circle's secant line, though I can't imagine it would be overly complex to implement.

TL;DR: I need to find and isolate areas of a rectangle that may intersect with a circle or another rectangle without checking every single pixel on-screen.

• It sounds like you want to split the shapes into their overlapping and non-overlapping parts, is that right? Are these parts then used as trigger regions to change the behaviour of areas in their interior? (Like the lights in The Swapper I presume you're alluding to) If so, you may find it's easier, less code, and probably more efficient to test against the source shapes individually when applying these behaviours. Both rectangles and circles have very simple and fast overlap tests, which won't be the case in general for arbitrary compound shapes formed by their intersection. May 29 '14 at 11:51
• In any case, a picture of what you want and a description of how this is being used to affect gameplay/rendering will help us provide better answers. May 29 '14 at 11:54
• Have you considered using an implicit representation of geometry instead of explicit? en.wikipedia.org/wiki/Constructive_solid_geometry Jun 10 '14 at 12:28

You can do this by clipping one volume to that of another. The original question you asked actually falls under the category of boolean operations on volumes, and can get very complicated.

In your case you want to find an intersection, which is a fundamental boolean operation. Since you have the constraints of only rectangles and circles you're in luck! You can solve for the intersection of two convex solids in 2D with an algorithm called Sutherland-Hodgman clipping.

In order to use a clipping routine to find the intersecting area you will need to represent a circle as a discrete set of points. The more points your circle has the more smooth the arc is, but the more expensive each volume is to collide with. You'll have to tune how many vertices your circle approximation has. Note that you can render a circle as smooth as you like with a much lower-fidelity collision object underneath that remains invisible.

Here is an article I wrote on the topic of Sutherland-Hodgman clipping. The idea is to loop over the edges of one of your volumes and clip each edge inside the boundaries of all edges of another polygon.

Sutherland-Hodgman works by defining a few different cases of having two end-points of a line segment on either side of a plane (a line in 2D); here is the most relevant pseudo-code from the article:

// InFront = plane.Distance( point ) > 0.0f
// Behind  = plane.Distance( point ) < 0.0f

Vec2 p1, p2;
ClipPlane plane;

case p1 InFront and p2 InFront
push p2
case p1 InFront and p2 Behind
push intersection
case p1 Behind and p2 InFront
push intersection
push p2


This psuedo code gets applied to each segment of one volume for each plane of the other. As this code is run vertices are output into a new array, and they represent the boundary of your intersection. The intersection of two convex volumes is always a new convex volume. This means you can easily render the volume with a triangle fan, and collide it with other convex volumes with the Separating Axis Theorem.