7 Replies - 3517 Views - Last Post: 15 April 2009 - 09:13 PM Rate Topic: -----

#1 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,137
  • Joined: 14-September 07

Sphere Wall Collision

Posted 31 March 2009 - 08:50 AM

I've been thinking about this for a few weeks now and all of my various attempts have failed. I think its due to the fact that there is a math formula I could use, but I just don't know it.

The problem? Detecting a collision between a sphere particle and a "wall" (i.e. bounds of a 3D box), they are bouncing around in. I can detect and resolve collision between spheres relatively well:

 //if two spheres will collide within a given timestamp, create a CollisionPair and
	//add it to the vector
	static void detectCollisions(Vector<Sphere> spheres, Vector<CollisionPair> pairs, double time)
	{
		/*A simple way to check for collision between two spheres given the start and end position for a given time frame
		* is to see the smallest distance between them--ever
		  d^2 = a^2-(A*B)^2/b^2 (distance = d^2)
		* lower case letters are the magnitude of each vector where the upper case are the actual vectors

		Given two spheres P and Q with two points P1, Q1, etc... we have two vectors A and B where
		 A = P1-Q1
		 B = (P2-P1)-(Q2-Q1)

		if distance < (rp+rq)^2, there is a collision (r is the radius of each respective sphere)
		 */

		double distance = 0.00, radii = 0.00, t = 0.00;
		CollisionPair pair = new CollisionPair();

		//clean out the pairs vector for each time stamp
		pairs.removeAllElements();
		
		//Get our appropriate A and B vectors 
		//spheres 1 and 2:
		Vector3D pOne = spheres.get(0).getCurPosition();
		Vector3D qOne = spheres.get(1).getCurPosition();
		Vector3D pTwo = spheres.get(0).getStartPosition().gravitationalAcceleration(spheres.get(0).getVelocity(), time);
		Vector3D qTwo = spheres.get(1).getStartPosition().gravitationalAcceleration(spheres.get(1).getVelocity(), time);
		Vector3D A1 = pOne.subtract(qOne);
		Vector3D B1 = (pTwo.subtract(pOne)).subtract(qTwo.subtract(qOne));

		distance = Math.pow(A1.getMagnitude(), 2.0)-(Math.pow(A1.numericalDotProduct(B1), 2.0)/Math.pow(B1.getMagnitude(),2.0));
		radii = Math.pow(spheres.get(0).getRadius()+spheres.get(1).getRadius(),2.0);

		if(distance < radii)
		{
			//before collision coordinates of the two patciles
			pair.setFirst(spheres.get(0));
			pair.setSecond(spheres.get(1));
			pair.setFirstID(0);
			pair.setSecondID(1);
			//get time (coliision between t0 and t1 timesteps):
			//quadratic equation equivalent if t is between 0 and 1 that is collision tiem within the timestamp
			t = -(A1.numericalDotProduct(B1));
			t -= Math.sqrt((Math.pow(A1.numericalDotProduct(B1),2.0)) - ((Math.pow(B1.getMagnitude(),2.0))*
					(Math.pow(A1.getMagnitude(),2.0)-(radii))));
			t/= Math.pow(B1.getMagnitude(),2.0);
			pair.setCollisionTime(Math.abs(t));
			//add pair to the vector
			pairs.add(pair);
		}

		//spheres 1 and 3
		pOne = spheres.get(0).getCurPosition();
		qOne = spheres.get(2).getCurPosition();
		pTwo = spheres.get(0).getStartPosition().gravitationalAcceleration(spheres.get(0).getVelocity(), time);
		qTwo = spheres.get(2).getStartPosition().gravitationalAcceleration(spheres.get(2).getVelocity(), time);
		A1 = pOne.subtract(qOne);
		B1 = (pTwo.subtract(pOne)).subtract(qTwo.subtract(qOne));
		
		distance = Math.pow(A1.getMagnitude(), 2.0)-(Math.pow(A1.numericalDotProduct(B1), 2.0)/Math.pow(B1.getMagnitude(),2.0));
		radii = Math.pow(spheres.get(0).getRadius()+spheres.get(2).getRadius(),2.0);
		
		if(distance < radii)
		{
			//before collision coordinates of the two patciles
			pair.setFirst(spheres.get(0));
			pair.setSecond(spheres.get(2));
			pair.setFirstID(0);
			pair.setSecondID(2);
			//get time (coliision between t0 and t1 timesteps):
			//quadratic equation equivalent if t is between 0 and 1 that is collision tiem within the timestamp
			t = -(A1.numericalDotProduct(B1));
			t -= Math.sqrt((Math.pow(A1.numericalDotProduct(B1),2.0)) - ((Math.pow(B1.getMagnitude(),2.0))*
					(Math.pow(A1.getMagnitude(),2.0)-(radii))));
			t/= Math.pow(B1.getMagnitude(),2.0);
			pair.setCollisionTime(Math.abs(t));
			//add pair to the vector
			pairs.add(pair);
		}

		//spheres 2 and 3
		pOne = spheres.get(1).getCurPosition();
		qOne = spheres.get(2).getCurPosition();
		pTwo = spheres.get(1).getStartPosition().gravitationalAcceleration(spheres.get(1).getVelocity(), time);
		qTwo = spheres.get(2).getStartPosition().gravitationalAcceleration(spheres.get(2).getVelocity(), time);
		A1 = pOne.subtract(qOne);
		B1 = (pTwo.subtract(pOne)).subtract(qTwo.subtract(qOne));
		
		distance = Math.pow(A1.getMagnitude(), 2.0)-(Math.pow(A1.numericalDotProduct(B1), 2.0)/Math.pow(B1.getMagnitude(),2.0));
		radii = Math.pow(spheres.get(1).getRadius()+spheres.get(2).getRadius(),2.0);
		
		if(distance < radii)
		{
			//before collision coordinates of the two patciles
			pair.setFirst(spheres.get(1));
			pair.setSecond(spheres.get(2));
			pair.setFirstID(1);
			pair.setSecondID(2);
			//get time (coliision between t0 and t1 timesteps):
			//quadratic equation equivalent if t is between 0 and 1 that is collision tiem within the timestamp
			t = -(A1.numericalDotProduct(B1));
			t -= Math.sqrt((Math.pow(A1.numericalDotProduct(B1),2.0)) - ((Math.pow(B1.getMagnitude(),2.0))*
					(Math.pow(A1.getMagnitude(),2.0)-(radii))));
			t/= Math.pow(B1.getMagnitude(),2.0);

			pair.setCollisionTime(Math.abs(t));
			//add pair to the vector
			pairs.add(pair);
		}

		//if no collision between any spheres, pairs vector will be empty
		return;
	}



