Since it's tough to draw in 3D with paint, I made up a quick 2D example. In the example I only drew and split vertically and horizontally to make things simple, but in reality you wouldn't. Also notice that each divider lies on the same line as a wall -- this is because it would be impossible to check all of the planes, so you'd usually just use planes which a wall goes through. The other benefit of that is you won't split the polygon on which that plane lies.
I'll post the process in 3 posts.
Here's the original level: