ProblemBaby 122 Report post Posted November 16, 2003 Hi I wonder if it exist an easy way to check if a line and a rectangle collide and get the collisionpoint(s). Or do I have to make lines of the rectangle? (I hope not ) Thanks in forward /pb 0 Share this post Link to post Share on other sites

Leyder Dylan 122 Report post Posted November 16, 2003 http://www.gametutorials.com/ ========================Leyder Dylan (dylan.leyder@slug-production.be.tf http://users.skynet.be/fa550206/Slug-Production/Index.htm/ 0 Share this post Link to post Share on other sites

Zeblar Nagrim 150 Report post Posted November 16, 2003 Are the lines straight? 0 Share this post Link to post Share on other sites

johnnyBravo 100 Report post Posted November 16, 2003 i cant remember the forumale, but you can work out if two lines intersect, so basically u check all 5 lines.you get the equation of the line, and do something with it or so, use google or sometingits fairly simple, and probably the clearest way,and it wont matter if the lines are straight or not editoh and to work out the collision point would beeg3y=2x+5 ...(1)y=3x-3 ...(2)then5= 3y - 2x ...(3)3 =y-3x ...(4)then ...(4) * 312 = 3y - 9x ...(5)then(3)-(5)5= 3y - 2x ...(3)12 = 3y - 9x ...(5)-7=5xx=-7/5SO now u have found the x posthensub x=-7/5 into (2)y= 3*(-7/5)-3so x=-7/5y= 3*(-7/5)-3im 2 lazy to work out the numbers, but its pretty simple, [edited by - johnnyBravo on November 16, 2003 9:21:58 AM] 0 Share this post Link to post Share on other sites

Guest Anonymous Poster Report post Posted November 16, 2003 quote:Original post by Leyder Dylan http://www.gametutorials.com/ ========================Leyder Dylan (dylan.leyder@slug-production.be.tf http://users.skynet.be/fa550206/Slug-Production/Index.htm/ WOW, you have been around these forums for three years but you still don''t know how to use hyperlinks! Or maybe you don''t want to use them?! 0 Share this post Link to post Share on other sites

Ilici 862 Report post Posted November 16, 2003 if p1 and p2 give you the line: vNormal.x = -(p1 - p2).y;vNormal.y = (p1 - p2).x;float d;float center;for (i = 0; i < numVertices; i++) objectCenter += vertices[i];objectCenter /= numVertices;center = DotProd(p1 - objectCenter, vNormal);for (i = 0; i < numVertices; i++){ d = DotProd(p1 - vertices[i], vNormal); if (d * center < 0) BANG Collision! } [edited by - Ilici on November 16, 2003 9:27:00 AM] 0 Share this post Link to post Share on other sites

JasonA 152 Report post Posted November 16, 2003 Excellent. This is exactly what I was going to ask!Ilici: I tried your method, but, unless I am doing something wrong, it seems HIGHLY inaccurate. I created a fast and short C# demo (1.0 Framework). It's pretty much the code you posted but instead of testing between a line and a polygon, I modified the code to test between a line and a rectangle. I would appreciate if you or anyone else could take a look and verify it.C# testgametutorials.com doesn't have very much on it and nothing as far as this is concerned. Or at least I couldn't find anything.johnnyBravo: I'll try your method next. It seems the most promising if Ilici's method doesn't work that well. [edited by - JasonA on November 16, 2003 7:04:14 PM] 0 Share this post Link to post Share on other sites

Ilici 862 Report post Posted November 18, 2003 quote:Original post by JasonA Excellent. This is exactly what I was going to ask!Ilici: I tried your method, but, unless I am doing something wrong, it seems HIGHLY inaccurate. I created a fast and short C# demo (1.0 Framework). It''s pretty much the code you posted but instead of testing between a line and a polygon, I modified the code to test between a line and a rectangle. I would appreciate if you or anyone else could take a look and verify it.C# testwell, i''ve used it and it was very good. basiclly it tests if each of the vertices are on the same side of the line. the dot product is > 0 if they 2 points are on the same side and < 0 if the points are on different sides. 0 Share this post Link to post Share on other sites

DEbig3 122 Report post Posted November 18, 2003 thats fine if your testing for collision between a line and a plane, but not a rectangle.. 0 Share this post Link to post Share on other sites

