this algorithm has many
uses, but I’ll focus one collision detection of fast moving particles, such as
bullets, and special effects point sprites.
first of, imagine you want to
model a bullet fired from a gun. the logical way to do it would be
so the bullet will travel along
a straight line at a constant velocity. The most basic way of checking is a
bullet hit an object (box, polygon, triangle, …), is to check if the bullet is
inside the object. For a box, it is straight forward.
I assumed the box is
defined by two vectors, which are the two points at a diagonal of the box.
ok, so far so good. But for
fast bullets, it’s very possible a collision will be miss, as the bullet will
‘leapfrog’ the box.
a solution is to consider
the bullet as a segment or ray, defined by the bullet’s current position, and
the bullet’s prediceted position, as if there were no collisions, and check if
anything is intersected in between.
This also works for
projectiles under the influence of gravity or external forces (such as heat
seeking missiles for example). The path of a bullet in a frame is approximated
to a segment. This still not 100% accurate (for that, you’d have to consider
the curved trajectory of the bullet within the frame), but it’s a lot better
than checking a single point, and not difficult to implement.
I will explain the general
method of intersecting a segment with a polygon. The case of a box and a ray is
kind of a special case, but also interesting.
The algorithm considered is
the standard clipping algorithm, where a ray is ‘cut’ with the edges of the
polygon. It has the advantage of giving us both the normal and the points of
collision, which is always useful.
Segments are described by
two points, A and B. A point P is on the infinite line passing through A and B if
P = A + (B – A).t,
where t is a scalr.
now, the point P is on
segment A and B if it verifies a similar equation
P = A + (B – A).t, t = [0,
1] (t in range [0, 1]).
you can see that if t = 0,
P = A, and if t = 1, P = B. In between , t = 0.5, then P will be at the middle
of segment [AB], and so on….
Polygons are a list of connected
points, that forms an enclosed area. They come in several forms, but for the
principle of collision detection, the most interesting of the bunch are convex
polygons.
Convex polygons are
polygons where every angles between two consecutive edges is less than 180
degrees. When an angle ‘cave-in’, forming an angle > 180 degrees, the
polygon is not convex. They are concave.
you can see the angle at
the top-centre of the yellow polygon forming an angle > 180 degrees.
So, why do we need to
classify concave polygons to convex polygons?
the convexity of the
polygons brings some interesting properties. For example, imagine a ray
crossing a convex polygon. you can see that you will only ever get two intersection
point.
if the ray started inside
the polygon, you can see that you will only ever get one intersection point.
however, with a concave
polygon, the same principle does not quite hold.
but you can also see that
the number of intersections is odd if the start of the ray is inside the
polygon, odd if it is outside.
this, for example, is used
in some algorithm to detect if a point is inside a polygon or not.
Convexity has more useful
features, and we can use a method called ‘clipping’ very efficiently, since we
can reduce clipping against segments to clipping against the infinite line
going through the segment.
the line going through the
segment splits the space in two, called half-space. one called ‘positive’, and
one ‘negative’. therefore, the line is
kind of ‘signed’, the direction in which the line is pointing is important.
In the first picture, the line is pointing down. the positive half space
is the portion of the space on the left of the line, while the negative portion
is on the right. When the line is pointing up, the spaces are swapped around.
the ‘normal’ of the line is a vector that is perpendicular to the line
direction, and obeying the right-hand rule. point the thumb of your right hand
towards the line direction, and the index will point towards the direction of
the normal, towards the positive half space.
this rule is more a coordinate system convention, and it’s quite
important to stick to it. for example, following the right-hand rule, all
convex polygons should have their vertices listed anti-clckwise, so the space
enclosed in the polygon is the intersection of all the negative half-space of
the lines passing through the edges of the polygons.
take for example a triangle, with it’s vertices listed anti-clockwise.
The inside of the triangle is the intersection of the negative half-space
of the line passing through the line [V0, V1], and the negative half-space of
the line passing through the line [V1, V2], and finally the negative half-space
of the line passing through the line [V2, V0].
now, to detect is a point is in the red area, it’s simply a matter of
detecting if the point is inside one of the blue areas instead. And if it is,
then the point cannot be in the red area.
to detect on which side of the line the point lies, you check the sign
of the normal of the line dot the segment starting from a point on the line,
and going twards the point of interest.
here, P0 is in the blue area, and if you dot product vector (P0 – V0)
and the normal, the product will be positive.
P1 is in the negative area, since (P1 – V0) dot Normal will be negative.
so, as soon as you find the point in a blue area, you know it cannot be
in the polygon area, which is the intersecion of all half-spaces for every
edges.
you can see that the algorithm will brake is the polygons where concave.
the red areas shows parts of the polygon where the points will be
wrongfully detected as not being in the polygon.
here is how the code would look like to detect if a point is inside a
convex polygon with its vertices listed in a anti-clockwise order.
For a segment cut by a convex polygon, you know you will get two
intersection point, a near point and a far point. the near point being the
point the closest to the segment origin, the far point the point the closest to
the segment’s end.
if the segment starts outside, then the intersection point lies in one
of the positive half space of the polygon. and the near point will be a point
that is the intersection of the segment and a line where the origin lies on the
positive half space.
Pnear0 and Pnear1 are two candidates for the near point. The right point
is the point which is the furthest away from the start position of the
ray.
for the far point, it is the same principle. the far point will be a
point that is the intersection of the segment and a line where the start point
lies on the negative half space.
pfar0 is the point you are looking for, which is this time the point the
closest of all the far point candidates.
how to calculate the intersection of a segment and a line?
to calculate the intersection of a segment and a line, we refer to the
equation of a segment. P = A + (B – A).t.
the point of intersection Q will be a point on that line, so Q = A + (B
– A).t
and the point of intersection Q is such that (Q – V).N = 0, where V is a
vertex of the edge we are trying to intersect, and N is the normal of that
edge.
so, we have a system of two equations
(1) Q = A + (B – A).t
(2) (Q – V).N = 0
now, we can calculate t, the unkown, by substituting Q from equation 1
into equation (2). the result will be .
t = (V – A).N / (B-A).N
and you find Q, the point of intersection, by plugging t back into the
first equation
Q = A + (B – A).t
Putting it all together
so, now, we have a method to calculate the points of intersection Pnear and
Pfar, which are the intersection of the segment and two of the lines passing
through edges of the polygon.
the points Pnear and Pfar, have two tnear and tfar scalar values, as
calculated by the system of equations above.
Pnear = A + (B – A).tnear
Pfar = A + (B – A).tfar
to detect if the ray misses the polygon, it’s simply a matter of finding
if pfar is smaller than pnear, as demonstrated below.
also, tfar has to be > 0, and tnear has to be < 1, as shown
below
if one of those conditions fail, then there are no intersection possible.
an algo that detects if a segment
intersects a convex polygon. Note that the code above returns the normal of the
intersection at both points. That is if the ray actually intersects at the near
and far plane. the ray origin might laredy be in the polygon, in that case,
tnear will be 0.0f, but the normal Nnear will be undefined. Similarly for tfar
= 1.0f, that is if the end point is inside the polygon, the normal Nfar will be
undefined.
also, before calling the
algorithm, tnear and tfar have to be initialised to respectively 0.0f and 1.0f.
This algorithm can be used therefore as a mean to find the very first point of
intersection and the very last point of intersection, when testing a ray
against multiple polygons.