Plane & Sphere Intersection Algorithm?

Quote:

Original post by Cakey So I know how to do rectangular collision(duh), and AABB vs AABB collision(no big deal), but for some reason a Plane and a Plane is confusing me.... Because you don't know if they are aligned to the XZ or XY or ZY axis's? Anyone know where I can find an algorithm? Googling has failed me, so has the search function on this forum. Thanks!

Just out of curiosity, what do you need the plane-plane intersection test for? And are you only interested in axis-aligned planes?

As for the solution, two planes will either intersect in a line, or not at all. If there is an intersection, the line will be parallel to the cross product of the two plane normals, and any point that satisfies both plane equations can serve as the line origin (I think I got that right).

The way I'm going about it right now is, finding out what axis their being aligned too (XY,ZY,XZ) then doing a reallly primitive collision technique. I wonder if this is how most people go about solving this problem?

What I'm doing is making it so if you throw a bucket of paint at a wall in 3-D near a corner it will produce a Plane where the collision occured on the same axis/location but with a "radius"(plane size) of X, then I test to see if another wall is intersected by this plane to know if I should throw some goo over there too :). Think of it as blood spray maybe, but in a corner.

Btw what are normals? I've seen that term alot lately and I have no idea.

A normal is a vector at right angles to something. A plane normal is the vector that is perpendicular to the plane.

I don't think you actually need a plane-plane intersection for what you want to do. Find the intersection point, create a sphere there and do sphere-plane segment intersections with that.

Hmmmmmmmm. Good idea! Thanks a bunch man.
So when you use

gl.glNormal3f(X,Y,Z);

OpenGL finds the normal of the last points?maybe? maybe I should just read the API instead of asking. But once again thanks for that I'll report back once I get further into it.

http://en.wikipedia.org/wiki/Plane%E2%80%93sphere_intersection
I found this, but I'm not sure exactly how to apply it. Got a helping hand?

So I create a sphere with radius r at point X,Y,Z. Then I test to see if the planes surrounding this sphere have points which coincide between the Sphere and the Plane. Howww????

If the sphere Intersects then it will create a mini-circle on the plane which then I could get the midpoint between two points on that mini-circle(coinciding on the collided plane).That won't be hard just find one point on the circle then 180 it with cos and sin to get the opposite.

I'm struggling with understanding on how to implement this idea, but mathematically I understand it. I think???

[Edited by - Cakey on March 19, 2009 6:33:23 PM]

Edit: ehh still can't get it

[Edited by - Cakey on March 19, 2009 10:59:37 PM]

Quote:

If the sphere Intersects then it will create a mini-circle on the plane

This is correct. The radius R of the circle is:
R² = r² - [(c-p).n]²
where r = sphere radius, c = centre of sphere, p = any point on the plane (typically the plane origin) and n is the plane normal. (c-p).n is equivalent to (c.n)-(p.n) which may be easier depending on how you define planes (the d-value is often p.n).

Obviously if (c-p).n is greater than r then the sphere does not intersect the plane. In this case the value R² will be negative and you can skip out immediately.

The centre of the circle in world coordinates is
p - [(c-p).n]n
In plane local coordinates is:
[ x: (c-p).x, y: (c-p).y, z: 0 ]
... where x and y are the local coordinate axes within the plane. p must be the plane origin now (not any point on the plane). Assuming the coordinate systems are not scaled the radius will be correct in both.

You can then perform a simple circle-polygon test to see whether the circle intersects the section of the plane (heretofore considered infinite) that is of interest to you. If it's a rectangular wall then I think this is a well documented problem (circle-rectangle intersection test). In any case it is a simple case of testing if the centre is either on the right side of all edges or within one radius of any edge.

Edit: quote fail. And yes I had to draw a diagram to work it out :p

Okay I think I am understanding this a bit more, but I'm confused by normals. Considering I just learned what a Vector is a week or so ago bare with me...
http://en.wikipedia.org/wiki/Normal_vector

