Archived

This topic is now archived and is closed to further replies.

LostBoy

Please Help - Simple collision detection problem

Recommended Posts

LostBoy    122
I cannot find a specific example of what I need to do. I simply need to test to see if my sphere touches a line. All of the examples that I can find deal with spheres coliding with polygons or polygons with polygons. The reason that I need to do it with lines is because I have bound my area with lines. Thanks JC

Share this post


Link to post
Share on other sites
Crispy    556
I''m not 100% sure, but didn''t gametutorials (www.gametutorials.com) have a sphere-line collision example?

Hope this helps,
Crispy

Share this post


Link to post
Share on other sites
Datalor    122
Horizontal/Verticle lines?

X + Radius <= Line X then they are touching. etc etc.

If the lines are on an angle... that gets complicated.
Hmm... Just thinking from the top of my head...
*head explodes*

Hm.... actually, you could convert the x&y values to polar, add at the angle that the line is at and then check it the same way, ya?

*hopes hes not wrong*

Share this post


Link to post
Share on other sites
vincoof    514
Once you have the equation of the line, you can compute the distance between any point and the line.
Get the distance between the line and the center of the sphere (the center being a point obviously), and if this distance is inferior than the radius of the sphere : collision happens.

Share this post


Link to post
Share on other sites
LostBoy    122
Does anyone have any code examples ? What throws me for a loop is that I draw my sphere the way that NEHE does in one of his tuts, but then I see it being done differently in other tuts. Maybe there are different methods for different situations, but if possible I''m trying to stick to one way.

I don''t need to know the reactions that the ball would have if it did hit. I just need help with the ball touching the line which surounds my mini golf course. I can figure out the if statements.

Thanks guys

JC

Share this post


Link to post
Share on other sites
vincoof    514
By "line" you mean a "wall" in fact, isn''t it ?

How is represented your "line" in your code ? Is it a couple of 2D points ? Is it the equation ax+by+c=0 ? Is it something else ?

Share this post


Link to post
Share on other sites
circuit    134
I think it goes something like this (might be wrong):

BOOL line_and_sphere(POINT p1, POINT p2, POINT sphere, float radius)
{
float v, d;
VECTOR EO, ray;

EO=make_vector(p1, sphere);
ray=make_vector(p1, p2);

v=dot(EO, ray);

if (v<0) return FALSE;
d=radius*radius-(dot(EO,EO)-v*v);

if (d<0)
return FALSE;
else
{
d=v-sqrt(d);
if (d>lenght(ray)) return FALSE;
}

return TRUE;
}

Share this post


Link to post
Share on other sites
vincoof    514
And if you have the Cartesian equation as ax+by+c=0, you can do :


  
bool intersect_sphere_line(float center_x, float center_y, float radius, float a, float b, float c)
{
float sqr_norm = a*a+b*b; // compute (a²+b²)

if (sqr_norm==0) return c==0;
else
{
float dot_prod = a*center_x+b*center_y; // compute ax+by+c

float sqr_dot = dot_prod*dot_prod; // compute (ax+by+c)²

float sqr_dist = sqr_dot/sqr_norm; // compute distance²=(ax+by+c)²/(a²+b²)

float sqr_radius = radius*radius; // compute radius²

return sqr_radius < sqr_dist; // intersection happens if radius²<distance²

}
}

Share this post


Link to post
Share on other sites
LostBoy    122
Here is what I have so far everyone. It's enough to draw my rectangle (with bitmap on to for course), draw 4 of my boundary lines, draw my sphere (ball), and a temporary means of setting my ball in motion. Note the "delay" variable. It is only so that the ball will not move until a second or so after everything appears. Maybe my code will make it more clear as to what I am trying to do. Also, if you provide code, please include how I would initialize any variables so that I don't get errors.
Please feel free to correct me if I have done anything unneccesarily or ineficiently. Also note my comments where there is a push or pop. Let me know if I am thinking the wrong way with those. When I see something like that, I am thinking assembley language and stack actions (from my days with ASM). If this code looks familiar it's because I adapted with NEHE's code.


