Sign in to follow this  

Fast enough for realtime?

This topic is 4336 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
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
The times are based of tracing a ray from a set point in the quake3 level q3dm1 (near the rocket launcher if you must know) to eveyr single vertex in the level. The total time is measured for each one to give a good indication of what an average collision time would be.

I have also now noticed that short lines are very fast, long lines are slow but generally don't exceed the avg time. I'm going to hope that I wont be needing too many long line traces.

Share this post


Link to post
Share on other sites
Quote:
From the GotW coding standards:
- avoid inlining or detailed tuning until performance profiles prove the need (Cline95: 139-140, 348-351; Meyers92: 107-110; Murray93: 234-235; 242-244)
- corollary: in general, avoid inlining (Lakos96: 631-632; Murray93: 242-244)

~ http://www.gotw.ca/gotw/033.htm

I don't remember where exactly, but one of Sutter's books also says that most compilers ignore inline, since it's only a hint anyways and they have heuristics that are usually better at figuring out when to inline than the programer is.

Share this post


Link to post
Share on other sites
Right. The compiler can see into the future to see how often a function will be called. They can't, which is why profile guided optimization was made, in which the compiler can gather statistics on a running application to make better optimization choices.

Compilers do not ignore the inline keyword. The fact that using the keyword doesn't guarantee that it will be done doesn't mean it is being ignored. It means that even with your hint that changes the heuristics the compiler ended up thinking it still wasn't worth it. In no way is that ignoring.

Share this post


Link to post
Share on other sites
Quote:
Original post by DrEvil
Compilers do not ignore the inline keyword. The fact that using the keyword doesn't guarantee that it will be done doesn't mean it is being ignored. It means that even with your hint that changes the heuristics the compiler ended up thinking it still wasn't worth it. In no way is that ignoring.

What a compiler does with inline is entirely implementation dependent. There is no guarantee that a particular instance of inline will be expanded or not. This keyword is a hint. A compiler can very well decide to completely ignore inline, this doesn't make it broken.

For VC8. Note this passage:
Quote:

The compiler treats the inline expansion options and keywords as suggestions. There is no guarantee that functions will be expanded inline. You cannot force the compiler to inline a particular function.


So whether a particular compiler ignores or takes the hint is irrelevant. There is no way of knowing, and you cannot rely on it in any way.

Share this post


Link to post
Share on other sites

This topic is 4336 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this