Terrain map building is an essential component of a planning autonomous navigator. External terrain must be represented in a manner that is convenient for the path planning subsystem to use, and that is useful for fine tuning the position estimate. This work is concerned with the solution of the particular problems encountered when attempting high speed navigation of an autonomous vehicle on rough terrain. These problems include the requisite longer downrange field of view, the range shadow problem, the image fusion problem, and the motion of the vehicle during image digitization. Experimental results have been obtained for an all terrain autonomous vehicle testbed--the Navlab II. The perception system was successful in supporting runs of 6.7 kilometers at speeds averaging 1.8 meters/second while checking for obstacles, 5.1 kilometers at 1.8 meters/sec while avoiding obstacles, and 0.3 kilometers at 4.5 meters/second while checking for obstacles.