View Issue Details
ID  Project  Category  View Status  Date Submitted  Last Update 

0005137  The Dark Mod  Coding  public  01.02.2020 05:22  05.01.2021 18:20 
Reporter  stgatilov  Assigned To  stgatilov  
Priority  normal  Severity  major  Reproducibility  sometimes 
Status  resolved  Resolution  fixed  
Product Version  TDM 2.07  
Target Version  TDM 2.08  Fixed in Version  TDM 2.08  
Summary  0005137: Dmap optimization breaks rain patches  
Description  Dmap processing splits all patches and brushes with BSP tree, then merges some stuff back in "optimize" phase. Unfortunately, this optimizations tends to frequently produce two types of problems on rain patches in my experiments: 1) A few triangles of a patch are dropped. As the result, there is no rain from a collisionStatic patch under these triangles. 2) Sometimes triangles start overlapping, at least by texture coordinates. This results in runParticle tool throwing error without producing the cutoff image. With this problem present, it is unlikely that a mapper would be able to use rain on global scale.  
Additional Information  The known workaround is disabling dmap optimization: dmap noOpt {mapname} However, this disables optimization on the whole map, so triangle count will increase a lot.  
Tags  particle  
I fixed this problem switching a some places in optimize.cpp to double precision. After that I went on and applied double precision to more routines important for dmap. First of all, I decided to add doubleprecision version of idVec3 (svn rev 8555). I implemented only a bare minimum of methods, since I hope it would be used only in case of necessity. The current issue with rain patches is fixed by svn rev 8556, where double precision is applied to basic routines of mesh optimization algorithm. Then I decided to go on and improve precision in a few more places. In svn rev 8557 double precision is applied to various idWinding routines: mainly splitting with plane and getting its own plane. Lastly, grid snapping is improved in svn rev 8558. 

