[Aardwolf]

Pretty sure it's spheres, not cubes.

[EvidenceOfFault]

A sphere is really cheap for collision detection: All you need to do is
1. Take the square of the distance between the centres of the models
2. Take the sum of the squares of the model radii
3. Compare the two

This is 3 subtractions, 3 multiplications and 2 additions for (1),
2 multiplications and 1 addition for (2),
1 subtraction and a conditional jump for (3).

If you memoise the squares of the model radii, you can shave 2 multiplications off the algorithm.

Any other check for intersection will be much more expensive. It might be worth it, to cut down on the number of narrow-phase checks, but this is exactly the kind of situation where you have to try it out and profile.
Even if you find a case where a different algorithm is faster, it's quite possible that a different setting (ships less clustered, fewer missiles...) shows a regression with the new algorithm.

[The E]

The problem is that, and this may be surprising, most of the objects in your typical mission are not sphere-shaped. Sphere testing produces lot of false positives in our case.

[Luis Dias]

I see where I got wrong. Sorry.

The problem is that, and this may be surprising, most of the objects in your typical mission are not sphere-shaped. Sphere testing produces lot of false positives in our case.

yeah that was the gist of my ramblings.

[EvidenceOfFault]

The problem is that, and this may be surprising, most of the objects in your typical mission are not sphere-shaped. Sphere testing produces lot of false positives in our case.

Sure, but everything smaller than a cruiser is effectively sphere-shaped (at least in vanilla Freespace). Only capships really have concave shapes at the resolution where a smaller object can legitimately pass inside their bounding box, and they are the only thing sufficiently oblong to not be very close to colliding when their bounding sphere intersects another model.

[m!m]

The main problem of the collision code is that the actual collision detection cannot be multi-threaded which would give us a pretty big performance boost. Swifty already pointed that the broadphase is not really a big bottleneck and I can confirm that using data from previous profiling tests. The issue lies within the obj_collide_pair function which does the collision detection math and the actual handling of the collision in one step which makes multi-threading impossible.
A solution would be to detect the collision using multiple threads, store that information and then handle it within the main engine thread.

[Uchuujinsan]

The way I read the code it is a bounding box, not a sphere - well, basically a box that includes the calculated sphere, making it a cube with an edgelength of 2xradius

Code: [Select]

if ( min ) {
return pos->a1d[axis] - Objects[obj_num].radius;
} else {
return pos->a1d[axis] + Objects[obj_num].radius;
}If performed for each axis, this piece of code from get_collider_endpoint describes a cube/cuboid as the intersection of 6 planes in space (the min and max plane for each axis).
I got a few hours time today, let's see if I can do something productive.

[Phantom Hoover]

The problem is that, and this may be surprising, most of the objects in your typical mission are not sphere-shaped. Sphere testing produces lot of false positives in our case.

Sure, but everything smaller than a cruiser is effectively sphere-shaped (at least in vanilla Freespace). Only capships really have concave shapes at the resolution where a smaller object can legitimately pass inside their bounding box, and they are the only thing sufficiently oblong to not be very close to colliding when their bounding sphere intersects another model.

No, most ships are very definitely not sphere-shaped. Take the Karuna, for instance: it's much, much longer than it is wide or tall.

[EvidenceOfFault]

The problem is that, and this may be surprising, most of the objects in your typical mission are not sphere-shaped. Sphere testing produces lot of false positives in our case.

Sure, but everything smaller than a cruiser is effectively sphere-shaped (at least in vanilla Freespace). Only capships really have concave shapes at the resolution where a smaller object can legitimately pass inside their bounding box, and they are the only thing sufficiently oblong to not be very close to colliding when their bounding sphere intersects another model.

No, most ships are very definitely not sphere-shaped. Take the Karuna, for instance: it's much, much longer than it is wide or tall.

The Karuna is a) not vanilla FS, and b) a capship.

[pecenipicek]

The problem is that, and this may be surprising, most of the objects in your typical mission are not sphere-shaped. Sphere testing produces lot of false positives in our case.

Sure, but everything smaller than a cruiser is effectively sphere-shaped (at least in vanilla Freespace). Only capships really have concave shapes at the resolution where a smaller object can legitimately pass inside their bounding box, and they are the only thing sufficiently oblong to not be very close to colliding when their bounding sphere intersects another model.

No, most ships are very definitely not sphere-shaped. Take the Karuna, for instance: it's much, much longer than it is wide or tall.

The Karuna is a) not vanilla FS, and b) a capship.

retail examples then?
Cruisers: Rakshasa, Cain, Zephyrus, Anuket, Aeolus, Leviathan, Fenris
Corvettes: Deimos, Moloch
Destroyers: Hatshepsut, Typhon (to a lesser extent ), Orion
these are just off the top of my head.

