- Joined
- Feb 17, 2012
- Messages
- 1,552
- Reaction score
- 2,604
Good news,
the lag/fps drop bug has finally been fixed. I also managed to increase the general performance of the physics engine in cube-cube collisions.
I'm still releasing this as a pre-build to check for eventual bugs from the new system. I'll do a full release of this exact version if there are no problems found in the test.
http://files.star-made.org/build/pre/starmade-build_20130918_153848.zip
(as always, "dev" is both password and username)
Technical: This bug was hard to find since it's trigger seems non-deterministic. The reason for the lag was iteration: When two structures are near each other, they check the area intersecting between their bounding boxes. First a region (8x8x8 segments) test is done, then the segments are iterated with each others. Now when a planet or a huge ships collides with another big structure, empty segments are iterated over bug skipped:
So for every segment in A, if it is non empty, find the non empty segments that have an intersection with that segment. This works ok for big ships for A and e.g. planets for B. However, the order of what is tested against what depends on the order it was added to physics (and as a precondition must not matter). So when revisiting a sector, the order can change (even likely changes). So suddenly the planet is A and the ship is B, and this caused the problem. If B has a lot of empty segments they are iterated over (but not processed) for all nonempty segments of A. This caused the number of iterations done to skyrocket into the millions for work, that only should have been done once (skipping empty segments).
The fix now caches for both structures the non-empty segments for each structure that are part of the intersection. This gets rid of the problem completely and improves the general performance (as the additional iterations were always happening, just not slowing down as much. Furthermore this also gave me the opportunity to cache the segment Axis-Aligned Bounding Boxes calculation, which saves a lot of multiplication and branches per iteration.
With this new system there also is another opportunity to optimize. Ordering the Axis-Aligned Bounding Boxes and doing an axis sweep (like it is done with the general physics broadphase) could further reduce iterations by a lot.
Thank you for testing,
and thank you for playing StarMade,
- schema
the lag/fps drop bug has finally been fixed. I also managed to increase the general performance of the physics engine in cube-cube collisions.
I'm still releasing this as a pre-build to check for eventual bugs from the new system. I'll do a full release of this exact version if there are no problems found in the test.
http://files.star-made.org/build/pre/starmade-build_20130918_153848.zip
(as always, "dev" is both password and username)
Technical: This bug was hard to find since it's trigger seems non-deterministic. The reason for the lag was iteration: When two structures are near each other, they check the area intersecting between their bounding boxes. First a region (8x8x8 segments) test is done, then the segments are iterated with each others. Now when a planet or a huge ships collides with another big structure, empty segments are iterated over bug skipped:
So for every segment in A, if it is non empty, find the non empty segments that have an intersection with that segment. This works ok for big ships for A and e.g. planets for B. However, the order of what is tested against what depends on the order it was added to physics (and as a precondition must not matter). So when revisiting a sector, the order can change (even likely changes). So suddenly the planet is A and the ship is B, and this caused the problem. If B has a lot of empty segments they are iterated over (but not processed) for all nonempty segments of A. This caused the number of iterations done to skyrocket into the millions for work, that only should have been done once (skipping empty segments).
The fix now caches for both structures the non-empty segments for each structure that are part of the intersection. This gets rid of the problem completely and improves the general performance (as the additional iterations were always happening, just not slowing down as much. Furthermore this also gave me the opportunity to cache the segment Axis-Aligned Bounding Boxes calculation, which saves a lot of multiplication and branches per iteration.
With this new system there also is another opportunity to optimize. Ordering the Axis-Aligned Bounding Boxes and doing an axis sweep (like it is done with the general physics broadphase) could further reduce iterations by a lot.
Thank you for testing,
and thank you for playing StarMade,
- schema
