Hi all, I’m implementing a Quake-style BSP traversal using my own runtime structs. I’ve loaded the disk structs (dnode_t / dleaf_t) correctly, and I’ve created corresponding runtime nodes and leaves (mnode_t / mleaf_t) for traversal.
Traversal generally works, but I’m always stuck at leaf 0 initially. After moving slightly, I sometimes get the correct leaf (e.g., leaf 185), but then moving again sends me back to leaf 0.
when i render all available faces without traversal it works fine wich makes me assume i’m loadint the structs from disk correctly .
here are the structs and code i use to create nodes and leaves and implement the traversal:
typedef struct mnode_s {
int contents; // 0 for nodes
int visframe;
int16_t minmaxs[6];
struct mnode_s *parent;
struct mnode_s *children[2];
int plane_id;
uint16_t firstsurface;
uint16_t numsurfaces;
} mnode_t;
typedef struct mleaf_s {
int contents; // negative for leaves
int visframe;
int16_t minmaxs[6];
struct mnode_s *parent;
int index_to_leaf;
} mleaf_t;
typedef struct
{
int32_t plane_id; // The plane that splits the node
// must be in [0,numplanes[
//TODO: I changed the front and back children from unsigned to signed,according to the Quake source code
int16_t front; // If bit15==0, index of Front child node
// If bit15==1, ~front = index of child leaf
int16_t back; // If bit15==0, id of Back child node
// If bit15==1, ~back = id of child leaf
bboxshort_t box; // Bounding box of node and all childs
uint16_t face_id; // Index of first Polygons in the node
uint16_t face_num; // Number of faces in the node
} dnode_t;
typedef struct
{
int32_t type; // Special type of leaf
int32_t vislist; // Beginning of visibility lists
// must be -1 or in [0,numvislist[
bboxshort_t bound; // Bounding box of the leaf
uint16_t lface_id; // First item of the list of faces
// must be in [0,numlfaces[
uint16_t lface_num; // Number of faces in the leaf
uint8_t sndwater; // level of the four ambient sounds:
uint8_t sndsky; // 0 is no sound
uint8_t sndslime; // 0xFF is maximum volume
uint8_t sndlava; //
} dleaf_t;
mleaf_t* create_custom_leafs(dleaf_t* in_leafs, int num_in_leafs) {
mleaf_t* out_leafs = (mleaf_t*)malloc(sizeof(mleaf_t) * num_in_leafs);
memset(out_leafs, 0, sizeof(mleaf_t) * num_in_leafs);
for (int i = 0; i < num_in_leafs; i++) {
out_leafs[i].minmaxs[0] = in_leafs[i].bound.minX;
out_leafs[i].minmaxs[1] = in_leafs[i].bound.minY;
out_leafs[i].minmaxs[2] = in_leafs[i].bound.minZ;
out_leafs[i].minmaxs[3] = in_leafs[i].bound.maxX;
out_leafs[i].minmaxs[4] = in_leafs[i].bound.maxY;
out_leafs[i].minmaxs[5] = in_leafs[i].bound.maxZ;
out_leafs[i].contents = -1; // negative to mark as leaf
out_leafs[i].index_to_leaf = i;
}
return out_leafs;
}
mnode_t* create_custom_nodes(dnode_t* in_nodes, mleaf_t* leafs, int num_in_nodes) {
mnode_t* out_nodes = (mnode_t*)malloc(sizeof(mnode_t) * num_in_nodes);
memset(out_nodes, 0, sizeof(mnode_t) * num_in_nodes);
for (int i = 0; i < num_in_nodes; i++) {
out_nodes[i].contents = 0;
out_nodes[i].minmaxs[0] = in_nodes[i].box.minX;
out_nodes[i].minmaxs[1] = in_nodes[i].box.minY;
out_nodes[i].minmaxs[2] = in_nodes[i].box.minZ;
out_nodes[i].minmaxs[3] = in_nodes[i].box.maxX;
out_nodes[i].minmaxs[4] = in_nodes[i].box.maxY;
out_nodes[i].minmaxs[5] = in_nodes[i].box.maxZ;
out_nodes[i].plane_id = in_nodes[i].plane_id;
out_nodes[i].firstsurface = in_nodes[i].face_id;
out_nodes[i].numsurfaces = in_nodes[i].face_num;
int p = in_nodes[i].front;
out_nodes[i].children[0] = (p >= 0) ? out_nodes + p : (mnode_t*)(leafs + (-1 - p));
p = in_nodes[i].back;
out_nodes[i].children[1] = (p >= 0) ? out_nodes + p : (mnode_t*)(leafs + (-1 - p));
}
Mod_SetParent(out_nodes, NULL); // sets parents recursively
return out_nodes;
}
mleaf_t* bsp_traversal(bsp_model_t* tree, mnode_t* nodes, vec3 cam_pos) {
mnode_t* node = nodes;
while (1) {
if (node->contents < 0)
return (mleaf_t*)node;
plane_t* plane = &tree->planes[node->plane_id];
float d = DotProduct(cam_pos, plane->normal) - plane->dist;
node = (d > 0) ? node->children[0] : node->children[1];
}
return NULL;
}
How can I correctly traverse the BSP using these runtime node/leaf structs without getting “stuck” at leaf 0? Could the issue be in the way I handle child pointers, the root node, or the leaf contents?
any help will be really appreciated ,thanks!