int DrawGLScene(GLvoid) // Here's Where We Do
All The Drawing
{
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
// Clear Screen And Depth Buffer

glLoadIdentity();
// Reset The Current Modelview Matrix

glTranslatef(-3.0f,0.0f,-2.0f);
// Move Left 3 And Into The Screen 2

glTranslatef(3.0f,0.0f,0.0f);
// Move Right 3 Units

glEnable(GL_TEXTURE_2D);
// Enable Texture Mapping

glBindTexture(GL_TEXTURE_2D, texture[0]);
// Binds our BMP to next object

glPushMatrix();
// Save matrix position

glBegin(GL_QUADS);// Draw A Quad (our corse)
//Texture and quad coordinates

glTexCoord2f(0.0f, 1.0f); glVertex3f(-1.0f, 1.0f, 0.0f);
// Top Left

glTexCoord2f(1.0f, 1.0f); glVertex3f( 1.0f, 1.0f, 0.0f);
// Top Right

glTexCoord2f(1.0f, 0.0f); glVertex3f( 1.0f,-1.0f, 0.0f);
// Bottom Right

glTexCoord2f(0.0f, 0.0f); glVertex3f(-1.0f,-1.0f, 0.0f);
// Bottom Left

glEnd();// Done Drawing Quad

//glTranslatef(0.0f,0.0f,1.0f);
glDisable(GL_TEXTURE_2D);//disable last texture
glBegin(GL_LINES);
glColor3f(1.0f,0.0f,0.0f);

glVertex3f( -0.334f,-0.612f,.0f); // start of line 1
glVertex3f( -0.681f,-0.612f,.0f); // end of line.

glVertex3f( -0.681f,-0.612f,.0f); // start of line 2
glVertex3f( -0.681f,0.415f,.0f); // end of line.

glVertex3f( -0.6812f,0.415f,.0f); // start of line 3
glVertex3f( -0.332f,0.765f,.0f); // end of line.

glVertex3f( -0.332f,0.765f,.0f); // start of line 4
glVertex3f( 0.29f,0.765f,.0f); // end of line.

glEnd();

//glTranslatef(-1.0f,0.0f,0.0f);(not used)

glTranslatef(xtravel,ytravel,0.0f);
// Move to ball position

//glDisable(GL_TEXTURE_2D); (not used)

glColor3f(1.0f,0.0f,0.0f);
// Load red for our ball

gluSphere(quadratic,0.02f,32,32);
// Draw a sphere (our ball)

glColor3f(1.0f,1.0f,1.0f);// Reset color

delay=delay-5.0f;
if (delay<=0)
{
delay=0;//all of this is temporary,
just to set ball in motion

glPopMatrix(); // Get matrix position
ytravel=ytravel+decay;// increment ytravel
glPushMatrix(); // Save matrix position
decay=decay-.00001f; // Decrement decay
}

if (decay<=0) // Eventually stop/
decay=0; prevent going backwards

return TRUE; // Keep Going
}

PS hey vincoof, would you be so kind as to tell me how you got your code in your reply to look like real code ? This reply box is really pissing me off. I can't simply cut and paste my code, I have to screw with it alot just to make it readable.

Thanls all !


[edited by - LostBoy on September 30, 2002 4:00:50 PM]

Share this post


Link to post
Share on other sites
vincoof    514
After reading this, I''ve got a few comments to make. And to be honest, only one is critical. The others are *just* optimizations.



First the worst : pushing and popping the matrix.
Everytime you call glPushMatrix, you''re supposed to call a corresponding glPopMatrix sooner or later. In fact, you''re not obliged to do so (not like you''re obliged to call the corresponding glEnd for every glBegin) but it''s a mistake not to call it because you screw up the stack levels.

In your sample code, you''re calling either glPushMatrix once, either glPushmatrix twice and glPopMatrix once... that means that you''re always calling glPushMatrix one more time than glPopMatrix, resulting in a stack overflow after a few iterations !

You''re right about the fact that the matrix behaves like a stack, so I don''t know why you made that mistake.

Though in this case OpenGL won''t crash. Your matrix will not be pushed when the stack overflow happens (that is, glPushMatrix has no effect when the matrix stack is full) but obviously you should not play with such dangerous tricks.



Secondly, there are a few hints
You can replace this piece of code :
  
glTranslatef(-3.0f,0.0f,-2.0f);
// Move Left 3 And Into The Screen 2


glTranslatef(3.0f,0.0f,0.0f);
// Move Right 3 Units

with that :
  
glTranslatef(0.0f,0.0f,-2.0f);
// Move 2 Units Into The Screen

I don''t feel like I should give explanations because I think it''s obvious, but feel free to ask if it''s not obvious for you.


Because all your lines are connected, you can use a better primitive than GL_LINES, which is called GL_LINE_STRIP.
Replace :
  
glBegin(GL_LINES);
glColor3f(1.0f,0.0f,0.0f);

glVertex3f( -0.334f,-0.612f,.0f); // start of line 1

glVertex3f( -0.681f,-0.612f,.0f); // end of line.


glVertex3f( -0.681f,-0.612f,.0f); // start of line 2

glVertex3f( -0.681f,0.415f,.0f); // end of line.


