Collision detection between bezier and ball.

[CornedBee]

OK, I got a really weird problem. I have a cubic bezier curve in 3d space and a sphere. The bezier curve is static, the sphere moves. Given the curve's definition a, c1, c2, e, each of which is a 3d vector, and the ball's position and movement vector, I need to find out the closest the bezier and the ball ever get to each other.

This is probably confusing.

Ball
{
  Vector3d center;
  Vector3d movement;
}

Bezier
{
  Vector3d start;
  Vector3d control1;
  Vector3d control2;
  Vector3d end;
}

Find
1) the least distance between any point on the bezier curve and any point on the line segment (Ball.center, Ball.movement).
2) the point on the line segment that is closest.
3) the bezier parameter t of the point on the bezier that is closest.

Given these three, I can achieve the other things I need to do.

Any ideas are GREATLY appreciated! I've been sitting on this for 2 days, and it has mostly given me a headache.

[damasterjo]

ok you said "any ideas" so here i go...
well if understand corectly you have a curve somewhere in space, also a sphere moving around. You want to know the closet they ever get to each other...

Reading this I would guess you could calculate the distance between two points, such as the spheres center I guess and a point on the curve. Then log them in an array or a variable that will say overwrite itself when it is a smaller value. And there you go... Cant think of much else...

EDIT:
Also although I dont know the exact shape of you cubic bezier curve, I would assume most of the time, the max would be the closest point, so you could calculate the distance from the max to the center, then test a point slightly to the right and left of the max, to see if smaller if it is, just move the calculated point till it stops decreasing...

[CornedBee]

I'm indeed thankful for any ideas, but that won't work. The issue here is finding the point on the bezier that's closest. Because the bezier lies in 3d space, finding the min/max is not as useful as in 2d. The other issue is that the bezier is much larger than the ball, and the ball is usually very close to the bezier, most of the time touching it.

But you hit the heart of the point, that I have to iterate along the bezier. Subdividing let's me actually narrow down the closest point pretty quickly.

Now comes the funny part.

The ball moves over time, and I need to find the moment it first touches the bezier.
Hmm ... I think you've given me an idea ...

[damasterjo]

Hmm ... I think you've given me an idea ...

Good cause Im out of them

[jcis]

Some Articles about Collision detection (in VC++), maybe help..
Collision Detection

[CornedBee]

Thanks for the link. I'll look into it later.

[fartman_900]

I dont know if this will help, but heres my thought:

So start at one of the endpoints the bezier curve, go through each point on the line and find the vector from it to the centre of the sphere, then scale it (somehow) so that the vector ends on the surface of the sphere and get the closest. Then for the closest one, check to see if the length of that vector to the surface is smaller or equal to the radius.

Just my thoughts on it

[EDIT]
Could you please post a picture if possible of what the bezier looks like? Im curious to see it lol

[CornedBee]

Fartman, that's exactly what I'm trying to do, except that I don't walk the bezier linearly but instead subdivide it constantly.
However, it seems I'm beaten by lack of precision or something like that, because the ball still doesn't hit properly.

As for pictures, since my game has no screenshot function (yet), that's kind of hard.

[cyborg]

Do you know the ball's radius?

[cyborg]

Could you please post a picture if possible of what the bezier looks like? Im curious to see it lol

Here's one in 2D space

[CornedBee]

Do you know the ball's radius?

I do, it's a compile-time constant.

[cyborg]

I think fartman's way should work... What's happening when you try that?

[CornedBee]

It tends to hit inaccurately. It might hit a point ahead instead of directly under, and thus the ball behaves as if it ran into a wall. Sometimes it simply falls through.

[wossname]

Did you ever find a solution to this?

[CornedBee]

Well, one of the tutors told me why the system didn't even seem to behave deterministically (it was because the calculations depended on rendering speed). But no, I never found a solution that didn't let the ball fall through my race track eventually.

I failed that course.