[Uchuujinsan]

Well, not quite. Some details are actually different, but apart from them there is a main difference:
1. Sort objects by one coordinate
2. Detect whether two objects are closer together along that coordinate than the sum of their radii
3. For all objects were this is true, sort by the second coordinate
4. Detect whether two objects are closer together along that coordinate than the sum of their radii
5. For all objects were this is true, sort by the third coordinate
6. Detect whether two objects are closer together along that coordinate than the sum of their radii
7. For all objects were this is true, initiate narrow phase

If you substitute 1. 3. or 5. (even only one of them) with some sphere approximation, you can no longer sort them, making it a n² algorithm average case, which isn't an improvement.

[edit]
Note that the broadphase detection currently only uses less than 15% of the run time of the collision system (according to the latest profiling I did)
We don't use an explicit AABB either, it's just an implicit result of the algorithm.

[headdie]

Cool

ok so in basic terms how does the narrowphase operate

[Luis Dias]

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.

Thank god I thought I was going stoopid for not being unable to see this .

BTW, I like the "several bounding cubes" idea, feels really cheap computationally and the volume is definitely better, but I'm not sure it's easy to implement.

[Flaming_Sword]

A solution would be to detect the collision using multiple threads, store that information and then handle it within the main engine thread.

This is what I'm working on. The tricky part is getting it to run faster given the introduced overhead.

[m!m]

I'm implementing a general multi-threading framework for our engine before I try to convert the code.
What threading-framework are you using?

[m!m]

I just took a look at the actual collision detection code and all I can say is: That thing is a mess!
It will take a pretty big effort to get it to work with multiple threads, maybe even as much work as including an external physics engine like Bullet and converting FSO to use that.
Thoughts?

[The E]

Better to leave that for another day, I think.

Don't get me wrong, the possibilities of having an actual physics engine are exciting, but let's get the near-term big things sorted first.

[m!m]

Yeah, I wasn't entirely serious but after looking at the collision code I just came to the conclusion that deleting it would be a good idea

[Flaming_Sword]

I'm implementing a general multi-threading framework for our engine before I try to convert the code.
What threading-framework are you using?

SDL2, based on antipodes with updates from trunk.

Mine works, but runs at lower fps. I'm just messing with scheduling and caching at the moment.

[Bobboau]

you using a thread pool? what sort of synchronization mechanism you using? and where?

[Flaming_Sword]

It's currently a bit ad-hoc, just to get the game to run and not crash.

The main thread gets the list of collisions to evaluate (object pairs, basically) from broadphase (the logic of the current predictive evaluation and caching are preserved) and passes it to threads (number passed in via command line option) that aren't busy. When all list items have been passed and no threads are busy, those pairs that have actually collided are processed by the main thread (the part that's more or less impossible to make parallel unless you rewrite big portions of the engine).

There's other gotchas around things like script hooks and rendering calls around fireball creation that will crash the game if executed in parallel.

Oh yeah, there was also a rewrite of the model collision code to make it threadsafe and rewrite of the collision functions for threadsafety and separation of evaluation vs. processing.

My current build uses so much RAM it's not funny, since you now have to store the relevant information for every collision for later processing instead of using it immediately.