Jump to content
  • Advertisement
Steven Ford

Algorithm Projectile collision detection / line segment maths

Recommended Posts

Hi guys,

I've got a little problem which is irritating me as there must be a simple solution but Google isn't necessarily being my friend right now.

In my new game, I've got a set of projectiles for which I need to check for collisions with typically rectangular shapes (but which aren't axis aligned). My general approach is to create an axis aligned bounding box for both the projectile's movement and the target object. If there's a match on the broad phase, then I want to check whether the projectile collides with any of the edges of the collision and then report the first collision (i.e. if the projectile would have gone through multiple lines then I want to know the first collision so I can display the explosion animation in the right place).

I represent my shapes as a series of line segments (there's a future question about colliding with semi-circles and circles, but that's later). Can anyone 'refresh my memory' on being able to test for the interaction of line segments?

Thanks

Steve

Share this post


Link to post
Share on other sites
Advertisement

Its quite straight forward, you move projectile over time and implement last_frame_pos with nowframepos vector which you test against each shape: whenever both points are on same sides then theres no collision, and if not you need to check for point on plane from ray. Then you test if the point lies inside polygon. As far as i remeber there was a code on gametutorials.net? Or something similar.

Anyway there are many ways to implement this, one would be:

template <class T>
bool  SegmentPlaneIntersection(t3dpoint<T> n, T d, t3dpoint<T> rA, t3dpoint<T> rB, t3dpoint<T> & res)
{



//t3dpoint<T>  pop = poly.V[0];
//
//t3dpoint<T>  A = vectorAB(poly.V[0],poly.V[1]);
//t3dpoint<T>  B = vectorAB(poly.V[0],poly.V[poly.Count-1]);
//t3dpoint<T>  n = Normalize(A * B);

t3dpoint<T> PointOnPlane;

 long double originDistance = (long double )d;
//		 -1.0 * ((n.x * poly.V[0].x) +
//						   (n.y * poly.V[0].y) +
//						   (n.z * poly.V[0].z));


  long double		distance1 = ((n.x * rA.x)  +
				 (n.y * rA.y)  +
				 (n.z * rA.z)) + originDistance;

  long double		distance2 = ((n.x * rB.x)  +
				 (n.y * rB.y)  +
				 (n.z * rB.z)) + originDistance;

T clsnull = T(epsilona);

if ( (absnf(distance1) <= clsnull) && (absnf(distance2) <= clsnull) )
return false;


if (absnf(distance1) <= clsnull)
{
	res = rA;
	return true;
}

if (absnf(distance2) <= clsnull)
{
	res = rB;
	return true;
}

	if (distance1 * distance2 > clsnull) //oryginalnie bylo >=
										return false;

 t3dpoint<T> vLineDir = Normalize(rB - rA);


	long double 	Numerator = -1.0 * (n.x * rA.x +
						   n.y * rA.y +
							 n.z * rA.z + originDistance);




 long double 	Denominator = ( (n.x * vLineDir.x) + (n.y * vLineDir.y) + (n.z * vLineDir.z) );

	if( Denominator == 0.0)    {
PointOnPlane = rA;
	} else	{
long double		dist = Numerator / Denominator;
  PointOnPlane = (rA + (vLineDir * T(dist)));
}
res = PointOnPlane;
return true;

}

Now that function only returns point on plane and actually it can be done a bit easier (more readable code) but nvm

Now the main goal was to gind if thenpoint is inside polygon, i remember that original code used the technique to find angles between points and check if they match or are greater than  2*pi*0.999999, i hovever calculate side planes and check whenever point lies on one side for all planes, thus it can lie on the edge of one side so youll have to take account on that, and it only states for convex shapes

 

Oh here it is https://github.com/gametutorials/tutorials/blob/master/OpenGL/Camera%20World%20Collision/3DMath.cpp

 

Search for intersectedpolygon function

Share this post


Link to post
Share on other sites

