plane intersection

Game Mechanics
#1

I am trying to convert .map file brushes (quake, hl) into models. The data of a brush, which is just a shape in the editor, is given as a bunch of planes, each being defined by 3 points (each with x,y,z). It is the intersection of any 3 planes that give you the actual vertex points of the shape (for those that do intersect).

I am trying to use this page http://mathworld.wolfram.com/Plane-PlaneIntersection.html to achieve it, but I cannot get it to work.

This is the formula from that page:

I have been told the first part (the bit to the negative 1) is calculated by:

dotProduct [normal1, crossProduct (normal2, normal3 ) ]; does anyone know if this is correct?

Second, these normals for each plane, I have been calculating these:

For 3 points, p1, p2, p3

cross( (p2 - p1), (p3-p1) );

After this I normalize them.

Finally, in that formula, is the x1, x2, x3 simply one of my 3 points for each plane?

Would be really grateful if anyone who knows this math could clarify those points for me. Alternatively if anyone knows of any code that finds the intersection of 3 planes when it exists, that would be awesome

#2

So I’m just gonna step through the algebra that I worked out. Hopefully it will help you out.

Now the equation for a hyper plane is:

N.(P0-P) = 0

Where N is the normal of the plane, P0 is a known point on the plane and P is any point on the plane. Think through what that means if you don’t understand the equation.

Now we rearrange that equation. Firstly the dot product is distributive so we can go to this:

N.P0- N.P = 0
and
N.P0 = N.P

So if we have three intersecting planes - A, B and C -, then we can say:

NA.PA = NA.P
NB.PB = NB.P
NC.PC = NC.P

Now lets add those equations together:

NA.PA + NB.PB + NC.PC = NA.P + NB.P + NC.P

And again the dot product is distributive so we can factorize that to:

NA.PA + NB.PB + NC.PC = P.(NA + NB + NC)

And using the algebraic definition of the dot product ( In three dimensions: A.B = A.xB.x + A.yB.y + A.z*B.z) then:

(NA.PA + NB.PB + NC.PC).x = P.x *(NA + NB + NC).x
(NA.PA + NB.PB + NC.PC).y = P.y *(NA + NB + NC).y
(NA.PA + NB.PB + NC.PC).z = P.z *(NA + NB + NC).z

Hence:

P.x = (NA.PA + NB.PB + NC.PC).x / (NA + NB + NC).x
P.y = (NA.PA + NB.PB + NC.PC).y / (NA + NB + NC).y
P.z = (NA.PA + NB.PB + NC.PC).z / (NA + NB + NC).z

Having gone through the calculation step by step, I hope you have a better understanding of what to do and how to do it. I know I have sometimes used “.” to mean “dot product” and sometimes to mean “component of” (although if you consider “x” to be the x-axis vector, or the “standard basis vector” for any hardcore mathematicians, and equivalent for “y” and “z” then it actually makes sense) but I’m sure you’ll work it out.

Also this is just something I worked out just now. I make no assumption that is it correct - it certainly isn’t the same as your posted equation, not that that means it is wrong. But your equation confused me somewhat (which is why I did this rather than talking you through that one).

And now I’ve talked enough.

#3

Thank you for typing this out for me, extremely helpful

#4

Sorry, but this is where your derivation goes wrong. You cannot take the components of a scalar like you are on the left side of these equations.

Yes, that is the formula for |n_1 n_2 n_3| (you still need to do the ^-1 to get the coefficient in the equation). It’s fairly easy to show that with the matrix determinant.

#5

FYI:

x^-1 = 1/x

More broadly:

x^-y = 1/(x^y)

#6

@kramin42: What’s the location of your icon/avatar pic…whatever you want to call it.

#7

Seems to be from here: http://www.gravatar.com/avatar/bb982b00f38c4e5001f1c6f8d7045a9c

#8

I meant the complex location :wink:

#9

I appreciate the posts thanks guys. Turns out I actually wasn’t adding my found point to the list of points, which is why it never worked… so uh… bit embarassing.

#10

@kramin42 of course you can’t. How stupid of me, not sure what I was thinking. Thanks.

#11

I don’t think I saved the location/zoom but you might be able to find it if you follow these steps:

  1. zoom in on the ‘v’ between the main cardoid and the first circle of the Mandelbrot set
  2. zoom in on one of the spirals on the edge of the cardoid
  3. zoom in on one the sub-Mandelbrots in the spiral
  4. repeat 1 for the sub-Mandelbrot and you should see a bunch of the shapes in my avatar

I think it might be called the valley of seahorses too so you can try searching for that.