Okay, I've been struggling with this problem for a while and I'm finally turning here for help:

PROBLEM: You have a sphere moving through an environment populated by a single arbitrary polygon. You know the position, radius and velocity of the sphere, as well as the normal of the polygon and the position of each vertex. How do you calculate the time, if any, until the sphere collides with the polygon? (Must also take into account edge, 'glancing' and vertex collisions).

Calculus. Pretty simple.

If it's so simple why don't you post the solution?

Math, duh.

How large is the environment compared to the size of the polygon and circle?

It's a sphere in 3-space. The environment has no boundaries.

triple integrals. duuuh

How to calculate the solution to this problem...hmm...

Put in numbarz?

While I won't go that far...unless necessary, but so far Bobbert has been the only helpful one.

I'm sure James Bond, maevie, et al. can come up with a solution. I have a .25 solution swimming in my head right now.

Edit: So far this is pictorally what the problem is. Look right, Jon'C?

Stop being dumb ubuu.

I have not yet taken vector calculus, but i have been thinking about it, I keep revolving around this:

Make the Sphere stationary at the origin, and make the polygon move instead.

Take the dot product of the a unit vector in the same direction as the velocity vector now on the polygon against the normal vector of the polygon.

From here I have don’t know where to go, but I keep getting stuck on the normal vector, that is the key.

Teeheee... I think Jon`C is asking for Sith 2 physics help >.>

*ahem*. It might help to think about this in two dimentions first, and then extrapolate to 3 once you have a solution to 2.

So we have a circle and a line with endpoints.

What I might try to do is find the line that is perpendicular to our line, and the circle center point is a point on that line. Then we find where the circle intersects that line, and where the line intersects the original line. Now we just check the length between the two. If it == 0 or changes sign we've hit.

There's a problem where we have created this off of an INFINITE LINE rather than the line segment. More checks could be used to see if the perpendicular line crosses the line segment... if not, then we can use the circle center and the closest line end as our two points. When the distance is <= circle radius we've colided.

Finding out WHEN this happens would be a bit more tricky and I'm not going to try. >.>

Back in my first year I had to program something similiar in Java for my project in the course...

It wasn't as complicated and just involved balls bouncing round in 2d off each other and off walls...

still, I never managed to get it to work, balls kept getting stuck inside one another....they bounced off the walls fine. I never managed to get the formula working for predicting where the ball would be on the next step all too well, hence if it was going fast enough it could enter inside another ball...that's when the program went screwy...

I *could* sit down and try and work this out...however its 3am in the morning, I've got a tonne of marking to do by monday, not to mention I've got to start writting applications for PhD positions...(also I'm kinda experiencing a lazy streek at the moment...)

The problem isn't too hard just thinking about it, however getting it into a mathematical form...uuummm...not so easy.

I have to admit vector mechanics isn't my strong point, I've avoided what classes I could in respect to mechanics, JG is on the right path but I'm sure you've most likely got something similiar already. The hardest thing will figuring out how the sphere will detect the polygon, I've never done any 3d modelling of objects and figuring out how to detect their edges...

If you do figure it out let me know, I'll ask a few friends who are more "modelling" inclined and see what they say.

How are you doing this problem btw? are you writting a program? if not and your having to do this on paper...geh, hard question, its probably simplier than it looks because doing it realistically on paper would be a nightmare (I think).

Hmm, yeah, it seems as though the solution should be something somewhat simple, but my brain's not wanting to think that way after the last week of hell. Can't really think of anything offhand to use to approach this problem, but it doesn't seem like it should be something incredibly involved.

I had the same feeling, but I don't have an answer. If you knew which points on the circle and the polygon would be colliding first, you could just treat it like particle motion and ignore the rest of the system.

Yeah. It's amazingly straightforward to find the point that's going to collide if the point is inside the polygon. If it's on the edge of a polygon you can still find the point on the polygon easily enough, but it's harder to find the point on the sphere.

42

Sorry. Out of all seriousness I thought this was a joke because I know how smart Jon is. I wish I new the real answer...if he cant solve it, i sure as hell cant. Godspeed.

Icky, sounds like the Discrete Element Modelling I did for my final year project - and like JB I had real trouble getting the bloody thing to work. If you're looking for an analytical answer I've got no clue, but if you're looking at time step intervals it's a case of simply resolving the current velocity into its components.... bugger this it's too hard. I'll have a look for my DEM code so you can see how I (nearly) did it.

why not let the point they collide at be (0/0/0) and then work the problem backwards? Meaning, for each possible scenario, let the point of collision be (0/0/0), then work it backwards using the known varibles you established in the beginning of the problem. It shouldn't be too difficult to find a problem that will figure all of the possible combinations (the program should output where on the sphere and where on the polygon the collision occured). Then apply the apropriate offsets based on where they collide at. That should be fairly easily to accomplish since the offset will be the point in each scenario where it collides relative to the origin (center) of the shere relative to the origin (Center) of the polygon.

That should get you started in the right direction AND should work regardless of the (P/Y/R) of the polygon...

Let me know if that helped any.

.

Could you simplify it by pretending that the polygon is encased in a sphere of its own? The sphere would be of smallest radius possible such that the whole polygon fits in. Then you could easily estimate the contact time by calculating in respect to the polygon's sphere. It might make things more simple, although losing some accuracy.

Oh, well, my plan would suck for objects that extend in one direction disproportionately to other directions. . . .

He is having a problem with the sphere, not the polygon. I suppose he could bound the sphere with a square, but it will not be as accurate as he probably wants it to be.

correct me if I'm wrong

• You know where it collides with the polygon (you can make it 0,0)
• You know the radius, position, and velocity of the sphere
• You know the position of the polygon (not moving?)

These sites may help
http://www.gamedev.net/reference/articles/article1234.asp
(This one looks exactly like your problem)
http://www.gamedev.net/community/forums/topic.asp?topic_id=60754
Nehe's tutorial about sphere>plane, sphere>sphere, and sphere>cylinder collisions (I think. I'm only on lesson 22)
http://nehe.gamedev.net/data/lessons/lesson.asp?lesson=30

I'm too a little confused with what you are trying to find. Do you know the direction/trajectory by which the sphere is moving or you have to find one?

If you have to find it how do you limit the possible trajectories?

If trajectory is a known straight line then:

- Calculate the point on trajectory when sphere touches polygon plane (dot product of polygon normal and X,Y,Z-polygonpount=sphere radius)

If the point is inside the polygon (dot product with all edge vectors >0) that's your collision point.

Else

Find closest point on trajectory when it touches one of the edges (similar formula). That's your collision point.

Then calculate the time it takes to reach this point.

Unless I screwed it up somewhere or didn't understand it, that should od it.