most efficient Bounding Sphere vs Ray collision algorithms

SirYakalot
  • most efficient Bounding Sphere vs Ray collision algorithms SirYakalot

    Is there a known 'most efficient' algorithm for Sphere vs Ray collision detection?

    I recently stumbled accross Arvo's AABB vs Sphere collision algorithm, and I am wondering if there is a similarly noteworthy algorithm for this.

    One must have condition for this algorithms is that I need to have the option of querying the result for the distance from the ray's origin to the point of collision. Although if there is another, faster algorithm which does not return distance, then in addition to posting one that does, also posting that algorithm would be very helpful indeed.

    Please also state what the function's return argument is, and how you use it to return distance or a 'no-collision' case. For example, does it have an out parameter for the distance as well as a bool return value? or does it simply return a float with the distance, vs a value of -1 for no collision?

  • Given a sphere with centre at point C with radius r and a ray starting at point A with direction vector d.

    First check if the vector CA is shorter than r, if so A lies within the sphere and there is definitely a collision.

    Second compute the dot product of CA and d, if it is negative A is "behind" the sphere and there may be a collision, otherwise there is no collision unless A is within the sphere.

    The key to this problem is to find the minimum length from the sphere centre to the line. Project the vector CA onto d, subtract the result from CA, this gives you v, the shortest vector from C to the line going through A with direction d. If v is shorter than r, there is a collision.

    You can find two points where the line intersect the sphere using Pythagoras, C + v +- d * sqrt(r^2 - |v|^2).

    Edit:
    And for the record, this is as good as it gets, everything is done using simple vector maths, it requires a limited number of basic arithmetic functions, and there are only a few branches.

    Edit:
    CA is the vector from C to A, computed as A - C.

    In quick pseudocode, you'd do something like:

    //input
    vector A
    vector d
    vector C
    float r
    //end of input
    
    vector collisionPoint
    vector v
    vector CA = A-C
    float rSquared = r*r
    float vSquared
    if(dotProduct(CA,CA) <= rSquared){
        collisionPoint = A
    }
    else if(dotProduct(CA,d) <= 0){
        v = CA - projection(CA,d)
        vSquared = dotProduct(v,v)
        if(vSquared <= rSquared){
            collisionPoint = C + v - multiply(normalize(d),squareRoot(rSquared-vSquared))
        }
        else{
            collisionPoint = none
        }
    }
    else{
        collisionPoint = none
    }
    

    You could code up all the functions yourself, but it may be handy to use a vector library, note that while A and C are points I have declared them as vectors in the code as it is common not to differentiate between point and vectors in code. This code finds the point closest to A where the ray and the sphere collide. If you are interested in the furthest point that will be C + v + multiply(normalize(d),squareRoot(rSquared-vSquared)).

Tags
c++ collision-detection
Related questions and answers
  • I have a very simple effect file shown below. I am using this to draw 2D lines, however it is not behaving how I expected and I can't seem to get my head round why. If I draw a line that goes from 0,0 to 100, 100 for example, I would expect it to draw a line from one corner of the screen to a little way in. I would expect it to treat these numbers as screen coordinates. Instead, the line is huge! A line of about 2 long fills the whole screen. Why is this? How can I modify my shader to 'think' in screen coordinates? // a struct for the vertex shader return value struct VSOut { float4 Col

  • are examples of actual calculated interpolation value i.e. the proportion of the physics update that is complete at the time the frame is being drawn. I am going to have to change the draw code to draw the objects at a fraction of the distance between their previous and current value positions and rotations. That is yet to be done. Question: Will I also have to do move my collision detection code...Questions: When we draw with interpolation, where should the collision detection code be? Is it worth implementing interpolation in the following situation? This is for Scrolling Asteroids. I have

  • So, alpha-beta pruning seems to be the most efficient algorithm out there aside from hard coding (for tic tac toe). However, I'm having problems converting the algorithm from the C++ example given..._score next_move = move end best_score = alpha end end return best_score end currently, the algorithm is playing terribly. It will initially pick the last space, and then choose the first (from left to right) available space after that. Any idea with whats wrong with it? Also, I've been doing TDD, so I know that self.has_this_player_won

  • I am setting an HLSL effect variable in the following way in a number of places. extern ID3D10EffectVectorVariable* pColour; pColour = pEffect->GetVariableByName("Colour")->AsVector(); pColour->SetFloatVector(temporaryLines[i].colour); In one of the places it is set in a loop, each line in the vector temporaryLines has a D3DXCOLOR variable associated with it. The most annoying thing... float4 Colour; // a struct for the vertex shader return value struct VSOut { float4 Col : COLOR; // vertex normal float4 Pos : SV_POSITION; // vertex screen coordinates }; // the vertex

  • ) return -1; return processed; } I checked that error is never anything but AL_NO_ERROR. I generate the source in the constructor: alGenSources(1, &source); This also never gives any error...Posted this question on SO but got no answers. Maybe somebody can help me here. I recently had a well-working program which streamed WAV and Ogg sounds with OpenAL. I then decided to abstract the source and buffer objects into C++ classes. I got as far as the source class. My function which returns the number of processed buffers is not altering the integer passed to alGetSourcei. int ALSource

  • . Is there an obvious design pattern I am missing out on? Have I made this too complicated? Ideally I need an efficient, and hard to abuse system. Any ideas? ...(_resource) { resource->reference(); } virtual ~ResourceGuard() { resource->dereference();} const T* operator*() const { return (resource); } }; class ResourceManager...) { // Calls a private method, pretend it exits T *temp = dynamic_cast<T*> (_getResource(resourceId)); assert(temp != NULL); return (ResourceGuard<T>(temp

  • until you pop out into an open space, known as a ' ' (space) character. You lose one life for each INITIAL collision with the X wall, and do not lose another until you have popped out and been freed from it. As an added touch i have made it so after you collide while traveling down the randomly generated map (or rather as the walls move uppward while your character stays put) the X chars you've collided with are deleted. However I am having trouble getting the INITIAL COLLISION with the wall to be detected correctly. the result is the playe incorrectly losing 4 lives after hitting 1 wall

  • I have a MD2 model loader, I am trying to substitute its immediate drawing function with a Vertex Buffer Object one.... I am getting a really annoying access violation reading error and I can't... glEnableClientState(GL_TEXTURE_COORD_ARRAY); glDisableClientState(GL_NORMAL_ARRAY); First of all, does it look right? Second, I get access violation error "Unhandled exception at 0x01455626 in Graphics_template_1.exe: 0xC0000005: Access violation reading location 0xed5243c0" pointing at line 7 Vec3f pos = v1->pos * (1 - frac) + v2->pos * frac; where the two Vs seems to have no value

  • version that takes a pointer to an array of length one? I can't imagine its to let you toggle the pointed-to bool to change the value later because the documentation would have to mention that to avoid inadvertent frees. I don't know of any platform where a pointer is smaller than a bool. When would one use glEdgeFlagv instead of glEdgeFlag? ...I know that what both glEdgeFlagv and glEdgeFlag do is toggle boundary edge status, but my question is why does the v version exist when the documentation specifies that the only difference

Data information