BSP Trees and dynamic objects

How do I handle dynamic objects using BSPs? Do I have to remove the object and re-insert it in its new position every time the object moves? Seems rather messy.

Yep, it’s messy.

Moving objects like ammo boxes or game characters, are generally not part of the BSP tree, they are inserted into the BSP for positional/sort purposes, but it’s not a full insert, you just figure out which leaf it’s in, if you need to. You don’t add the plane equations to the full BSP tree. The finer points of visibility sorting are resolved with the zbuffer.