Sphere:
public class Sphere {

	private Vector3D velocity;
	private Vector3D curPosition, startPosition;
	private double radius;
	private double mass;
	private double startTime;
	private Vector<Vector3D> path;
	DecimalFormat vec = new DecimalFormat("0.00");

	//everything is zero by default, reserved for possible future expantion
	public Sphere()
	{
		curPosition = new Vector3D();
		startPosition = new Vector3D();
		velocity = new Vector3D();
		curPosition.setX(0);
		curPosition.setY(0);
		curPosition.setZ(0);
		startPosition.setX(0);
		startPosition.setY(0);
		startPosition.setZ(0);
		velocity.setX(0);
		velocity.setY(0);
		velocity.setZ(0);
		radius = mass = startTime = 0;
	}

	public Sphere(Vector3D c, Vector3D v, double r, double s)
	{
		startPosition = c;
		curPosition = c;
		velocity = v;
		radius = r;
		mass = (4/3)*Math.PI*Math.pow(r, 3);
		startTime = s;
		path = new Vector();
		path.add(c);
	}

	public void setVelocity(Vector3D v)					 {velocity = v;};
	public void setCurPosition(Vector3D c)				  {curPosition = c;};
	public void setStartPosition(Vector3D s)				{startPosition = s;};
	public void setRadius (double r)						{radius = r;};
	public void setMass(double m)						   {mass = m;};
	public void setStartTime(double s)					  {startTime = s;};
	public Vector3D getVelocity()						   {return velocity;};
	public Vector3D getStartPosition()					  {return startPosition;};
	public Vector3D getCurPosition()						{return curPosition;};
	public double getRadius()							   {return radius;};
	public double getMass()								 {return mass;};
	public double getStartTime()							{return startTime;};
	public Vector<Vector3D> getPath()					   {return path;};

