View Issue Details

IDProjectCategoryView StatusLast Update
0000128Medieval EngineersEnhancementpublic2022-04-09 04:32
Reporterequinox Assigned Toequinox  
Status resolvedResolutionfixed 
Target Version0.7.3.33D4BBFixed in Version0.7.3.33D4BB 
Summary0000128: Improve grid-voxel narrowphase performance

When complex grids containing a lot of unique shapes pass near voxels without touching (for example, a train going through a tunnel -- I have an example world from Xaerthus) the Havok midphase uses hkpSparseGrid (for the grid) and hkpBvCompressedMesh (for voxels) to gather pairs of shape keys to process in the narrow phase. Because the hkpSparseGrid is made out of many 12^3 cells each one of these cells has to be intersected against every voxel triangle within the large grid cell. Individually these tests are fairly cheap because the grid cells internally use a MOPP and MOPP-triangle is a fast narrowphase, but the shear number (~12k) of them causes pretty horrible performance hits.

Ultimately the solution here is to push tight fitting bounding volumes up into the root shape of a grid so the midphase can whittle down the number of shape key pairs needing to be processed in the narrow phase. Ideally we could put every single block shape in a single MOPP but this is not practical because of the shape key limit (65k) and the cost of rebuilding the MOPP after each grid change is too high. That said in testing this approach yielded a 4-5x speed up in my test world once the MOPP was built, taking a 0.3 simspeed world to 1.0+ as long as no grid modifications were made

The alternative I'm proposing is we use a HkSmartListShape (a special list shape that transparently wraps a list of up to 64 BV shapes in such a way that the midphase can run against the 64 contained BV shapes instead of the list shape) that contains one "top level MOPP" and 0-63 "hot cell MOPPs". Grid cells that are being repeatedly modified will be compiled into a per-cell MOPP after each modification, and that per-cell MOPP will exist directly in the HkSmartListShape (costing 1 of the 65k shape keys per block). Grid cells that haven't been modified recently will be evicted from the hot tier of MOPPs and instead will all be rolled up into a single top level MOPP of MOPPs (costing 1 of the 65k shape keys per CELL). In preliminary testing this seems to yield a ~3x speed up while supporting realtime modification of the grid without issue.

Additionally to keep the MOPPs as tight fitting as possible we should continue to use a strategy that LODs the grid cells, with larger blocks being grouped together into larger cells. An additional optimization is "axial lodding" where the cell LOD is picked per axis, so a (1x1x10) block might end up in cell LOD (0,0,4). This increases the cell count but has the benefit that the cell MOPPs have a smaller amount of empty space causing unnecessary narrowphase operations.

Another benefit of this tier system is we can investigate incremental improvements to the grid shape in the future as well. For example, when evicting a cell from the hot tier into the cold tier we can merge box shapes together to further reduce the total shape count.

TagsNo tags attached.


related to 0000122 resolvedequinox "Dead grids" on large blocks are still happening (DS - modded)  
related to 0000175 resolvedequinox Player character no longer able to traverse 1x2 slopes (small block only)  



2022-02-18 22:07

administrator   #~0000056

Last edited: 2022-02-19 17:21

Old implementation tick lengths: avg 50 ms, max 170 ms

New implementation: avg 10ms, max 40ms

New implementation with 5 bit voxel geometry cells: avg 10ms, max 20ms

Issue History

Date Modified Username Field Change
2022-02-01 23:31 equinox New Issue
2022-02-01 23:31 equinox Assigned To => equinox
2022-02-01 23:31 equinox Status new => assigned
2022-02-05 15:21 equinox Status assigned => in progress
2022-02-08 17:48 equinox Target Version 0.7.4 (unreleased) =>
2022-02-18 22:07 equinox Note Added: 0000056
2022-02-18 22:07 equinox Note Edited: 0000056
2022-02-19 17:21 equinox Note Edited: 0000056
2022-02-27 13:56 equinox Status in progress => resolved
2022-02-27 13:56 equinox Resolution open => fixed
2022-02-27 13:56 equinox Fixed in Version =>
2022-04-08 19:53 equinox Relationship added related to 0000122
2022-04-09 04:32 equinox Relationship added related to 0000175