Jump to content
  • Advertisement
Sign in to follow this  
FlyingDodo

Fast enough for realtime?

This topic is 4551 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

I have a collision detection implemented and each line trace takes between 0.5 and 1 ms, maybe at worst would take 5ms. Is this fast enough for use in realtime? I'm planning on using this in an fps quake like game with many player/enemies shooting everywhere, maybe with shotgun blasts which would take around 20 shots times 40 players traces each (just giving an example of how often this tracing will be used). I thinking at that speed i'd only be able to get about 10 frames per second on the server side, or am I vastly overestimating the impact this will have? edit: I was also wondering ways of making it faster, would it be any use inlining functions/ slapping const around the place?

Share this post


Link to post
Share on other sites
Advertisement
You should be using const properly regardless. Modern compilers ignore inline anyway. And without knowing anything else about what you're doing, we can't possibly suggest any optimizations.

Share this post


Link to post
Share on other sites
Quote:
Original post by Puzzler183
Modern compilers ignore inline anyway.


Since when?

OP, yes that's far too slow for a raycast function. Are you using custom collision functions or a collision library such as opcode?
const won't give you any speed, you use it for its compile time safety checking.

Share this post


Link to post
Share on other sites
Quote:

Quote:
Original post by Puzzler183
Modern compilers ignore inline anyway.

Since when?

Since around VC7. There are compiler switches controlling how serious the compiler will take inline hints. It is usually best to leave the decision about inlining to the compiler, though.

Quote:
Original post by DrEvil
const won't give you any speed, you use it for its compile time safety checking.

That's only half correct. Correct use of const will give additional hints to the compiler, and allow it to optimize your code better. The performance impact of not using const properly is entirely dependent on the code. But don't expect miracles. In most cases, the performance improvements will be rather small.

To the OP: you shouldn't be "slapping consts around the place". You should learn how to use it properly, and use it consistently throughout your code from the beginning on. const isn't an optimization keyword, it expresses a concept that will make your code more safe, maintainable, and less bug prone. Possible performance improvements are a nice side effect, but not the keywords primary use.

About your CD function. For the usage you describe, it is far too slow. You should review the algorithm you're using, and try to exploit hierarchical structures and temporal coherence as far as possible.

Share this post


Link to post
Share on other sites
I've heard that const can improve performance before, but I've also heard contradictions to that claim. I don't know what to believe any more. Obviously things like constant folding are available to the compiler which is a good reason to use them and probably some other optimizations, but specifically the contradictions speak against performance gains when passing parameters with const.

To list some sources, whether they are correct or not.

http://developers.sun.com/prodtech/cc/articles/CC_perf/content.html Under "Const Declarations"

Does anyone have the book C++ FAQS? It has one called "Does const allow the compiler to generate more efficient code?"

I seem to remember the strongest contradiction to const optimizations coming from something similar.

For the record, by no means am I saying don't use const. Definately use it. See effective C++ "Use const whenever possible", I'm just saying to not rely on const for performance gains. It's highly implementation dependent it would seem on whether the library writers take advantage of const guarantees to do some optimizations. Use const whenever possible for the safety primarily, enjoy any performance gains that happen to show up in the process.

Sorry to take so off topic. In a crappy attempt to make up for it, I'll make some comments on topic :D

Raycasts are a very critical part of most games, especially FPS games, and especially if the game intends to have AI at some point. AI typically use raycasting a good deal as 'feelers' and line of sight testing and such. If you aren't locked into using your own implementation you might consider using something like opcode, which is a pretty highly optimized collision library that ODE uses.

Share this post


Link to post
Share on other sites
I am already using a bsp tree, however if the trace line is on both sides of the bsp split I send it down both sides of the node. If I split the line into two pieces along the bsp split then I get incorrect results, such as not getting the closesest collision point to the start or missing the collision altogether.

If I just loop through all bsp leaf nodes then collisions are always correct, so somehow by splitting the line it is does not visit all the needed leaf nodes.

Would I be correct in assuming that something is wrong with the code that deals with the line spanning the bsp split?



here it is:
(this is the code that does have the splitting of the line, which is much much faster but produces incorrect results)


