What algorithms can automatically determine a 3D scene from one or a few 2D images? For a project I'm doing, I'm trying to model a scene based on a phone camera's video input, and then insert arrows into it that indicate direction in three dimensions.

I've looked around, and this paper looks quite interesting, and I suppose I could try to adapt its methods:
http://kevinkarsch.com/publications/sa11-lowres.pdf

However, it has the problem that users must input some reasonable spatial constraints into it beforehand, whereas doing this for every frame of a live and constantly changing video is unreasonable.

Another thing that I found allows reconstruction of a 3D object from a few photos of it in various directions, but I can't seem to find the original source anymore.

Any ideas?
SLAM(Simultaneous Localization and Mapping) algorithms can be used to for 3D reconstruction. They offer solutions for both monocular as well as stereo cameras. With single camera they estimate depth with few images and reconstruct the scene. You can find some of the open source solutions here.

Real time 3D reconstruction can done using ORBSLAM and it is also opensource.Here is the related paper for monocular SLAM.