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 ?
Predict collision between spheres
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?
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?
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
falling.Add( 0 )
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 ) {
falling.Add(i);
}
}
}
[/source]
[source lang="java"]
list spheres //ordered list
list visited //list of booleans indicating visited spheres
list falling //indexes of falling spheres, empty
falling.Add( 0 )
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 ) {
falling.Add(i);
}
}
}
[/source]
Author
Thank you for taking the time to reply 
.
@Bacterius there is no physics involved so no siedways momentum
.
. @Bacterius there is no physics involved so no siedways momentum
.
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.
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:
then just count collisions
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
