[Gtkradiant] Finally, the cause of q3map2 math problems

[Nerius Landys]

Guys, I have discovered the main cause (or at least a very significant
cause) of the q3map2 math inaccuracy problems.  I discovered this
while analyzing a very specific brush in excruciating detail (I even
had my calculator out and was taking notes).

The problem that I'm about to describe may be difficult to grasp at
first, but after thinking about it for a while you may be able to
digest it.  In fact I'm still in the process of digesting this
problem, and I hope to wake up tomorrow morning with a fresh mind full
of new ideas.

The problem has to do with limited accuracy (32 bit float) and "base
windings".  A base winding is nothing more than 4 coplanar points
(forming a "rectangle") that are at very very great distance from the
origin.  A base winding is used to describe each plane of a brush at a
certain point during brush processing.  These base windings are later
"clipped" or "cropped" to form the actual brush faces.  So, you can
think of a base winding as an infinite plane that is the face of a
brush, and it gets clipped into the actual finite brush face
consisting of discrete vertexes.

Now, the problem is caused by very large base windings, meaning that
the points are too far from the origin.  Let me illustrate the problem
by reducing it to a case where we approximate a discrete line segment
(with 2 endpoints) by a very long line segment.  The very long segment
is analogous to the base winding.

To start, let's approximate the line segment in 2-space defined by the
endpoints (-1,0)->(2,1).  So a "base winding" for this segment could
be something like (-4,-1)->(5,2).  Note that such a base winding
overlaps the original segment perfectly and there is no error
involved.  However, such a base winding is very small.  In reality,
our base winding will be much much longer and likely won't have
perfect integer endpoint coordinates.

Now, think about the following.  The original segment is mostly
horizontal.  Assume that there will be some amount of error in the
endpoints chosen for the base winding (this is inevitable for
non-axial windings).  So for a certain length of base winding, the
error, let's say, is plus/minus epsilon.  A very bad case is where the
error on both endpoints happens to be at the +epsilon or both at
-epsilon.  In that case the base winding line will be higher or lower
by that amount (like I said our original line is mostly horizontal).
Now, when you make the base winding longer by a factor of two, you are
also increasing the epsilon error by a factor of two (because of the
way floating point numbers work internally - meaning, if your float
had a resolution of 0.25 at the million range, it will only have a
resolution of 0.5 at the 2 million range).  So now your line can by
higher or lower by double the original error amount [when you double
the base winding size].  If the base winding is huge, the epsilon
error becomes large as well.  The error will only manifest itself in
some cases, if the errors are both at the maximum positive value or
both at the minimum negative value (well that's a simplified view at
least).

Now I tested this theory about this problem by increasing the base
winding size in q3map2 by a factor of 2 repeatedly.  It turns out that
the errors produced are, in general, twice as large when the base
winding is doubled.  (Actually the upper bound on the error size
doubles, not every error.)

The q3map2 code relies on a large base winding in its logic (LordHavoc
will verify that).  Therefore we cannot make the base winding any
smaller unless we want to totally re-engineer the q3map2 internals
(which we don't).

The suggested fix to this problem is to add resolution for certain
math operations such as this one, by moving from a 32 bit float
(vec_t) to an outright double (which I think is 64 bit on all systems
we're running on, am I correct)?

I did some digging in the code and there there is very little use of
the double type.  So one must probably proceed with caution
presumably.

There are additional problems that manifest themselves due to the
initial base winding inaccuracy error, but I don't think we need to
address those quite yet (one thing at a time).

- Rambetter