1. A system, comprising; one or more computing devices configured to implement a real-time video exploration (RVE) system comprising: a playback module configured to begin playback of at least a portion of a pre-recorded video to a client device; and a graphics processing and rendering module configured to: receive input from the client device indicating an interaction with a scene of the video; generate a model of the scene according to graphics data for the scene; render new video of the scene from the model of the scene based at least in part on scene exploration input received from the client device; and stream the new video of the scene to the client device.