View Issue Details

IDProjectCategoryView StatusLast Update
0005488The Dark ModCodingpublic11.03.2021 03:50
Reporterstgatilov Assigned Tostgatilov  
PrioritynormalSeverityfeatureReproducibilityN/A
Status resolvedResolutionfixed 
Product VersionTDM 2.09 
Target VersionTDM 2.10Fixed in VersionTDM 2.10 
Summary0005488: dmap: faster optimize algorithm
DescriptionCurrently dmap "optimizes" all planar triangulations ("groups") to reduce number of triangles.
The underlying algorithm takes O(N^3) time and cannot be improved by a simple heuristic.
As the result, if the map has a complex planar surface in one area, the optimization algorithm can take ages.
It can also be disabled by passing noOpt argument to dmap, but this is a bad thing to do (aside from debugging).
Steps To ReproduceTo make it a big problem, you might want to :
1) Run entitylimit2.py in maps/test/ to generate a VERY LARGE map.
2) Try "dmap entitylimit2_gen.map" and see where execution chokes.
Note that there are other problems with such a huge map, so don't expect you will hit this problem first.
Additional InformationSee also:
  https://forums.thedarkmod.com/index.php?/topic/16837-when-youre-getting-close-to-the-entity-limit-inlining/&do=findComment&comment=454663
  https://forums.thedarkmod.com/index.php?/topic/16837-when-youre-getting-close-to-the-entity-limit-inlining/&do=findComment&comment=454721
TagsNo tags attached.

Activities

stgatilov

stgatilov

10.03.2021 17:35

administrator   ~0013773

Committed the new algorithm, made it default.

The following commits don't affect anything:
  r9194 Preliminary changes.
  r9198 Preliminary: added idVec2d type.
  r9199 Preliminary: added idBinHeap container.

Then there go some minor improvements in dmap optimization algorithm in general:
  r9195 SplitOriginalEdgesAtCrossings: never add zero-length edges after split (always enabled)
  r9196 When splitting edges by intersections, handle all T-junctions precisely (controlled by optimizeExactTjuncIntersection)
  r9197 Never split zero-area triangles in T-junctions removal (always enabled)
They are independent of the new algorithm, and should be good for the old one too.

The actual new algorithm comes in:
  r9200 Implemented and enabled new triangulation optimization algorithm for dmap.
That's where most of the changes are... although it's adding tns of new code in new files, but not changing much in existing files.
stgatilov

stgatilov

10.03.2021 17:36

administrator   ~0013774

Copy/pasting commit message of r9200:

0005488. Implemented and enabled new triangulation optimization algorithm for dmap.

It is enabled by default, controlled by cvar dmap_optimizeTriangulation.
Unlike the old algorithm with O(N^3) complexity, the new one is mostly linear (quadratic in worst case).
Note that the old algorithm is usually very fast, but if you happen to create single polygon with 1000+ vertices, then it can take ages.

tools/compilers/dmap/earcut.*
  New class EarCutter for triangulating a polygon (possibly with holes).
  It is an implementation of the well-known ear cutting/clipping algorithm.
tools/compilers/dmap/planargraph.*
  New class PlanarGraph for searching all faces in a planar graph.
  It is based on edge traversal algorithm, with preliminary sorting incident edges by polar angle.
  Connected components are related to each other based on "lies inside" queries.
  The faces are needed in order to triangulate them using ear-cutting algorithm.
sys/msvc/natvis/game.natvis
  Added definitions for some internal data structures of PlanarGraph class.
tools/compilers/dmap/optimize.cpp
  Integrated the new algorithm into planar group optimization code.
  The old cubic method AddInteriorEdges is replaced with the new method AddTriangulationEdges.
  The new method build planargraph, finds its faces and triangulates them, thus finds new diagonal edges to be added.

Hot dmap time improvements:
  painterswife\city: 5:37 -> 3:32
  NHAT\politics: 4:35 (no change)
stgatilov

stgatilov

10.03.2021 17:41

administrator   ~0013775

Last edited: 10.03.2021 17:47

The heart of the new algorithm is the PlanarGraph data structure.
It takes a set of vertices located on the plane with edges connecting them (without intersections), and produces the set of faces in this graph.
Every face is independently triangulated using ear-clipping algorithm.
As the result, we can turn a given planar graph into a complete triangulation.
Although integration only uses the additional diagonal edges for convenience --- actual triangles are rebuilt by existing code.

Of course, the planar graph algorithm is much smarter and thus much more fragile than greedy triangulation.
So some attention should be payed to dmap outputs now.

By the way, planargraph.cpp contains some unit tests on the structure.
Including stress-tests on random bitmap-generated planar graphs with validation of outputs.

Most of the new code uses floats to represent vertex coordinates and doubles to represent derivative quantities (e.g. cross/dot products).
Due to such policy, it is expected that geometric predicates are evaluated exactly, thus there are no tolerances in most places.

Another interesting point is that the whole code is called 100K times during dmap, mainly on small graphs.
For that reason, I had to design data structures in such a way that everything is stored in linear arrays.
That's not always obvious, and not always convenient, but it allows reusing memory buffers between runs --- which is important for performance here.
The buffers are stored in static variables in AddTriangulationEdges in optimize.cpp: technically it is a memory leak since I don't shutdown them, but I hope nobody cares.

Issue History

Date Modified Username Field Change
08.01.2021 06:05 stgatilov New Issue
08.01.2021 06:05 stgatilov Status new => assigned
08.01.2021 06:05 stgatilov Assigned To => stgatilov
10.03.2021 17:35 stgatilov Note Added: 0013773
10.03.2021 17:36 stgatilov Note Added: 0013774
10.03.2021 17:41 stgatilov Note Added: 0013775
10.03.2021 17:47 stgatilov Note Edited: 0013775
11.03.2021 03:50 stgatilov Status assigned => resolved
11.03.2021 03:50 stgatilov Resolution open => fixed
11.03.2021 03:50 stgatilov Fixed in Version => TDM 2.10