Java-Gaming.org Hi !
 Featured games (83) games approved by the League of Dukes Games in Showcase (582) Games in Android Showcase (163) games submitted by our members Games in WIP (633) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 plane intersection  (Read 2573 times) 0 Members and 1 Guest are viewing this topic.
JESTERRRRRR
 « Posted 2013-12-07 23:06:09 »

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

quew8

JGO Knight

Medals: 41

 « Reply #1 - Posted 2013-12-08 14:44:40 »

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.x*B.x +  A.y*B.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.
JESTERRRRRR
 « Reply #2 - Posted 2013-12-09 05:00:32 »

Thank you for typing this out for me, extremely helpful
 Games published by our own members! Check 'em out!
kramin42
 « Reply #3 - Posted 2013-12-09 07:22:03 »

And using the algebraic definition of the dot product ( In three dimensions: A.B = A.x*B.x +  A.y*B.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

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.

Quote
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?
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.

"All science is either physics or stamp collecting." - Ernest Rutherford.
CodeGolf4k
M4nkala
ClickerMonkey

JGO Coder

Medals: 20

Game Engineer

 « Reply #4 - Posted 2013-12-09 14:14:42 »

FYI:

x^-1 = 1/x

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

Roquen
 « Reply #5 - Posted 2013-12-09 14:33:17 »

@kramin42:  What's the location of your icon/avatar pic...whatever you want to call it.
Varkas
 « Reply #6 - Posted 2013-12-09 14:34:21 »

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

if (error) throw new Brick(); // Blog (german): http://gedankenweber.wordpress.com
Roquen
 « Reply #7 - Posted 2013-12-09 14:36:18 »

I meant the complex location
JESTERRRRRR
 « Reply #8 - Posted 2013-12-09 18:32:41 »

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.
quew8

JGO Knight

Medals: 41

 « Reply #9 - Posted 2013-12-09 19:45:10 »

@kramin42 of course you can't. How stupid of me, not sure what I was thinking. Thanks.
 Games published by our own members! Check 'em out!
kramin42
 « Reply #10 - Posted 2013-12-09 21:22:50 »

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

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.

"All science is either physics or stamp collecting." - Ernest Rutherford.
CodeGolf4k
M4nkala
Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Ralphanese (16 views) 2015-05-29 13:07:55 Gibbo3771 (12 views) 2015-05-29 06:54:17 Ralphanese (23 views) 2015-05-28 16:52:52 theagentd (31 views) 2015-05-27 22:21:17 theagentd (35 views) 2015-05-27 22:21:08 CopyableCougar4 (25 views) 2015-05-27 19:24:50 MrMapcom (24 views) 2015-05-23 20:26:16 MrMapcom (32 views) 2015-05-23 20:23:34 Waterwolf (37 views) 2015-05-20 15:01:45 chrislo27 (44 views) 2015-05-20 03:42:21
 Rayvolution 24x theagentd 22x Riven 19x Spasi 17x BurntPizza 17x orangepascal 15x Drenius 15x ra4king 13x princec 12x opiop65 12x EgonOlsen 11x Husk 11x DavidBVal 11x KevinWorkman 11x kevglass 9x scanevaro 8x
 Intersection Methodsby Roquen2015-05-29 08:19:33List of Learning Resources2015-05-05 10:20:32How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org