	@Override
	public String toString()
	{
		String temp = "Position: " + "[" + vec.format(this.getCurPosition().getX()) + ", " +
				vec.format(this.getCurPosition().getY()) + ", " + vec.format(this.getCurPosition().getZ()) + "]" +
				" Velocity: " + "[" + vec.format(this.getVelocity().getX()) + ", " +
				vec.format(this.getVelocity().getY()) + ", " + vec.format(this.getVelocity().getZ()) +
				"]" + " Radius: " + this.getRadius() + " Mass: " + vec.format(this.getMass());
		return temp;
	}

	/* print out the "path" of each sphere, useful for debugging
	 * and visually determniing if there was a collision
	 * This vector will be sent to a log file for possible future plotting
	 */
	public void displayPath()
	{
		for(int i = 0; i < path.size(); i++)
		{
			System.out.println(path.get(i).toString());
		}
	}
}



Vector3D
public class Vector3D {

	private double x, y, z;
	DecimalFormat vec = new DecimalFormat("0.00");

	//default constructor here for temp Vectors created when performing functions
	public Vector3D()
	{
		x = y = z = 0;
	}

	public Vector3D(double pX, double pY, double pZ)
	{
		x = pX;
		y = pY;
		z = pZ;
	}

	//Accessor Mutator functions
	public void setX(double pX)		 { x = pX; };
	public void setY(double pY)		 { y = pY; };
	public void setZ(double pZ)		 { z = pZ; };
	public double getX()				{ return x; };
	public double getY()				{ return y; };
	public double getZ()				{ return z; };

	@Override
	public String toString()
	{
		String temp = "[" + vec.format(this.getX()) + ", " + vec.format(this.getY()) + ", " +
				vec.format(this.getZ()) + "]";
		return temp;
	}

	public double getMagnitude()
	{
		double magnitude = Math.sqrt(x*x+y*y+z*z);
		return magnitude;
	}

	public Vector3D normalize()
	{
		double length = this.getMagnitude();
		Vector3D temp = new Vector3D();
		temp.setX(this.getX()/length);
		temp.setY(this.getY()/length);
		temp.setZ(this.getZ()/length);
		return temp;
	}

	public Vector3D crossProduct(Vector3D vectOne, Vector3D vectTwo)
	{
		Vector3D temp = new Vector3D();
		temp.setX(vectOne.getY()*vectTwo.getZ()-vectOne.getZ()*vectTwo.getY());
		temp.setY(vectOne.getZ()*vectTwo.getX()-vectOne.getX()*vectTwo.getZ());
		temp.setZ(vectOne.getX()*vectTwo.getY()-vectOne.getY()*vectTwo.getX());
		return temp;
	}

	public Vector3D scalarMultiplication(double num)
	{
		Vector3D temp = new Vector3D();
		temp.setX(this.getX()*num);
		temp.setY(this.getY()*num);
		temp.setZ(this.getZ()*num);

		return temp;
	}

	public Vector3D scalarDivision(double num)
	{
		Vector3D temp = new Vector3D();
		temp.setX(this.getX()/num);
		temp.setY(this.getY()/num);
		temp.setZ(this.getZ()/num);

		return temp;
	}

	//overloaded '+' operator equivalent
	//add two vectors, does not change calling object,
	//merely returns the vector result
	public Vector3D add(Vector3D rhs)
	{
		Vector3D temp = new Vector3D();
		temp.setX(this.getX() + rhs.getX());
		temp.setY(this.getY() + rhs.getY());
		temp.setZ(this.getZ() + rhs.getZ());
		return temp;
	}

	//overloaded '-' operator equivalent
	//subtracts two vectors, does not change calling object,
	//merely returns the vector result
	public Vector3D subtract(Vector3D rhs)
	{
		Vector3D temp = new Vector3D();
		temp.setX(this.getX() - rhs.getX());
		temp.setY(this.getY() - rhs.getY());
		temp.setZ(this.getZ() - rhs.getZ());
		return temp;
	}

