• ### Popular Now

• 13
• 16
• 27
• 9
• 9

#### Archived

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

# Fast negitive # detection and line colision

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

## 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 on other sites
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 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 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 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| 0What I wanted to know was how to the last line with the XOR in it fast.I hope this helpsThanx for reading!Tazzel3d ~ Zach



##### 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 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.