OpenMeridian / Meridian59

The MMORPG Meridian 59 - Server 103
openmeridian.org
Other
141 stars 74 forks source link

Improve server BSP performance #1349

Closed cyberjunk closed 8 years ago

cyberjunk commented 8 years ago

This is a cleaned up variant of https://github.com/OpenMeridian/Meridian59/pull/1344 It does not contain any extensive additional benchmark projects etc. It contains the following improvements:

1) https://github.com/OpenMeridian/Meridian59/commit/8dde32766c406851b4a478af080436684d15e7fd This will add an improved geometry.h version (fully backward compatible), containing the following improvements:

2) https://github.com/OpenMeridian/Meridian59/commit/074b0ee51eca39d6abc0bca0b724474c2b871def This contains the following improvements to the BSP queries in roofile:


Other things/improvements: 1) Some logical operators (in geometry.h as well as roofile) have been replaced by binary ones, in cases the expression is very unlikely to skip over some further conditions. 2) Linux compatibility: Not tested so far


Further things to improve (not in this pull): 1) The "constant" LOS or Move line S->E is calculated on the fly a lot during the recursive calls. Especially for each triangle-intersection right now It might be better to do this once before the recursion/algorithm starts. 2) The IntersectLineTriangle() is suboptimal for the convex polygon check. It has some "intro"-calculation to check whether line and triangle are parallel (which is either true for all or none of the triangles in the convex polygon). Preferrably the geometry.h should contain an "IntersectLineConvexPolygon()" function, which is build from the triangle-intersection algorithm and checks the whole polygon optimized. 3) The recursive tree-traversal functions for LOS and CanMove could be ported to while based ones. Since these functions have cases which require evaluating both children, it's not as trivial as the GetHeight() rewrite.I think there exists a rather complex "constant-space-while-tree-traversal" algorithm, however the readability of these functions could likely be hurt...

skittles1 commented 8 years ago

+1, please let me know when you've finished with this PR so we can test/merge

cyberjunk commented 8 years ago

+1, please let me know when you've finished with this PR so we can test/merge

I don't plan to add anything to this pull except bugfixes. Everything mentioned in "Things to improve" would be a next, dedicated pull.

First thing we probably should check now is linux compatibility...