From fca02eb3fbc4ece0ddec2f42d95d91eeba32f61c Mon Sep 17 00:00:00 2001 From: rambetter Date: Mon, 27 Dec 2010 08:08:00 +0000 Subject: [PATCH] Fixing "disappearing_sliver" bug. A regression test is included. This is a bug in q3map2. Please read regression_tests/q3map2/disappearing_sliver/README.txt for more info. git-svn-id: https://zerowing.idsoftware.com/svn/radiant/GtkRadiant/trunk@363 8a3a26a2-13c4-0310-b231-cf6edde360e5 --- libs/mathlib/mathlib.c | 9 +- .../q3map2/disappearing_sliver/README.txt | 164 ++++++++++++++++++ .../maps/disappearing_sliver.map | 84 +++++++++ .../radiant_regression_tests/tile.tga | Bin 0 -> 812 bytes 4 files changed, 252 insertions(+), 5 deletions(-) create mode 100644 regression_tests/q3map2/disappearing_sliver/README.txt create mode 100644 regression_tests/q3map2/disappearing_sliver/maps/disappearing_sliver.map create mode 100644 regression_tests/q3map2/disappearing_sliver/textures/radiant_regression_tests/tile.tga diff --git a/libs/mathlib/mathlib.c b/libs/mathlib/mathlib.c index b9b7b869..33945cde 100644 --- a/libs/mathlib/mathlib.c +++ b/libs/mathlib/mathlib.c @@ -127,7 +127,7 @@ void _VectorCopy (vec3_t in, vec3_t out) } vec_t VectorNormalize( const vec3_t in, vec3_t out ) { - vec_t length, ilength; + vec_t length; length = (vec_t)sqrt (in[0]*in[0] + in[1]*in[1] + in[2]*in[2]); if (length == 0) @@ -136,10 +136,9 @@ vec_t VectorNormalize( const vec3_t in, vec3_t out ) { return 0; } - ilength = 1.0f/length; - out[0] = in[0]*ilength; - out[1] = in[1]*ilength; - out[2] = in[2]*ilength; + out[0] = in[0]/length; + out[1] = in[1]/length; + out[2] = in[2]/length; return length; } diff --git a/regression_tests/q3map2/disappearing_sliver/README.txt b/regression_tests/q3map2/disappearing_sliver/README.txt new file mode 100644 index 00000000..5914cc3d --- /dev/null +++ b/regression_tests/q3map2/disappearing_sliver/README.txt @@ -0,0 +1,164 @@ +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. + + +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, print out the coordinates of the +winding_t "w" parameter right after the ChopWindingInPlace() call in +CreateBrushWindings() in brush.c.) + +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. diff --git a/regression_tests/q3map2/disappearing_sliver/maps/disappearing_sliver.map b/regression_tests/q3map2/disappearing_sliver/maps/disappearing_sliver.map new file mode 100644 index 00000000..821497d4 --- /dev/null +++ b/regression_tests/q3map2/disappearing_sliver/maps/disappearing_sliver.map @@ -0,0 +1,84 @@ +// entity 0 +{ +"classname" "worldspawn" +// brush 0 +{ +( -704 -1152 0 ) ( 4480 -1152 0 ) ( -704 -1152 -768 ) common/caulk 0 0 0 0.500000 0.500000 134217728 4 0 +( 67 -1022 0 ) ( 67 -4096 0 ) ( 88 -892 -768 ) common/caulk 0 0 0 0.500000 0.500000 134217728 4 0 +( 67 -1022 0 ) ( 88 -892 -768 ) ( 134 -1015 0 ) radiant_regression_tests/tile 0 0 0 0.500000 0.500000 134217728 0 0 +( 88 -892 -768 ) ( 88 -4096 -768 ) ( 134 -1015 0 ) common/caulk 0 0 0 0.500000 0.500000 134217728 4 0 +( 134 -1015 0 ) ( 134 -4096 0 ) ( 67 -1022 0 ) common/caulk 0 0 0 0.500000 0.500000 134217728 4 0 +} +// brush 1 +{ +( 584 -640 -768 ) ( 520 -640 -768 ) ( 520 -1160 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 528 -1160 320 ) ( 528 -640 320 ) ( 592 -640 320 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 528 -1152 0 ) ( 592 -1152 0 ) ( 592 -1152 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 520 -1160 0 ) ( 520 -640 0 ) ( 520 -640 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 584 -640 0 ) ( 520 -640 0 ) ( 520 -640 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 512 -640 0 ) ( 512 -1160 0 ) ( 512 -1160 -768 ) radiant_regression_tests/tile 0 0 0 0.500000 0.500000 0 0 0 +} +// brush 2 +{ +( 512 -552 -768 ) ( -296 -552 -768 ) ( -296 -640 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( -296 -640 320 ) ( -296 -552 320 ) ( 512 -552 320 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( -296 -640 320 ) ( 512 -640 320 ) ( 512 -640 -768 ) radiant_regression_tests/tile 0 0 0 0.500000 0.500000 0 0 0 +( 512 -640 320 ) ( 512 -552 320 ) ( 512 -552 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 528 -632 320 ) ( -280 -632 320 ) ( -280 -632 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( -512 -536 320 ) ( -512 -624 320 ) ( -512 -624 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +} +// brush 3 +{ +( -512 -648 -768 ) ( -536 -648 -768 ) ( -536 -1152 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( -536 -1152 320 ) ( -536 -648 320 ) ( -512 -648 320 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( -536 -1152 320 ) ( -512 -1152 320 ) ( -512 -1152 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( -512 -1152 320 ) ( -512 -648 320 ) ( -512 -648 -768 ) radiant_regression_tests/tile 0 0 0 0.500000 0.500000 0 0 0 +( -512 -640 320 ) ( -536 -640 320 ) ( -536 -640 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( -520 -648 320 ) ( -520 -1152 320 ) ( -520 -1152 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +} +// brush 4 +{ +( 512 -640 320 ) ( 24 -640 320 ) ( 24 -1152 320 ) radiant_regression_tests/tile 0 0 0 0.500000 0.500000 0 0 0 +( 48 -1152 328 ) ( 48 -640 328 ) ( 536 -640 328 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 24 -1152 440 ) ( 512 -1152 440 ) ( 512 -1152 328 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 512 -1152 440 ) ( 512 -640 440 ) ( 512 -640 328 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 512 -640 440 ) ( 24 -640 440 ) ( 24 -640 328 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( -512 -640 464 ) ( -512 -1152 464 ) ( -512 -1152 352 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +} +// brush 5 +{ +( -328 -896 -776 ) ( -512 -896 -776 ) ( -512 -1152 -776 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( -512 -1152 -768 ) ( -512 -896 -768 ) ( -328 -896 -768 ) radiant_regression_tests/tile 0 0 0 0.500000 0.500000 0 0 0 +( -512 -1152 -768 ) ( -328 -1152 -768 ) ( -328 -1152 -776 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( -512 -896 -768 ) ( -512 -1152 -768 ) ( -512 -1152 -776 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 512 -1152 -768 ) ( 512 -896 -768 ) ( 512 -896 -776 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( -368 -640 -824 ) ( -856 -640 -824 ) ( -856 -640 -960 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +} +// brush 6 +{ +( -512 -1168 320 ) ( -512 -1584 320 ) ( -512 -1584 0 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 1152 -1152 320 ) ( 176 -1152 320 ) ( 176 -1152 0 ) radiant_regression_tests/tile 0 0 0 0.500000 0.500000 0 0 0 +( 512 -1576 320 ) ( 512 -1160 320 ) ( 512 -1160 0 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 208 -1160 320 ) ( 1184 -1160 320 ) ( 1184 -1160 0 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( 176 -1568 320 ) ( 176 -1152 320 ) ( 1152 -1152 320 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +( -256 -1152 -768 ) ( -520 -1152 -768 ) ( -520 -1192 -768 ) common/caulk 0 0 0 0.500000 0.500000 0 4 0 +} +} +// entity 1 +{ +"light" "3000" +"origin" "0 -768 -480" +"classname" "light" +} +// entity 2 +{ +"angle" "270" +"origin" "0 -712 -640" +"classname" "info_player_deathmatch" +} +// entity 3 +{ +"classname" "light" +"origin" "0 -832 160" +"light" "3000" +} diff --git a/regression_tests/q3map2/disappearing_sliver/textures/radiant_regression_tests/tile.tga b/regression_tests/q3map2/disappearing_sliver/textures/radiant_regression_tests/tile.tga new file mode 100644 index 0000000000000000000000000000000000000000..2154015fc4c3cac9f1b6a3d8100faaa9075c1e5a GIT binary patch literal 812 zcmZQz;9`IQ2L=ZQ35Ndv|NqYi3W4Y$$p*T8KFIALKa8^J9}Yu2{Q#2;7=#3cx`ufM Qd;0t7M!0$Uxau(g0MliYy#N3J literal 0 HcmV?d00001 -- 2.39.2