This looks really cool! I have no idea how you would even solve the first one with bounding boxes. I guess you would progressively build up a scene using the raw depth data then move onto more complex shapes at higher levels?
It's relatively and unsolved area but there are definitely people working on it. Technically when you have RGBD you can create a point-cloud and go the 3D object recognition route. There are 2D to 3D methods out there too.