Examples of the present disclosure relate to generating optimal scanning trajectories for 3D scenes. In an example, a moveable camera may gather information about a scene. During an initial pass, an initial trajectory may be used to gather an initial dataset. In order to generate an optimal trajectory, a reconstruction of the scene may be generated based on the initial data set. Surface points and a camera position graph may be generated based on the reconstruction. A subgradient may be determined, wherein the subgradient provides an additive approximation for the marginal reward associated with each camera position node in the camera position graph. The subgradient may be used to generate an optimal trajectory based on the marginal reward of each camera position node. The optimal trajectory may then be used by to gather additional data, which may be iteratively analyzed and used to further refine and optimize subsequent trajectories.