glVertex3f( -0.6812f,0.415f,.0f); // start of line 3

glVertex3f( -0.332f,0.765f,.0f); // end of line.


glVertex3f( -0.332f,0.765f,.0f); // start of line 4

glVertex3f( 0.29f,0.765f,.0f); // end of line.


glEnd();

with :
  
glBegin(GL_LINE_STRIP);
glColor3f(1.0f,0.0f,0.0f);

glVertex3f( -0.334f,-0.612f,.0f); // corner 1


glVertex3f( -0.681f,-0.612f,.0f); // corner 2


glVertex3f( -0.681f,0.415f,.0f); // corner 3


glVertex3f( -0.332f,0.765f,.0f); // corner 4


glVertex3f( 0.29f,0.765f,.0f); // final corner.


glEnd();

This line strip connects the corner 1 with corner 2, corner 2 with corner 3, corner 3 with corner 4, and corner 4 with the final corner.
The primitive GL_LINE_STRIP is better than GL_LINES because you call glVertex less often. In other words, you send less data through the pipeline (if you know what the pipeline is in OpenGL).


And finally, I''m not sure why you call glPopMatrix and glPushMatrix there :
  
glPopMatrix(); // Get matrix position

ytravel=ytravel+decay;// increment ytravel

glPushMatrix(); // Save matrix position

It''s like you want to want to restore the matrix as it was before, and then immediately save it again. It''s a nice trick... apart the fact that saving the matrix is useless since you''re not performing anymore matrix operations after that !



Formating posts on gamedev forums
To post source-like formated text, you have to use the [source] and [/source] tags before and after your source code, respectively. If you look at the FAQ you will find useful information for posting in gamedev forums.



Final note
Since your lines are axis-aligned, you can use very fast collision detection like Datalor presented. It''s more simple, it''s faster and uses less memory ! What do you want on top of that ? Oh yes, I admit it''s less flexible. Do you plan on using non axis-aligned borders ?

Share this post


Link to post
Share on other sites
LostBoy    122
Hey, thanks alot for your suggestions. Everything that you said to me made sense, and I have optimized my code. It works just as it did before. I felt a little silly when you had pointed out my errors with the stack (that is supposed to make sense to a guy that understands ASM). Also, I do have a basic understanding of the pipe line, and I see what you were talking about with sending unneccesary code through it (which would bog things down when I got more elaborate with things later on). And last but not least, I understand the HTML tags.

Thanks very much

JC






[edited by - LostBoy on October 2, 2002 1:27:47 AM]

Share this post


Link to post
Share on other sites
tylerbingham    122
look.....I know what everyone is saying and it is ALL right. But here is the deal. If you have one color for the ball and one color for the wall...all you need to do is to write this as a global variables

GLfloat wallcolor[3]={1.0f,1.0f,1.0f} //white as test color
GLfloat ballX;
GLfloat ballY;

GLfloat pixels[3];
GLint viewport[4];

then in the main drawing function do this:

glGetIntegerv(GL_VIEWPORT,viewport);

glReadPixels(ballX,ballY,1,1,GL_RGB, GL_FLOAT, (void *)pixels);

if(pixels[0]==wallcolor[0] && pixels[1]==wallcolor[1] && pixels
[2]==wallcolor[2])
{
WALL COLLISION HAPPENED!!!!!!!!!!!!!!!!!
}
else
KEEP ROLLING!!!!!!!!!!!!!!!!!!!!






this just gets tricky if you have different colored golf-balls or different colored walls(on each hole).Email me if you have any questions.

Share this post


Link to post
Share on other sites
LostBoy    122
Wow! Thanks very much for that code ! That was my original idea (to use the colors for colision detection), I just didn''t know how to code it. It seems to be the most simple approach for what I want to do.

Thanks very much

JC

Share this post


Link to post
Share on other sites
LostBoy    122
I''m still having problems. Here is my code :

First my global variables :

  
GLfloat ballX=-.508f; // Initialize ball coordinate horizontal

GLfloat ballY=-.542f; // Initialize ball coordinate vertical

GLfloat decay=.005f;
GLfloat delay=1000.0f;
GLuint texture[1]; // Storage For One Texture

GLUquadricObj *quadratic;// Storage For Our Quadratic Objects


GLfloat wallcolor[3]={1.0f,1.0f,1.0f}; // Line color

GLfloat pixels[3];
GLint viewport[4];


Now the drawing routine :

  
int DrawGLScene(GLvoid) // Here''s Where We Do All The Drawing

