Jump to content
  • Advertisement

Archived

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

Dwiel

Fast negitive # detection and line colision

This topic is 6075 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey, I was trying to impliment a fast line collision detection function, but my algo needs to find out if a number is negitive. What is the fastest way to do this? Also fast XOR test for the negitive value. ex. | 1|-1| 1| 0| 1| -1| 1| 0| Maybe it would be easier/ faster to do something like | n|-n| n| 0| n| -n| n| 0| where n is any positive #(except obviously where the - sign precedes it, where it is any negitive number) Here is my pseodocode: xor(neg((xa1 - xb1) + (xa2 - xb2)), neg((ya1 - yb1) + (ya2 - yb2))) or if the xor can take any positive or negitive #: xor((xa1 - xb1) + (xa2 - xb2), (ya1 - yb1) + (ya2 - yb2)) Thanx for the help ahead! Tazzel3D ~ Zach P.S. Dont bother to ask me to explain something better because I know from experience that I am not good at explaining things!!

Share this post


Link to post
Share on other sites
Advertisement
I came up w/ one way that works well, but it only works with ints because you can''t ^ or & a float. Anyway here it is.

if ((((ixa1 - ixb1) + (ixa2 - ixb2)) ^ ((iya1 - iyb1) + (iya2 - iyb2))) & -1)
return 1;
else
return 0;

This is very fast, but only works with int. when i have to convert foats to an int by multipling by 256 (floating pint math) the algo slowed from .945 seconds per 10,000,000 computations to 3.9 seconds per 10,000,000!

Is there a faster way to this.

Thanx Alot!!

Share this post


Link to post
Share on other sites
Actually, I changed it and now it goes faster. Heres my code:

if ((int(((xa1 - xb1) + (xa2 - xb2)) * 256) ^ int(((ya1 - yb1) + (ya2 - yb2)) * 256)) & -1)
{}
else
{}

This time I didn''t convert each value to fpi. I converted the values that needed to be ^ed and &ed. Sped it up to 1.4 seconds per 10,000,000. Is this a reasonable speed?

I am not sure.

Thanx alot!

Share this post


Link to post
Share on other sites
I am having trouble understanding what you want (especially your pseudcode), so let me take some guesses

You want a fast way to see if a number is negative? try
if (num < 0) {do stuff};

You want a fast way to see if 2 numbers are the same sign (kinda like an xor)? try
if ((num1^num2) & 0x80000000) {do stuff};
assuming num1 and num2 are both 32 bit ints

EDIT: for that last one, actually it returns true if the numbers are different signs, false if they are they same sign

Edited by - LordKronos on February 2, 2002 2:21:34 PM

Share this post


Link to post
Share on other sites
I am trying to find if two lines collide. My algo goes like this:

// line #1 = (xa1, ya1)-(xa2, ya2)
// line #2 = (xb1, yb1)-(xb2, yb2)

// find direction vector between first point of first line and first point of second line

xfin1 = xa1 - xb1
yfin1 = ya1 - yb1

// find direction vector between second point of first line and second point of second line

xfin2 = xa2 - xb2
xfin2 = ya2 - yb2

if (XOR(neg(xfin1 + xfin2), neg(yfin1, yfin2)))
{
col
}

where XOR:



|-1| 1
-1| 0| 1
1| 1| 0

What I wanted to know was how to the last line with the XOR in it fast.

I hope this helps

Thanx for reading!

Tazzel3d ~ Zach

Share this post


Link to post
Share on other sites
I can''t belive my self!!!!!!! My new code (below is 25x faster, and 100000000x easier to understand!!!!!!)



if (((xa1 - xb1) + (xa2 - xb2)) > 0) // if x +
{
if (((ya1 - yb1) + (ya2 - yb2)) > 0) // if y -
{
// cout << "col!" << "\n";
}
else
{
// cout << "no col!" << "\n";
}
}
else // if x -
{
if (((ya1 - yb1) + (ya2 - yb2)) < 0) // if y +
{
// cout << "col!" << "\n";
}
else
{
// cout << "no col!" << "\n";
}
}

I hate it when you try so hard to make this algo, and make it even more complex by trying to make it faster, when the original way is actually faster!!!!!!

anyway

Share this post


Link to post
Share on other sites
quote:
Original post by Tazzel3D
I hate it when you try so hard to make this algo, and make it even more complex by trying to make it faster, when the original way is actually faster!!!!!!
anyway


That''s usually how it goes. The lesson here is to always save optimization to the end. Premature optimization results in trying to speed up code that is only accessed 0.0001% of the time, or just making things more complex and deterring you from progressing.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!