• Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

# Predict collision between spheres

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

5 replies to this topic

### #1cold_heats_.--.  Members   -  Reputation: 127

Like
0Likes
Like

Posted 21 September 2012 - 02:56 PM

A list of n spheres, each described by the (x,y,z) coordinates of its highest point and ® its radius, is given.
The first sphere starts falling down vertically.If it touches another sphere during the fall , this one also starts to fall down and so on.The trajectory is not modified. The Oz axis is oriented vertically up.Find the number of spheres that will hit the ground.

I know that if it were circles in 2D , the solution would be simple.
I was thinking of projecting each sphere onto the plane determined by the normal of the direction and for each sphere test if its projection collides with the others .However my 3D math is not very good ...
How do I do this ?

Edited by cold_heats_.--., 21 September 2012 - 02:58 PM.

### #2Bacterius  Crossbones+   -  Reputation: 9043

Like
0Likes
Like

Posted 22 September 2012 - 02:15 AM

You can work out if two spheres are colliding by taking the distance between their centers, if it is less than the sum of the two sphere's radii then they are colliding. To work out if a sphere intersects a cylinder (hint: consider the cylindrical volume traversed by a sphere when falling) you calculate the distance of its center to the cylinder's axis, if it is less than the sum of the two sphere's radii then the sphere collides with the cylinder - and hence, will get hit by the falling sphere.

You can sort your spheres by initial highest point, too, so you can just iterate through the list and recursing every time a sphere gets hit.

Unless I misunderstood - do the spheres *only* fall down or do they also have sideways momentum? Do they transfer it upon colliding?

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

- Pessimal Algorithms and Simplexity Analysis

### #3Inferiarum  Members   -  Reputation: 733

Like
0Likes
Like

Posted 22 September 2012 - 04:57 AM

order spheres by z axis, then throw it away (the z component)

[source lang="java"]list spheres //ordered listlist visited //list of booleans indicating visited sphereslist falling //indexes of falling spheres, emptyfalling.Add( 0 )visited[0] = truefor (cnt = 0; cnt < length(falling); cnt++) { currentIndex = falling[cnt] for (i = currentIndex + 1; i < length(spheres); i++) { if ( collision(spheres[currentIndex], spheres[i]) && !visited[i] ) { falling.Add(i); } }}[/source]

Edited by Inferiarum, 22 September 2012 - 05:00 AM.

### #4cold_heats_.--.  Members   -  Reputation: 127

Like
0Likes
Like

Posted 22 September 2012 - 07:13 AM

Thank you for taking the time to reply .
@Bacterius there is no physics involved so no siedways momentum .

### #5Álvaro  Crossbones+   -  Reputation: 13624

Like
0Likes
Like

Posted 22 September 2012 - 08:37 PM

order spheres by z axis, then throw it away (the z component)

Be aware that you need to order the spheres by the z component of their *center*, not their highest point (which is what you are given): Just subtract the radius.

Edited by alvaro, 22 September 2012 - 08:38 PM.

### #6WiredCat  Members   -  Reputation: 352

Like
0Likes
Like

Posted 24 September 2012 - 02:53 PM

soif trajectory is constant you should make a ray from the top to the bottom then test pointline distance (other spheres) if their distance to ray is < than their ardius they will collide add them to stack and repeat pointline test untill no collision is found:

this will help:

t3dpoint __fastcall ClosestPointOnLine (t3dpoint vA,t3dpoint  vB,t3dpoint  vPoint)
{
t3dpoint   vVector1, vVector2,  vVector3;// : t3dpoint;
t3dpoint vClosestPoint;// : t3dpoint;
float  D, T;// : Single;
//First, we create a vector from our end point vA to our point vPoint
vVector1.x = vPoint.x - vA.x;
vVector1.y = vPoint.y - vA.y;
vVector1.z = vPoint.z - vA.z;
//Now we create a normalized direction vector from end point vA to end point vB
vVector2.x = vB.x - vA.x;
vVector2.y = vB.y - vA.y;
vVector2.z = vB.z - vA.z;
vVector2 = Normalize(vVector2);
//Now we use the distance formula to find the distance of the line segment
D = n3ddistance(vA, vB);
//Using the dot product, we project the vVector1 onto the vector vVector2. This essentially
//gives us the distance of our projected vector from vA
T = Dot(vVector2, vVector1);
//If our projected distance from vA, "t",  is greater than or equal to 0, it must be closest to the end point
//vA.  So we return this end point.
if (T<=0) return vA;
//If our projected distance from vA, "t", is greater than or equal to the magnitude or distance of the line
//segment, it must be closest to the end point vB, so we return vB.
if (T>=0) return vB;
//Here we create a vector that is of length T and in the direction of vVector2
vVector3.x = vVector2.x * T;
vVector3.y = vVector2.y * T;
vVector3.z = vVector2.z * T;
//To find the closest point on the line, we just add vVector3 to the original end point vA
vClosestPoint.x = vA.x + vVector3.x;
vClosestPoint.y = vA.y + vVector3.y;
vClosestPoint.z = vA.z + vVector3.z;
return vClosestPoint;
}

then just count collisions

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS