Sphere Intersecting Plane help?

Cakey · March 20, 2009, 2:26am

:-\ So I am trying to do something goofy it’s pretty hard to explain. Here’s the situation:

I call it “fragmentation grenade” handling?

I have a Point in three-space. I want to make an invisible sphere around it. Then I want to check if multiple planes collide with this sphere. That part is easy, just the 3-D distance formula. Cool.

But, I want to find a point(I’m aware a sphere in most cases collides with more than one point on a plane) on the plane were the sphere hit’s it. Does that make sense?

Is this going to be impossible? I found a wikipedia page about it, that didn’t help, and asked for help on GameDev’s Math forum and no one really helped. So I came back here :D. Here’s the wiki if it helps anyone help me. Btw I will post the working code once this is figured out! I’m also willing to use a library or someone elses class file for this if that’s availible(spent 7 hours on this…).

Any help at this point would be immaculate…

gouessej · March 20, 2009, 8:32am

Look at nehe.gamedev.net, I had found something about this in a tutorial about collisions some years ago and I had used it for my ray tracer in C.

pjt33 · March 20, 2009, 10:37am

The bit where it says “we obtain a parametric equation for the circle in terms of θ” gives you far more than you need. Pick any value of theta and you have a solution.

DzzD · March 20, 2009, 3:35pm

I have some trouble to understand what you are exacly looking for ? intersection circle ??

cylab · March 20, 2009, 3:37pm

He probably need the intesection volume, so he can slice out a part of the wall due to the grenate effect. Or he simply wants the intersection circle, so he can draw som decals…

DzzD · March 20, 2009, 3:54pm

thks for the precision

so for the intersection circle you can easily determine it center and it radius.

starting with your plane equation ax+by+c*z+d=0 where a,b,c is the normal vector of the plane and d is computed using one vertex that lie on the plane

you can compute the radius of the circle using the distance of the sphere to the plane.
sphere center pos : sx,sy,sz
signedDistanceToPlane=asx+bsy+c*sz+d

then
if distanceToPlane>sphereRadius or distanceToPlane<-sphereRadius no intersection
else (severals other way but here is one)
circleRadius=sphereRadius*Math.cos(Math.asin(distanceToPlane/sphereRadius));

you can determine the circle center using the signed distance and the inverse of the normal vector a,b,c:

C=S-N*signedDistanceToPlane;

where :
C is the circle center
S the sphere center
N the normal (a,b,c of the plane equation=>must be normalized)

=>
Cx=Sx-NxsignedDistanceToPlane;
Cy=Sy-NysignedDistanceToPlane;
Cz=Sz-Nz*signedDistanceToPlane;

Cakey · March 20, 2009, 5:20pm

Okay so how do I calculate the normal of a plane were I have 4 vertexes? I just googled it and found only equations for infinite plains. How exactly do you turn a plain into a vector? Here’s what I’ve figured out so far.

I understand that a normal is just a 90 degree angle from the plane. But does it matter which normal I get from the plane?
And once I get the normal I just use this?


signedDistanceToPlane=planeNormX*sphereCenterX+planeNormY*sphereCenterY+planeNormZ*sphereCenteZ + d

What is D in that equation. On the wiki it says

[quote] a x + b y + c z = d
[/quote]
But on your equation you have + d. I also read Somewere else (if I remember right) that d needs to be figured out from a point on the plane?

Thanks a bunch everyone. I’m in College Algebra right now so all this Calc/Advanced Geometry(?) stuff programming asks for can be a bit overwhelming…

Edit -

Could I also “shoot” out 4 rays in 90 degree angles bound from the “sphere”? Then check for ray to plane intersection? I guess I’d still need to figure out what a normal is to even do that… this is frusterating. But I know once I get it it will be a party.

One way I can think of is to make these 4 rays and project them using for loops(for distance) and check each iteration for collision. But that is going to be horrifically slow, and innacurate…

ORRRRR -

I could create a plane of the “radius” specified then check to see if that plane collides with the other planes. But once again I’m not sure of how good that will be or how to do a plane vs plane intersection…Probably involves normals…

