SFML community forums
Help => General => Topic started by: reDo on May 31, 2011, 08:21:50 pm
-
I am trying to make my own collision detection between line and ball but it doesnt working correctly. Green circle should be shown only when it is collision. Please can someone chcek my code? :roll:
My collision detection plan:
(http://i51.tinypic.com/2427595.png)
bug that I mentioned
(http://i56.tinypic.com/28uwix.png)
#include <SFML/Window.hpp>
#include <SFML/System.hpp>
#include <SFML/Graphics.hpp>
#include <cmath>
#include <iostream>
using std::cout;
using std::endl;
struct point
{
float x;
float y;
float distance;
};
bool Check(point & Point, float CircX, float CircY)
{
float CircAngle = atan2(CircY,CircX);
cout<<"CircAngle = "<<CircAngle<<" radians, "<<CircAngle*180/3.14<<" degrees"<<endl;
float PointAngle = atan2(Point.y,Point.x);
cout<<"PointAngle = "<<PointAngle<<" radians, "<<PointAngle*180/3.14<<" degrees"<<endl;
float angle = CircAngle - PointAngle;
cout<<"angle = "<<angle<<" radians, "<<angle *180/3.14<<" degrees"<<endl;
if(angle < 0)
{
angle *= -1;
cout<<"changed by multiplication"<<endl;
cout<<"angle = "<<angle<<" radians, "<<angle *180/3.14<<" degrees"<<endl;
}
float distance_circle_point = sqrt( pow(Point.x - CircX,2) + pow(Point.y - CircY,2) );
cout<<"distance_circle_point = "<<distance_circle_point<<endl;
float distance = sin(angle) * distance_circle_point;
cout<<"distance = "<<distance<<endl;
cout<<endl<<endl;
if(distance <= 20)
return true;
return false;
}
int main()
{
sf::RenderWindow App(sf::VideoMode(800, 600, 32), "animation");
float x=400, y=300;
point p1 = {100,100}, p2 = {300,300};
while (App.IsOpened())
{
sf::Event Event;
while (App.GetEvent(Event))
{
// Close window : exit
if (Event.Type == sf::Event::Closed)
App.Close();
// Escape key : exit
if ((Event.Type == sf::Event::KeyPressed) && (Event.Key.Code == sf::Key::Escape))
App.Close();
}
if (App.GetInput().IsKeyDown(sf::Key::Up))
y-=2;
if (App.GetInput().IsKeyDown(sf::Key::Down))
y+=2;
if (App.GetInput().IsKeyDown(sf::Key::Right))
x+=2;
if (App.GetInput().IsKeyDown(sf::Key::Left))
x-=2;
App.Clear();
if(Check(p1,x,y))
App.Draw(sf::Shape::Circle(20, 20, 20, sf::Color(0,255,0)));
App.Draw(sf::Shape::Line(p1.x, p1.y, p2.x, p2.y, 1, sf::Color(0,255,128)));
App.Draw(sf::Shape::Circle(x, y, 20, sf::Color(255,128,0)));
App.Display();
sf::Sleep(0.025f);
}
return EXIT_SUCCESS;
}
-
The most efficient way to do it would probably be to use a specialized Separating Axis Theorem implementation.
If it's an infinite line, then translate the circle parallel to the line until either the x or y coordinate is 0, then check if the distance of the circle's center from the origin is less than or equal to the radius of the circle. If it is, there's a collision. Otherwise, no collision.
-
I don't see where you're using p2 in your Check function. You only have one of the line points and the circle point. There's no way the function could possibly work with just that.
EDIT: you also don't have the diameter/radius of the circle...
-
I cant understand why it is not working because math is good I think
Please tell me where is mistake in code please :roll:
Better explained plan, I know the line is not infinite on plan but in code it is
(http://i52.tinypic.com/bhd0k3.png)
little modificated source
#include <SFML/Window.hpp>
#include <SFML/System.hpp>
#include <SFML/Graphics.hpp>
#include <cmath>
#include <iostream>
using std::cout;
using std::endl;
struct point
{
float x;
float y;
float distance;
};
bool Check(point & Point, float CircX, float CircY, float radius)
{
float CircAngle = atan2(CircY,CircX);
cout<<"CircAngle = "<<CircAngle<<" radians, "<<CircAngle*180/3.14<<" degrees"<<endl;
float PointAngle = atan2(Point.y,Point.x);
cout<<"PointAngle = "<<PointAngle<<" radians, "<<PointAngle*180/3.14<<" degrees"<<endl;
float angle = CircAngle - PointAngle;
cout<<"angle = "<<angle<<" radians, "<<angle *180/3.14<<" degrees"<<endl;
if(angle < 0)
{
angle *= -1;
cout<<"changed by multiplication"<<endl;
cout<<"angle = "<<angle<<" radians, "<<angle *180/3.14<<" degrees"<<endl;
}
float distance_circle_point = sqrt( pow(Point.x - CircX,2) + pow(Point.y - CircY,2) );
cout<<"distance_circle_point = "<<distance_circle_point<<endl;
float distance = sin(angle) * distance_circle_point;
cout<<"distance = "<<distance<<endl;
cout<<endl<<endl;
if(distance <= radius)
return true;
return false;
}
int main()
{
sf::RenderWindow App(sf::VideoMode(800, 600, 32), "animation");
float x=400, y=300, radius = 30;
point p1 = {0,0}, p2 = {500,600};
while (App.IsOpened())
{
sf::Event Event;
while (App.GetEvent(Event))
{
// Close window : exit
if (Event.Type == sf::Event::Closed)
App.Close();
// Escape key : exit
if ((Event.Type == sf::Event::KeyPressed) && (Event.Key.Code == sf::Key::Escape))
App.Close();
}
if (App.GetInput().IsKeyDown(sf::Key::Up))
y-=2;
if (App.GetInput().IsKeyDown(sf::Key::Down))
y+=2;
if (App.GetInput().IsKeyDown(sf::Key::Right))
x+=2;
if (App.GetInput().IsKeyDown(sf::Key::Left))
x-=2;
App.Clear();
if(Check(p1,x,y,radius) || Check(p2,x,y,radius))
App.Draw(sf::Shape::Circle(20, 20, 20, sf::Color(0,255,0)));
App.Draw(sf::Shape::Line(p1.x, p1.y, p2.x, p2.y, 2, sf::Color(0,255,255)));
App.Draw(sf::Shape::Circle(x, y, radius, sf::Color(255,128,0)));
App.Display();
sf::Sleep(0.025f);
}
return EXIT_SUCCESS;
}
-
1. get first point angle (one is enough because the line is infinite and the second point has the same angle)
This isn't true. A line is defined by two points. If you only have 1 point, the line could be moving in any direction and it'd be impossible to determine.
You need either a second point or an angle to specify the orientation of the line. Without this it's impossible to know what line you have.
Your function does not have this. It's trying to solve a problem that it doesn't have enough information to solve. How could you possibly be getting that "angle" in your diagram without knowing a second point on the line?
EDIT:
I would solve the problem with something like this:
(http://i55.tinypic.com/206gdxs.jpg)
EDIT 2:
Here's some (untested) code that should do the trick. Again note: untested.
// handy Point typedef
typedef sf::Vector2<double> Point;
// Perpendicular dot product
inline double PerpDot(const Point& a,const Point& b) { return (a.y*b.x) - (a.x*b.y); }
// Line vs. Line Segment Collision
bool LineVsSegmentCollision(const Point& lineA,const Point& lineB,const Point& segA,const Point& segB)
{
// the vector of the line
Point line( lineB - lineA );
// vectors from one point of the line to each line segment
Point A( segA - lineA );
Point B( segB - lineA );
// segment intersects with the line if each endpoint is on opposing sides of the line.
// which side the endpoint is on can be determined by examining the sign of the perpdot product
return (PerpDot(line,A) < 0) != (PerpDot(line,B) < 0);
}
// Line vs. Circle Collision
bool LineVsCircleCollision(const Point& lineA,const Point& lineB,const Point& circle,double radius)
{
//we need to get a line segment that is of length equal to the diameter of the circle
// centered on the circle's center point
// and perpendicular to the line
// Step 1) Get a unit vector of the line
Point unit( lineB - lineA );
double linelength = sqrt( (unit.x * unit.x) + (unit.y * unit.y) );
unit /= linelength;
// now make the unit vector perpendicular
// a perpendicular line is:
// x = y'
// y = -x'
double x = unit.x;
unit.x = unit.y;
unit.y = -x;
// now extend the unit vector by our radius
unit *= radius;
// the line segment is now 'circle' extending out in each direction by 'unit'
Point a = circle + unit;
Point b = circle - unit;
// now that we have the line segment, hand the job off to LineVsSegmentCollision
return LineVsSegmentCollision(lineA,lineB,a,b);
}
EDIT 3: fixed LineVsSegmentCollision
-
I dont know vector stuff like dot product and so on, so I have to learn it but I thought my solution will solve that problem . :(
-
I dont know vector stuff like dot product and so on, so I have to learn it
You should learn it. Especially if you want to do this kind of math. It really makes it much, much easier. Dot product and perpendicular dot product are really quite magical, and they're not that complicated.
but I think my solution will solve that problem
It should work fine if you get the information correct.
The thing is you're not referencing an origin point in your calculations. You're just using an arbitrary line point and the circle's center. Therefore your angles are probably wrong.
Look at what you're doing here:
bool Check(point & Point, float CircX, float CircY, float radius)
{
float CircAngle = atan2(CircY,CircX);
cout<<"CircAngle = "<<CircAngle<<" radians, "<<CircAngle*180/3.14<<" degrees"<<endl;
float PointAngle = atan2(Point.y,Point.x);
cout<<"PointAngle = "<<PointAngle<<" radians, "<<PointAngle*180/3.14<<" degrees"<<endl;
To get PointAngle you're just calling atan2 with the Point.y and Point.x. This won't work. atan2 gets the angle based on the origin (origin point = 0,0).
To illustrate that:
(http://i56.tinypic.com/2q8y43s.jpg)
If you want this to work, you need to give the lines you're projecting new origins. Basically you want to move the origin to a point on the line. You do this by subtracting the desired origin point from the target point, which gets you the line's vector. This is why you need two line points:
Point linevector = LineB - LineA; // LineA is our origin point
Point circlevector = Circle - LineA; // same
// now if we atan2, we'll get the proper angle
double circangle = atan2(circlevector.y,circlevector.x);
double lineangle = atan2(linevector.y,linevector.x);
-
Can't you use dot product to find the closest point on the line from the circle ?
-
Possibly. It's probably not as simple as just a single dot product, but I'm sure there's a way to figure it out. I'd have to think about it some more.
Also @ OP:
Note that everything I've been doing is based on the collision line being infinite. If the collision line is a finite line segment, then that problem is an entirley different beast and you shouldn't be wasting your time solving for an infinite line.
So which are you looking for?
-
Here is an interesting illustrated article (in AS) that may help.
http://blog.generalrelativity.org/actionscript-30/collision-detection-circleline-segment-circlecapsule/
-
oh duh... yeah just project onto the line.
That's much simpler. And faster... no trig functions needed and only 1 division!
Again untested:
// Dot product / Perpendicular dot product
inline double Dot(const Point& a,const Point& b) { return (a.x*b.x) + (a.y*b.y); }
inline double PerpDot(const Point& a,const Point& b) { return (a.y*b.x) - (a.x*b.y); }
bool LineVsCircleCollision(const Point& lineA,const Point& lineB,const Point& circle,double radius)
{
Point line(lineB - lineA); // the line vector
Point circ(circle - lineA); // the vector of the origin line point to the circle center
// project the circle vector onto the line vector
double proj = Dot(line,circ) / Dot(line,line);
{ // remove this block if the line extends infinitely
if(proj < 0) proj = 0;
else if(proj > 1) proj = 1;
}
// apply the projected position to our vector, and offset it by our origin
Point nearest = (line * proj) + lineA;
// 'nearest' is now the point on the line nearest the circle
// see if the distance between this point and the circle center is greater than the radius.
// if the radius is larger, the circle intersects
Point dist = circle - nearest; // the vector between the circle and the nearest point on the line
return Dot(dist,dist) <= (radius*radius);
}
EDIT: I wonder if the OP is even still interested?
-
I tried both ways from Disch, it works only when it has 45, 90, 135, ... angles :( , I just tried it and dont know how it works , but you can improve it if you want
#include <SFML/Window.hpp>
#include <SFML/System.hpp>
#include <SFML/Graphics.hpp>
#include <cmath>
#include <iostream>
using std::cout;
using std::endl;
struct Point
{
double x;
double y;
};
bool Check(Point & Point1, Point & Point2, Point & Circle, double radius)
{
Point linevector; // LineA is our origin point
linevector.x = Point2.x - Point1.x;
linevector.y = Point2.x - Point1.x;
Point circlevector; // same
circlevector.x = Circle.x - Point1.x;
circlevector.y = Circle.y - Point1.y;
// now if we atan2, we'll get the proper angle
double circangle = atan2(circlevector.y,circlevector.x);
double lineangle = atan2(linevector.y,linevector.x);
double angle = circangle - lineangle;
cout<<"angle = "<<angle<<" radians, "<<angle *180/3.14<<" degrees"<<endl;
if(angle < 0)
{
angle *= -1;
cout<<"changed by multiplication"<<endl;
cout<<"angle = "<<angle<<" radians, "<<angle *180/3.14<<" degrees"<<endl;
}
double distance_circle_point = sqrt( pow(Point1.x - Circle.x,2) + pow(Point1.y - Circle.y,2) );
cout<<"distance_circle_point = "<<distance_circle_point<<endl;
double distance = sin(angle) * distance_circle_point;
cout<<"distance = "<<distance<<endl;
cout<<endl<<endl;
if(distance <= radius)
return true;
return false;
}
// Dot product / Perpendicular dot product
inline double Dot(const Point& a,const Point& b) { return (a.x*b.x) + (a.y*b.y); }
inline double PerpDot(const Point& a,const Point& b) { return (a.y*b.x) - (a.x*b.y); }
bool LineVsCircleCollision(const Point& lineA,const Point& lineB,const Point& circle,double radius)
{
Point line; // the line vector
line.x = lineB.x - lineA.x;
line.y = lineB.x - lineA.x;
Point circ; // the vector of the origin line point to the circle center
circ.x = circle.x - lineA.x;
circ.y = circle.y - lineA.y;
// project the circle vector onto the line vector
double proj = Dot(line,circ) / Dot(line,line);
{ // remove this block if the line extends infinitely
if(proj < 0) proj = 0;
else if(proj > 1) proj = 1;
}
// apply the projected position to our vector, and offset it by our origin
Point nearest;
nearest.x = line.x * proj + lineA.x;
nearest.y = line.y * proj + lineA.y;
// 'nearest' is now the point on the line nearest the circle
// see if the distance between this point and the circle center is greater than the radius.
// if the radius is larger, the circle intersects
Point dist; // the vector between the circle and the nearest point on the line
dist.x = circle.x - nearest.x;
dist.y = circle.y - nearest.y;
return Dot(dist,dist) <= (radius*radius);
}
int main()
{
sf::RenderWindow App(sf::VideoMode(800, 600, 32), "animation");
double radius = 30;
Point p1 = {100,100}, p2 = {300,300}, circle = {400,300};
while (App.IsOpened())
{
sf::Event Event;
while (App.GetEvent(Event))
{
// Close window : exit
if (Event.Type == sf::Event::Closed)
App.Close();
// Escape key : exit
if ((Event.Type == sf::Event::KeyPressed) && (Event.Key.Code == sf::Key::Escape))
App.Close();
}
if (App.GetInput().IsKeyDown(sf::Key::Up))
circle.y-=2;
if (App.GetInput().IsKeyDown(sf::Key::Down))
circle.y+=2;
if (App.GetInput().IsKeyDown(sf::Key::Right))
circle.x+=2;
if (App.GetInput().IsKeyDown(sf::Key::Left))
circle.x-=2;
App.Clear();
if(LineVsCircleCollision(p1,p2,circle,radius))
App.Draw(sf::Shape::Circle(20, 20, 20, sf::Color(0,255,0)));
if(Check(p1,p2,circle,radius))
App.Draw(sf::Shape::Circle(60, 20, 20, sf::Color(255,0,0)));
App.Draw(sf::Shape::Line(p1.x, p1.y, p2.x, p2.y, 1, sf::Color(0,255,128)));
App.Draw(sf::Shape::Circle(circle.x, circle.y, radius, sf::Color(255,128,0)));
App.Display();
sf::Sleep(0.025f);
}
return EXIT_SUCCESS;
}
bug with Check function Point2 x = 300, Point 2 y = 300
http://imageshack.us/photo/my-images/849/error1z.jpg/
LineVsCircleCollision and Check functions OK Point2 x = 300, Point 2 y = 300
http://imageshack.us/photo/my-images/851/error2i.jpg/
both functions's bug Point2 x = 300, Point 2 y = 600
http://imageshack.us/photo/my-images/830/error3u.jpg/
-
I'll check it out when I get home. Can't really compile it at work.
Any reason why you're redefining your own Point structure instead of just using sf::Vector2 like I suggested?
typedef sf::Vector2<double> Point;
sf::Vector provides all the operator overloads so you didn't have to rewrite all of that.
EDIT:
I just got home and tried it.
My LineVsCircleCollision function as I posted it works fine. You must have converted something incorrectly when you "translated" it to use your Point struct. When you use sf::Vector's overloaded operators it works fine.
This code below works in that 300,600 case.
Didn't figure out what's wrong with your Check function yet. I'll keep looking.
#include <SFML/Window.hpp>
#include <SFML/System.hpp>
#include <SFML/Graphics.hpp>
#include <cmath>
#include <iostream>
#pragma comment(lib,"sfml-graphics-s-d.lib")
#pragma comment(lib,"sfml-system-s-d.lib")
#pragma comment(lib,"sfml-window-s-d.lib")
using std::cout;
using std::endl;
typedef sf::Vector2<double> Point;
bool Check(Point & Point1, Point & Point2, Point & Circle, double radius)
{
Point linevector; // LineA is our origin point
linevector.x = Point2.x - Point1.x;
linevector.y = Point2.x - Point1.x;
Point circlevector; // same
circlevector.x = Circle.x - Point1.x;
circlevector.y = Circle.y - Point1.y;
// now if we atan2, we'll get the proper angle
double circangle = atan2(circlevector.y,circlevector.x);
double lineangle = atan2(linevector.y,linevector.x);
double angle = circangle - lineangle;
cout<<"angle = "<<angle<<" radians, "<<angle *180/3.14<<" degrees"<<endl;
if(angle < 0)
{
angle *= -1;
cout<<"changed by multiplication"<<endl;
cout<<"angle = "<<angle<<" radians, "<<angle *180/3.14<<" degrees"<<endl;
}
double distance_circle_point = sqrt( pow(Point1.x - Circle.x,2) + pow(Point1.y - Circle.y,2) );
cout<<"distance_circle_point = "<<distance_circle_point<<endl;
double distance = sin(angle) * distance_circle_point;
cout<<"distance = "<<distance<<endl;
cout<<endl<<endl;
if(distance <= radius)
return true;
return false;
}
// Dot product / Perpendicular dot product
inline double Dot(const Point& a,const Point& b) { return (a.x*b.x) + (a.y*b.y); }
inline double PerpDot(const Point& a,const Point& b) { return (a.y*b.x) - (a.x*b.y); }
bool LineVsCircleCollision(const Point& lineA,const Point& lineB,const Point& circle,double radius)
{
Point line(lineB - lineA); // the line vector
Point circ(circle - lineA); // the vector of the origin line point to the circle center
// project the circle vector onto the line vector
double proj = Dot(line,circ) / Dot(line,line);
{ // remove this block if the line extends infinitely
if(proj < 0) proj = 0;
else if(proj > 1) proj = 1;
}
// apply the projected position to our vector, and offset it by our origin
Point nearest = (line * proj) + lineA;
// 'nearest' is now the point on the line nearest the circle
// see if the distance between this point and the circle center is greater than the radius.
// if the radius is larger, the circle intersects
Point dist = circle - nearest; // the vector between the circle and the nearest point on the line
return Dot(dist,dist) <= (radius*radius);
}
int main()
{
sf::RenderWindow App(sf::VideoMode(800, 600, 32), "animation");
double radius = 30;
Point p1(100,100), p2(300,600), circle(433,300);
while (App.IsOpened())
{
sf::Event Event;
while (App.GetEvent(Event))
{
// Close window : exit
if (Event.Type == sf::Event::Closed)
App.Close();
// Escape key : exit
if ((Event.Type == sf::Event::KeyPressed) && (Event.Key.Code == sf::Key::Escape))
App.Close();
}
if (App.GetInput().IsKeyDown(sf::Key::Up))
circle.y-=2;
if (App.GetInput().IsKeyDown(sf::Key::Down))
circle.y+=2;
if (App.GetInput().IsKeyDown(sf::Key::Right))
circle.x+=2;
if (App.GetInput().IsKeyDown(sf::Key::Left))
circle.x-=2;
App.Clear();
if(LineVsCircleCollision(p1,p2,circle,radius))
App.Draw(sf::Shape::Circle(20, 20, 20, sf::Color(0,255,0)));
if(Check(p1,p2,circle,radius))
App.Draw(sf::Shape::Circle(60, 20, 20, sf::Color(255,0,0)));
App.Draw(sf::Shape::Line(p1.x, p1.y, p2.x, p2.y, 1, sf::Color(0,255,128)));
App.Draw(sf::Shape::Circle(circle.x, circle.y, radius, sf::Color(255,128,0)));
App.Display();
sf::Sleep(0.025f);
}
return EXIT_SUCCESS;
}
EDIT AGAIN:
Found your conversion error:
bool LineVsCircleCollision(const Point& lineA,const Point& lineB,const Point& circle,double radius)
{
Point line; // the line vector
line.x = lineB.x - lineA.x;
line.y = lineB.x - lineA.x; // <- should be lineB.y - lineA.y
But of course it's easier if you just keep the sf::Vector2<double> bit.
?FINAL? EDIT:
You made the same mistake in your Check function:
bool Check(Point & Point1, Point & Point2, Point & Circle, double radius)
{
Point linevector; // LineA is our origin point
linevector.x = Point2.x - Point1.x;
linevector.y = Point2.x - Point1.x; // <-- should be .y, not .x
After making that change, Check() seems to work assuming the line extends infinitely in each direction.
PS:
- Using pow() to square stuff should be a sin. Instead of doing pow(x,2), just do (x*x) or write your own square function that does (x*x). Using pow is like driving a small nail with a sledgehammer.
- Note how my function takes no expensive trig calculations, works with line segments, and is much simpler. That's the magic of linear algebra. I'm happy to explain how it all works if you're interested. Just let me know.
-
I am really happy with this kind of help, thanks a milion for your patience and time spent with this. :D Yes I wanna to learn it, I am learning it from http://www.tonypa.pri.ee/vectors/start.html
and then I wanna learn from here
http://www.metanetsoftware.com/technique/tutorialA.html
If I found some problem I will write here or directly to you.
:wink:
-
Dot product is very simple. It's kind of magical in a way.
As you can see from my code:
Dot( a, b )
{
return (a.x * b.x) + (a.y * b.y);
}
Perpendicular dot product is the same idea, only you take a vector perpendicular to a (or b):
PerpDot( a, b )
{
return (a.y*b.x) - (a.x*b.y);
}
Now... what makes this significant is that:
Dot(a,b) == cos(theta) * length(a) * length(b)
and
PerpDot(a,b) == sin(theta) * length(a) * length(b)
(where theta is the angle between a,b)
This can be useful for any number of things. For example, if you want to find out if two lines are parallel, you can just do a perpdot on their vectors (if they're parallel, sin(theta) will be 0, therefore the perpdot will also be 0)
In my function I used Dot to do projection, which "projects" a point onto a vector.
Projection is easiest to visualize like you're looking at a TV or monitor. Here's a diagram to illustrate:
(http://i52.tinypic.com/23sejrd.png)
In my code I projected A onto B with the below:
double proj = Dot(A,B) / Dot(B,B);
But how does that work?
Well remember that Dot(A,B) = cos(theta) * len(A) * len(B)
So that means that the above can be simplified:
Dot(A,B) cos(theta) * len(A) * len(B) cos(theta) * len(A)
________ = ____________________________ = ___________________
Dot(B,B) cos(0) * len(B) * len(B) 1 * len(B)
len(A)
= cos(theta) * ______
len(B)
cos(theta) * len(A) is how far along the desired axis our vector extends. And dividing it by len(B) scales it down to be relative to the target vector (our TV screen).
This means that if the projected point is lying on our target vector, the above calculation would have given us a value between 0..1
The rest of my function should be pretty self explanitory. Let me know if you need any further clarification.
-
I have to learn basics at first and then I will give you know. :)
-
I thought those were the basics =x lol
I assumed you already knew what sin/cos/etc are since you used SOHCAHTOA in your approach to the problem.
oh well. ^^
-
yes I know sin, cos, tan, cotan but I dont know dot product and so on :D
-
That's why I explained them in that post. ;P
lol nevermind.
-
yes but I wanna learn from zero that I will understand everything, unit vector ...
-
Hi again, I learned vectors and now I am wondering how to use it to chcek collision between line and line :) :roll:
-
You caught me at work!
I'll reply when I get home (maybe ~6 hrs from now)
But yeah, line-line collision is easy and fast using these same concepts.
-
OK!
Say you have two lines AB (with endpoints A and B) and CD (with points C and D)
Any point on line AB can be represented in the following form:
P = (B - A) * k + A
Where 'P' is the point, and 'k' is a value between [0..1]. Basically k acts as a "scale" to find the point according to it's distance from A. So if P is exactly halfway between A and B, k would be 0.5
The same can be said of line CD. Any point can be represented in the following form:
Q = (D - C) * m + C
To shorten/simplify future equations, I'm going to use some shorthand and say vBA = (B-A) and vDC = (D-C)
Now, assuming AB and CD extend to infinity, that means P=Q at the intersection point.
Which further means that:
P = vBA * k + A
Q = vDC * m + C
P = Q
vBA * k + A = vDC * m + C
Now if we solve this equation for k and m, we have found the intersection point. Assuming you know standard algebra, you should be able to solve it yourself so I'll skip the steps. Basically you're left with this:
k = (vDC * m + vCA) / vBA
m = (vBA * k - vCA) / vDC
Now keep in mind that each of these equations are actually 2 equations in one, because the vectors all consist of both an x component and a y component. So, actually, we have 2 ways to find k:
k = (vDC.x * m + vCA.x) / vBA.x
and
k = (vDC.y * m + vCA.y) / vBA.y
Likewise, we have 2 ways to find m.
Using this, we can substitute 'm' in one of the 'k' equations to eliminate it as a variable:
k = (vDC.x * m + vCA.x) / vBA.x
m = (vBA.y * k - vCA.y) / vDC.y
so
k = (vDC.x * ( m ) + vCA.x) / vBA.x
k = (vDC.x * ((vBA.y * k - vCA.y) / vDC.y) + vCA.x) / vBA.x
Now we can solve for 'k' and have the result using only the given points A,B,C, and D. We can also do the same thing to get 'm'.
So after all that solving you finally get this:
k = (vDC.y*vCA.x - vDC.x*vCA.y) / (vDC.y*vBA.x - vDC.x*vBA.y)
m = (vBA.y*vCA.x - vBA.x*vCA.y) / (vDC.y*vBA.x - vDC.x*vBA.y)
But wait a moment.... don't those expressions look a little familiar?
inline double PerpDot(const Point& a,const Point& b) { return (a.y*b.x) - (a.x*b.y); }
That's right! It's good old PerpDot! That magical linear algebra function!
This means we can further simplify:
k = PerpDot(vDC,vCA) / PerpDot(vDC,vBA)
m = PerpDot(vBA,vCA) / PerpDot(vDC,vBA)
Note the bottom part for each is the same.
Knowing that we're working with finite lines -- this means k and m must both be within the range [0..1] or else there is no intersection.
Also note the divide by 0 situation. If PerpDot(vDC,vBA) is zero, there is no intersection. Remember that PerpDot gives you sin(theta) and if sin(theta) is zero, it means the lines are parallel, so they cannot intersect. Hence why the above equation wouldn't work in that case.
So all that roundabout math aside, we're left with a very, very simple function:
bool LineCollision( const Point& A, const Point& B, // line AB
const Point& C, const Point& D, // line CD
Point* out ) // filled with intersection point
{
Point vBA(B - A);
Point vDC(D - C);
double f = PerpDot(vDC,vBA);
if(!f) // lines are parallel
return false;
Point vCA(C - A);
double k = PerpDot(vDC,vCA) / f;
if(k < 0) return false;
if(k > 1) return false;
double m = PerpDot(vBA,vCA) / f;
if(m < 0) return false;
if(m > 1) return false;
if(out)
*out = (vDC * m) + C; // or (vBA * k) + A if you prefer -- same thing
return true;
}
-
Thanks I will learn it :wink:
-
I tried to make collision detection rotated rectangle vs rotated rectangle(I know that one is not rotated but this is just a test =) ) using separating axis theorem by this article http://www.gamedev.net/page/resources/_/reference/programming/game-programming/collision-detection/2d-rotated-rectangle-collision-r2604 , but it doesnt work sometimes. Can someone help me find that bug please, because I am beginner in vectors so I am glad it works most of the time :D ? Thanks a million for any help :roll:
Here is bug picture
(http://i55.tinypic.com/os74v4.jpg)#include <SFML/System.hpp>
#include <SFML/Graphics.hpp>
#include <SFML/Window.hpp>
#include <iostream>
#include <cmath>
using namespace std;
typedef sf::Vector2f VECTOR;
float RetDotProduct(const VECTOR & v1, const VECTOR & v2)
{
return (v1.x*v2.x + v1.y*v2.y);
}
void DrawRect(sf::RenderWindow & App, const VECTOR rect[], int r, int g, int b)
{
for(int i=0;i<4;i++)
App.Draw(sf::Shape::Line(rect[i].x,rect[i].y,
rect[i+(i==3? -3 : 1)].x,rect[i+(i==3? -3 : 1)].y,1,sf::Color(r,g,b)));
}
float FindMax(float projects[])
{
float max = projects[0];
for(int i=0;i<4;i++)
if(max < projects[i])
max = projects[i];
return max;
}
float FindMin(float projects[])
{
float min = projects[0];
for(int i=0;i<4;i++)
if(min > projects[i])
min = projects[i];
return min;
}
bool IsColOnAxis(const VECTOR axisA, const VECTOR axisB, const VECTOR rectA[], const VECTOR rectB[])
{
VECTOR axisAB = axisA - axisB;
float Aprojections[4];
float Bprojections[4];
//rect A
for(int i=0;i<4;i++)
{
Aprojections[i] = RetDotProduct(axisAB,rectA[i]-axisA) / RetDotProduct(axisAB,axisAB);
}
//rect B
for(int i=0;i<4;i++)
{
Bprojections[i] = RetDotProduct(axisAB,rectB[i]-axisA) / RetDotProduct(axisAB,axisAB);
}
float Amax = FindMax(Aprojections);
float Amin = FindMin(Aprojections);
float Bmax = FindMax(Bprojections);
float Bmin = FindMin(Bprojections);
if((Bmin > Amin && Bmin < Amax) || (Bmax > Amin && Bmax < Amax))
return true;
return false;
}
bool RectVsRect(const VECTOR rectA[], const VECTOR rectB[])
{
if(IsColOnAxis(rectA[0],rectA[1],rectA,rectB) &&
IsColOnAxis(rectA[1],rectA[2],rectA,rectB) &&
IsColOnAxis(rectB[0],rectB[1],rectA,rectB) &&
IsColOnAxis(rectB[1],rectB[2],rectA,rectB))
return true;
return false;
}
int main()
{
bool drag=false;
sf::RenderWindow App(sf::VideoMode(800,600,32),"Vector");
VECTOR rect1[4] = {VECTOR(200,200),VECTOR(300,100),VECTOR(500,300),VECTOR(400,400)};
VECTOR rect2[4] = {VECTOR(350,200),VECTOR(450,200),VECTOR(450,400),VECTOR(350,400)};
while(App.IsOpened())
{
sf::Event Event;
App.PollEvent(Event);
if(Event.Type == sf::Event::Closed)
App.Close();
if(Event.Key.Code == sf::Keyboard::Escape)
App.Close();
if((Event.Type == sf::Event::KeyPressed) && (Event.Key.Code == sf::Keyboard::Up))
rect2[0].y-=0.25;
if((Event.Type == sf::Event::KeyPressed) && (Event.Key.Code == sf::Keyboard::Down))
rect2[0].y+=0.25;
if((Event.Type == sf::Event::KeyPressed) && (Event.Key.Code == sf::Keyboard::Right))
rect2[0].x+=0.25;
if((Event.Type == sf::Event::KeyPressed) && (Event.Key.Code == sf::Keyboard::Left))
rect2[0].x-=0.25;
rect2[1] = VECTOR(rect2[0].x+200,rect2[0].y);
rect2[2] = VECTOR(rect2[1].x,rect2[1].y+100);
rect2[3] = VECTOR(rect2[0].x,rect2[0].y+100);
App.Clear();
if(RectVsRect(rect1,rect2))
App.Draw(sf::Shape::Circle(100,100,10,sf::Color::Green));
DrawRect(App,rect1,255,0,0);
DrawRect(App,rect2,0,255,255);
App.Display();
}
return 0;
}
-
Very good job. You really seem to understand the concept pretty well.
The problem is how you're testing the overlap. Here's the function with my comments and fix:
bool IsColOnAxis(const VECTOR axisA, const VECTOR axisB, const VECTOR rectA[], const VECTOR rectB[])
{
VECTOR axisAB = axisA - axisB; // should be perpendicular axis, not parallel, but doesn't matter for rectangles.
// if you want to correct that, though, you would do this instead of axisA - axisB:
axisAB.y = axisA.x - axisB.x;
axisAB.x = axisB.y - axisA.y; // now axisAB is perpendicular to AB, not parallel
// but again this REALLY doesn't matter with rectangles because each of the 2 important
// axis are perpendicular to each other anyway. If you were doing some other
// kind of shape, though, this would have screwed it up.
float Aprojections[4];
float Bprojections[4];
//rect A
for(int i=0;i<4;i++)
{
Aprojections[i] = RetDotProduct(axisAB,rectA[i]-axisA) / RetDotProduct(axisAB,axisAB); // probably should be "rectA[i]-axisB" since axisB is your origin.
// but that really doesn't matter. All that will do is negate all your projected lines, but they will all be negated the same
// way, so it won't really affect anything. I only bring it up because it confused me a little when I first saw it.
}
//rect B
for(int i=0;i<4;i++)
{
Bprojections[i] = RetDotProduct(axisAB,rectB[i]-axisA) / RetDotProduct(axisAB,axisAB); // same notes as above
}
float Amax = FindMax(Aprojections);
float Amin = FindMin(Aprojections);
float Bmax = FindMax(Bprojections);
float Bmin = FindMin(Bprojections);
// you only check to see if the B points are "inside" the A line
// you do not check to see if the A points are inside the B line, which will cause a failure
// when the A line is fully enclosed in the B line.
//
// IE:
// ================================== <- B
// ============= <- A
//
// In this case, your test was returning false, but it should be returning true. This is why the function was failing sometimes.
/*
if((Bmin > Amin && Bmin < Amax) || (Bmax > Amin && Bmax < Amax)
|| (Amin > Bmin && Amin < Bmax) || (Amax > Bmin && Amax < Bmax)) // <- to fix you can add this
return true;
return false;
*/
// Although the massive if statements are fugly and confusing. Instead I would get rid of the above junk and do this instead:
if(Bmax < Amin) return false;
if(Amax < Bmin) return false;
if(Bmin > Amax) return false;
if(Amin > Bmax) return false;
return true;
// much simpler. Also note that this is fewer checks (4 conditionals instead of 8) so it'll likely be faster.
// You could also optimize this for rectangles. The thing with rectangles is 2 of their sides are parallel with the other 2 sides.
// so really you only need to project 2 corners and not 4 (specifically, the corners that are not adjacent to each other, like [0] and [2])
//
// You also only need to project them onto 2 axis, not 4. Because the other 2 axis will be parallel.
}
-
Thanks a lot :D now I feel really happy