Trienco 2555 Report post Posted November 18, 2003 its a nice first step, but you need the point of intersection to check if this point is even part of the rectangle side.your life will be a lot easier if the rectangles are axis aligned, maybe even so much easier that i would think about transforming line and rectangle to make it axis aligned.after that for the left side:if (side.y-p0.y)*(side.y-p1.y) is positive both points (start and end point of your line) are on the same side of the side (the same as above with the dot product, just simpler). in that case, go to the next side.if its negative or 0 you line equation looks like this:p0 + t*(p1-p0). you know it will intersect, so:p0.y + t*(p1.y-p0.y) = side.ysolving this shouldnt be hard and you get a t. short:t = (side.y - p0.y) / (p1.y - p0.y)if this t is smaller than 0 or larger than 1 they would intersect, but not in the interval between p0 and p1 (though here they will, we already did a quick and dirty test to figure that out). but the equation for our simplified 2d case is easy enough so forget about the quick and dirty test ,-)next, plug this t into the equation to get x at the intersection.x = p0.x + t * (p1.x-p0.x)this x has to be between the two points of the rectangle side:if xside.maxx forget it and go to the next side.also, you might get up to 4 intersections but the one with the smallest t will happen first.doing the same without the rectangle being axis aligned isnt much different except you would have line equations on both sides and solving this will be a little more work.p0 + t*(p1-p0) = side0 + s*(side1-side0)basically twice, for x and y coord. solve one for s and then plug the whole ugly thing into the other instead of s, then solve for t. chances are that a lot of sites will already present you with the formula ,-)in the end both, s and t will have to be between 0 and 1 for the segments to intersect, if you need the point of intersection just plug t or s into its equation. [edited by - Trienco on November 18, 2003 12:52:30 PM] 0 Share this post Link to post Share on other sites

Leyder Dylan 122 Report post Posted November 18, 2003 lol 0 Share this post Link to post Share on other sites