I reviewed mesh processing in the late stages of dmap: Tjunctions removal and optimization. Tjunctions appear a lot after geometry gets splitted by BSP tree. Removing them is necessary, since stencil shadows computations won't work otherwise. The code for removing Tjunctions is very clever, because it also heals the mesh in process. It takes minimum integervalued box bounding the model, and creates a 32 x 32 x 32 grid in this space. Then all vertices of the mesh are "snapped" to the points of this grid. The snapping is imaginary, the coordinates of mesh vertices don't change in normal case. But if several vertices get snapped to the same grid point, then one of the vertices is stitched precisely to the other. Every triangle get checked against any points that it covers and is split in them. Tjunctions removal algorithm does not need any increased precision due to its good use of snapping. The only problem that I found is the way how snap point is deduced from coordinate: iv[i] = floor( ( v[i] + 0.5/SNAP_FRACTIONS ) * SNAP_FRACTIONS ); If coordinate equals (2*integer+1)/64, i.e. is between to numbers looking like integer/32, then it can be rounded both down and up with equal error. Of course, C library would choose rounding up, but only if value is precise. In the reality, several logically same vertex can have this coordinate with different roundoff errors. Some of them get snapped down, others are snapped up. As the result, Tjunctions healing does succeed in its healing goal. I fixed it by adding a small "random" shift in snapping: double eps = 0.009656781074217107; iv[i] = floor( ( v[i] + (0.5eps)/SNAP_FRACTIONS ) * SNAP_FRACTIONS ); Now values near (2*integer+1)/64 will be snapped to same direction, problem solved. Of course, there is still some theoretical chance that some set of vertices would get very close to the split between "rounddown" and "roundup". But this is vary unlikely: much less likely that hitting into (2*integer+1/64) case. It turned out that this problem happens in New Job FM for several equal func_statics. Here is how it looked before my fix: model { /* name = */ "func_static_2062" /* numSurfaces = */ 1 /* surface 0 */ { "textures/darkmod/decals/signs/sign_tea" /* numVerts = */ 30 /* numIndexes = */ 171 ( 7.59375 17 30.0625 0.53125 0.2676149011 0.9769040942 0 0.2136782408 ) ( 5.65625 17 30.5 0.697265625 0.5703207254 0.9769040942 0 0.2136782408 ) ( 5.65625 17 30.5 0.53125 0.5703207254 0.9769040942 0 0.2136782408 ) ( 7.59375 17 30.0625 0.697265625 0.2676149011 0.9769040942 0 0.2136782408 ) ( 5.65625 17 30.5 0.7109332085 0.9395671487 0 1 0 ) ( 5.625 17 30.5 0.7109333277 0.939419508 0 1 0 ) ( 7.59375 17 30.0625 1.013671875 0.939419508 0 1 0 ) ( 7.59375 17 30.0625 0.7109265327 0.9491802454 0 1 0 ) ( 5.65625 17 30.5 1.013671875 0.9492185116 0 1 0 ) ( 7.59375 17 30.0625 0.302734375 0.8866784573 0.2136782408 0 0.9769040942 ) ( 7.625 17 30.0625 0.46875 0.8866784573 0.2136782408 0 0.9769040942 ) ( 5.65625 17 30.5 0.46875 0.896484375 0.2136782408 0 0.9769040942 ) ( 5.65625 17 30.5 0.302734375 0.8965177536 0.2136782408 0 0.9769040942 ) ( 5.65625 17 30.5 1 0 0.9769040942 0 0.2136782408 ) ( 5.625 17 30.5 1 0 0.9769040942 0 0.2136782408 ) ( 7.59375 17 30.0625 0 1 0.9769040942 0 0.2136782408 ) ( 7.625 17 30.0625 1 1 0.9769040942 0 0.2136782408 ) ( 5.65625 17 30.5 0 0 0.9769040942 0 0.2136782408 ) ( 5.625 17 30.5 0 0 0.9769040942 0 0.2136782408 ) ( 7.59375 17 30.0625 0.8104814291 0.6901836991 0 1 0 ) ( 5.65625 17 30.5 0.9316613078 0.6906604767 0 1 0 ) ( 7.625 17 30.0625 0.931687355 0.6946712136 0 1 0 ) ( 5.625 17 30.5 0.8105236292 0.6940877438 0 1 0 ) ( 5.65625 17 30.5 0.8105105162 0.6940876842 0 1 0 ) ( 7.59375 17 30.0625 0.302734375 0.103515625 0.2136782408 0 0.9769040942 ) ( 7.59375 17 30.0625 0.46875 0.103553921 0.2136782408 0 0.9769040942 ) ( 5.65625 17 30.5 0.46875 0.1131670028 0.2136782408 0 0.9769040942 ) ( 5.625 17 30.5 0.46875 0.1133146435 0.2136782408 0 0.9769040942 ) ( 5.65625 17 30.5 0.302734375 0.1131664068 0.2136782408 0 0.9769040942 ) ( 5.625 17 30.5 0.302734524 0.1131664068 0.2136782408 0 0.9769040942 ) 0 1 2 3 1 0 4 5 6 7 4 5 4 5 6 7 4 5 7 5 6 7 6 8 9 10 11 12 9 11 13 14 15 14 16 15 17 13 14 17 14 18 18 13 14 17 13 14 17 14 18 13 14 18 17 13 14 17 14 18 18 13 14 14 17 13 18 17 14 18 13 14 18 14 15 19 20 21 22 19 21 23 19 22 22 23 21 23 19 22 24 25 26 24 26 27 28 24 26 28 26 27 28 27 29 29 26 27 28 26 27 28 27 29 26 27 29 28 26 27 28 27 29 29 26 27 27 28 26 29 28 27 29 26 27 27 28 26 29 28 27 27 29 26 27 28 26 29 28 27 29 26 27 28 26 27 28 27 29 29 26 27 27 28 26 29 28 27 29 26 27 } } And here is how it looks after the fix: model { /* name = */ "func_static_2062" /* numSurfaces = */ 1 /* surface 0 */ { "textures/darkmod/decals/signs/sign_tea" /* numVerts = */ 24 /* numIndexes = */ 36 ( 7.59375 17 30.0625 0.53125 0.2676149011 0.9769040942 0 0.2136782408 ) ( 5.65625 17 30.5 0.697265625 0.5703207254 0.9769040942 0 0.2136782408 ) ( 5.65625 17 30.5 0.53125 0.5703207254 0.9769040942 0 0.2136782408 ) ( 7.59375 17 30.0625 0.697265625 0.2676149011 0.9769040942 0 0.2136782408 ) ( 7.59375 17 30.0625 0.7109265327 0.9491802454 0 1 0 ) ( 5.65625 17 30.5 0.7109333277 0.939419508 0 1 0 ) ( 7.59375 17 30.0625 1.013671875 0.939419508 0 1 0 ) ( 5.65625 17 30.5 1.013671875 0.9492185116 0 1 0 ) ( 7.59375 17 30.0625 0.302734375 0.8866784573 0.2136782408 0 0.9769040942 ) ( 7.59375 17 30.0625 0.46875 0.8866784573 0.2136782408 0 0.9769040942 ) ( 5.65625 17 30.5 0.46875 0.896484375 0.2136782408 0 0.9769040942 ) ( 5.65625 17 30.5 0.302734375 0.8965177536 0.2136782408 0 0.9769040942 ) ( 5.65625 17 30.5 1 0 0.9769040942 0 0.2136782408 ) ( 7.59375 17 30.0625 1 1 0.9769040942 0 0.2136782408 ) ( 7.59375 17 30.0625 0 1 0.9769040942 0 0.2136782408 ) ( 5.65625 17 30.5 0 0 0.9769040942 0 0.2136782408 ) ( 7.59375 17 30.0625 0.8104814291 0.6901836991 0 1 0 ) ( 5.65625 17 30.5 0.9316613078 0.6906604767 0 1 0 ) ( 7.59375 17 30.0625 0.931687355 0.6946712136 0 1 0 ) ( 5.65625 17 30.5 0.8104979396 0.6941475868 0 1 0 ) ( 7.59375 17 30.0625 0.302734375 0.103515625 0.2136782408 0 0.9769040942 ) ( 7.59375 17 30.0625 0.46875 0.103553921 0.2136782408 0 0.9769040942 ) ( 5.65625 17 30.5 0.46875 0.1133146435 0.2136782408 0 0.9769040942 ) ( 5.65625 17 30.5 0.302734375 0.1133146286 0.2136782408 0 0.9769040942 ) 0 1 2 3 1 0 4 5 6 4 6 7 8 9 10 11 8 10 12 13 14 15 12 14 16 17 18 19 16 18 20 21 22 23 20 22 } } 

