Thursday, April 23, 2015

Intersection of three planes

Three plane intersections can make framing shapes on a screen trivial, along with many other applications. While useful for prototyping, I don’t tend to use three plane intersection in final products as there are a lot of things working together.

There are several cases where three planes do not meet in a single point, but there is a simple test for that. For most intersection applications with camera space I have not encountered this but it is worth keeping in mind.

Intersection of three planes

Unsurprisingly the solution is similar to finding a point along the line of a two plane intersection:

P = (d1(n2n3) + d2(n3n1) + d3(n1n2)) / (n1 ᐧ (n2n3))

I’m not going to include the entire solution in this post so I can move on and focus on more camera specific topics in the next, but I want to indicate the steps towards the solution.

Considering the direction of line intersection between each pair of planes, the three plane intersection must be along all three lines:

P = k1D12 + k2D23 + k3D31

And substituting the directions:

P = k1(n1n2) + k2(n2n3) + k3(n3n1)

Using P in the plane equation for each plane yields:

n1 ᐧ (k1(n1n2) + k2(n2n3) + k3(n3n1)) = d1
n2 ᐧ (k1(n1n2) + k2(n2n3) + k3(n3n1)) = d2
n3 ᐧ (k1(n1n2) + k2(n2n3) + k3(n3n1)) = d3

As a vector is perpendicular to itself cross another vector is empty the equations can be reduced to:

n1 ᐧ (k2(n2n3)) = d1
n2 ᐧ (k3(n3n1)) = d2
n3 ᐧ (k1(n1n2)) = d3

Solving this results in:

P = (d1(n2n3) + d2(n3n1) + d3(n1n2)) /  (n1 ᐧ (n2n3))

As noted above, there are cases where three planes don’t intersect in a single point. The test for this case is checking if the denominator n1 ᐧ (n2n3) is near zero and exit.

As an example application of three plane intersection, consider a number of spheres and a set of planes representing a view frustum that should fit all spheres:

Minimum frustum fitting random spheres

Position ballCenter[] = { … }
float ballRadius[] = { … }

Direction planeNormals[COUNT] = { … }
float planeDist[COUNT]

First step is to determine the plane distances:

for (p =0; p<COUNT; p++) {
float dist = -MAX_FLT
foreach (ball) {
float d = Dot(ballCenter[ball], planeNormals[p]) +
if (d > dist)
dist = d
planeDist[p] = dist

Now the planes are defined and we can use intersection to find the corner points of the frustum, note that I’m ignoring the error case of the intersection might not be a single point to make it easier to read:

Position FrustumVerts[4][2]

previous = 3
for (p=0; p<4; p++) {
for (e=0; e<2; e++) {
FrustumVerts[p][e] = Intersect_3Planes(
planeNormals[previous], planeDist[previous],
planeNormals[p], planeDist[p],
planeNormals[NEAR+e], planeDist[NEAR+e])
previous = p


No comments:

Post a Comment