StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Taking </p> <ol> <li><strong>E</strong> is the starting point of the ray, </li> <li><strong>L</strong> is the end point of the ray, </li> <li><strong>C</strong> is the center of sphere you're testing against </li> <li><strong>r</strong> is the radius of that sphere</li> </ol> <p>Compute:<br> <strong>d</strong> = L - E ( Direction vector of ray, from start to end )<br> <strong>f</strong> = E - C ( Vector from center sphere to ray start ) </p> <p>Then the intersection is found by..<br> Plugging:<br> <strong>P = E + t * d</strong><br> This is a parametric equation:<br> P<sub>x</sub> = E<sub>x</sub> + td<sub>x</sub><br> P<sub>y</sub> = E<sub>y</sub> + td<sub>y</sub><br> into<br> <strong>(x - h)<sup>2</sup> + (y - k)<sup>2</sup> = r<sup>2</sup></strong><br> (h,k) = center of circle. </p> <blockquote> <p>Note: We've simplified the problem to 2D here, the solution we get applies also in 3D</p> </blockquote> <p><strong>to get:</strong></p> <ol> <li><strong>Expand</strong><br> x<sup>2</sup> - 2xh + h<sup>2</sup> + y<sup>2</sup> - 2yk + k<sup>2</sup> - r<sup>2</sup> = 0 </li> <li><strong>Plug</strong><br> x = e<sub>x</sub> + td<sub>x</sub><br> y = e<sub>y</sub> + td<sub>y</sub><br> ( e<sub>x</sub> + td<sub>x</sub> )<sup>2</sup> - 2( e<sub>x</sub> + td<sub>x</sub> )h + h<sup>2</sup> + ( e<sub>y</sub> + td<sub>y</sub> )<sup>2</sup> - 2( e<sub>y</sub> + td<sub>y</sub> )k + k<sup>2</sup> - r<sup>2</sup> = 0</li> <li>Explode<br> e<sub>x</sub><sup>2</sup> + 2e<sub>x</sub>td<sub>x</sub> + t<sup>2</sup>d<sub>x</sub><sup>2</sup> - 2e<sub>x</sub>h - 2td<sub>x</sub>h + h<sup>2</sup> + e<sub>y</sub><sup>2</sup> + 2e<sub>y</sub>td<sub>y</sub> + t<sup>2</sup>d<sub>y</sub><sup>2</sup> - 2e<sub>y</sub>k - 2td<sub>y</sub>k + k<sup>2</sup> - r<sup>2</sup> = 0</li> <li><strong>Group</strong><br> t<sup>2</sup>( d<sub>x</sub><sup>2</sup> + d<sub>y</sub><sup>2</sup> ) + 2t( e<sub>x</sub>d<sub>x</sub> + e<sub>y</sub>d<sub>y</sub> - d<sub>x</sub>h - d<sub>y</sub>k ) + e<sub>x</sub><sup>2</sup> + e<sub>y</sub><sup>2</sup> - 2e<sub>x</sub>h - 2e<sub>y</sub>k + h<sup>2</sup> + k<sup>2</sup> - r<sup>2</sup> = 0</li> <li><strong>Finally,</strong><br> t<sup>2</sup>( _d * _d ) + 2t( _e * _d - _d * _c ) + _e * _e - 2( _e*_c ) + _c * _c - r<sup>2</sup> = 0<br> *Where _d is the vector d and * is the dot product.*</li> <li><strong>And then,</strong><br> t<sup>2</sup>( _d * _d ) + 2t( _d * ( _e - _c ) ) + ( _e - _c ) * ( _e - _c ) - r<sup>2</sup> = 0 </li> <li><strong>Letting _f = _e - _c</strong><br> t<sup>2</sup>( _d * _d ) + 2t( _d * _f ) + _f * _f - r<sup>2</sup> = 0</li> </ol> <p>So we get:<br> <strong>t<sup>2</sup> * (d DOT d) + 2t*( f DOT d ) + ( f DOT f - r<sup>2</sup> ) = 0</strong><br> So solving the quadratic equation:</p> <pre><code>float a = d.Dot( d ) ; float b = 2*f.Dot( d ) ; float c = f.Dot( f ) - r*r ; float discriminant = b*b-4*a*c; if( discriminant < 0 ) { // no intersection } else { // ray didn't totally miss sphere, // so there is a solution to // the equation. discriminant = sqrt( discriminant ); // either solution may be on or off the ray so need to test both // t1 is always the smaller value, because BOTH discriminant and // a are nonnegative. float t1 = (-b - discriminant)/(2*a); float t2 = (-b + discriminant)/(2*a); // 3x HIT cases: // -o-> --|--> | | --|-> // Impale(t1 hit,t2 hit), Poke(t1 hit,t2>1), ExitWound(t1<0, t2 hit), // 3x MISS cases: // -> o o -> | -> | // FallShort (t1>1,t2>1), Past (t1<0,t2<0), CompletelyInside(t1<0, t2>1) if( t1 >= 0 && t1 <= 1 ) { // t1 is the intersection, and it's closer than t2 // (since t1 uses -b - discriminant) // Impale, Poke return true ; } // here t1 didn't intersect so we are either started // inside the sphere or completely past it if( t2 >= 0 && t2 <= 1 ) { // ExitWound return true ; } // no intn: FallShort, Past, CompletelyInside return false ; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload