regression_tests/q3map2/disappearing_sliver/README.txt

   1 DESCRIPTION OF PROBLEM:
   2 =======================
   3
   4 The example map, maps/disappearing_sliver.map, contains an example of this bug.
   5 There are 6 walls in the map, and one tall thin triangular sliver brush in the
   6 middle of the room (7 brushes total).  Only one face of the sliver in the
   7 middle of the room is a draw surface.  The bug is that this sliver surface is
   8 not rendered in the compiled BSP.  Note that the sliver brush was hand-crafted
   9 to demonstrate the bug.  If you re-save the map, Radiant might adjust the
  10 order in which the planes on the brush are defined, and this might, as a side
  11 effect, get rid of the immediate bug.
  12
  13 To trigger the bug, compile the map; you don't need -vis or -light.  Only
  14 -bsp (the first q3map2 stage) is necessary to trigger the bug.  The only
  15 entities in the map are 2 lights and a single info_player_deathmatch, so the
  16 map will compile for any Q3 mod.
  17
  18
  19 SOLUTION TO PROBLEM:
  20 ====================
  21
  22 Several days were spent studying this problem in great detail.
  23
  24 The fix for this problem was to make the outcome of the VectorNormalize()
  25 function libs/mathlib/mathlib.c more accurate.  The previous code in this
  26 function looks something like this:
  27
  28   vec_t length, ilength; // vec_t is a typedef for 32 bit float.
  29
  30   /* Compute length */
  31
  32   ilength = 1.0f/length;
  33   out[0] = in[0]*ilength;
  34   out[1] = in[1]*ilength;
  35   out[2] = in[2]*ilength;
  36
  37 As you can see, we are introducing a lot of extra error into our normalized
  38 vector by multiplying by the reciprocal length instead of outright dividing
  39 by the length.  The new fixed code looks like this:
  40
  41   out[0] = in[0]/length;
  42   out[1] = in[1]/length;
  43   out[2] = in[2]/length;
  44
  45 And we get rid of the recpirocal length ilength altogether.  Even the
  46 slightest math errors are magnified in successive calls to linear algebra
  47 functions.
  48
  49 The change described above was commmitted to GtkRadiant trunk as revision r363.
  50
  51
  52 POSSIBLE SIDE EFFECTS:
  53 ======================
  54
  55 The only negative side effect is that compilation of a map might take longer
  56 due to an increased number of divide operations.  (I'm actually not sure if
  57 that is indeed the case.)  Another side effect might be that if you're used
  58 to a map being broken (missing triangles) or having "sparklies" between
  59 brushes, those might be gone now.  :-)
  60
  61
  62 IN-DEPTH DISCUSSION:
  63 ====================
  64
  65 VectorNormalize() is used very frequently in Radiant and tools code.  My goal
  66 for this fix was to make the least amount of code change but still be able to
  67 demonstrate a significant improvement in math accuracy (including a fix to
  68 the test case).  At the same time don't risk that any other bugs pop up as a
  69 side effect of this change.
  70
  71 Here is the sequence of calls (stack trace) that cause the example bug to
  72 happen:
  73
  74   main() in main.c -->
  75     BSPMain() in bsp.c -->
  76       LoadMapFile() in map.c -->
  77         ParseMapEntity() in map.c -->
  78           ParseBrush() in map.c -->
  79             FinishBrush() in map.c -->
  80               CreateBrushWindings() in brush.c -->
  81                 ChopWindingInPlace() in polylib.c
  82
  83 What basically happens in this sequence of calls is that a brush is parsed
  84 out of the map file, "infinite" planes are created for each brush face, and
  85 then the planes are "intersected" to find the exact vertex topologies of each
  86 brush face.  The vertex topology of the visible face of the sliver (in the
  87 example map) gets computed with a significant amount of math error.  If we
  88 did our math with infinite precision, the sliver face would have the following
  89 vertices:
  90
  91   (67 -1022 0)
  92   (88 -892 -768)
  93   (134 -1015 0)
  94
  95 In fact, if you open the map file (disappearing_sliver.map), you can actually
  96 see these exact points embedded in the third plane defined on brush 0.
  97
  98 I managed to print out the actual computed vertices of the sliver face before
  99 and after this bug fix.  Basically this is printed out after all the
 100 ChopWindingInPlace() calls in the above stack trace:
 101
 102   (66.984695 -1021.998657 0.000000)
 103   (87.989571 -891.969116 -768.174316)
 104   (133.998917 -1014.997314 0.000000)
 105
 106 (If you want to print this out for yourself, print out the coordinates of the
 107 winding_t "w" parameter right after the ChopWindingInPlace() call in
 108 CreateBrushWindings() in brush.c.)
 109
 110 The same vertices after the bugfix have the following coordinates:
 111
 112   (67.000229 -1021.998657 0.000000)
 113   (88.000175 -891.999146 -767.997437)
 114   (133.999146 -1014.998779 0.000000)
 115
 116 As you can see, the vertices after the fix are substantially more accurate,
 117 and all it took was an improvement to VectorNormalize().
 118
 119 The problem before the fix was the Z coordinate of the second point, namely
 120 -768.174316.  There is a lot of "snap to nearest 1/8 unit" and "epsilon 0.1"
 121 code used throughout q3map2.  0.174 is greater than the 0.1 epsilon, and that
 122 is the problem.
 123
 124   main() in main.c -->
 125     BSPMain() in bsp.c -->
 126       ProcessModels() in bsp.c -->
 127         ProcessWorldModel() in bsp.c -->
 128           ClipSidesIntoTree() in surface.c -->
 129             ClipSideIntoTree_r() in surface.c -->
 130               ClipWindingEpsilon() in polylib.c
 131
 132 Now what ClipWindingEpsilon() does is, since -768.174316 reaches below the
 133 plane z = -768 (and over the 0.1 epsilon), it clips the winding_t and creates
 134 two points where there used to be only one.
 135
 136   main() in main.c -->
 137     BSPMain() in bsp.c -->
 138       ProcessModels() in bsp.c -->
 139         ProcessWorldModel() in bsp.c
 140           FixTJunctions() in tjunction.c
 141             FixBrokenSurface() in tjunction.c
 142
 143 FixBrokenSurface() realizes that there are two points very close together
 144 (in our case, since they were "snapped", the are coincident in fact).
 145 Therefore it reports the surface to be broken.  The drawable surface is
 146 deleted as a result.
 147
 148
 149 RELATED BUGS:
 150 =============
 151
 152 A lot of the math operations in the Radiant codebase cut corners like this
 153 example demonstrates.  There is a lot more code like this that can be
 154 improved upon.  In fact, it may make sense to use 64 bit floating points in
 155 some important math operations (and then convert back to 32 bit for the return
 156 values).  Plans are to look at similar code and improve it.
 157
 158 The following "issue" was discovered while doing research for this bug.
 159 If FixBrokenSurface() sees two points very close together, it attempts to
 160 partially fix the problem (the code is not complete) and then returns false,
 161 which means that the surface is broken and should not be used.  So in fact
 162 it attempts to fix the problem partially but none of the fixes are used.
 163 It seems that FixBrokenSurface() should be fixed to completely fix the case
 164 where there are two close points, and should report the surface as fixed.
 165 This might be a destabilizing change however, so if this is indeed fixed, it
 166 may make sense to activate the fix only if a certain flag is set.