This paper presents the problem of constructing a 3D terrain model for localization and navigation of planetary rover. We presented our approach to 3D terrain reconstruction from large sparse range data sets. In space robotics applications, an accurate and up-to-date model of the environment is very important for a variety of reasons. In particular, the model can be used for safe tele-operation, path planning and mapping points of interest. We propose an on-line terrain modeling using data provided by an on-board high resolution, accurate, 3D range sensor. Our approach is based on on-line acquisition of range scans from different view-points with overlapping regions, merge them together into a single point cloud, and then fit an irregular triangular mesh on the merged data. The outdoor experimental results demonstrate the effectiveness of the reconstructed terrain model for rover localization, path planning and motion execution scenario.