   Nice quick collision detection
  So in my game I will have triangles, rectangles, lines, and points as shapes that I will try to detect collisions between.  This is what it'll all boil down to.  It will be in 2D not 3D.I saw articles on different techniques including the separating axis theorem.  I think it might be overkill to use separating axis theorem since I'm limiting it to triangles as the most complex shape possible.  The rectangles are all axis aligned and usually used as bounding boxes for more complex shapes.I'm trying to find algorithms for nice quick collision detection between all of these objects.  Complex math is not a problem.So at the moment I have a function that detects intersections between two lines, but can't figure out a good algorithm for seeing if a point is on a line that works in all cases.  Can't use slope intercept form since finding the slope can get very imprecise as the line gets closer and closer to vertical, eventually becoming 0.Then I want to detect collisions of triangle and triangle, and rectangle and triangle.Separating axis theorem sounds like overkill for such simple shapes.  At the moment I'm thinking of just checking for intersections between all sides of triangle or square, which means checking collisions between each pair of sides.  I've done a lot of googling and can't find the best answers, so I was hoping to get some tips here.  The best solutions, I think, are ones that just do a clever little hack that's nice and fast.  This is why I'm limiting the complexity of my shapes, because I believe that for the simpler shapes it's possible to find a special case that you can't apply to a polygon with like 20 sides that works really fast when checking collision between two triangles for example.   
  y = mx + b;if I have the line y = 2x + 1and I want to check if the point (1,3) is on that line I just have to substitute:if( 2(1)+ 1 == 3){   point is on line.}   ;  Yeah but the problem with slope intercept form, as I said above, is when a line gets close to being vertical.Also division gets more unprecise with the floating point numbers because as a line gets close to being vertical the division is by a smaller number.   ;  if the slope is 0;y = 0x + 3   (so line is at y = 3 straight left to right)and the point is (1,4) you get 4 = 0+3 which is not on the line,with (10000, 3) you get 3 = 10000*0 + 3, which is true so therefore on the line, it does hold true.There is no division there, its plug in x into slope intercept form, if you get the y value of your point, it is on the line.There will have to be an epsilon that you check because floating point inaccuracies will cause problems eventually. Otherwise this still holds up when slope is 0.[Edited by - JonConley on November 17, 2010 2:26:08 PM];  AFAIK, the fastest intersection tests are special cases of the SAT.  Granted, some of these special cases can be quite simple indeed; SAT for AABBs is just the same "within-bounds" checks you'd write naively....Also, ditch the "slope" stuff for your lines.  Line-line intersection should work like this:  Solve the matrix equation[n1, n2]^T p = [b1, b2]^Twhere n1,n2 are the lines' normals, and b1,b2 are their squared distances from the origin.  The inverse of a 2x2 matrix is easy to write down using Cramer's rule.  You get,[x] 1    [n2y  -n1y] [b1][ ] = ----------------- [    ] [  ][y]   n1x n2y - n1y n2x [-n2x  n1x] [b2]The case when the determinant (that's the denominator above) equals zero corresponds to parallel lines.  In fact it has the geometric interpretation of being the sine of the angle between them.If you really want to be clever, you can also represent the point in homogeneous coordinates as [ [n2y  -n1y] [b1]  ] [ [-n2x  n1x] [b2]  ] [ n1x n2y - n1y n2x ]in which case even "points at infinity" are defined.;Quote:Original post by JonConleyif the slope is 0;y = 0x + 3   (so line is at y = 3 straight up and down)and the point is (1,4) you get 4 = 0+3 which is not on the line,with (10000, 3) you get 3 = 10000*0 + 3, which is true so therefore on the line, it does hold true.There is no division there, its plug in x into slope intercept form, if you get the y value of your point, it is on the line.There will have to be an epsilon that you check because floating point inaccuracies will cause problems eventually. Otherwise this still holds up when slope is 0.You do not want to use the slope-intercept form for this (as has been noted several times in the thread at this point).   ;Quote:Original post by illSeparating axis theorem sounds like overkill for such simple shapes.  At the moment I'm thinking of just checking for intersections between all sides of triangle or square, which means checking collisions between each pair of sides.  I've done a lot of googling and can't find the best answers, so I was hoping to get some tips here.  The best solutions, I think, are ones that just do a clever little hack that's nice and fast.  This is why I'm limiting the complexity of my shapes, because I believe that for the simpler shapes it's possible to find a special case that you can't apply to a polygon with like 20 sides that works really fast when checking collision between two triangles for example.I think you've got it a little backwards. As noted previously, the SAT is (arguably) the optimal solution for the shapes you mentioned; it's actually the per-feature tests you mentioned that would likely be excessive for this, not the SAT.   ;Quote:Original post by jykQuote:Original post by JonConleyif the slope is 0;y = 0x + 3   (so line is at y = 3 straight up and down)and the point is (1,4) you get 4 = 0+3 which is not on the line,with (10000, 3) you get 3 = 10000*0 + 3, which is true so therefore on the line, it does hold true.There is no division there, its plug in x into slope intercept form, if you get the y value of your point, it is on the line.There will have to be an epsilon that you check because floating point inaccuracies will cause problems eventually. Otherwise this still holds up when slope is 0.You do not want to use the slope-intercept form for this (as has been noted several times in the thread at this point).For point line collision why not? I understand that you'd be storing the line in different ways for this method (since nothing else uses it), but to see if a point is on the line wouldn't you just plug in 1 value (since y is solved for already) plug in x coordinate, if you get the y coordinate that point is on the line.I guess it'd be because at no slope (vertical line), you can't use it?   ;  I realized that I will in fact have to use Separating axis theorem for triangle to triangle and triangle to AABB collision because when I check for line-line intersections between all sides I still have to check if the verteces of each side are in any of the shapes to account for when a shape is completely inside another shape.Box-box collision is super simple and doesn't need to use SAT.  In fact I do bounding box checks for each shape before I even do SAT.Box-point collision is just as simple.There are probably special cases for Triangle-Point checking and Line-point and Triangle-Line and Rectangle-Line or should I just use SAT for everything?I have code for line-line collision I found, it also returns the point of collision.  Not sure exactly how it works but here is the source I took and modified to work with my classes.  What I don't get is why it uses cross product.  I haven't even tested it yet.  I found the original here:http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/1968345#1968345Also I made myself a TODO in case the cross product ends up being 0.  Not sure what should happen if it is 0 since I'm not sure why it uses cross product.  Maybe it means the lines are parallel in which case I should just return true?struct Vector2{double m_x;double m_y;//omitted function declarations...}struct Line2{Vector2 m_a;Vector2 m_b;//omitted function declarations...}bool Line2::intersect(const Line2 &other, Vector2 *intersectionPoint) const{//TODO: make sure no div by 0 happensVector2 vec1 = m_a - m_b;Vector2 vec2 = other.m_a - other.m_b;double cross = vec1.crossProduct(vec2);double s = (-vec1.m_y * (m_a.m_x - other.m_a.m_x) + vec1.m_x * (m_a.m_y - other.m_a.m_y)) / cross;double t = (vec2.m_x * (m_a.m_y - other.m_a.m_y) - vec2.m_y * (m_a.m_x - other.m_a.m_x)) / cross;if (s >= 0 && s <= 1 && t >= 0 && t <= 1){//collision detectedif(intersectionPoint != NULL){intersectionPoint -> m_x = m_a.m_x + (t * vec1.m_x);intersectionPoint -> m_y = m_a.m_y + (t * vec1.m_y);}return true;}return false;};Quote:Original post by JonConleyFor point line collision why not? I understand that you'd be storing the line in different ways for this method (since nothing else uses it), but to see if a point is on the line wouldn't you just plug in 1 value (since y is solved for already) plug in x coordinate, if you get the y coordinate that point is on the line.I guess it'd be because at no slope (vertical line), you can't use it?Short answer: in the given context, there's no reason (that I can think of, at least) to use a line representation that is not invariant with respect to orientation when there are representations that *are* invariant with respect to orientation.Also, consider this. The OP was asking about line intersection in the context of testing for intersection between shapes (polygons, etc.) in 2-d. In this context, the lines (line segments, actually) will be (for example) edges of polygons. Said edges may be arbitrarily oriented, and may very well be vertical or nearly so, and the slope-intercept form will break down in these cases.In any case, computing the intersection point (if any) between two line segments is essentially a solved problem, and none of the standard solutions (at least in the context of game development) uses slope-intercept form. In order to make a case for using slope-intercept form in this context, I think you'd have to be able to show how a method that used slope-intercept form would be superior to the aforementioned standard solutions.In other words, what advantage would using slope-intercept form offer?Quote:Original post by illI realized that I will in fact have to use Separating axis theorem for triangle to triangle and triangle to AABB collision because when I check for line-line intersections between all sides I still have to check if the verteces of each side are in any of the shapes to account for when a shape is completely inside another shape.You shouldn't have to perform per-feature (e.g. segment-segment) tests at all when using the SAT, so I think maybe what you have in mind still isn't really the SAT.Quote:Box-box collision is super simple and doesn't need to use SAT.The 'super simple' test that you're almost certainly thinking of is, in fact, the SAT.   