The main problem was caused by the fact that "optimize" step relies on increased intermediate precision. Originally it was provided for free by x87 arithmetics, but now we need to use it explicitly. Also I think that this problem was the reason for tweaking compiler optimization of this cpp file on GCC. This algorithm receives a set of triangles in same plane, and tries to simplify this triangulation as much as possible. As the first step, it builds the graph of vertices and edges. Since it tries to work with any input, it also handles edge intersections: this happens in function SplitOriginalEdgesAtCrossings. For any pair of edges, it checks if they intersect (function EdgesCross, calling PointsStraddleLine, calling IsTriangleDegenerate and IsTriangleValid). Logically, it happens if two points of one edge are at different side of the the other edge and vice versa. Note that the case of a point lying on the edge also counts, i.e. Tjunctions are also considered as a cross here. When edges cross, their intersection point is computed by EdgeIntersection. If this point already exists (checked by FindOptVertex), then it is reused. In such case also one of the edges is usually not split, e.g. in case of Tjunction. Otherwise, a new point is created and both edges are splitted for sure. Now the main problem is that FindOptVertex does not use any tolerance when checking if vertices are the same. The vertices are equal only if they match precisely. The reason for this is that optimize algorithm is expected to be run after Tjunctions removal, and Tjunctions removal heals the mesh, so that neither close vertices nor Tjunctions remain in it. Tolerance is simply not needed in this case. Normally, mesh optimization is always launched after Tjunctions removal. But if surface has "discrete" material (this includes particleemitting materials), then Tjunctions removal is disabled for it. I'm not sure exactly what the reason is. The Tjunctions removal is done on many different scales, and some of the things it does really should not happen to particleemitting surfaces. So for discrete surfaces Tjunctions removal is not done, so optimization algorithm creates many almostequal vertices at Tjunctions. This makes it impossible to merge triangles back. I simply used double precision in critical places of the code (FindOptVertex, VertexBetween, IsTriangleDegenerate, IsTriangleValid, PointInTri, EdgeIntersection). Using double precision allows to compute cross and dot products precisely. As the result, intersection point at Tjunctions precisely matches the vertex. This fixes all the problems for me, and makes tessellation of rain patches perfect. 

As for rev 8557, I simply decided to apply double precision in all places which are used to compute triangle vertices in dmap. These are mainly idWinding splitting algorithms, which need good precision in all contexts (they even contain special paths for axisaligned planes to improve precision). Also applied double to some triangle area computations (they are used to check if triangle is degenerate), and idWinding plane calculation. The plane computation was particularly bad, because it returned very imprecise results if first two vertices of the winding happen to be close to each other. 

Date Modified  Username  Field  Change 

01.02.2020 05:22  stgatilov  New Issue  
01.02.2020 05:22  stgatilov  Status  new => assigned 
01.02.2020 05:22  stgatilov  Assigned To  => stgatilov 
01.02.2020 05:22  stgatilov  Tag Attached: particle  
01.02.2020 05:36  stgatilov  Relationship added  related to 0004957 
02.02.2020 16:47  stgatilov  Note Added: 0012172  
02.02.2020 16:57  stgatilov  Note Added: 0012173  
02.02.2020 16:58  stgatilov  Note Edited: 0012173  
02.02.2020 17:18  stgatilov  Note Added: 0012174  
02.02.2020 17:21  stgatilov  Note Added: 0012175  
02.02.2020 17:21  stgatilov  Status  assigned => resolved 
02.02.2020 17:21  stgatilov  Resolution  open => fixed 
02.02.2020 17:21  stgatilov  Fixed in Version  => TDM 2.08 
12.04.2020 05:17  stgatilov  Relationship added  related to 0005212 
05.01.2021 18:20  stgatilov  Relationship added  related to 0005486 