We propose a novel method of robustly and automatically creating surface meshes from the very sparsely populated 3D point clouds typically produced by Structure from Motion algorithms. Prior to meshing the point cloud is augmented with new points created by planar intersection thus improving the subsequent reconstruction of edges and corners in the scene. Image-consistent triangulation is then used within a simulated annealing algorithm to create an optimal surface mesh by selecting the subset and triangulation of a 3D point cloud that best represents the actual topology of the scene. This method provides a number of advantages: the reconstruction of crucial areas such as corners and edges is improved, it copes well with noisy data, it produces a simplified mesh, particularly for scenes that contain many planes and, unlike greedy search techniques, it is much more likely to converge to a global minimum. Results are provided for real and synthetic data and it is shown that even using datasets containing large numbers of outliers this method is capable of producing a surface mesh that reliably represents the real surface of the object.