As noted above there are various ways to test for intersection between line segments, but there are algorithms specific to various shapes you can use as well. For example, for linear components and boxes (oriented or axis-aligned), a commonly used test is the 'slab' test. This can be performed directly with respect to oriented boxes, or you can transform the linear component into the local space of the box and perform the test against an axis-aligned box in local space.

I found this with a quick search:

https://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter3.htm

I only looked it over briefly, so I can't guarantee its correctness, but it does describe the algorithm in question. It's in 3-d, but the test is the same for 2-d (just with the third axis dropped).

Here's another reference:

https://www.scratchapixel.com/lessons/3d-basic-rendering/minimal-ray-tracer-rendering-simple-shapes/ray-box-intersection

I see mention there of the 'y = mx + b' representation for lines, which you typically don't want to use directly (as it's not orientation-independent), but based on a quick skim of the article, the actual code may not use that representation.

The slab test is vulnerable to numerical issues when the linear component is nearly parallel to one of the box axes, so you'll typically want to use an epsilon when checking for parallelness (this issue can come up in segment-segment tests as well).

You mentioned you're representing your shapes with a series of line segments. Although a series of segment-segment tests might be sufficient, a naive implementation based on segment-segment tests could return false negatives due to numerical error (e.g. when intersecting more or less directly with a corner). You could easily never encounter just a case in practice, but if you're interested in robustness, something other than naive segment-segment tests might be preferable.

Share this post


Link to post
Share on other sites
On 11/20/2018 at 10:35 PM, Steven Ford said:

Can anyone 'refresh my memory' on being able to test for the interaction of line segments?

An infinite line in 2D has a base-point (a, b), and direction vector (dx, dy). All points of the line are at (a + n * dx, b + n * dy) for all values of n.

Line intersection is the problem of 2 lines (line 1 and line 2) sharing a point, ie

a1 + n1 * dx1 = a2 + n2 * dx2  and b1 + n1 * dy1 = b2 + n2 * dy2. Alll values are known except n1 and n2, so you can solve this set of equations for non-parallel lines, giving you n1 and n2. The shared point is then (a1 + n1 * dx1, b1 + n1 * dy1).

 

For line segments, you solve the above infinite case first, and then check if the shared point is in both segments. The simplest way is to select a smart (dx, dy) value for that.

A line segment from point (a, b) to (c, d) gets direction vector (c-a, d-b). This maps n=0 onto point (a, b), and n=1 onto point (c, d). Values of n larger than 1 or smaller than 0 are outside the segment. Thus, after finding n1 and n2 in the above infinite line intersection, you only have to test "n1 >= 0 and n1 <= 1 and n2 >= 0 and n2 <= 1".

 

 

Edited by Alberth

Share this post


Link to post
Share on other sites

Hi all, thanks for the comments. 

The approach that I've been taking (as with @Alberth) is that each line can be described as:

  • x = startX + lineProportion*dX
  • y = startY + lineProportion*dY

I can't use y = ax + b as this won't handle vertical lines.

I'm clearly missing something when it comes to solving the equations for n1 and n2. It feels like there must be a simple closed form (i.e. not iterative) approach which can be used to solve the equations, but I'm drawing a blank. My main thought is to transform one of the lines into an axis aligned line by calculation the angle of one of the lines and then transforming all of the vectors by this angle and then I'd only need to solve one equation which should be easy. This feels like I'm over complicating efforts, especially when I look at @_WeirdCat_ code. If I'm reading it correctly, one takes the normal between the 2 vectors but then I get a little lost (it's been almost 2 decades since I studied this area :/ )

@Zakwayda - in terms of complete reliability, I'm not massively bothered if there are some extreme edge cases which aren't covered, My collision boxes are slightly padded so it wouldn't be an issue in the main. I just want to make sure that the explosion graphics appear in the right place as at the moment, I display them where the projectile would have gotten to if nothing had gotten in the way which means that the animation sometimes starts within the walls rather than on the wall.

 

