 |
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. |
|
|
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) |
|
|
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. |
- Anonymous
