X-Git-Url: http://de.git.xonotic.org/?a=blobdiff_plain;f=misc%2Fmediasource%2Fextra%2Fnetradiant-src%2Fregression_tests%2Fq3map2%2Fdisappearing_sliver%2FREADME.txt;fp=misc%2Fmediasource%2Fextra%2Fnetradiant-src%2Fregression_tests%2Fq3map2%2Fdisappearing_sliver%2FREADME.txt;h=0000000000000000000000000000000000000000;hb=65bc0125990fdbce3dd3232d61f1554cb7e317cb;hp=a65d9203cc80596488e9b468f2cb031d34ae4534;hpb=4dab6b8497e278118a8237e150d276e91501bfb0;p=voretournament%2Fvoretournament.git diff --git a/misc/mediasource/extra/netradiant-src/regression_tests/q3map2/disappearing_sliver/README.txt b/misc/mediasource/extra/netradiant-src/regression_tests/q3map2/disappearing_sliver/README.txt deleted file mode 100644 index a65d9203..00000000 --- a/misc/mediasource/extra/netradiant-src/regression_tests/q3map2/disappearing_sliver/README.txt +++ /dev/null @@ -1,183 +0,0 @@ -DESCRIPTION OF PROBLEM: -======================= - -The example map, maps/disappearing_sliver.map, contains an example of this bug. -There are 6 walls in the map, and one tall thin triangular sliver brush in the -middle of the room (7 brushes total). Only one face of the sliver in the -middle of the room is a draw surface. The bug is that this sliver surface is -not rendered in the compiled BSP. Note that the sliver brush was hand-crafted -to demonstrate the bug. If you re-save the map, Radiant might adjust the -order in which the planes on the brush are defined, and this might, as a side -effect, get rid of the immediate bug. - -To trigger the bug, compile the map; you don't need -vis or -light. Only --bsp (the first q3map2 stage) is necessary to trigger the bug. The only -entities in the map are 2 lights and a single info_player_deathmatch, so the -map will compile for any Q3 mod. - - -SOLUTION TO PROBLEM: -==================== - -Several days were spent studying this problem in great detail. - -The fix for this problem was to make the outcome of the VectorNormalize() -function libs/mathlib/mathlib.c more accurate. The previous code in this -function looks something like this: - - vec_t length, ilength; // vec_t is a typedef for 32 bit float. - - /* Compute length */ - - ilength = 1.0f/length; - out[0] = in[0]*ilength; - out[1] = in[1]*ilength; - out[2] = in[2]*ilength; - -As you can see, we are introducing a lot of extra error into our normalized -vector by multiplying by the reciprocal length instead of outright dividing -by the length. The new fixed code looks like this: - - out[0] = in[0]/length; - out[1] = in[1]/length; - out[2] = in[2]/length; - -And we get rid of the recpirocal length ilength altogether. Even the -slightest math errors are magnified in successive calls to linear algebra -functions. - -The change described above was commmitted to GtkRadiant trunk as revision 363. - - -POSSIBLE SIDE EFFECTS: -====================== - -The only negative side effect is that compilation of a map might take longer -due to an increased number of divide operations. (I'm actually not sure if -that is indeed the case.) Another side effect might be that if you're used -to a map being broken (missing triangles) or having "sparklies" between -brushes, those might be gone now. :-) - - -IN-DEPTH DISCUSSION: -==================== - -VectorNormalize() is used very frequently in Radiant and tools code. My goal -for this fix was to make the least amount of code change but still be able to -demonstrate a significant improvement in math accuracy (including a fix to -the test case). At the same time don't risk that any other bugs pop up as a -side effect of this change. - -Here is the sequence of calls (stack trace) that cause the example bug to -happen: - - main() in main.c --> - BSPMain() in bsp.c --> - LoadMapFile() in map.c --> - ParseMapEntity() in map.c --> - ParseBrush() in map.c --> - FinishBrush() in map.c --> - CreateBrushWindings() in brush.c --> - ChopWindingInPlace() in polylib.c - -What basically happens in this sequence of calls is that a brush is parsed -out of the map file, "infinite" planes are created for each brush face, and -then the planes are "intersected" to find the exact vertex topologies of each -brush face. The vertex topology of the visible face of the sliver (in the -example map) gets computed with a significant amount of math error. If we -did our math with infinite precision, the sliver face would have the following -vertices: - - (67 -1022 0) - (88 -892 -768) - (134 -1015 0) - -In fact, if you open the map file (disappearing_sliver.map), you can actually -see these exact points embedded in the third plane defined on brush 0. - -I managed to print out the actual computed vertices of the sliver face before -and after this bug fix. Basically this is printed out after all the -ChopWindingInPlace() calls in the above stack trace: - - (66.984695 -1021.998657 0.000000) - (87.989571 -891.969116 -768.174316) - (133.998917 -1014.997314 0.000000) - -(If you want to print this out for yourself, use winding_logging.patch.) - -The same vertices after the bugfix have the following coordinates: - - (67.000229 -1021.998657 0.000000) - (88.000175 -891.999146 -767.997437) - (133.999146 -1014.998779 0.000000) - -As you can see, the vertices after the fix are substantially more accurate, -and all it took was an improvement to VectorNormalize(). - -The problem before the fix was the Z coordinate of the second point, namely --768.174316. There is a lot of "snap to nearest 1/8 unit" and "epsilon 0.1" -code used throughout q3map2. 0.174 is greater than the 0.1 epsilon, and that -is the problem. - - main() in main.c --> - BSPMain() in bsp.c --> - ProcessModels() in bsp.c --> - ProcessWorldModel() in bsp.c --> - ClipSidesIntoTree() in surface.c --> - ClipSideIntoTree_r() in surface.c --> - ClipWindingEpsilon() in polylib.c - -Now what ClipWindingEpsilon() does is, since -768.174316 reaches below the -plane z = -768 (and over the 0.1 epsilon), it clips the winding_t and creates -two points where there used to be only one. - - main() in main.c --> - BSPMain() in bsp.c --> - ProcessModels() in bsp.c --> - ProcessWorldModel() in bsp.c - FixTJunctions() in tjunction.c - FixBrokenSurface() in tjunction.c - -FixBrokenSurface() realizes that there are two points very close together -(in our case, since they were "snapped", the are coincident in fact). -Therefore it reports the surface to be broken. The drawable surface is -deleted as a result. - - -RELATED BUGS: -============= - -A lot of the math operations in the Radiant codebase cut corners like this -example demonstrates. There is a lot more code like this that can be -improved upon. In fact, it may make sense to use 64 bit floating points in -some important math operations (and then convert back to 32 bit for the return -values). Plans are to look at similar code and improve it. - -The following "issue" was discovered while doing research for this bug. -If FixBrokenSurface() sees two points very close together, it attempts to -partially fix the problem (the code is not complete) and then returns false, -which means that the surface is broken and should not be used. So in fact -it attempts to fix the problem partially but none of the fixes are used. -It seems that FixBrokenSurface() should be fixed to completely fix the case -where there are two close points, and should report the surface as fixed. -This might be a destabilizing change however, so if this is indeed fixed, it -may make sense to activate the fix only if a certain flag is set. - - -MORE NOTES: -=========== - -As stated above, the accuracy after revision 363 is: - - (67.000229 -1021.998657 0.000000) - (88.000175 -891.999146 -767.997437) - (133.999146 -1014.998779 0.000000) - -A further change was committed for a related problem in revision 377. After -this change: - - (66.99955750 -1022.00262451 0.00000000) - (87.99969482 -892.00170898 -768.00524902) - (133.99958801 -1015.00195312 0.00000000) - -The results look similar with respect to the amount of error present.