bool CfileBsp::TraceThroughTree(Cvector3 start, Cvector3 end, int node, Cvector3 &hitPoint, bool& gotHit){

bool sf = false;
bool bf = false;
int traceNode;

if(ClassifyPoint(start,node) == FRONT){
sf = true;

}

if(ClassifyPoint(end,node) == FRONT){
bf = true;

}

if((sf != bf)){//if the start and end points are on different sides of the bsp split

//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//find intersection point
Cvector3 dir = end - start;
double dp = Cvector3::DotProduct(m_bspPlanes[m_bspNodes[node].plane].normal,dir);

if(dp == 0){
return false;
}

double t = -( Cvector3::DotProduct(m_bspPlanes[m_bspNodes[node].plane].normal,start) -m_bspPlanes[m_bspNodes[node].plane].d ) / dp;

Cvector3 Intersect = start + (dir * t);
/////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////

//deal with front half
traceNode = m_bspNodes[node].children[FRONT];
if(traceNode >= 0){

TraceThroughTree(start,Intersect,traceNode,hitPoint, gotHit);

}else{

TraceThroughLeaf(~traceNode,start,Intersect,hitPoint,gotHit);

}

//deal with back half
traceNode = m_bspNodes[node].children[BACK];
if(traceNode >= 0){
//if its a node, trace through it
TraceThroughTree(Intersect,end,traceNode,hitPoint, gotHit);

}else{

//if its a leaf, see if the line hits anything
TraceThroughLeaf(~traceNode,start,end,hitPoint,gotHit);

}

}else if((sf == bf) && sf == true){ //if both points are in front of the splitting plane

traceNode = m_bspNodes[node].children[FRONT];

if(traceNode >= 0){
//if its another node, trace through it
TraceThroughTree(start,end,traceNode,hitPoint, gotHit);
}else{
//if its a leaf, see if the line hits anything
TraceThroughLeaf(~traceNode,start,end,hitPoint,gotHit);



}


}else{//if both points are behind the splitting plane

traceNode = m_bspNodes[node].children[BACK];
if(traceNode >= 0){
//if its another node, trace through it
TraceThroughTree(start,end,traceNode,hitPoint, gotHit);

}else{
//if its a leaf, see if the line hits anything
TraceThroughLeaf(~traceNode,start,end,hitPoint,gotHit);



}

}

return gotHit;
}








edit: It seems that with the line splitting it misses a lot of leaf nodes.

[Edited by - FlyingDodo on January 29, 2006 8:34:26 PM]

Share this post


Link to post
Share on other sites
I've managed to get the time down to around 0.2 ms, is this fast enough?

edit: seems to be 0.3 ms, worst case, avg 0.2, best 0.06.

[Edited by - FlyingDodo on January 29, 2006 9:44:52 PM]

Share this post


Link to post
Share on other sites
Sorry that I don't have the time to read all the codes you've posted. My suggestion is:

Make your algorithm and code correct before any code optimizations. This is the best way to improve performance. Like you said, visiting all nodes in BSP must be slow.


Off topic:

General guide lines are to inline those functions with little codes when compared to function call. Like those have simple calculations involving a few arithmetics.

Though, heavy inlining may increase code size which causes CPU cache misses. Then? Testing is the rule of thumb. You need experience on this.

Whether const can improve performance optimization for compilers? Largely depends on the compiler's implementation. Normally, a margine can be gained. Though, negligible.

Share this post


Link to post
Share on other sites
Quote:
Original post by FlyingDodo
I've managed to get the time down to around 0.2 ms, is this fast enough?

edit: seems to be 0.3 ms, worst case, avg 0.2, best 0.06.


That's completely irrelevant if we don't know how complex your scene is (as well as your CPU type). 0.2 ms to cast a ray onto a cube is horrible, but if the scene is many million triangles, it's good. In Minas Tirith, i cast a ray onto the city (5 millions triangles) in 0.05 ms (best), 0.1 ms (avg), 0.2 ms (worst) on a ~2Ghz CPU. One thing you can do is to limit the max distance at which to do your tests, if you aren't doing it yet. For collisions for example, if you know your object has moved by one meter, there's no need to check collisions with an object that is 1 km away.

Y.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
About inline...

It's ludicrus to declare or assert that "most compilers" ignore inline. The only compiler that ignores inline is a broken one.

Surly, the keyword has substantial implications regarding how inlined methods are linked. It will also hint to the compiler to inline methods in a debug build if you enable inlining in those builds (some engines need to enable inlining in debug builds to get a usable framerate, unfortunately).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!