{
// Clear Screen And Depth Buffer

glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
glLoadIdentity();// Reset The Current Modelview Matrix





glTranslatef(0.0f,0.0f,-2.0f); // Move Into The Screen 2

glEnable(GL_TEXTURE_2D);// Enable Texture Mapping

glBindTexture(GL_TEXTURE_2D, texture[0]);// Binds our

//BMP to next object


glBegin(GL_QUADS);// Draw A Quad (our corse)

//Texture and quad coordinates

// Top Left

glTexCoord2f(0.0f, 1.0f); glVertex3f(-1.0f, 1.0f, 0.0f);
// Top Right

glTexCoord2f(1.0f, 1.0f); glVertex3f( 1.0f, 1.0f, 0.0f);
// Bottom Right

glTexCoord2f(1.0f, 0.0f); glVertex3f( 1.0f,-1.0f, 0.0f);
// Bottom Left

glTexCoord2f(0.0f, 0.0f); glVertex3f(-1.0f,-1.0f, 0.0f);
glEnd();// Done Drawing Quad


glDisable(GL_TEXTURE_2D);


glBegin(GL_LINE_STRIP);
glColor3f(1.0f,1.0f,1.0f);
glVertex3f( -0.334f,-0.612f,.0f);//corner 1

glVertex3f( -0.681f,-0.612f,.0f);//corner 2

glVertex3f(-0.681f,.415f,.0f);//corner 3

glVertex3f( -0.332f,0.765f,.0f);//corner 4

glVertex3f( 0.29f,0.765f,.0f);//corner 5

glEnd();

GLfloat radius=0.02f;



glTranslatef(ballX,ballY,0.0f);// Move to ball position

glColor3f(1.0f,0.0f,0.0f); // Load red for our ball

gluSphere(quadratic,radius,32,32);//Draw a spher(ourball)

glColor3f(1.0f,1.0f,1.0f); // Reset color


delay=delay-5.0f;
if (delay<=0)
{
delay=0;//This is temporary, just to set ball in motion

ballY=ballY+decay;// increment ytravel

decay=decay-.00001f;// Decrement decay

}

glGetIntegerv(GL_VIEWPORT,viewport);

glReadPixels(ballX,ballY,1,1,GL_RGB, GL_FLOAT,(void *)
pixels);

if(pixels[0]==wallcolor[0] && pixels[1]==wallcolor[1] &&
pixels[2]==wallcolor[2])
decay=0;


if (decay<=0)// Eventually stop/prevent going backwards

decay=0;

return TRUE;// Keep Going

}


My red ball just keeps on going through the white diagonal line towards the top of my course. What I''m trying to do here is make decay = 0 if they touch so that ballY + decay = 0 and my ball will stop. This is just to test functionality. If I can get the damn thing to at least respond I can get on with it. This is the only bad obstacle that I have run into. With help from others on the forum, my previous problems were easily solved.

I might also add that I am getting 2 warnings when I compile since I have added the collision detection. My variable initialization looks OK. I am thinking that it is in the drawing routine.

Thanks everyone

JC

Share this post


Link to post
Share on other sites
vincoof    514
If you encounter problems hitting the wall, you could try to enlarge the wall line (because the line is too thin). Call glLineWidth(4.0f) for instance.

And for you compilation warnings, I guess the best thing you could do is posting them here.

Share this post


Link to post
Share on other sites
LostBoy    122
Thanks for the advice, but it still doesn't work. This is rough territory for an OpenGl beginner.

Here are the warnings :

c:\program files\microsoft visual studio\myprojects\golf\golf.cpp(199) : warning C4244: 'argument' : conversion from 'float' to 'int', possible loss of data

c:\program files\microsoft visual studio\myprojects\golf\golf.cpp(199) : warning C4244: 'argument' : conversion from 'float' to 'int', possible loss of data


[edited by - LostBoy on October 2, 2002 4:07:28 PM]

Share this post


Link to post
Share on other sites
vincoof    514
Are you sure that your ballX and ballY values correspond to SCREEN ccordinates ?
and why do you write :
quote:

My red ball just keeps on going through the white diagonal line towards the top of my course.

Does it mean that it is the only border where there is the problem, and there's no problems for other walls ?


Your warning are simply telling that converting from float to int may lose decimals if your floating value is too precise, and if your floating value is too high you won't be able to convert it in a decent way. Generally you can skip the warning by casting explicitally your floating expression.
For instance, if the warning appears in such line :
my_integer = my_float_value;
Replace it with :
my_integer = (int)my_float_value;
And that should do the trick for most compilers (if not all)

[edited by - vincoof on October 2, 2002 4:29:07 PM]

Share this post