Share this post


Link to post
Share on other sites
2 hours ago, Steven Ford said:

I'm clearly missing something when it comes to solving the equations for n1 and n2. It feels like there must be a simple closed form

Simple straight formula shuffling I think

1st equation
    a1 + n1 * dx1 = a2 + n2 * dx2

move a1 to the right
<-> n1 * dx1 = a2 + n2 * dx2 - a1

divide by dx1 at both sides (dx1 != 0 thus!)
<-> n1 = (a2 + n2 * dx2 - a1) / dx1  (#)


2nd equation
    b1 + n1 * dy1 = b2 + n2 * dy2

fill in n1 from above
<-> b1 + ((a2 + n2 * dx2 - a1) / dx1) * dy1 = b2 + n2 * dy2

split the big / dx1 into seperate terms
    b1 + (a2 / dx1 + n2 * dx2 / dx1 - a1 / dx1) * dy1 = b2 + n2 * dy2

same with * dy1
    b1 + (a2 * dy1 / dx1) + (n2 * dx2 * dy1 / dx1) - (a1 * dy1 / dx1) = b2 + n2 * dy2

move terms without n2 to the left, with n2 to the right
factor n2 out
    b1 + (a2 * dy1 / dx1) - (a1 * dy1 / dx1) - b2 = n2 * dy2 - (n2 * dx2 * dy1 / dx1)
                                                  = n2 * (dy2 -  (dx2 * dy1 / dx1))


divide by  (dy2 -  (dx2 * dy1 / dx1))   (which should not be 0 !)
    n2 = (b1 + (a2 * dy1 / dx1) - (a1 * dy1 / dx1) - b2) / (dy2 -  (dx2 * dy1 / dx1))

n2 in terms of line segment number, is computable

fill n2 into the first equation at (#) and get n1

 

 

Edited by Alberth

Share this post


Link to post
Share on other sites

Hi @Alberth,

thank you very much, that explains it rather nicely and easily! I'm guessing that the 2 edge cases are:

1. Line 1 is vertical => can have a separate code path to check that
2. (dy2 - (dx2.dy1/dx1)) == 0 - If I'm correct, this means that the lines are running parallel to each other - again, I can have a separate code path for this.

I'll get this implemented today and then hopefully I can have my pretty (well, by developer art standards) explosions in the right place!

Share this post


Link to post
Share on other sites
1 hour ago, Steven Ford said:

I'm guessing that the 2 edge cases are:

1. Line 1 is vertical => can have a separate code path to check that

You don't need a special case for vertical lines, I don't believe. Unless I've got my math wrong, the equation Alberth provided can be manipulated further to eliminate the secondary divisions, leaving you with the equations for t and u given in the Wikipedia article here:

https://en.wikipedia.org/wiki/Line-line_intersection

Those equations are expressed in terms of four points rather than two point-vector pairs, but it's equivalent.

Share this post


Link to post
Share on other sites
2 hours ago, Steven Ford said:

1. Line 1 is vertical => can have a separate code path to check that

In that case you know the x position, so you can use that in the 2nd line to find n2 (unless the 2nd line is vertical as well, then you end up in the parallel case, see below). Use the 'x position' equation of the 2nd line where you use the x of the first line as resulting x position. This gives n2, and y of the shared point. Next you can use the 'y position' equation of the 1st line to get n1.

 

2 hours ago, Steven Ford said:

2. (dy2 - (dx2.dy1/dx1)) == 0 If I'm correct, this means that the lines are running parallel to each other

Good point. I didn't interpret the result, I just mechanically performed equation rewriting. Make sense though, that the equation can't be solved in that case 😛

 

Technically, both lines can also be on top of each other, which means you will need to check if the segments overlap. I think it's sufficient if one of the end-points is part of the other line segment. I wonder if a simple AABB (axis aligned bounding box) check would suffice.

Share this post


Link to post
Share on other sites
4 hours ago, Alberth said:

In that case you know the x position, so you can use that in the 2nd line to find n2 (unless the 2nd line is vertical as well, then you end up in the parallel case, see below). Use the 'x position' equation of the 2nd line where you use the x of the first line as resulting x position. This gives n2, and y of the shared point. Next you can use the 'y position' equation of the 1st line to get n1.

Yep; that's a relatively easy one, I was just calling it out explicitly to remind me to add it in my code 🙂

 

4 hours ago, Alberth said:

Technically, both lines can also be on top of each other, which means you will need to check if the segments overlap. I think it's sufficient if one of the end-points is part of the other line segment. I wonder if a simple AABB (axis aligned bounding box) check would suffice.

Yep, so what I do is work out whether the start of line 1 is within line 2's range, and then, if it's not, calculate n1 for the start and end of line 2 and use the lowest valid value of n1 - i.e. which end would have been hit first.

This has now all been implemented (see attached) and the explosions are now visually in the right place!

Thanks again for all your help - much appreciated!

	template<class T = float>
	static bool DoLinesIntersect(
		T line1StartX,
		T line1StartY,
		T line1EndX,
		T line1EndY,
		T line2StartX,
		T line2StartY,
		T line2EndX,
		T line2EndY,
		T& line1Proportion,
		T& line2Proportion) {

		bool line1IsPoint = line1StartX == line1EndX && line1StartY == line1EndY;
		bool line2IsPoint = line2StartX == line2EndX && line2StartY == line2EndY;

		auto dx2 = line2EndX - line2StartX;
		auto dy2 = line2EndY - line2StartY;

		if (line1IsPoint && line2IsPoint) {
			// both points, just check if they're the same
			if (line1StartX == line2StartX &&
				line1StartY == line2StartY) {
				line1Proportion = 0.0;
				line2Proportion = 0.0;
				return true;
			}

			return false;
		}

		if (line1IsPoint) {
			// line 2 must be a line...
			if (dx2 == 0 && line1StartX != line2StartX)
				return false;

			if (dy2 == 0 && line1StartY != line2StartY)
				return false;

			auto line2ProportionX = (line1StartX - line2StartX) / (line2EndX - line2StartX);
			auto line2ProportionY = (line1StartY - line2StartY) / (line2EndY - line2StartY);

			if (dx2 == 0) {
				line2Proportion = line2ProportionY;
			}
			else if (dy2 == 0) {
				line2Proportion = line2ProportionX;
			}
			else {
				if (line2ProportionX != line2ProportionY)
					return false;

				line2Proportion = line2ProportionX;
			}

			if (line2Proportion < 0 || line2Proportion>1)
				return false;

			line1Proportion = 0;
			return true;
		}

		if (line2IsPoint) {
			// Line 1 is a line though...
			return DoLinesIntersect(line2StartX,
				line2StartY,
				line2EndX,
				line2EndY,
				line1StartX,
				line1StartY,
				line1EndX,
				line1EndY,
				line2Proportion,
				line1Proportion);
		}

		// At this stage, we have 2 general lines and need to see if they intersect with each other...
		//
		// There are 3 possibilities:
		// 1. The lines are parallel to each other
		// 2. Line 1 is a vertical line (has to be separated out to enable the equations to be solved)
		// 3. they're general lines and there's a general solution

		auto dx1 = line1EndX - line1StartX;
		auto dy1 = line1EndY - line1StartY;

		auto a1 = line1StartX;
		auto b1 = line1StartY;
		auto a2 = line2StartX;
		auto b2 = line2StartY;

		bool line1IsVertical = dx1 == 0;
		if (line1IsVertical) {

			if (dx2 == 0) {
				// We have the even more special case that both lines are vertical hence this is similar to the parallel case
				if (a1 != a2)
					return false;

				// There are 4 options if we're in the same linear space:
				//  1. No overlap
				//  2. Initial overlap
				//  3. line 2 starts in line 1
				//  4. line 2 ends in line 1
				//
				// Note that #3 and #4 are both possible, at which point the lowest n1 should be selected				
				auto n2Initial = (b1 - b2) / dy2;
				if (n2Initial >= 0 && n2Initial <= 1) {
					line1Proportion = 0;
					line2Proportion = n2Initial;
					return true;
				}

				auto n1Line2Start = (b2 - b1) / dy1;
				auto n1Line2End = (line2EndY - b1) / dy1;

				bool line2StartIntersects = n1Line2Start >= 0 && n1Line2Start <= 1;
				bool line2EndIntersects = n1Line2End >= 0 && n1Line2End <= 1;

				if (line2StartIntersects && line2EndIntersects) {
					line2StartIntersects = n1Line2Start <= n1Line2End;
					line2EndIntersects = !line2StartIntersects;
				}

				if (line2StartIntersects) {
					line1Proportion = n1Line2Start;
					line2Proportion = 0;
					return true;
				}

				if (line2EndIntersects) {
					line1Proportion = n1Line2End;
					line2Proportion = 1;
					return true;
				}

				return false;
			}

			// Check to see where we hit line 2
			auto n2 = (a1 - a2) / dx2;
			if (n2 < 0 || n2 > 1)
				return false;

			// Check to see whether this would give a reasonable value for line 1
			auto n1 = (b2 - (n2*dy2) - b1) / dy1;
			if (n1 < 0 || n1 > 1)
				return false;

			line1Proportion = n1;
			line2Proportion = n2;
			return true;
		}

		bool linesAreParallel = (dy2 - (dx2*dy1 / dx1)) == 0;
		if (linesAreParallel) {

			auto n2InitialX = (a1 - a2) / dx2;
			auto n2InitialY = (b1 - b2) / dy2;

			if (dx2 != 0 &&
				dy2 != 0 &&
				n2InitialX != n2InitialY)
				return false;

			auto n2Initial = dx2 == 0 ? n2InitialY : n2InitialX;
			if (n2Initial >= 0 && n2Initial <= 1) {
				line1Proportion = 0;
				line2Proportion = n2Initial;
				return true;
			}

			// Now, it's time to do the check for the line2Start and line2End and calculate accordingly
			T n1Line2Start, n1Line2End;
			{
				auto n1Line2StartX = (a2 - a1) / dx1;
				auto n1Line2StartY = (b2 - b1) / dy1;
				n1Line2Start = dx1 == 0 ? n1Line2StartY : n1Line2StartX;
			}
			{
				auto n1Line2EndX = (line2EndX - a1) / dx1;
				auto n1Line2EndY = (line2EndY - b1) / dy1;
				n1Line2End = dx1 == 0 ? n1Line2EndY : n1Line2EndX;
			}

			bool line2StartIntersects = n1Line2Start >= 0 && n1Line2Start <= 1;
			bool line2EndIntersects = n1Line2End >= 0 && n1Line2End <= 1;

			if (line2StartIntersects && line2EndIntersects) {
				line2StartIntersects = n1Line2Start <= n1Line2End;
				line2EndIntersects = !line2StartIntersects;
			}

			if (line2StartIntersects) {
				line1Proportion = n1Line2Start;
				line2Proportion = 0;
				return true;
			}

			if (line2EndIntersects) {
				line1Proportion = n1Line2End;
				line2Proportion = 1;
				return true;
			}

			return false;
		}

		// General solution time
		{
			// Calculate n2
			line2Proportion = (b1 + (a2 * dy1 / dx1) - (a1*dy1 / dx1) - b2) / (dy2 - (dx2*dy1 / dx1));
			if (line2Proportion < 0 || line2Proportion > 1)
				return false;

			// We hit within a reasonable region of line 2, now let's check for line 1
			line1Proportion = (a2 + (line2Proportion*dx2) - a1) / dx1;
			if (line1Proportion < 0 || line1Proportion>1)
				return false;

			return true;
		}
	}

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!