Edit #2:
Or I could try to calculate the closest point on a selected plane then check it’s distance. I just don’t understand what a Dot product is or even how to implement it to be honest… I’m kinda rethinking my comp sci major…

DzzD · March 20, 2009, 7:05pm

[quote]a x + b y + c z = d
[/quote]
this is just a matter of tast, dont care about that

you can compute the plane normal using three vertex (three point liing on it) : v0,v1,v2, you find unit normal by normalizing the cross product of two edge :

V1=V1-V0
V2=V2-V0

the normal of the plane is : V1^V2 then to get a unit vector you divide by the lenght of the result

to find the d parameter of the eqution you can use any vertex that liing on the plane. let’s take v0

ax+by+c*z+d=0

v0 is a vertex
n is the unit computed normal above

so

nxv0x+nyv0y+nz*v0z+d=0

finally :

d=-(nxv0x+nyv0y+nz*c0z)

Cakey · March 20, 2009, 7:15pm

Okay okay I think I get it now!
ohhh okay so N represents Normal(duh) and there is only one normal from 3 points selected on the plane?

Lemme try!Then I’ll report back

Cakey · March 20, 2009, 8:04pm

Hmmm…


	public void SpherePlaneIntersection(float sx, float sy, float sz, Plain p){
		//Sphere's center is sx, sy, sz(inputs)
		//and p.x, p.y, p.z are the planes center point.
		//NOTE: My plain object contains a center point, and width/depth/height values
		Point3D V0 = null, V1 = null, V2 = null, Normal = new Point3D();
		float D, distance, sphereRadius = 4.5f;
		if(p.splatAxis == "XY" || p.splatAxis == "ZY"){
			V0 = new Point3D(p.X, p.Y, p.Z);
			V1 = new Point3D(p.X, p.Y-(p.Height/2), p.Z);
			V2 = new Point3D(p.X, p.Y+(p.Height/2), p.Z);
		}else if(p.splatAxis == "XZ"){
			V0 = new Point3D(p.X, p.Y, p.Z);
			V1 = new Point3D(p.X, p.Y, p.Z-(p.Depth/2));
			V2 = new Point3D(p.X, p.Y, p.Z+(p.Depth/2));
		}
		
		V1.X -= V0.X; V1.Y -= V0.Y; V1.Z -= V0.Z;
		V2.X -= V0.X; V2.Y -= V0.Y; V2.Z -= V0.Z;
		///*
		Normal.X = (float)Math.pow(V1.X, V2.X);
		Normal.Y = (float)Math.pow(V1.Y, V2.Y);
		Normal.Z = (float)Math.pow(V1.Z, V2.Z);
		/*
		Normal.X = V1.X * V2.X;
		Normal.Y = V1.Y * V2.Y;
		Normal.Z = V1.Z * V2.Z;
		*/
		D = -((Normal.X * V0.X) + (Normal.Y * V0.Y) + (Normal.Z * V0.Z));
		distance = (Normal.X * sx) + (Normal.Y * sy) + (Normal.Z * sz) + D;
		//System.out.println(D + " / " + distance);
		if(distance <= sphereRadius || distance < -sphereRadius){
			float circleRadius, cX, cY, cZ;
			float xRatio = 0f, yRatio = 0f;
			circleRadius = sphereRadius * (float)Math.cos( Math.asin( distance / sphereRadius ) );
			cX = sx - Normal.X * distance;
			cY = sy - Normal.Y * distance;
			cZ = sz - Normal.Z * distance;
		}
	}

I don’t think this code is quite right just yet

What do you mean by this?

Riven · March 20, 2009, 8:24pm

There are a few obvious bugs…

Spelling: it’s Plane, not Plain
String comparing, do not use == “XY”, use str.equals(“XY”) , why? google it a bit
I don’t know what you are doing with Math.pow(…, …) but that won’t normalize your normal, also google how to normalize a vector

Cakey · March 20, 2009, 8:28pm

