View Issue Details
|ID||Project||Category||View Status||Date Submitted||Last Update|
|0006085||The Dark Mod||Coding||public||28.08.2022 09:42||18.09.2022 15:34|
|Product Version||TDM 2.10|
|Target Version||TDM 2.11||Fixed in Version||TDM 2.11|
|Summary||0006085: FixGlobalTjunctions is very slow on large-scale map|
|Description||T-junctions fixing function spreads vertices into a grid of 16 x 16 x 16 cells.|
When map bounds are large, every call gets a lot of vertices, resulting in almost quadratic performance.
|Steps To Reproduce||This issue is very strong on Blackheart Manor WIP mission (in betamapper repo).|
Its bounds are huge:
+ min (-35897.0000, -32577.0000, -5357.00000) idVec3
+ max (4609.00000, 14461.0000, 7605.00000) idVec3
|Tags||No tags attached.|
Committed in svn rev 10118.
I reimplemented the whole T-junction fixing algorithm from scratch.
First of all, it uses hashgrid (like e.g. in idVectorSet) instead of regular grid, which allows to reduce cell size and avoid having too many cell collisions.
The first pass is merging vertices together: now it is done with VERTEX_EPSILON_NEW = (1.8 / 32) Euclidean distance, instead of some weird snapping-dependent condition in the old algorithm.
Cell size is set to 10 * tolerance, so that points rarely span over several cells, but cells are still very small so that distinct points rarely get into same cell.
The second pass is about splitting triangles by vertices.
We can't use too small cell size here because then we'll have to iterate over too many cells in triangle's bounding box.
And we can't use too large cell size since then we'll have to iterate through too many points in a cell.
So now the cell size is chosen adaptively: we start with "average triangle size" as cell size, then halve it while it improves our cost estimate.
The cost estimate is computed by running a simple prepass: just counting how many points are in each cell and doing the searches in triangles' bounding boxes.
I believe this is the best thing we can do performance-wise.
The new algorithm is enabled under cvar "dmap_tjunctionsAlgorithm 1".
Note that it only supportes the behavior of "dmap_fixVertexSnappingTjunc2" (current default), and with different "close" condition.
However, enabling this algorithm resulted in more data in .proc file on New Job FM.
It turns out that a fence func_static_2855 generates insane number of triangles (like 4:1 ratio between number of tris and verts), which becomes even larger with new algorithm.
I tracked this issue down to dmap_disableCellSnappingTjunc cvar: setting this to 0 removes the trash regardless of which T-junctions fixing algorithm is used.
dmap_disableCellSnappingTjunc cvar is explained here:
It was originally introduced to fight with decals depth-fighting problems, but in the end I realized that offsetting decals by 0.1 in world-space depth would be better solution.
Also, I noted that it fixes holes in the rope in Saint Lucia... but now that I test it, I don't see any holes even with all-new defaults.
In the end, I decided to revert dmap_disableCellSnappingTjunc back to "always snap all vertices".
The case of fence shows that snapping indeed improves stability in this unstable world =)
Oh, it turned out that the issue was not fixed on Blackheart Manor WIP FM.
That's because of a small stupid bug in estimation of average triangle size.
Fixed in svn rev 10121.
Now FixGlobalTjunctions takes 4.25 seconds for me =)
That's where Bikerdude reported almost 8 minutes.
|28.08.2022 09:42||stgatilov||New Issue|
|28.08.2022 09:42||stgatilov||Status||new => assigned|
|28.08.2022 09:42||stgatilov||Assigned To||=> stgatilov|
|17.09.2022 08:48||stgatilov||Note Added: 0015251|
|17.09.2022 09:00||stgatilov||Note Added: 0015253|
|17.09.2022 09:01||stgatilov||Status||assigned => resolved|
|17.09.2022 09:01||stgatilov||Resolution||open => fixed|
|17.09.2022 09:01||stgatilov||Fixed in Version||=> TDM 2.11|
|18.09.2022 15:34||stgatilov||Note Added: 0015264|