[Gtkradiant] State of Rambetter's q3map2 fixes
Nerius Landys
nlandys at gmail.com
Tue Jan 4 19:58:59 CST 2011
Hi guys I just wanted to give everyone a brief status report.
As you may already know, I'm working on addressing some bugs in
q3map2, mostly related to "disappearing triangles". These bugs are
mostly caused by imprecision in math calculations (the "disappearing
triangles" problem will tend to happen when a vertex is off by more
than 0.1 units).
I'm currently doing this work in the "Rambetter-math-fix-experiments"
branch of GtkRadiant. My goal is to leave the legacy code intact 100%
and control which code is used via #if statements. This is the way it
currently works. Also, this way I can easily measure which maps are
broken with which code version. In fact I have more than one #define
defined, they are for various fixes.
The current state of Rambetter-math-fix-experiments is that it's
"working" and "significantly improved" with respect to disappearing
triangle issues. I stopped drinking coffee (and black tea) on New
Year's Eve, and I've been suffering from severe caffeine withdrawal
symptoms for the past 4-5 days. My hope is that the decaffeinated
Rambetter will understand code that the caffeinated Rambetter was
attempting to write.. I should be productive again by the weekend.
I did discover one new bug just by looking at the code and thinking
about it. The bug is caused by the fact that the data type for plane
distance is 32 bit float, which isn't enough resolution. A plane is
defined by a unit normal (float triple) and a distance from origin
(distance is the "closest distance to origin").
Here is the problem. The plane distance can become as large as 2^16,
or 65536. In 32 bit floating point numbers, the "epsilon around one"
(which is the smallest value that can be added to 1.0 such that the
number will take on a value greater than 1.0) is approximately
0.0000001. If you multiply that by 2^16, you get 0.007, more or less.
So the "epsilon" at a very far point is quite large (0.007).
Now, the problem is that two planes with the same normal and distance
0.006 apart will be considered equal. (In fact currently the "plane
distance epsilon" in the code is defined to be 0.01.)
The problem happens when we have a brush with two planes that form a
very sharp angle (say, maybe 8 degrees or so). If one of the planes
of the brush is approximated with an error of 0.01 (our current plane
distance epsilon), the intersection of the two sharp-angled planes can
easily be off by 0.1 units or more. (The error is multiplied very
quickly when you perform intersection computations of sharp angles.)
0.1 is the point at which really big problems such as disappearing
triangles start to happen.
The solution is to decrease the plane distance epsilon from 0.01 to
something more like 0.001 (a factor of 10). However we cannot do this
because the resolution of 32 bit floats at great plane distance
exceeds this number. So, the only choices are to constrain world
coordinates to something smaller than 2^16 or move certain math
operations to 64 bit floating points.
I'm going to try to address this issue. First, I will create a
regression test that demonstrates the problem (it will take a map with
8 brushes total, 6 walls and 2 things in the center). Then, I will
see what I can do by adding an extra "accurate distance" field to the
plane structure that will be used and maintained only be certain
operations (in particular the operations that compute the brush
windings in the -bsp stage of q3map2).
By the way, I don't think this problem is nearly as mission-critical
as the problem already addressed, which had to do with math
imprecision when calculating the "base windings" (described in a
previous email).
- Rambetter
More information about the Gtkradiant
mailing list