Thanks Riven. Those are some good suggestons as welll…
http://www.fundza.com/vectors/normalize/index.html - good info for normalizing a vector if any passer-by is looking


		public void SpherePlaneIntersection(float sx, float sy, float sz, Plain p){
		//Sphere's center is sx, sy, sz(inputs)
		//and p.x, p.y, p.z are the planes center point.
		//NOTE: My plain object contains a center point, and width/depth/height values
		Point3D V0 = new Point3D(), V1 = new Point3D(), V2 = new Point3D();
		Point3D Normal = new Point3D();
		Point3D N1 = new Point3D(), N2 = new Point3D(), N3 = new Point3D();
		float D, distance, sphereRadius = 2.5f;
		
		if(p.splatAxis.equals("XY") || p.splatAxis.equals("ZY")){
			V0 = new Point3D(p.X, p.Y, p.Z);
			V1 = new Point3D(p.X, p.Y-(p.Height/2), p.Z);
			V2 = new Point3D(p.X, p.Y+(p.Height/2), p.Z);
		}else if(p.splatAxis.equals("XZ")){
			V0 = new Point3D(p.X, p.Y, p.Z);
			V1 = new Point3D(p.X, p.Y, p.Z-(p.Depth/2));
			V2 = new Point3D(p.X, p.Y, p.Z+(p.Depth/2));
		}
		
		float length = (float)Math.sqrt( (V1.X * V1.X) + (V1.Y * V1.Y) + (V1.Z * V1.Z) );
		N1.X = V1.X / Math.abs(length);
		N1.Y = V1.Y / Math.abs(length);
		N1.Z = V1.Z / Math.abs(length);
		length = (float)Math.sqrt( (V2.X * V2.X) + (V2.Y * V2.Y) + (V2.Z * V2.Z) );
		N2.X = V2.X / Math.abs(length);
		N2.Y = V2.Y / Math.abs(length);
		N2.Z = V2.Z / Math.abs(length);
		length = (float)Math.sqrt( (V0.X * V0.X) + (V0.Y * V0.Y) + (V0.Z * V0.Z) );
		N3.X = V0.X / Math.abs(length);
		N3.Y = V0.Y / Math.abs(length);
		N3.Z = V0.Z / Math.abs(length);
		
		N1.X -= N3.X; N1.Y -= N3.Y; N1.Z -= N3.Z;
		N2.X -= N3.X; N2.Y -= N3.Y; N2.Z -= N3.Z;
		N3.X = (N1.X+N2.X)/2;N3.Y = (N1.Y+N2.Y)/2;N3.Z = (N1.Z+N2.Z)/2;
		
		D = -((N3.X * V1.X) + (N3.Y * V1.Y) + (N3.Z * V1.Z));
		distance = (N3.X * sx) + (N3.Y * sy) + (N3.Z * sz) + D;

		if(distance <= sphereRadius || distance < -sphereRadius){
			float circleRadius, cX, cY, cZ;
			float xRatio = 0f, yRatio = 0f;
			//circleRadius = sphereRadius * (float)Math.cos( Math.asin( distance / sphereRadius ) );
			cX = sx - N3.X * distance;
			cY = sy - N3.Y * distance;
			cZ = sz - N3.Z * distance;
		}
	}

Am I even close?

Cakey · March 20, 2009, 9:21pm

