 |
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 double-precision 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: T-junctions removal and optimization. T-junctions 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 T-junctions is very clever, because it also heals the mesh in process. It takes minimum integer-valued 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. T-junctions 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 round-off errors. Some of them get snapped down, others are snapped up. As the result, T-junctions 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.5-eps)/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 "round-down" and "round-up". 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. T-junctions 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 T-junction. 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 T-junctions removal, and T-junctions removal heals the mesh, so that neither close vertices nor T-junctions remain in it. Tolerance is simply not needed in this case. Normally, mesh optimization is always launched after T-junctions removal. But if surface has "discrete" material (this includes particle-emitting materials), then T-junctions removal is disabled for it. I'm not sure exactly what the reason is. The T-junctions removal is done on many different scales, and some of the things it does really should not happen to particle-emitting surfaces. So for discrete surfaces T-junctions removal is not done, so optimization algorithm creates many almost-equal vertices at T-junctions. 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 T-junctions 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 axis-aligned 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. |
- Anonymous
