Humanoid robots have the potential to traverse the same com- plex terrain as humans: dealing with all the challenges of uneven and discontinuous surfaces, cracks and gaps while moving at typical human speeds. While locomotion research spans actuator development, dynamic planning and control, in this work we focus on terrain estimation and footstep plan- ning — in particular while in continuous motion. We demonstrate that a precisely accurate dense terrain map can be estimated using only imagery from a humanoid robot’s passive stereo camera . This result then provides the necessary sensory input for an on-demand footstep planner which can in turn compute a set of footsteps which are optimal (within our assumptions) and kinematically feasible; yet does so suffi- ciently quickly that the robot can continuously locomote over uneven terrain. Our experiments demonstrate the Boston Dynamics Atlas robot continuously walking over a terrain course similar to the DARPA Robotic Challenge (DRC) walking task. Our aim with this work is to demonstrate how modern dense visual mapping techniques can be used by dynamic robots while in motion.