Okay so bob jahnova from GameDev.net was kind enough to tell me that in order to get a normal you need three consecutive points which define your plane.
Such as Top Left, Top Right, Bottom Right…


	public void SpherePlaneIntersection(float sx, float sy, float sz, Plain p){
		//Sphere's center is sx, sy, sz(inputs)
		//and p.x, p.y, p.z are the planes center point.
		//NOTE: My plain object contains a center point, and width/depth/height values
		Point3D V0 = new Point3D(), V1 = new Point3D(), V2 = new Point3D();
		Point3D Normal = new Point3D();
		float D, distance, sphereRadius = 2.5f;
		
		if(p.splatAxis.equals("XY")){
			V0 = new Point3D(p.X - (p.Width/2), p.Y + (p.Height/2), p.Z);
			V1 = new Point3D(p.X + (p.Width/2), p.Y + (p.Height/2), p.Z);
			V2 = new Point3D(p.X + (p.Width/2), p.Y - (p.Height/2), p.Z);
		}else if(p.splatAxis.equals("ZY")){
			V0 = new Point3D(p.X, p.Y + (p.Height/2),p.Z - (p.Depth/2));
			V1 = new Point3D(p.X, p.Y + (p.Height/2), p.Z + (p.Depth/2));
			V2 = new Point3D(p.X, p.Y - (p.Height/2), p.Z + (p.Depth/2));
		}else if(p.splatAxis.equals("XZ")){
			V0 = new Point3D(p.X-(p.Width/2), p.Y, p.Z+(p.Depth/2));
			V1 = new Point3D(p.X+(p.Width/2), p.Y, p.Z+(p.Depth/2));
			V2 = new Point3D(p.X+(p.Width/2), p.Y, p.Z-(p.Depth/2));
		}
		//Normalize
		V1.X -= V0.X;
		V1.Y -= V0.Y;
		V1.Z -= V0.Z;
		
		V2.X -= V0.X;
		V2.Y -= V0.Y;
		V2.Z -= V0.Z;
		
		V0.X = (float) V1.X - V2.X;
		V0.Y = (float) V1.Y - V2.Y;
		V0.Z = (float) V1.Z - V2.Z;
		
		//Calculate D
		D = -((V0.X * V0.X) + (V0.Y * V0.Y) + (V0.Z * V0.Z));
		//Get Distance
		distance = (V0.X * sx) + (V0.Y * sy) + (V0.Z * sz) + D;

		if(distance <= sphereRadius || distance < -sphereRadius){
			float cX, cY, cZ;//Circle Center Point
			float xRatio = 0f, yRatio = 0f;
			cX = sx - V0.X * distance;
			cY = sy - V0.Y * distance;
			cZ = sz - V0.Z * distance;
			
		}
	}

And I found out how to normalize a vector… However nomalizing a plane seems to still mystify me…

DzzD · March 20, 2009, 9:50pm

[quote]if(distance <= sphereRadius || distance < -sphereRadius)
[/quote]
rather : distance <= sphereRadius && distance > -sphereRadius

[quote]Quote
the normal of the plane is : V1^V2 then to get a unit vector you divide by the lenght of the result

What do you mean by this?
[/quote]
I mean cross/vectorial product : http://en.wikipedia.org/wiki/Cross_product

this one:

Cakey · March 20, 2009, 10:00pm

Doh! that || vs &&is what I get for drinking malt liquor so early… haha. Hopefully this time I’ll get it. Once again thanks to everyone for their contribution for this and once I get it I’ll definitly post the code so no one asks this again. And if they do - you can just link them!

Cakey · March 20, 2009, 10:20pm

Here’s what I have so far.(still not working)


