We propose a novel method that uses simulated annealing to create an optimal surface mesh by selecting a subset of a 3D point cloud and a triangulation that reliably represents the actual topology of the scene. This method provides a number of advantages: 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.