[Gtkradiant] Finally, the cause of q3map2 math problems

[Forest Hale]

On 12/29/2010 01:46 AM, Nerius Landys wrote:
> 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.)

Yep, exactly what I observed in my tests in the past, and why I was forced to upgrade my portal generation (DarkPlaces engine does a bsp2prt stage at load - one of the most horrendous cases of 
precision error one can imagine) to double precision years back.

> 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).

It's possible to produce a bounded base winding by axial projection onto the plane, of the known brush dimensions - but this is a bit of a chicken and egg problem (produce large sloppy brush to get 
bounds, then produce "more precise" geometry by using the bounded quads).

> 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)?

This solution is by no means perfect, but it allows an epsilon to be extremely small comparatively (+30 bits of mantissa works wonders for THIS exact kind of problem), furthermore it hides some of the 
degradation one gets on very large point locations (they inherently are not as precise as their lesser magnitude brethren, and this causes deformed polygons, which can have interesting consequences in 
intermediate results).

Worth noting that in the Q1 tools, vec_t defaulted to double, the file format structures were intentionally defined with float, so that conversion occurred when loading/saving the bsp into the static 
arrays (hurray for crude programming and large virtual address spaces, but that's a rant for another day).

I was always fond of this approach, if only because it allowed the entire compile to operate at double precision, and this particularly matters on some very thin wedge-shaped BSP leafs - generating 
the portals at single precision was very error-prone, granted it used the same polygon generation and clipping routines in question here!

> 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).

I do want to give some food for thought, in case it is helpful; it is possible to produce points from plane intersections without a basewinding, I am not enough of a math whiz to work out how to 
calculate these intersections of 3D planes however, I only speculate it is possible.

The main novelty of producing points from intersections is that it yields the same point no matter which way you approach it, where as the current approach has a certain cumulative error due to 
intermediate results (I.E. the order of the clipping yields minutely different point locations).

A side note: 64bit to 32bit float conversions are quite slow on x86/amd64, but this is not an important issue for a map compiler's geometry stage.

-- 
LordHavoc
Author of DarkPlaces Quake1 engine - http://icculus.org/twilight/darkplaces
Co-designer of Nexuiz - http://alientrap.org/nexuiz
"War does not prove who is right, it proves who is left." - Unknown
"Any sufficiently advanced technology is indistinguishable from a rigged demo." - James Klass
"A game is a series of interesting choices." - Sid Meier