bool SynthGame::LineLineIntersect(const D3DXVECTOR2& p1, const D3DXVECTOR2& p2,
const D3DXVECTOR2& p3, const D3DXVECTOR2& p4,
D3DXVECTOR2* result)
{
D3DXVECTOR2 mov_vec=p2-p1;
if(!(D3DXVec2Length(&mov_vec)>0)) return false;
mov_vec=p4-p3;
if(!(D3DXVec2Length(&mov_vec)>0)) return false;
float x1=p1.x;
float y1=p1.y;
float x2=p2.x;
float y2=p2.y;
float x3=p3.x;
float y3=p3.y;
float x4=p4.x;
float y4=p4.y;
float denom=0;
float ua=0;
float ub=0;
bool intersection=false;
//define denominator
denom=(y4-y3)*(x2-x1)-(x4-x3)*(y2-y1);
//check if lines are not parallel
if(denom)
{
intersection=true;
ua=( (x4-x3)*(y1-y3)-(y4-y3)*(x1-x3) )/denom;
ub=( (x2-x1)*(y1-y3)-(y2-y1)*(x1-x3) )/denom;
(*result).x=x1+ua*(x2-x1);
(*result).y=y1+ua*(y2-y1);
}
return intersection;
}
why is this function so slow?
Author
Hello all -
I wrote a function for determining the intersection between two lines. In a certain section of my game, this function is called no more than maybe one-hundred times. This causes a dramatic fps drop from about 140 to 80. I can't seem to figure exactly why this is happening
Note: The fps goes back to normal if I comment out the line
denom=(y4-y3)*(x2-x1)-(x4-x3)*(y2-y1);
Can anyone explain why this function is so slow? Thanks for any help!
-synth_cat
If you comment out that line, the denominator becomes zero and your program should explode, not run faster.
So that is your reason. You skip all the bulk of the mathematics in the function, and when that occurs it runs faster. You just need to find a more efficient method.
That code doesn't look like it should bog down the CPU at all. You should be able to do that thousands of times a frame easily.
My guess is that what you do as a result of when this function returns true is what is causing it to slow down. Does your execution follow a different branch where this function is called if it returns true rather than false?
My guess is that what you do as a result of when this function returns true is what is causing it to slow down. Does your execution follow a different branch where this function is called if it returns true rather than false?
Quote:
This causes a dramatic fps drop from about 140 to 80
Try actually timing the function; don't use FPS as a benchmark. Tell us exactly (or as close as you can get) how many ms the function takes, and we will see if it's actually slow or if it's something else.
Like the previous poster said, I bet you'll find the function itself is fast. Just because you skip one little part of the code doesn't mean that's what's causing the slowdown, it just means it results in a state where the slow code is being executed.
When you force denom to always be 0, you always return false, which means lines never intersect. I'm sure this means you are skipping some other intensive parts of your code that deal with collision. Show us the part of your code that deals with the intersection, until then we can't really tell you what's so slow [smile]
You can easily double the speed (at least) of this function in 2 ways.
First off, you're checking that the distance between 2 points is greater than 0. You should really just be comparing the X and Y co-ordinates of the vectors, and save yourself a square root (or 2 in your case)
The other thing I notice is you're creating 8 local variables that serve virtually no purpose, aside from making things more readible. Although it could be considered "splitting hairs", each variable you create on the local stack is a few cycles to create, and initialize. Since you're at the optimization stage, you should really consider changing these to pre-calculations, for example:
and then sub these into your equations:
Also adding the const to the variables allows the compiler to make assumptions, and potential optimizations. It may be irrelevant in this case, but it's good practice, and safer.
Anyway, that covers some of the basic code optimizations. You could probably simplify the math calculations themselves, and save yourself some multiplications, or divisions. But if you make the changes I mentioned above, you'll double the speed of this routine.
Hope that helps!
Andrew
First off, you're checking that the distance between 2 points is greater than 0. You should really just be comparing the X and Y co-ordinates of the vectors, and save yourself a square root (or 2 in your case)
The other thing I notice is you're creating 8 local variables that serve virtually no purpose, aside from making things more readible. Although it could be considered "splitting hairs", each variable you create on the local stack is a few cycles to create, and initialize. Since you're at the optimization stage, you should really consider changing these to pre-calculations, for example:
const float x4x3 = (p4.x-p3.x);const float y1y3 = (p1.y-p3.y);const float y4y3 = (p4.y-p3.y);const float x1x3 = (p1.x-p3.x);const float x2x1 = (p2.x-p1.x);const float y2y1 = (p2.y-p1.y);and then sub these into your equations:
denom = y4y3 * x2x1 - x4x3 * y2y1;...ua=( x4x3 * y1y3 - y4y3 * x1x3 )/denom;ub=( x2x1 * y1y3 - y2y1 * x1x3 )/denom;result->x = p1.x + ua * x2x1;result->y = p1.y + ua * y2y1;Also adding the const to the variables allows the compiler to make assumptions, and potential optimizations. It may be irrelevant in this case, but it's good practice, and safer.
Anyway, that covers some of the basic code optimizations. You could probably simplify the math calculations themselves, and save yourself some multiplications, or divisions. But if you make the changes I mentioned above, you'll double the speed of this routine.
Hope that helps!
Andrew
Quote:Original post by arudson
You can easily double the speed (at least) of this function in 2 ways.
I don't believe you.
Quote:Original post by arudson
First off, you're checking that the distance between 2 points is greater than 0. You should really just be comparing the X and Y co-ordinates of the vectors, and save yourself a square root (or 2 in your case)
Reasonable enough.
Quote:Original post by arudson
...each variable you create on the local stack is a few cycles to create...
No they don't.
Quote:
...and initialize. Since you're at the optimization stage, you should really consider changing these to pre-calculations, for example:const float x4x3 = (p4.x-p3.x);const float y1y3 = (p1.y-p3.y);const float y4y3 = (p4.y-p3.y);const float x1x3 = (p1.x-p3.x);const float x2x1 = (p2.x-p1.x);const float y2y1 = (p2.y-p1.y);
and then sub these into your equations:denom = y4y3 * x2x1 - x4x3 * y2y1;...ua=( x4x3 * y1y3 - y4y3 * x1x3 )/denom;ub=( x2x1 * y1y3 - y2y1 * x1x3 )/denom;result->x = p1.x + ua * x2x1;result->y = p1.y + ua * y2y1;
The compiler has to perform those calculations in advance anyhow. Specifying them explicitly provides nominal additional information, at best.
Quote:Original post by arudson
Also adding the const to the variables allows the compiler to make assumptions, and potential optimizations. It may be irrelevant in this case, but it's good practice, and safer.
No it isn't. The compiler learns nothing from a const modifier in this case, as it is incapable of making any assumptions it couldn't figure out on its own anyhow. That just leaves personal safety, and if your routines are so convoluted that you aren't sure you're not changing a local variable, then perhaps you have other problems.
Quote:Original post by arudson
Anyway, that covers some of the basic code optimizations. You could probably simplify the math calculations themselves, and save yourself some multiplications, or divisions. But if you make the changes I mentioned above, you'll double the speed of this routine.
Again, I don't believe you.
CM
Quote:Original post by Conner McCloud
No it isn't. The compiler learns nothing from a const modifier in this case, as it is incapable of making any assumptions it couldn't figure out on its own anyhow. That just leaves personal safety, and if your routines are so convoluted that you aren't sure you're not changing a local variable, then perhaps you have other problems.
CM
There are compilers that totally suck at generating decent math code. By writing out your math code one operation per line with const modifiers and by separating load instructions from store instructions can easily double the speed of the code snippet. True, sometimes this kind of code starts looking convoluted and assembly-like but it's worth it, especially during an optimization stage. Arudson, I believe you.
Quote:Original post by deathkrush
There are compilers that totally suck at generating decent math code. By writing out your math code one operation per line with const modifiers and by separating load instructions from store instructions can easily double the speed of the code snippet. True, sometimes this kind of code starts looking convoluted and assembly-like but it's worth it, especially during an optimization stage. Arudson, I believe you.
Any modern compiler that bothers with an optimization pass or two will be completely unaffected by his suggestions. Until the OP suggests he's programming for a cell phone, recommending that he rewrite perfectly functional code is foolish. Working code is better than code that is theoretically faster on a system he probably isn't even developing for.
CM
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
