Map UV calculation issue

[Paril]

This is a legacy issue that spawned from the fact that Quake and Quake II used x87 float calculations. In some very very specific cases, clients compiled in either x86 or x64 mode without the proper changes will generate larger results for surface extents than are actually in the map, causing lightmap corruption on some surfaces. They're normally surfaces with very imprecise planes (like imported obj2map geometry).

This was an issue that we tackled in editors by forcing the calculations to be done against a long double, which in both x86 and x64 mode generate results much closer to the original x87 floating point code (which was an 80-bit floating point intermediate value).

I don't have the time atm to write out a full patch but here's a fixed build_surface_poly which seems to work in my testing in matching the results from ericw-tools:

#define LDDotProduct(x,y)         ((long double)((x)[0])*(long double)((y)[0])+(long double)((x)[1])*(long double)((y)[1])+(long double)((x)[2])*(long double)((y)[2]))

static void build_surface_poly(mface_t *surf, vec_t *vbo)
{
    msurfedge_t *src_surfedge;
    mvertex_t *src_vert;
    medge_t *src_edge;
    mtexinfo_t *texinfo = surf->texinfo;
    vec2_t scale, mins, maxs;
	long double tc[2];
    int i, bmins[2], bmaxs[2];
    uint32_t color;

    surf->texnum[0] = texinfo->image->texnum;
    surf->texnum[1] = 0;

    color = color_for_surface(surf);

    // convert surface flags to state bits
    surf->statebits = GLS_DEFAULT;
    if (gl_static.use_shaders) {
        if (!(surf->drawflags & SURF_TRANS_MASK)) {
            surf->statebits |= GLS_TEXTURE_REPLACE;
        }
        if (!(surf->drawflags & SURF_COLOR_MASK)) {
            surf->statebits |= GLS_INTENSITY_ENABLE;
        }
    } else {
        if (!(surf->drawflags & SURF_COLOR_MASK)) {
            surf->statebits |= GLS_TEXTURE_REPLACE;
        }
    }

    if (surf->drawflags & SURF_WARP) {
        surf->statebits |= GLS_WARP_ENABLE;
    }

    if (surf->drawflags & SURF_TRANS_MASK) {
        surf->statebits |= GLS_BLEND_BLEND | GLS_DEPTHMASK_FALSE;
    } else if (surf->drawflags & SURF_ALPHATEST) {
        surf->statebits |= GLS_ALPHATEST_ENABLE;
    }

    if (surf->drawflags & SURF_FLOWING) {
        surf->statebits |= GLS_FLOW_ENABLE;
    }

    // normalize texture coordinates
    scale[0] = 1.0f / texinfo->image->width;
    scale[1] = 1.0f / texinfo->image->height;

    mins[0] = mins[1] = 99999;
    maxs[0] = maxs[1] = -99999;

    src_surfedge = surf->firstsurfedge;
    for (i = 0; i < surf->numsurfedges; i++) {
        src_edge = src_surfedge->edge;
        src_vert = src_edge->v[src_surfedge->vert];
        src_surfedge++;

        // vertex coordinates
        VectorCopy(src_vert->point, vbo);

        // vertex color
        memcpy(vbo + 3, &color, sizeof(color));

        // texture0 coordinates
        tc[0] = LDDotProduct(vbo, texinfo->axis[0]) + (long double)(texinfo->offset[0]);
        tc[1] = LDDotProduct(vbo, texinfo->axis[1]) + (long double)(texinfo->offset[1]);

        if (mins[0] > tc[0]) mins[0] = tc[0];
        if (maxs[0] < tc[0]) maxs[0] = tc[0];

        if (mins[1] > tc[1]) mins[1] = tc[1];
        if (maxs[1] < tc[1]) maxs[1] = tc[1];

        vbo[4] = tc[0] * (long double)(scale[0]);
        vbo[5] = tc[1] * (long double)(scale[1]);

        // texture1 coordinates
        vbo[6] = tc[0];
        vbo[7] = tc[1];

        vbo += VERTEX_SIZE;
    }

    // calculate surface extents
    bmins[0] = floor(mins[0] / 16);
    bmins[1] = floor(mins[1] / 16);
    bmaxs[0] = ceil(maxs[0] / 16);
    bmaxs[1] = ceil(maxs[1] / 16);

    surf->texturemins[0] = bmins[0] * 16;
    surf->texturemins[1] = bmins[1] * 16;

    surf->extents[0] = (bmaxs[0] - bmins[0]) * 16;
    surf->extents[1] = (bmaxs[1] - bmins[1]) * 16;
}

