Jon Blow BSP tree example

bool object_hits_world(BSP_Node *world_node, Polyhedron *solid) {
    if (world_node == NULL) return false;

    int status = classify(world_node, solid->center, solid->radius);

    if (status & SLICED) {
        if (test_solid_against_polygons(world_node->faces, solid)){
            return true;
        }
    }

    if (status & TOUCHES_NEG_HALFSPACE) {
        bool found_hit = object_hits_world(world_node->negative, solid);
        if (found_hit){
            return true;
        }
    }

    if (status & TOUCHES_POS_HALFSPACE) {
        bool found_hit = object_hits_world(world_node->positive, solid);
        if (found_hit){
            return true;
        }
    }

    return false;
}

int classify(BSP_Node *node, Point center, float radius) {
    float dot = dot_product(node->normal, center);

    float distance = dot + node->d;

    int status = 0;
    if (distance - radius <= 0.0) status |= TOUCHES_NEG_HALFSPACE;
    if (distance + radius >= 0.0) status |= TOUCHES_POS_HALFSPACE;
    if (fabs(distance) <= radius) status |= SLICED;

    return status;
}

bool test_solid_against_polygons(List *world_polygons, Polyhedron *solid) {
    Polygon *face1, *face2;
    Foreach(world_polygons->face, face1, {
        Foreach(solid->faces, face2, {
            if (polygons_intersect(face1, face2)) return true;
        });
    });

    return false;
}