So I just get any point on my plane(I'm going to use the center most point), turn it 90 degrees so it is perpendicular to the plane(right angle)? This is kind of hard for me conceptually because my plains are aligned on different axis's(XZ,XY,ZY) however, I don't rotate them in my code. I just use different points.

The normal is the vector which comes out of the plane at right angles. If you have any two (non-parallel) vectors – such as difference vectors between points – within the plane, you can construct a normal by normalise(v1, v2).

If you have a triangle then you can find a normal by normalise(v1-v0, v2-v0) where vN are the vertices of the triangle. This works for the first three points (actually any three in sequence) on a convex polygon too. There is another thread about exactly that issue at the moment.

	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 = 3.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;						if(p.splatAxis.equals("XY")){		    	xRatio = (cX - (p.X - (p.Width/2)))/p.Width;				yRatio = (cY - (p.Y - (p.Height/2)))/p.Height;	    	}else if(p.splatAxis.equals("ZY")){	    		xRatio = (cZ - (p.Z - (p.Depth/2)))/p.Depth;				yRatio = (cY - (p.Y - (p.Height/2)))/p.Height;	    	}else if(p.splatAxis.equals("XZ")){	    		yRatio = (cZ - (p.Z - (p.Depth/2)))/p.Depth;				xRatio = (cX - (p.X - (p.Width/2)))/p.Width;			}			p.updateSubTexture(gl, xRatio, yRatio);		}	}

It's written in Java and not quite working... Yet... Any Idea's as to why???

[Edited by - Cakey on March 20, 2009 5:10:00 PM]

These will help you ;) (change the properties to get/set methods if Java hasn't got around to properties yet).

If your planes are fixed to axes then the normal is along the other; i.e. an XZ plane will have a normal [0,1,0] or [0,-1,0].

The step you missed is normalising the cross product. If you look at your V0 at that point you will find that in the general case it is not of length 1. Normals should always be normalised (i.e. length 1), as should coordinate axes.

Also, it's plane, not plain ;)

I'm confused... What's magnitude do? and is that normalizing? I'm lost. I've been told normalizing was three different things today hahahhaa. First one was subtracting points, second was dividing by the vector length, then I was told the cross product was. BLAHHH.

Okay so after I do the mnemic cross-product I set the magnitude to 1? where does that fall into play in the equation?

Oh and yes it is "plane" lol, I didn't realize that(yesterday) until I had to dig into all this mathematics :(.

Magnitude = length. (You should be able to see that from the definition?)

Normalisation = setting the length to 1. (Note that this is a different term to a normal vector, which as I previously explained is a vector perpendicular to something, usually a surface. A normal vector should be normalised, though.)

If you can find a primer on vector mathematics I think that will help you, as the problems that you are trying to solve are using it all the time.

Quote:

Okay so after I do the mnemic cross-product I set the magnitude to 1? where does that fall into play in the equation?

Yes. The cross product is trying to find the plane normal, which as I said above should be normalised. (Don't blame me, I didn't choose the nomenclature :p.) All normal vectors should be normalised.

I didn't mean to demean you. I was just confused and asking questions :D. You've helped me sooo much. Thanks for that.
Reading up on some of these things would be a very good idea! haha it might end some confusion :).
edit -
I guess my problem is my "vectors" aren't real vectors. They have no magnitude :( wooops hahhaa. Hopefully I can figure this out haha.

Well there goes 16 hours for nothing haha.
I give up but I found a work around... If anyone figures it out I'd be curious how.

Quote:

Original post by Cakey I'm confused... What's magnitude do? and is that normalizing? I'm lost. I've been told normalizing was three different things today hahahhaa. First one was subtracting points, second was dividing by the vector length, then I was told the cross product was. BLAHHH.

second is correct, I'd be sceptical of the sources that gave you answers 1 and 3.

As bob said, to really 'get' this stuff you'll have to read a primer on vector calculus. It doesn't have to be very heavy, but knowing cross products, dot products, vector projection and basic vector arithmatic will really serve you well for figuring out things like this. Once you understand the tools you're using it all becomes far easier.

Also I recommend that you learn the geometrical meaning of the vector operations (dot/cross), as I often solve 3D problems by visualising it instead of by working through the maths.