This paper describes a novel approach to surface fitting for the creation of a 3D surface map for use by a small articulated wall-climbing robot. Both a laser range finder and a low-resolution camera are used to acquire data in a sparse manner. By scanning at large intervals, such as every 5-10°, and then fusing the data, it is shown that it is possible to fit planar surfaces at an accuracy comparable to dense range scanning. Infinite planes are fit to lines extracted from the range scans and then the image corners and lines are used to provide polygon boundaries on these planes. This method is faster and more flexible, both in acquiring data and in computing the planar features and less memory is required. This method also works well in feature poor environments where stereo vision can struggle and does not need to process the feature correspondences in the typical fashion which also saves time. This surface fitting approach is demonstrated using a real data set and results show promise in providing quick yet accurate 3D planar surfaces which could be integrated into SLAM and motion planning frameworks. ©2010 IEEE.