The other day while working on my thesis research, I came across the need to compute whether the slung-load’s line was in collision with an obstacle, and compute it very efficiently. This certainly isn’t a novel application; however, I couldn’t easily find an algorithm online and it’s not worth the effort to learn and install a library for this one thing. So I came up with a little solution and want to make it available for whomever it might help.

First I’ll set up the problem, show the mathematics behind the solution, then the code in C that I used to implement it.

Setup

Assumptions:

- The slung-load line can be treated as a three-dimensional line segment.
- All obstacles can be represented as groups of two-dimensional rectangles with an arbitrary position and orientation in three-dimensional space.
- The three-dimensional coordinates of the corner of the rectangle are known, as well as the two ends of the line segments. A normal vector for the plane is defined, along with two additional unit orthogonal basis vectors align with the perpendicular edges of the rectangle. The length and width of the rectangle are also known. This information is obviously redundant but it was the format I had available.
- The actual point of intersection isn’t important, as long as a collision is detected.

We will define the inputs as vectors and as the positions of the pivot and load, as the corner of the rectangle, the normal vector, and the unit vectors defining the edges of the rectangle, and and as the length and width of the rectangle.

Solution

and represent the multiples of the normal vector the pivot and load are away from the plane’s surface. If they have the same sign, then both points are on one side of the plane and there is no collision–no further computation required.

If the two points are on opposite sides of the plane, then the point of intersection lay on the line segment . Further, this point divides the line segment into portions proportional to and .

So we *do* end up with the point of intersection. We need to project that point of intersection onto the basis vectors of the edges, and check if the point lay inside the rectangle.

If and are greater than zero and less than and respectively, there is a collision, and otherwise there is none.

Implementation in C

static bool planeIntersect( double P[3], double L[3], struct treeObstacleQuad_ref plane ) { double rp[3], rl[3], isect[3], kp, kl; int ii; // Presume there is no collision bool colliding = false; for( ii = 0; ii < 3; ii++ ) { rp[ii] = P[ii] - plane.corner[ii]; rl[ii] = L[ii+6] - plane.corner[ii]; } kp = plane.normal[0]*rp[0] + plane.normal[1]*rp[1] + plane.normal[2]*rp[2]; kl = plane.normal[0]*rl[0] + plane.normal[1]*rl[1] + plane.normal[2]*rl[2]; if( kp*kl > 0 ) { return colliding; } else { for( ii = 0; ii < 3; ii++ ) isect[ii] = rp[ii] + ( rl[ii] - rp[ii] ) * fabs( kp ) / ( fabs( kp ) + fabs( kl ) ); double a, b; a = isect[0]*plane.horizontal[0] + isect[1]*plane.horizontal[1] + isect[2]*plane.horizontal[2]; b = isect[0]*plane.vertical[0] + isect[1]*plane.vertical[1] + isect[2]*plane.vertical[2]; if( a > 0 && a < plane.length && b > 0 && b < plane.width ) colliding = true; } return colliding; }