Need help in implementing Quake 1 BSP traversal: incorrect leaf returned when finding camera position

I don't see any bugs in your traversal code. I would check that you are loading the data correctly, e.g. ensure that “long” and “u_short” have the expected sizes, that there is no structure padding.

Note: it will be significantly faster to implement the traversal using a loop instead of recursion.

@undefined Thanks, that helps. Since traversal looks correct, I’m now double-checking my BSP loading assumptions: I’m using Quake 1 BSP files (version 29), and I assume traversal and PVS queries should only be done on models[0] (world model), with other models having their own BSP trees. I also read BSP data directly into C structs using long/short, so I want to confirm whether switching to fixed-width types and avoiding direct struct reads is recommended to prevent padding or size issues. Finally, I treat negative child indices as leaves and convert them using leaf = ~index; can you confirm this is correct for Quake 1 BSP?

When you read structs from persistent memory or over a socket, you should always use sized integer types, make sure that the endianness is correct (though I assume the file format uses little endian, and you're probably on an x86 or some other little-endian machine, so you don't have to do anything), and finally also make sure you do not have padding bytes, using something like #pragma pack(push, 1), or whatever your compiler uses, or by manually adding up the size of the fields and checking that natural alignment will not lead to padding for this struct. I think there are also some handy macros that let you do a PACKED_STRUCT macro that simply replaces the struct keyword in the struct declaration, and will make it packed. As long as you know the machine has the same endianness as the data you load, packed structs are safe to load directly.

On Windows and linux, there exists a different convention for the size of long. On 32-bit OSes and all Windows versions, it is 4 bytes, while on 64-bit linux, it is 8 bytes. short is reliably 2 bytes on all platforms in use today. But still, it is best to use the size-specific types whenever you do care about the exact size of the type.

Under GCC and probably also clang, you can use:

#define PACKED_STRUCT struct __attribute__((packed))

PACKED_STRUCT MyStruct { uint64_t x; uint8_t y; uint32_t z; };
static_assert(sizeof(MyStruct) == 13);
static_assert(alignof(MyStruct) == 1);

MyStruct data;
fread(&data, sizeof(data), 1, data_file);

If the file format is big-endian, you'll have to go over all the fields and use std::byteswap() on them.

Another pitfall: operator ~ on a short will first promote it to an int, and then invert the bits. So ~(u_short)0xffff is (uint)0xffff0000. You have to manually narrow it to u_short again after using the ~ operator to remove the excess bits: (u_short)~node_index.

@RmbRT Thanks,i double-checked my BSP loading and most of the data seems correct: vertices, faces, textures, and lightmaps all render properly when I draw everything without visibility culling, so I believe the file parsing and structure sizes are mostly correct. I also verified that node children are stored as signed 16-bit values and that leaf indices are derived correctly. Since the issue only appears when using BSP traversal and PVS, I’m looking for other possible causes—such as plane side tests, leaf indexing assumptions, BSP version differences, model index usage (e.g. only model 0), or mistakes in PVS decompression—rather than basic file loading errors. Any pointers on what to verify next would be appreciated.