Also, EvidenceOfFault, for the record, these slowdowns do not happen due to there being tons of fighters in close formations. They happen because of tons of everything else in close formations


One question about such ships, would it for example make sense to keep the spherical check whilst their radii do not intersect, then switch to bounding box based checks if the the distance between them < combined radii?

[EvidenceOfFault]

retail examples then?
Cruisers: Rakshasa, Cain, Zephyrus, Anuket, Aeolus, Leviathan, Fenris
Corvettes: Deimos, Moloch
Destroyers: Hatshepsut, Typhon (to a lesser extent ), Orion
these are just off the top of my head.


One question about such ships, would it for example make sense to keep the spherical check whilst their radii do not intersect, then switch to bounding box based checks if the the distance between them < combined radii?

Can you actually read? cap-ship

Edit: To say something constructive: I suspect the worst-case is currently when lots of small craft and missiles swarm around a large capship (i.e., they are inside its bounding sphere). The problem I see is that many of them will also be inside its bounding box, because fighters tend to fly very close to capships in dogfight, and the capships are not exclusively convex shapes. The place where bounding boxes would help most is capship-capship collision detection, which is (hopefully) not limiting the frame rate.
Anyway, I haven't actually measured anything, nor looked at the current code a lot, so I'm just going to recommend actually benchmarking any idea somebody wants to implement.

[The E]

Okay, no. This is not going to be an argument we will be having in this thread. Evidence of Fault, please consider that we actually know what we are talking about. Your point about it being less of an issue to approximate fighters as spheres than it is to do the same for bigger models is correct. But, whether it makes sense to leave the existing behaviour in place for fighters and use a more efficient one for capitals is something we will need to test. Feel free to implement such test cases.

But an argument based on "In retail, this is sufficient" is not going to fly, because we're not in a position where we can only worry about retail anymore.

[zookeeper]

Random idea: approximate non-aligned bounding boxes with several aligned cubes. I'd expect that you can perform quite a few aligned box tests with the price of one non-aligned box test, and while the approximation would be somewhat wasteful, the volume the cubes would occupy would still be a whole lot smaller than the radius sphere in many cases.

[attachment deleted by an evil time traveler]

[General Battuta]

In colloquial usage I'm pretty sure everything cruiser up gets called a capship.

[Uchuujinsan]

I have to repeat that I'm pretty sure that the broadphases uses a cube for sorting, not a sphere.

But some good news! After some fails on my part, I finally managed to do a rather trivial thing: Caching the obj_get_collider_endpoint results, which cut the performance impact of the broadphase by roughly ~40%, given one measurement (due to low sample size, this might have some inaccuracies). Unfortunately, because the broadphase detection isn't actually an issue as noted before, that doesn't really help us THAT much. :/
But at the very least, there's a positive result

I'm not sure if I should commit the code yet, though, because the source file is due to some stuff I did there quite a mess...

[Dragon]

Post a test build then. We'll see what this thing is worth.

[Uchuujinsan]

Like this? It's a pretty simple code change :>

[attachment deleted by an evil time traveler]

[Aardwolf]

So previously you were computing x+r, x-r, etc., in every comparison, and now you are computing them before the comparisons? Mmm. How costly would it be to do what I was talking about earlier... computing the AABB of the OBB (or some tighter approximation of the AABB of the oriented model, even), and caching that? Obviously a long ship oriented diagonally would not see much improvement, but maybe it would be worth it?

[Uchuujinsan]

We have to use an AABB for the broadphase detection, otherwise the binary search/sort of quicksort won't work. The AABB however can probably be smaller with low additional cost, assuming we do some pre-calculations during loading (or even save it along with the model). Currently it's effectively a cube that completely surrounds a sphere given by the objects radius, which is not very precise. Using an intermediate step between the absolutely precise narrowphase and the broadphase imho sounds promising.
Basically, narrowing down the AABB in the general broadphase, using a OBB or something similar at the beginning of the narrowphase for further filtering, and only then doing the actual precise narrowphase collision.

[EvidenceOfFault]

I have to repeat that I'm pretty sure that the broadphases uses a cube for sorting, not a sphere.

So, if I understand this correctly, what the engine does is:
1. Sort objects by one coordinate
2. Detect whether two objects are closer together along that coordinate than the sum of their radii
3. If so, check whether they are also closer together than the sum of their radii in the other two dimensions.

This would be a bounding cube, aligned to the coordinate system.

If so, we can get from the bounding cube to a bounding cylinder by checking whether the two objects that can overlap in the first dimension (x) can overlap in y and z by: deltay²+deltaz² > r1² + r² . This is almost as cheap computationally, and could reduce conditional jumps, if the current algorithm checks both y and z dimensions independently.
On any architecture where the vector-units are big enough to hold and compute all three coordinates at once, checking for the full sphere after checking for overlap in the first dimension would take practically no extra time.