[General Battuta]

Play 'Her Finest Hour' in Tenebra.

[Flaming_Sword]

thats amazingly cruel. what is the problem, too much overhead destroying any advantage gained?

It was a first attempt, so the code can likely be improved (I have an alternative method I can try).

Btw, what do you actually use for profiling? Just curious.

http://www.hard-light.net/forums/index.php?topic=70745.0

http://www.hard-light.net/wiki/index.php/Artemis_Station

War in Heaven - First cutscene mission, a few minutes long, has a bit of everything and fairly consistent. Just sit back and watch the FPS and profiling numbers.

The time spent in the hashmap operator[] is an interesting result. I may be able to do something with this...

[General Battuta]

Oh, damn, the BP massive battle mission is also really great for collision detection. Tons of missiles flying around mean lots of collision pairs.

[Flaming_Sword]

Oh, damn, the BP massive battle mission is also really great for collision detection. Tons of missiles flying around mean lots of collision pairs.

The only problem being that in parts it's such an extreme case that the FPS counter hits the floor and it's hard to tell if your changes have made any difference.

[pecenipicek]

Oh, damn, the BP massive battle mission is also really great for collision detection. Tons of missiles flying around mean lots of collision pairs.

The only problem being that in parts it's such an extreme case that the FPS counter hits the floor and it's hard to tell if your changes have made any difference.

i'd like to point out that (at least from my highly anecdotal and utterly unrepeated test), your gpu ram might be a bottleneck for that particular mission.
i've watched the video ram usage on the card through msi afterburner to see just what happens and the thing happily climbed to 1.4-1.5GB, on a nvidia GTX660 with 2GB.

the performance was smooth-ish and hovering around 6 fps minimum.

if you want some other things that i could test for you, i'd be happy to help.

[Swifty]

Hey BP guys. I think BP Massive Battle wouldn't be as slow as it is if you didn't put all your cap ships so close to each other.



And from looking at these results, trying to optimize the broadphase collision detection isn't going to do much.

[The E]

Not putting them so close together goes against our artistic integrity

But your point is well taken, BP Massive Battle is certainly a degenerate edge case, not the norm.

[Swifty]

I think it might be prudent to compute tighter oriented bounding boxes for ships and use that to see if we need to narrowphase check because the simple radius check we do to prevent unecessary narrowphase checks is completely failing us here.

[Luis Dias]

A bounding box would be a great substitute. The Karuna (for example) has 1300m and perhaps just 300m both in height and width. Even if 400 in both directions, the resulting volume is ~ 200x10^6m, while a sphere has a volume somewhere around 115 x 10^7, which is 6 times greater.

Given how most capships in FS are narrow, this order of mag difference is probably shared by most of them.

Perhaps if the bounding box coding is too expensive to run comparatively with the sphere, a three tier could do the trick?

If the projectile is within the bounding sphere, THEN run the bounding box calculation, if it is inside the bb, THEN do the narrowphase checks?

[Phantom Hoover]

I've seen talk of using collision meshes rather than the full-detail model for collision detection (possibly just one of the LODs). Is that a practical option?

[Swifty]

The collisions on the models themselves are fine. It's just we're doing too many unnecessary ones which is why there needs to be a more strict test in-between the broadphase and the narrowphase.

[Flaser]

The collisions on the models themselves are fine. It's just we're doing too many unnecessary ones which is why there needs to be a more strict test in-between the broadphase and the narrowphase.

This probably sounds delinquent and naive, but couldn't collision checks be predictively pruned?

I'm talking about trying to remove pairs where a good assumption can be made that collision won't happen with the initial parameters of the objects. The problem of course is that ships can maneuver, so can some projectiles... however there's still a certain volume of space that the ship will be inside after a given time.

After some reading it seems "sweeping" collision detection algorithms do what I had in mind, but tend to be more resource intensive than the discrete reactive collision detection method in use currently... still I wonder if the two systems could be combined? Instead checking against every single projectile in existence, being able to preemptively cull a lot of collisions check could be worth the trade-off:

http://seb.ly/2010/01/predictive-collision-detection-techniques/

[The E]

We already do a lot of preemptive culling. There are some types of collisions that are rejected outright (primary-on-primary, primary-on-beam), others are rejected based on relative movement (primary weapon blast moving away from a secondary weapon), this is all part of what is called the broadphase rejection pass.

Basically, there is no way around the requirement that each object has to be checked against each other object at least once. You can eliminate subsequent checks, and gain a bit of performance there, and that's what the broadphase pass is for.

The issue here, however, is the narrowphase pass, the one where we get into trying to resolve potential collisions against models and objects that couldn't be ruled out in the broadphase pass.

[zookeeper]

The collisions on the models themselves are fine. It's just we're doing too many unnecessary ones which is why there needs to be a more strict test in-between the broadphase and the narrowphase.

This probably sounds delinquent and naive, but couldn't collision checks be predictively pruned?

I'm talking about trying to remove pairs where a good assumption can be made that collision won't happen with the initial parameters of the objects. The problem of course is that ships can maneuver, so can some projectiles... however there's still a certain volume of space that the ship will be inside after a given time.