Link to post
Share on other sites
tylerbingham    122
Hey man, I know about 10 problems with the code I gave you.It will work ,but it will miss on certain things the code needs to be changed a little.
First off---the code will miss if you resize the scene.You need to add in a variable for the screen width and height.

Second off---the color collision is a very tricky way to do things.It will work and probably will be the best approach for you, but you are going to need to test which way the ball is moving and modify the glReadPixels to test the side of the ball closest to the wall.You are also going to need to test the ball as a ball(test the diameter/circumcerence) and not as a QUAD for accuracy.

Id like to take a look at the code and help you more...but going back and forth in the forums gets kinda tricky.

Share this post


Link to post
Share on other sites
LostBoy    122
For the love of God, please help me man ! (laughs, but only half joking). This is driving me nuts !

1. I''m not sure as to what was vincoof talking about.-
(my_integer = (int)my_float_value

2. How do I make my ballX and ballY correspond to screen
coordinates ?

3. How can I make each pair of vertices in my line drawing equal
one object ? In other words, how can I make a given line
equal to a single variable ? If I could do this, then I could
test to see if ballX,ballY is touching this line, or has
passed this line.

4. Please explain things in a way that a beginner can
understand. I am not familiar with the advanced math being
thrown around in some of the posts. This is my first opengl
project, and I was trying to avoid complex measures. I will
get to the harry math soon enough, and don''t really want to
climb that mountain yet. Not to mention I am still learning
C++ as well. These are all reasons that I chose such a simple
project. (laughs - at least I thought it was simple).

Share this post


Link to post
Share on other sites
vincoof    514
1. In C++, if you write :

  
float my_float=1.5f;
int my_int;
my_int = my_float;

there will be a warning because converting a float to an int may lose some precision. In that example, ''my_int'' will receive the value ''1'', not ''1.5'' thus losing the decimals. You can''t store the value ''1.5'' in an integer.
But if your code is something like that :

  
float my_float=18.f;
int my_int;
my_int = my_float;

The warning is still here but you can ignore it since you do not lose precision. It''s not a problem to store ''18'' in an integer.


2. What I mean is that glReadPixels does use screen coordinates. If you don''t really know how to project the coordinates, I''d recommend not to use glReadPixels. Though if you really want to convert from world coordinates to screen coordinates, you may take a look at gluProject and gluUnproject functions.


3. I''m sorry but I don''t understand your question. I''m afraid you should rephrase it or argue with schemes please.


4. In fact the math behind the algorithms described here are very simple. If it doesn''t seem simple, that just mean we''re not very good teachers. Really, it''s very rare to have an algorithm easier than line collision detection in 2D !

Share this post


Link to post
Share on other sites
tuita    240
I'm not really sure (I'm somewhat of a beginner too), but to my understanding, using glReadPixels(x,y,1,1,...) would only give you the pixel at the centre of the sphere.
So basically, wouldn't it be possible that within an update of ballX/Y, that one pixel that you are checking could overstep the line, thus, passing the collision detection area.
Would it be possible (definitely slower) to perhaps use glReadPixels using a larger area (i.e. glReadPixels(ballX-(radius/2), ballY+(radius/2), ballX+(radius/2)..) then looping through to check all of those pixels?

Also, would this 'color-collision' technique work at all under certain rotations of the scene? (i.e. when objects cover one another on the z-axis)

Personally, I think the maths technique is the way to go. I know you want to avoid it, but its not THAT hard. I was definitely no genius at linear algebra, but even I managed to create basic collision detection systems for 3D models. Believe me, if you pick up an old math textbook, its all there.

quote:

1. I'm not sure as to what was vincoof talking about.-
(my_integer = (int)my_float_value



All he's saying is that its basic C/C++ practice to cast values when assigning them to a different data type. It will get rid of all those annoying error messages.

[edited by - tuita on October 3, 2002 11:12:31 AM]

Share this post


Link to post
Share on other sites
LostBoy    122
Thanks. I can usually pick up on math just by looking at it. When I get lost is when that math is combined with opengl standard practices that I am not used to seeing. It''s when someone covers some code, but leaves out something vital, because they think that I am already aware of certain details.
So far my experience has been good with opengl. Just reading some tuts and looking at code, I have been able to figure out what is going on. But I must say that this collision detection has stoped me in my tracks. I can grasp the concepts, but those concepts are not useful for someone like me that does not yet know how to implement his ideas with opengl.

I know that I have much to learn, and I thank everyone for their patience.

vincoof : what I meant by #3 is, I need to know how to store the entire line as a single variable so that I can use it in my math. That way I would not have to rely on pixel color detection, in the event that I get more fancy with my game as it evolves.

JC

Share this post


Link to post
Share on other sites