Scenes reconstruction may be performed using videos that capture the scenes at high resolution and frame rate. Scene reconstruction may be associated with determining camera orientation and/or location (“camera pose”) throughout the video, three-dimensional coordinates of feature points detected in frames of the video, and/or other information. Individual videos may have multiple frames. Feature points may be detected in, and tracked over, the frames. Estimations of camera pose may be made for individual subsets of frames. One or more estimations of camera pose may be determined as fixed estimations. The estimated camera poses for the frames included in the subsets of frames may be updated based on the fixed estimations. Camera pose for frames not included in the subsets of frames may be determined to provide globally consistent camera poses and three-dimensional coordinates for feature points of the video.