PlaneDist and PlaneDiff appear to calculate values incorrectly for planes with negative normals

[noodlecollie]

The following is the definition of the PlaneDist macro:

#define PlaneDist(point,plane) ((plane)->type < 3 ? (point)[(plane)->type] : DotProduct((point), (plane)->normal))

Looking at the second clause, DotProduct((point), (plane)->normal)), it would appear that this macro is used for projecting point onto the normal of plane (assuming the normal is a unit vector). This takes into account the direction of the normal:

DotProduct(Vec3(1,2,3), Vec3(-1,0,0)) = -1 (ie. 1*-1 + 2*0 + 3*0)
DotProduct(Vec3(1,2,3), Vec3(1,0,0)) = 1 (ie. 1*1 + 2*0 + 3*0)

However, the optimisation in the first clause that makes use of the plane type neglects to take into account the plane's sign bits. For example, a plane with normal (-1,0,0) will have a type of PLANE_X, in which case calling PlaneDist with a point of (1,2,3) will return point[PLANE_X], ie. point[0], a value of 1 instead of -1.

This seems like inconsistent behaviour for this macro, and is causing some issues for me in my implementation for loading BSPs of different versions. I wanted to confirm whether this was an actual bug before I went ahead and created/tested a proper pull request for it, as I thought it was a bit strange that this wouldn't have creating culling issues in the engine before now.

[nekonomicon]

AFAIR, bug with culling was fixed into original Unkle Mike's xash3d build 3598.

[a1batross]

PlaneDist macro is never used, but similar PlaneDiff is almost everywhere in the code.

There was a fix by Unkle Mike in Mod_PointInLeaf to replace < 0 by <= 0. This bug caused random visibility bugs on different modifications and broken FIND_CLIENT_IN_PVS server call, when client is standing in between two leafs, where is one leaf is visible and other is not. I don't know is this bugfix related, but try to reproduce your bug on 0.19.x branch(which is more fresh, but not guaranteed to be stable).

[noodlecollie]

I did come across this issue originally with PlaneDiff, though PlaneDist is a simpler macro with which to demonstrate it. However, I'll give an example of PlaneDiff which is representative of where I got confused:

Let's say I've got a plane at x = -2. The normal is facing along the positive X axis, so the plane's dist is -2 (you could write it as a vec4_t, (1, 0, 0, -2)). I have a point that I'm comparing to the plane, which is (-3, 0, 0). The plane has type 0, because its normal is parallel to X.

(-3,0,0) |
    *    |
         | ->
         | Plane points this way
         |
        x=-2

Clearly in this case the point is behind the plane, so PlaneDiff should return a negative value. It does:

#define PlaneDist(point,plane) ((plane)->type < 3 ? (point)[(plane)->type] : DotProduct((point), (plane)->normal))

// For brevity:
#define PlaneDiff(point, plane) PlaneDist(point, plane) - (plane)->dist

// If the plane is type 0, this boils down to:
point[0] - plane->dist

// If point is (-3, 0, 0) and plane is (1, 0, 0, -2), then we get:
  (-3) - (-2)
= -3 + 2
= -1 // The point is 1 unit behind the plane

Where the issue lies is if the plane faces the opposite way. If the normal is made negative then the distance the plane lies along the normal becomes positive. Therefore, the flipped version of (1, 0, 0, -2) is (-1, 0, 0, 2). The plane still has a type of 0, because the normal is still parallel to the X axis; the sign bits, however, will be different.

(-3,0,0) |
    *    |
      <- |
         | Plane points opposite way
         |
        x=-2

If the point was 1 unit behind the former plane, it should be 1 unit in front of the flipped plane. However, PlaneDist does not give a value of 1 in this case:

// Because the type of the plane is still 0, PlaneDist still gives this:
point[0] - plane->dist

// If point is (-3, 0, 0) and plane is (-1, 0, 0, 2), then we get:
  (-3) - 2
= -5 // The point is 1 unit in front of the plane, not 5 units behind!

// The correct calculation would multiply the point[0] by the plane's sign bits:
-(point[0]) - plane->dist

// This would then result in:
  -(-3) - 2
= 3 - 2
= 1 // Hooray!

So I guess my question is: since the PlaneDiff macro gives demonstrably incorrect results for certain planes, how come there aren't noticeable bugs in the engine culling?

[a1batross]

When compiler builds map, it marks face(dface_t::side) if it's points in opposite side, which turns engine to mark surface with negated plane(SURF_PLANEBACK flag) and then the culling rule will be with different sign.

The first example was right. But in the second, you can't have -5 or 1, you must have -1, so when the culling process starts it will not be culled, as -1 < -0.01(see R_CullSurface).

I don't know why you have dist turned sign of dist, but it's seems to be just mathematical error. :)

[noodlecollie]

The BSP format I'm attempting to import does sometimes have surfaces whose planes have negative normals, but I've had a look at a box map I compiled for Half Life and it seems the planes on those surfaces always have positive normals (and SURF_PLANEBACK is indeed used where appropriate). Perhaps that's where I'm going wrong, and Half Life's bsp.exe just doesn't write surfaces with planes that would cause this issue with PlaneDiff.

Thanks for the help anyway, I'll see what I can work out in my own project.

[a1batross]

I have looked into compilers source code and figured out, that planes marked as negative in faces, is odd numbers, i.e. face->side = planenum & 1. Check is this related to your BSPs, maybe "side" was replaced by something else.

[a1batross]

I think this should be closed, as this is not a bug and sort of discussion? Feel free to ask your questions though, @x6herbius. Your idea of making custom build for running Nightfire is awesome. :)

[noodlecollie]

Yeah, I'm fine with this being closed. I've worked around the confusing behaviour. :P