After some reading it seems "sweeping" collision detection algorithms do what I had in mind, but tend to be more resource intensive than the discrete reactive collision detection method in use currently... still I wonder if the two systems could be combined? Instead checking against every single projectile in existence, being able to preemptively cull a lot of collisions check could be worth the trade-off:

http://seb.ly/2010/01/predictive-collision-detection-techniques/

It's already being done. If two objects are far away from each other, then the code looks at their maximum speeds (and lifetimes for weapons, I believe) and determines whether they could ever collide or not. If they could, then it sets some kind of timestamp for when they should start checking against each other again, and skips checks between that pair until then.

[Luis Dias]

Basically, there is no way around the requirement that each object has to be checked against each other object at least once. You can eliminate subsequent checks, and gain a bit of performance there, and that's what the broadphase pass is for.

If, however, the broadphase can cull more 70-90% of volume per capship than it is currently by doing boundingboxes rather than spheres, wouldn't it diminish by a great lot (say 5 times?) the amount of narrowphase checks you'd be asking the cpu to make?

[Flaming_Sword]

The collisions on the models themselves are fine. It's just we're doing too many unnecessary ones which is why there needs to be a more strict test in-between the broadphase and the narrowphase.

This probably sounds delinquent and naive, but couldn't collision checks be predictively pruned?

I'm talking about trying to remove pairs where a good assumption can be made that collision won't happen with the initial parameters of the objects. The problem of course is that ships can maneuver, so can some projectiles... however there's still a certain volume of space that the ship will be inside after a given time.

After some reading it seems "sweeping" collision detection algorithms do what I had in mind, but tend to be more resource intensive than the discrete reactive collision detection method in use currently... still I wonder if the two systems could be combined? Instead checking against every single projectile in existence, being able to preemptively cull a lot of collisions check could be worth the trade-off:

http://seb.ly/2010/01/predictive-collision-detection-techniques/

It's already being done. If two objects are far away from each other, then the code looks at their maximum speeds (and lifetimes for weapons, I believe) and determines whether they could ever collide or not. If they could, then it sets some kind of timestamp for when they should start checking against each other again, and skips checks between that pair until then.

The predictive collision detection happens in the narrowphase and the results are cached (and always skipped when the initial check says they'll never, ever collide).

Basically, there is no way around the requirement that each object has to be checked against each other object at least once. You can eliminate subsequent checks, and gain a bit of performance there, and that's what the broadphase pass is for.

If, however, the broadphase can cull more 70-90% of volume per capship than it is currently by doing boundingboxes rather than spheres, wouldn't it diminish by a great lot (say 5 times?) the amount of narrowphase checks you'd be asking the cpu to make?

You have to be careful there. You're moving a chunk of the narrowphase check into the broadphase.

What the broadphase currently does is a quicksort of objects by position (using one side of the spherical boundary) along an axis, the do overlap checking (with the other side). Non-overlapping objects are culled and the process repeated for the other axes.

When there is overlap with all 3 axes, we move to narrowphase, with all that fancy predictive checking, bounding box checking, etc.

If you skip the overlap check, but do the bounding box check many more times, there's a risk that you get worse performance because those bounding box checks could take longer.

Also, quicksort is typically O(n log n) while with just a bounding box check you have O(n^2).

[Bobboau]

well, you are already checking a dimension on each of the three axes, the problem is you are checking radius (If I am not mistaken), you could swap out the bounding box dimensions and I don't see how it could affect performance.

[Aardwolf]

Presumably it would be an oriented bounding box, not just a simple AABB, and OBB x OBB collision checks are significantly more costly than Sphere x Sphere.

Edit: but if you computed the AABBs of all the OBBs beforehand, then you could do AABB x AABB, which is in theory cheaper than Sphere x Sphere since there's no need to square the distances on each axis. Although if the AABB of the OBB is bigger than the sphere, idk...

[zookeeper]

Exactly, checking for overlap of bounding boxes is super fast and simple only on aligned/non-oriented boxes. Less so when the boxes can be in arbitrary orientations. I'd expect radius overlap checking to be quite a bit faster.

[Luis Dias]

It's already doing a "bounding box" anyway, the radius description is faulty if what it really happens is what is described in this thread, which is the engine looks at the center position of the model and checks all the values of X - radius to X + radius, then Y then Z. That's a cube. Now you can say "yeah but look this cube is amazingly cheap", except for when? Except for the most problematic cases when it's not cheap at all, which is exactly when it becomes absolutely useless, for instance, in many BP cases.

Now what is the point of having an algorithm that works amazingly well when the scenario is simple, the warships are far away from each other, etc. but when we need the engine to get really optimized, "oops the optimizations just don't work here"? Why bother then? conversely, so what if the bounding boxes are costlier than the simple cube check that the engine does now, if when things get really complex and gritty it is able to perform admirably better? Isn't that the whole point of having an optimization algorithm?

The difference is not between having simple radius checks and bounding boxes, the real difference is between having these bounding boxes calculations and narrowphase full mesh intersection calculations.

Why do I say this? Simple. A bounding box will have at least 10 times less volume than the simple radius cube. This means that for each second, 90% of the time, instead of having a narrowphase check every time a bullet entered the radius of a ship, you'd have only a bounding box calculation. Unless this bounding box calculation is almost as costly as the narrowphase check, you are winning computation time here.

My two cents.