	//returns the numerical result of a vector dot product (as opposed to an actual vector)
	public double numericalDotProduct(Vector3D rhs)
	{
		double temp = 0;
		temp = this.getX()*rhs.getX()+ this.getY()*rhs.getY()+ this.getZ()*rhs.getZ();
		return temp;
	}

	public Vector3D gravitationalAcceleration(Vector3D vInit, double time)
	{
		//given the gravity vector Earth [0, 0, -9.81] and the particle initial position (the vector itself)
		// and the velocity desired we can calculate where it moves in 't' timesteps, a second for example
		//as long as the velocity is not parallel to the gravity, the result will be parabolic


	   //*************Equation*******************
	   //  p(t) = pInit + vInit*(t-tInit) + (1/2)*gravity*(t-tInit)^2
	  //****************************************
		Vector3D curPosition = new Vector3D();
		Vector3D gravity = new Vector3D(0, 0, -9.81);

		curPosition = this.add(vInit.scalarMultiplication(time));
		curPosition = curPosition.add(gravity.scalarMultiplication(0.5*(Math.pow(time, 2.0))));

		return curPosition;		
	}
}




CollisionPair:

public class CollisionPair {
	
	private Sphere first;
	private Sphere second;
	private double collisionTime;
	private int firstID, secondID; //identify which sphere (0-2)
	DecimalFormat vec = new DecimalFormat("0.00");
	
	public CollisionPair()
	{
		first = new Sphere();
		second = new Sphere();
		collisionTime = 0;
	}

	public void setFirst(Sphere rhs)				{first = rhs;};
	public void setSecond(Sphere rhs)			   {second = rhs;};
	public void setFirstID(int num)				 {firstID = num;};
	public void setSecondID(int num)				{secondID = num;};
	public void setCollisionTime(double n)		  {collisionTime = n;};

	public Sphere getFirst()						{return first;};
	public Sphere getSecond()					   {return second;};
	public int getFirstID()						 {return firstID;};
	public int getSecondID()						{return secondID;};
	public double getCollisionTime()				{return collisionTime;};


	@Override
	public String toString()
	{
		String temp = "Collision occurs between points: " + "[" + vec.format(this.getFirst().getCurPosition().getX()) + ", " +
				vec.format(this.getFirst().getCurPosition().getY()) + ", " + vec.format(this.getFirst().getCurPosition().getZ()) + "] " +
				"[" + vec.format(this.getSecond().getCurPosition().getX()) + ", " + vec.format(this.getSecond().getCurPosition().getY()) +
				", " + vec.format(this.getSecond().getCurPosition().getZ()) + "]" + " Time: " + vec.format(this.getCollisionTime());
		return temp;
	}
}



If the smallest distance between two sphere centers is less then the sum of their radii there is a collision. Easy enough. Is there a similar formula for a wall and a sphere?

Another problem is that this environment is frictionless, but does have regular Earth gravity. So I'll have to make the walls extra bouncy to compensate. But, having the spheres confined for the time being would be a great relief. I'm extremely bothered that I cannot solve this myself. Any thoughts?


edit: If this was in 2D I could just reverse the velocity, so maybe that's applicable here? A fresh perspective is needed. :)

This post has been edited by KYA: 31 March 2009 - 08:53 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Sphere Wall Collision

#2 SigurdSuhm  Icon User is offline

  • D.I.C Head

Reputation: 18
  • View blog
  • Posts: 111
  • Joined: 05-August 08

Re: Sphere Wall Collision

Posted 31 March 2009 - 11:21 AM

Are the walls axis aligned? In that case it is very simple. But if not then it's somewhat harder.

For axis aligned collision you can simply check whether the distance is less than the sphere's radius. For example:

Given a wall stretching in the Y and Z direction you can detect the distance between the difference between the sphere's radius' X coordinate and the wall's X coordinate. If this difference is less that the sphere's radius you have a collision.