Other compilers/engines will probably need to make the same adjustment; this is the same bugfix the Quake 1 community ended up agreeing on in order to fix it (it's the only way to also allow old maps to work, and new maps to work on old engines, otherwise the compiler & engine will be disagreeing on the calculations).

[skullernet]

This fix seems a bit dubious. Given how fragile surface extents calculation algorithm is, won't it fix some cases while also causing regressions in others? More importantly, does this even fix any existing maps made for Quake 2? I'd say maps with imprecise planes are broken and should themselves be fixed (they'll run into issues with pmove code sooner or later).

I'd rather welcome a better fix: what if maps tools stored actual computed surface extents in some extra lump in BSP file (in a backward-compatible way), so that newer engines can find and use this information.

[Paril]

The fix only affects the visual surfaces - collision is not affected, as the brush planes are stored as 32-bit float regardless.

It should not cause any regressions in existing maps. In fact, using 32-bit/64-bit floats instead of 80-bit floats is what causes the regression in the first place; old editors (like qbsp3), if not recompiled, are still using 80-bit float via x87, and same for older engines, but engines (especially ones compiled as x64, but it seems the issue happens under x86 now as well, I assume newer compilers are using SSE by default which is not as precise as the 80-bit floats) and compilers will disagree on this calculation causing the UV sizes to be off by one or two, which can cause errors if the surface in question is at the end of the list, but will appear as lightmap corruption. I can create an example map if it helps. I don't know offhand if this occurs in any existing stock maps, but I can also test for that later; it will most likely occur only in third party maps.

EDIT2: base2 has one surface with a mismatch - sadly I think it's a degenerate face, which doesn't help my case, heh.

Here's an example I was looking at earlier:

If the map is compiled with an older compiler (qbsp3, etc) with q2pro as-is, or with ericw-tools (as it uses the long double fix, to mimic the x87 calculation), the result is the top; if the fix is applied in engine, it ends up looking correct. If you use any compiler that instead uses SSE/64-bit floats for intermediate calculations, though, q2pro will probably agree on the size, but now vanilla engines will be the one displaying the corrupted lightmap. As with Q1, they err'd on the side of assuming the calculation that was used in the stock maps is "correct", and anything downstream should be fixed to use higher precision.

Q1 has the same issue, and this is the fix they had adopted; there's still a precision difference between 80-bit and 128-bit float, but so far it hasn't been an issue (see FTE for example, it uses a similar fix, although its 64-bit float instead of 32-bit: https://github.com/fte-team/fteqw/blob/a0f2ffda9088a396cf0017ebd6a2a0b865806e8b/engine/common/gl_q2bsp.c#L137 ). This fix has been in the Q1 community for a very long time (Quake 1 remaster has the same fix). Quakespasm, which is the Q1 engine of choice for "vanilla" use, also has the same fix: https://github.com/sezero/quakespasm/blob/87835bc3e3749618ef8a414e69b69c8d79780ac6/Quake/gl_model.c#L1092

The map compiler fix is basically the same, and just ensures that the engines and compilers are agreeing on the result calculated from a high precision float: https://github.com/ericwa/ericw-tools/blob/7b33b12146390b9b91f37ab13cb04b8dc5f35fc2/light/ltface.cc#L44

By "imprecise plane" I mean that it's easier to cause this issue when brush points end up not being aligned to a grid. It's pretty common for imported geometry and the like (which is used as detail only, not for structural stuff).

EDIT: I saw your second part of the post about an extra lump for surface size. I agree that this is the best way to future-proof BSPs, and there's actually been discussion in the Q1 community to do the same thing, but nothing has come out of it yet. BSPX is a pretty simple format for adding additional lumps in a backwards compatible way to the BSP. The issue with this specific case though is just that engines using SSE without long-double are actually calculating lightmaps incorrectly.

EDIT3: the LMCTF set of maps has quite a bit of off-integer geometry, and it has some pretty obvious examples:

Top is incorrect (x64 SSE), bottom is correct (long double).

[skullernet]

Can you share BSP file of top example? I wonder how it behaves in original client.

While map tools may have used 80-bit float, I think the assumption that original quake2.exe used the same is not correct. It used x87 FPU, but it also set FPU control word specifically to change intermediate float precision to 24-bits. For this reason SSE is now forced enabled on x86 builds of Q2PRO, or else there will be prediction misses between quake2.exe and Q2PRO if full 80-bit float is used.

[Paril]

Here's rammo1, an actual stock map:

You're correct, in a vanilla Quake II client (from the 3.20 patch) the result is actually broken as well, but in a different way:

I think qrad3 didn't set the FPU control word (basing on Q2-tools repo), which is why it would have used the x87 calculations and disagreed with the client. That's mainly what I'm going by here, not the client: the light compiler baked lightmap data assuming higher precision mins/maxs which are used in the extents calculation.

So I guess the question is then should we assume the light tool is correct, with the 80-bit values, or should we assume the vanilla client is correct with the corrupted lightmaps? qbsp3 and ericw-tools would both use high precision values now, but 4rad and kmquake2's rad would fall back to 32-bit floats.. but even with the 32-bit floats, they'd be less precise with the _fpcontrol set and look wrong on vanilla I'd assume, if they are using 24-bit precision for this same calculation.. this is a bit more complicated than I originally assumed.

EDIT: DanielGibson @ yquake2 suggested that double should suffice, and they appear to be correct. Long double likely isn't required in any real-world scenarios, and most systems probably won't even have long double to be 128-bit floats (on my system it is the same as double).

[DanielGibson]

I wonder what kinds of values we're dealing with here exactly, to understand why things go with normal floats..

(Cross-posting from yquake2/yquake2#886 (comment)):

Do you have examples of what specific values in v->position[i] and tex->vecs[j][i] (and maybe mins[j] and maxs[j] if that matters) we're dealing with in the broken cases?
Trying to understand why apparently so much precision is needed, when the vertex positions (world coordinates) AFAIK should usually be < +/- 4096

[skullernet]

This issue occurs due to inherent brokenness of surface extents calculation: when e.g. mins[0] is close to multiple of 16 floor(mins[0] / 16) can return a value that's off by one compared to what map compiler has computed.

[DanielGibson]

What's that /16 and *16 about anyway? That looks like it artificially reduces the precision to (full/integer) multiples of 16?! Why?

[skullernet]

It rounds surface extents to lightmap block size, which is 16x16. Engine needs to know exactly how many lightmap blocks there are in a surface so that it can position the lightmap correctly. If there's off by one error in calculation artifacts will occur.

[Paril]

Lightmap sizes are 1/16th the texture coordinate size. (if a texture spans 80x80, then the lightmap will be 5x5 on that surface).

I compiled some stuff with qrad3 (from 1998, with x87 calculations) to compare the outputs with a modern tool (4rad) which uses 32-bit floats. This should help explain the issue. The map is a bit hard to grok because some of these black spots are "normal", but specifically look at the right hand side where the lightmap differs.

Q2PRO with double precision calculations, with 4rad (modern tool, 32-bit floats/SSE):

Q2PRO with single precision calculations, with 4rad (modern tool, 32-bit floats/SSE):

Q2PRO with double precision calculations, with qrad3 (old tool, 80-bit floats):

Q2PRO with single precision calculations, with qrad3 (old tool, 80-bit floats):

Notice how the only ones that match up are when both tools are agreeing on the results; the problem though is that all legacy maps (up until.. well, whenever SSE was introduced as a default, or whenever compilers stopped defaulting to x87 80-bit mode) rely on this calculation being large precision.

If we use vanilla Quake II, the results are similar.
Vanilla Q2 (single precision 24-bit calculations) with 4rad (modern tool, 32-bit floats/SSE):

Vanilla Q2 (single precision 24-bit calculations) with qrad3 (old tool, 80-bit floats):

In vanilla's case, it also renders the high precision float ones incorrectly. So, the issue is that qrad3 was using high precision floats, which writes invalid lightmaps at lightofs for a given face if the client is not also using high precision floats to calculate those extents - any client reading these using single precision would be rendering them incorrectly, if it's a map compiled with double-precision or 80-bit floats, although newer compilers would match up.

Basically my goal is just to have everybody going forward to agree on a specific precision, and double/long double is the only one that would also allow legacy maps to use correct rendering while also allowing them going forward to work.

[DanielGibson]

Ok, thanks for the explanation!
Anyway, we're back at "I'd like to see specific values of the broken cases to get a better idea of what exactly is going wrong" :)

Random not fully thought through idea: Could it help to add some tolerance to

		bmins[i] = floor(mins[i] / 16);
		bmaxs[i] = ceil(maxs[i] / 16);

Like maybe

		bmins[i] = floor((mins[i] / 16) + 0.1);
		bmaxs[i] = ceil((maxs[i] / 16) - 0.1);

(or maybe + and - inverted and no idea if 0.1 is a good number here)

[skullernet]

I've tried something similar years ago and no, adding bias like this is not going to work. One can't predict what value map compiler has calculated except by repeating the same calculation with exactly the same precision. Id should have just stored surface lightmap dimensions explicitly in BSP file (it'd only take two extra bytes per surface!), but they didn't.

[Paril]

Cool! I'm glad this is making headway. I sent a few examples of surfaces that Daniel can check out in the yquake2 issue.
For the latter (explicit dimensions), I was thinking of a BSPX lump for storing the calculated extents, but backwards compatibility is a bit of an issue.. older engines (ones that don't make use of this lump) would still need to use the dot product to calculate the texture coordinates, meaning the lightmap pointed to at lightofs has to be the right size, so even if the BSPX lump specifies this it doesn't help in this specific case. I'll need to mull over it more and see what we can do in the compiler to help these situations (it would be nice to have a standardized method in both Q1 and Q2 BSPs to have lightmap UVs decoupled from the texture UVs).

[DanielGibson]

I don't mind using (normal) doubles for the calculations (but I'll check the values when I have some time, just out of curiosity), so they match what the original map compilers did - it's just a minor change and shouldn't impair performance much, I think.

We should make sure that current map compilers show the same behavior as the original ones did. I created an issue for YQ2's tools at yquake2/maptools#4

No idea what tools most mappers actually use nowadays, you mentioned 4rad, maybe there are others - but those should do the same then, for maximum compatibility between compilers and engines.

[Paril]

I know people still download Geoffrey DeWan's set of tools, which used the full 80-bit x87 calculations I believe. Qbism's tools is probably the main one that is using x86/x64 SSE; KMQuake2's tool set (which supports x64) is the second that I can think of.

We have Q2 support in ericw-tools almost finished, but we've always been using long double for the UV calc from the Q1 days so we're already patched up.