View Issue Details

IDProjectCategoryView StatusLast Update
0006085The Dark ModCodingpublic18.09.2022 15:34
Reporterstgatilov Assigned Tostgatilov  
Status resolvedResolutionfixed 
Product VersionTDM 2.10 
Target VersionTDM 2.11Fixed in VersionTDM 2.11 
Summary0006085: FixGlobalTjunctions is very slow on large-scale map
DescriptionT-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 ReproduceThis 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
TagsNo tags attached.




17.09.2022 08:48

administrator   ~0015251

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.


17.09.2022 09:00

administrator   ~0015253

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 =)


18.09.2022 15:34

administrator   ~0015264

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.

Issue History

Date Modified Username Field Change
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