If you need an algorithm for walls with any non axis aligned orientation let us know, and hopefully I or someone else can help. :)

Regards
Sigurd
Was This Post Helpful? 1
  • +
  • -

#3 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,137
  • Joined: 14-September 07

Re: Sphere Wall Collision

Posted 31 March 2009 - 11:46 AM

AABB sounds like a good way to go. It's a 3D cube so it'll be axis aligned (I think). This assignment has made me feel absolutely retarded.

I did experiment with checking bounds per each sphere's appropriate coordinate (making sure it isn't less then zero or greater then 100) so that makes sense. I'm pretty sure I did it wrong though.

Any chance for some more specifics regarding axis aligned collision detection?

Here's a visual of what I'm thinking, not 100% on this though.

Posted Image

does this constitute axis aligned walls?


I appreciate the response.
Was This Post Helpful? 0
  • +
  • -

#4 bobjob  Icon User is offline

  • D.I.C Head

Reputation: 23
  • View blog
  • Posts: 163
  • Joined: 29-March 08

Re: Sphere Wall Collision

Posted 31 March 2009 - 01:12 PM

A sphere collision just uses the formula a^2 = b^2+c^2 in order to work out the distance between the position of the particle and an object.

if ("distance" < radius) //than collision
else //keep moving in current direction



example for testing on the roof collision (assuming the roof is at a height of say '5' and that the arn't diagnal)

	double checkDistance3D(float x1,float y1,float z1,float x2,float y2,float z2) {
		float
			dx = x1 - x2,
			dy = y1 - y2,
			dz = z1 - z2;
		return squareRoot((dx*dx) + (dy*dy) + (dz*dz));
	}



if (checkDistance3d(0, 5, 0, ball.x, ball.y, ball.z) < ball.radius) {
   ball.x += xSpeed;
   ball.y += ySpeed;
   ball.z += zSpeed;
} else {
   ySpeed = -ySpeed;
}



you will probably need to make a "dummy" particle/ball or whatever, so as to check the position you want to go, before you actually confirm that its possible.
this should work for a single square room. if its anymore complex, a few changed need to be made.

and if you need to do diagnal walls, thats alot of fun, but alot math.

This post has been edited by bobjob: 31 March 2009 - 01:14 PM

Was This Post Helpful? 1
  • +
  • -

#5 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,137
  • Joined: 14-September 07

Re: Sphere Wall Collision

Posted 31 March 2009 - 01:35 PM

In your example is the y axis the up/down/vertical one?


Thanks for the snippet, I'll have to play around with it a bit.
Was This Post Helpful? 0
  • +
  • -

#6 SigurdSuhm  Icon User is offline

  • D.I.C Head

Reputation: 18
  • View blog
  • Posts: 111
  • Joined: 05-August 08

Re: Sphere Wall Collision

Posted 01 April 2009 - 02:44 AM

In the case where your bounding box has it's origin in (0,0) and all the corners have coordinates of either 0 or 100 it should be pretty easy. You can determine a minimum and maximum value for the sphere's center's coordinates. For example:

If the sphere has a radius of 6 and the box stretches from 0 to 100 on the X axis, then the X coordinate of the sphere's center has to be between 6 and 94. Otherwise you have a collision with a wall.

Should be pretty easy to do for all axes. Let us know if something's not working properly. :)

(oh and off topic... this April's Fool really had me cracking up. DIC we love you :P)
Was This Post Helpful? 0
  • +
  • -

#7 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,137
  • Joined: 14-September 07

Re: Sphere Wall Collision

Posted 04 April 2009 - 03:36 PM

Update: I ended up doing simple bounds checking with a random repositioning upon a wall collision. Unfortunately I was not able to incorporate angles of inclusion and a bunch of other items I had planned. Thanks for the responses guys!.
Was This Post Helpful? 0
  • +
  • -

#8 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3089
  • View blog
  • Posts: 19,137
  • Joined: 14-September 07

Re: Sphere Wall Collision

Posted 15 April 2009 - 09:13 PM

Thanks everyone for the replies. Like I mentioned above I didn't get exactly what I envisioned working, but I got a 100% on the project. Cheers!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1