# Predict collision between spheres

This topic is 2121 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
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?

##### Share on other sites
order spheres by z axis, then throw it away (the z component)

[source lang="java"]
list spheres //ordered list
list visited //list of booleans indicating visited spheres
list falling //indexes of falling spheres, empty

visited[0] = true

for (cnt = 0; cnt < length(falling); cnt++) {
currentIndex = falling[cnt]
for (i = currentIndex + 1; i < length(spheres); i++) {
if ( collision(spheres[currentIndex], spheres) && !visited ) {
}
}
}
[/source] Edited by Inferiarum

##### Share on other sites
Thank you for taking the time to reply .
@Bacterius there is no physics involved so no siedways momentum .

##### Share on other sites

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

##### Share on other sites
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

1. 1
2. 2
Rutin
21
3. 3
JoeJ
18
4. 4
5. 5

• 14
• 39
• 23
• 13
• 13
• ### Forum Statistics

• Total Topics
631717
• Total Posts
3001878
×