The success of NASA?s Mars Exploration Rovers has demonstrated the important benefits that mobility adds to planetary exploration. Very soon, mission requirements will impose that planetary exploration rovers drive autonomously in unknown terrain. This will require an evolution of the methods and technologies currently used. This paper presents our approach to 3D terrain reconstruction from large sparse range data sets, and the data reduction achieved through decimation. The outdoor experimental results demonstrate the effectiveness of the reconstructed terrain model for different types of terrain. We also present a first attempt to classify the terrain based on the scans properties.