oliii 2196 Report post Posted November 18, 2003 separation axis, or rectangle clipping, the choice is yours. The separation axis is faster, but does not tell you anything about how the line/rect collided. The clipping algorithm is slower, but returns the part of the segment inside the cube.class Box{ Vector2 Dir[2]; //the orientation of the box (for AABBox, Dir[0] = (1, 0), Dir[1] = (0, 1) float HalfSize[2]; // the extents of the box along Dir[0] and Dir[1]};class Segment{ Vector2 P1, P2;};separation axis--------------- void Segment::GetSpan(const Vector2& Axis, float& min, float& max) const{ float p1 = this->P1 * Axis; float p2 = this->P2 * Axis; if (p1 < p2) { min = p1; max = p2; } else { min = p2; max = p1; }}void Box::GetSpan(const Vector2& Axis, float& min, float& max) const{ float c = Centre * Axis; float r = fabs(Axis * Dir[0]) * HalfSize[0] + fabs(Axis * Dir[1]) * HalfSize[1]; min = c - r; max = c + r;}bool Box::AxisIntersect(const Vector2& Axis, const Segment& S) const{ float mins, maxs; float minb, maxb; this->GetSpan(Axis, minb, maxb); S.GetSpan(Axis, mins, maxs); if (mins > maxb || maxs < minb) return false; return true;}bool Box::Intersect(const Segment& S) const{ Vector2 Dir = S.P2 - S.P1; if (!AxisIntersect(Dir, S}) return false; if (!AxisIntersect(Vector2(-Dir.y, Dir.x), S}) return false; if (!AxisIntersect(Dir[0], S}) return false; if (!AxisIntersect(Dir[1], S}) return false; return true;}clipping-------- static bool AxisClip(float min, float max, float p1, float p2, float &tmin, float& tmin){ float d = p2 - p1; bool sign = (d > 0.0f); if (!sign) { float temp = p1; p1 = p2; p2 = temp; d = -d; } if (p1 > max || p2 < min) return false; tmin = 0.0f; tmax = 1.0f; if (d < 0.0000001f) return true; if (p1 < min) tmin = (min - p1) / (d); if (p2 > max) tmax = (max - p1) / (d); if (!sign) { float temp = p1; p1 = 1.0f - p2; p2 = 1.0f - temp; } return true;}bool Segment::Clip(const AABBox& B, Segment& ClippedSeg) const{ float minx, maxx; float miny, maxy; if (!AxisClip(B.MinX, B.MaxX, P1.x, P2.x, minx, maxx)) return false; if (!AxisClip(B.MinY, B.MaxY, P1.y, P2.y, miny, maxy)) return false; if (minx > maxy || maxx < miny) return false; float tmin, tmax; tmin = minx; tmax = maxx; if(miny > minx) tmin = miny; if(maxy < maxx) tmax = maxy; Vector2 D = P2 - P1; ClippedSeg.P1 = P1 + tmin * D; ClippedSeg.P2 = P1 + tmax * D; return true; }I''ll explain everything tomorrow... bedtime and the land of nod 0 Share this post Link to post Share on other sites

oliii 2196 Report post Posted November 19, 2003 the line clipping algo is basicaly what trienco said, except I do two parallel edges at a time. Why you may ask? here is why // intersecting//------------- xmin xmax P1 | | * | | \ | | ymax --.-+-----+----- ty0\| | .tx0 | ymin ----+.----+----- | \ty1| | \ | | \ | | \| | .tx1 | |*P2 // here the spans [tx0, tx1 and ty0, ty1] overlap, so the ray // crosses the rectangle// furthermore, the ray is clipped to [tx0, ty1] // non-intersecting//----------------- xmin xmax | | *P1 | | \ ty0 | | ymax --.-----+-----+----- \ | | \ ty1 | ymin ------.--+-----+----- \ | | \| | .tx0 | |\ | | \ | | \ | | \ | | \| | . tx1 | |\ | | *P2 // here the spans [tx0, tx1] and [ty0, ty1] do not overlap (ty1 < tx0). So the segment does not clipp the rectangle.it''s a typical way to intersect a ray with a box/rectangle. It''s quite fast. For oriented boxes, as trienco said, you can rotate the segment with the opposite angle of the rectangle (or the inverse of the orientation matrix of the rectangle), clip the segment with the Axis aligned box, and re-rotate the clipped segment with the rectangle''s angle. Or you can do the test with proper slopped segments, which isn''t hard. there you go anyway... static bool AxisClip(float min, float max, float p1, float p2, float &tmin, float& tmin){ float d = p2 - p1; bool sign = (d > 0.0f); if (!sign) { float temp = p1; p1 = p2; p2 = temp; d = -d; } if (p1 > max || p2 < min) return false; tmin = 0.0f; tmax = 1.0f; if (d < 0.0000001f) return true; if (p1 < min) tmin = (min - p1) / (d); if (p2 > max) tmax = (max - p1) / (d); if (!sign) { float temp = p1; p1 = 1.0f - p2; p2 = 1.0f - temp; } return true;}bool Segment::BoxAxisClip(const Vector2& C, const Vector2& D, float r, float &tmin, float& tmin) const{ float c = C * D; float p1 = P1 * D; float p2 = P2 * D; return AxisClip(c-r, c+r, p1, p2, tmin, tmax);}bool Segment::Clip(const AABBox& B, Segment& ClippedSeg) const{ float minx, maxx; float miny, maxy; if (!AxisClip(B.MinX, B.MaxX, P1.x, P2.x, minx, maxx)) return false; if (!AxisClip(B.MinY, B.MaxY, P1.y, P2.y, miny, maxy)) return false; if (minx > maxy || maxx < miny) return false; float tmin, tmax; tmin = minx; tmax = maxx; if(miny > minx) tmin = miny; if(maxy < maxx) tmax = maxy; Vector2 D = P2 - P1; ClippedSeg.P1 = P1 + tmin * D; ClippedSeg.P2 = P1 + tmax * D; return true; }bool Segment::Clip(const Box& B, Segment& ClippedSeg) const{ float minx, maxx; float miny, maxy; if (!BoxAxisClip(Box.Centre, Box.Dir[0], Box.HalfSize[0], minx, maxx)) return false; if (!BoxAxisClip(Box.Centre, Box.Dir[1], Box.HalfSize[1], miny, maxy)) return false; if (minx > maxy || maxx < miny) return false; float tmin, tmax; tmin = minx; tmax = maxx; if(miny > minx) tmin = miny; if(maxy < maxx) tmax = maxy; Vector2 D = P2 - P1; ClippedSeg.P1 = P1 + tmin * D; ClippedSeg.P2 = P1 + tmax * D; return true; } 0 Share this post Link to post Share on other sites