Results 1 to 15 of 15

Thread: Collision detection between bezier and ball.

  1. #1

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Collision detection between bezier and ball.

    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.

    Code:
    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.
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  2. #2
    Fanatic Member damasterjo's Avatar
    Join Date
    Nov 2005
    Location
    In front of my Comp DirectX7 EXpert
    Posts
    827

    Re: Collision detection between bezier and ball.

    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...
    Last edited by damasterjo; Apr 27th, 2006 at 02:19 PM.
    Software languages known:
    Qbasic - TI-Basic - Liberty Basic - Visual Basic 6
    Software API's known:
    Directx 7 and 8
    Internet languages, in the process of learning:
    HTML - JAVASCRIPT - PHP - CSS - MYSQL - AJAX

  3. #3

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Re: Collision detection between bezier and ball.

    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 ...
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  4. #4
    Fanatic Member damasterjo's Avatar
    Join Date
    Nov 2005
    Location
    In front of my Comp DirectX7 EXpert
    Posts
    827

    Re: Collision detection between bezier and ball.

    Quote Originally Posted by CornedBee
    Hmm ... I think you've given me an idea ...
    Good cause Im out of them
    Software languages known:
    Qbasic - TI-Basic - Liberty Basic - Visual Basic 6
    Software API's known:
    Directx 7 and 8
    Internet languages, in the process of learning:
    HTML - JAVASCRIPT - PHP - CSS - MYSQL - AJAX

  5. #5
    PowerPoster jcis's Avatar
    Join Date
    Jan 2003
    Location
    Argentina
    Posts
    4,430

    Re: Collision detection between bezier and ball.

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

  6. #6

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Re: Collision detection between bezier and ball.

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

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  7. #7
    Lively Member
    Join Date
    Jul 2002
    Posts
    86

    Re: Collision detection between bezier and ball.

    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
    Last edited by fartman_900; May 4th, 2006 at 10:20 PM.

  8. #8

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Re: Collision detection between bezier and ball.

    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.
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  9. #9
    Frenzied Member cyborg's Avatar
    Join Date
    May 2000
    Location
    Sweden
    Posts
    1,755

    Re: Collision detection between bezier and ball.

    Do you know the ball's radius?
    Check out the FAQ and do a search before you post.
    My tutorials: Anti-Alias Pixels, Accurate Game Loop, Resource File

  10. #10
    Frenzied Member cyborg's Avatar
    Join Date
    May 2000
    Location
    Sweden
    Posts
    1,755

    Re: Collision detection between bezier and ball.

    Quote Originally Posted by fartman_900
    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
    Attached Images Attached Images  
    Check out the FAQ and do a search before you post.
    My tutorials: Anti-Alias Pixels, Accurate Game Loop, Resource File

  11. #11

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Re: Collision detection between bezier and ball.

    Quote Originally Posted by cyborg
    Do you know the ball's radius?
    I do, it's a compile-time constant.
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  12. #12
    Frenzied Member cyborg's Avatar
    Join Date
    May 2000
    Location
    Sweden
    Posts
    1,755

    Re: Collision detection between bezier and ball.

    I think fartman's way should work... What's happening when you try that?
    Check out the FAQ and do a search before you post.
    My tutorials: Anti-Alias Pixels, Accurate Game Loop, Resource File

  13. #13

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Re: Collision detection between bezier and ball.

    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.
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

  14. #14
    type Woss is new Grumpy; wossname's Avatar
    Join Date
    Aug 2002
    Location
    #!/bin/bash
    Posts
    5,683

    Re: Collision detection between bezier and ball.

    Did you ever find a solution to this?
    I don't live here any more.

  15. #15

    Thread Starter
    Kitten CornedBee's Avatar
    Join Date
    Aug 2001
    Location
    In a microchip!
    Posts
    11,594

    Re: Collision detection between bezier and ball.

    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.
    All the buzzt
    CornedBee

    "Writing specifications is like writing a novel. Writing code is like writing poetry."
    - Anonymous, published by Raymond Chen

    Don't PM me with your problems, I scan most of the forums daily. If you do PM me, I will not answer your question.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width