public void SpherePlaneIntersection(float sx, float sy, float sz, Plain p){
		//Sphere's center is sx, sy, sz(inputs)
		//and p.x, p.y, p.z are the planes center point.
		//NOTE: My plain object contains a center point, and width/depth/height values
		Point3D V0 = new Point3D(), V1 = new Point3D(), V2 = new Point3D();
		Point3D Normal = new Point3D();
		float D, distance, sphereRadius = 1.0f, lengthOfVect;
		//Gather 3 points for normalization
		if(p.splatAxis.equals("XY")){
			V0 = new Point3D(p.X - (p.Width/2), p.Y + (p.Height/2), p.Z);
			V1 = new Point3D(p.X + (p.Width/2), p.Y + (p.Height/2), p.Z);
			V2 = new Point3D(p.X + (p.Width/2), p.Y - (p.Height/2), p.Z);
		}else if(p.splatAxis.equals("ZY")){
			V0 = new Point3D(p.X, p.Y + (p.Height/2),p.Z - (p.Depth/2));
			V1 = new Point3D(p.X, p.Y + (p.Height/2), p.Z + (p.Depth/2));
			V2 = new Point3D(p.X, p.Y - (p.Height/2), p.Z + (p.Depth/2));
		}else if(p.splatAxis.equals("XZ")){
			V0 = new Point3D(p.X-(p.Width/2), p.Y, p.Z+(p.Depth/2));
			V1 = new Point3D(p.X+(p.Width/2), p.Y, p.Z+(p.Depth/2));
			V2 = new Point3D(p.X+(p.Width/2), p.Y, p.Z-(p.Depth/2));
		}
		//Normalize Plane - This is not correct...
		//lengthOfVect = sqrt((ax * ax) + (ay * ay) + (az * az));
		V1.X = V1.X - V0.X;
		V1.Y = V1.Y - V0.Y;
		V1.Z = V1.Z - V0.Z;
		lengthOfVect = (float)Math.abs(Math.sqrt((V1.X * V1.X) + (V1.Y * V1.Y) + (V1.Z * V1.Z)));
		V1.X = V1.X / lengthOfVect;
		V1.Y = V1.Y / lengthOfVect;
		V1.Z = V1.Z / lengthOfVect;
		
		V2.X = V2.X - V0.X;
		V2.Y = V2.Y - V0.Y;
		V2.Z = V2.Z - V0.Z;
		lengthOfVect = (float)Math.abs(Math.sqrt((V2.X * V2.X) + (V2.Y * V2.Y) + (V2.Z * V2.Z)));
		V2.X = V2.X / lengthOfVect;
		V2.Y = V2.Y / lengthOfVect;
		V2.Z = V2.Z / lengthOfVect;
		
		
		//Mnemonic Cross Product of normalized vectors
		V0.X = (V1.Y * V2.Z) - (V1.Z * V2.Y);
		V0.Y = (V1.Z * V2.X) - (V1.X * V2.Z);
		V0.Z = (V1.X * V2.Y) - (V1.Y * V2.X);
		
		//Calculate D
		D = -((V0.X * V0.X) + (V0.Y * V0.Y) + (V0.Z * V0.Z));
		//Get Distance
		distance = (V0.X * sx) + (V0.Y * sy) + (V0.Z * sz) + D;

		if(distance <= sphereRadius && distance >= -sphereRadius){
			float cX, cY, cZ;//Circle Center Point
			float xRatio = 0f, yRatio = 0f;
			cX = sx - V0.X * distance;
			cY = sy - V0.Y * distance;
			cZ = sz - V0.Z * distance;
		}
	}

I just asked my friends linear algebra teacher for help… I guess he mainly programs in Mat-Lab(w/e that is) but maybe he’ll understand…

DzzD · March 21, 2009, 12:23am

hooo…

first you do not normalize a plane… you normalize a vector => the normal vector

also if your plane lie on one “axis” XY,YZ,XZ you can jump several steps ans it become pretty simple, is it the case ? because those three plane have well know equation that you dont need to compute

Cakey · March 21, 2009, 12:33am

Yes they do lie only on certain axis no rotations -DzzD
Sounds like there might be a short-cut which would be amazing.

SimonH · March 21, 2009, 1:59am

Hey, ‘normal’ is a tricky word in 3D.
To ‘normalise’ a vector you find the x,y,z values which make the vector of length==1.
The ‘normal’ of a plane is a vector which is at right angles to the plane (cross product of two vectors lying in the plane).
Don’t confuse the two! I know I did…

DzzD · March 21, 2009, 2:32am

zezeojeszgozr ghr irrr==+=+r kzerok erj(( (-… <= sry i have bugged …

forget about cross product and other…

if plane is XY the distance to the plane is simply Z pos of the sphere…
for XZ the distance is Y pos of the sphere
and for YZ it is X pos of the sphere

the center of your circle is the same :’(

for XY it is x,y pos of the sphere :-
for XZ it is x,z pos of the sphere :persecutioncomplex:
for YZ it is y,z pos of the sphere :-X