Tuesday, October 16, 2012

Simulating Laser: Line-Circle Intersection

Recently, I tried to apply a new kind of enemy which use laser. At first it seems so simple until I realise that laser-object intersection is not something that I know right away. The laser is a line and the object that I need to intersect, which is the player, is circle. So I need to figure out how to find an intersection point between a line and a circle.

The idea of finding the intersection is to find the point where the line and circle has the same coordinate. So if we define d as the direction of the line (end point (E) - start point (S) of the line), there's a value t from 0 to 1 that satisfy this equation:



Now if you didn't skipped math class as much as I did, you'll remember that we can define a circle with the equation below:

where (x0, y0) is the centre of the circle. Expanding the equation above, we can have

Since point P (xp, yp) is where the line and circle is intersected, then from the equation above, we can conclude that:

 Expanding xp and yp, we can have:

now this is the part where you actually wish you never enter computer graphic course. 

Moving on! We can simplify the equation above by grouping all variables containing t, hence

now if you recall the dot product equation:

we can simplify our previous equation become:

Modifying the formula above, we can find that: 

Lets assume that f = S-p0, we have

That looks extremely friendly than the equations above, right? But hold on we haven't finished yet! The equation above looks familiar, aint it? Those are second degree polynomial at2 + bt + c with

One way to solve polynomial equation is by using this equation:

There will be two solution (t1 and t2, if exist) which means that both these points


is both on the line and the circle.

So, how are we going to implement this on a code. It's simple. We already know what we need (a, b, and c), and we already know what to do with those. Here is part of my code where the laser is actually finding the intersection with the circle.

V3 l_direction = m_collisionPoint - *m_p_ownerPosition;
V3 l_posToTarget = *m_p_ownerPosition - PARR[0].m_position;
float l_a = l_direction.DotProduct(l_direction);
float l_b = 2 * l_posToTarget.DotProduct(l_direction);
float l_c = l_posToTarget.DotProduct(l_posToTarget) - (RADIUS * RADIUS);
float l_discriminant = (l_b * l_b)- (4 * l_a * l_c);
if (l_discriminant > 0);
   l_discriminant = sqrt( l_discriminant );
   // either solution may be on or off the ray so need to test both
   float l_t1 = (-l_b + l_discriminant)/(2 * l_a);
   float l_t2 = (-l_b - l_discriminant)/(2 * l_a);
   if( l_t1 >= 0 && l_t1 <= 1 && l_t1 < l_t2)
      f_collisionPoint = (*m_p_ownerPosition) + l_t1 * l_direction;
      l_colliding.value = true;
   else if( l_t2 >= 0 && l_t2 <= 1)
      f_collisionPoint = (*m_p_ownerPosition) + l_t2 * l_direction;
      l_colliding.value = true;

Notice there are some variables that might not fit your code, so it might need a few tweaks here and there. But most of the code will work right away. I also have a few rules in defining variable names, so you could ignore the prefix (l_*, m_*, m_p_*).

No comments: