/r/Quake Subreddit — Need help in implementing Quake 1 BSP traversal: incorrect leaf returned when finding camera position – From /r/Quake
Go to Source
Hi,
I’m implementing BSP traversal for Quake 1 (.bsp) maps and trying to determine which leaf the camera is currently inside, following the original Quake BSP specification.
I’m using the official documentation here:
https://www.gamers.org/dEngine/quake/spec/quake-spec34/qkspec_4.htm#BL5
According to the spec, BSP nodes store either:
- a child node index if bit 15 is not set, or
- a leaf index if bit 15 is set, where the leaf index is obtained by inverting all bits (
~value).
I implemented recursive traversal like this:
int find_camera_leaf (Camera* camera, bsp_model_t * tree){ model_t * model = &(tree->models[0]); return find_leaf_recursive(tree,model->node_id0,camera->pos); } int find_leaf_recursive ( bsp_model_t * tree, uint16_t node_index, vec3 cam_pos) { if (node_index & 0x8000) { // Leaf: bit 15 set return ~node_index; } node_t * node = &tree->nodes[node_index]; plane_t * plane = &tree->planes[node->plane_id]; float distance = cam_pos[0] * plane->normal.x + cam_pos[1] * plane->normal.y + cam_pos[2] * plane->normal.z - plane->dist; uint16_t child; if (distance >= 0.0f) { child = node->front; } else { child = node->back; } return find_leaf_recursive(tree, child, cam_pos); }
and The structure definitions match the spec:
typedef struct { long plane_id; u_short front; u_short back; bboxshort_t box; u_short face_id; u_short face_num; } node_t ;
The problem is that the function often returns an unexpected leaf index, frequently leaf 0 ,or wrong out of bound values like 65535 ,like (the dummy leaf), even when the camera is clearly inside visible geometry.
