In this article we present the complete details of the architecture and implementation of Leaving Flatland, an exploratory project that attempts to surmount the challenges of closing the loop between autonomous perception and action on challenging terrain. The proposed system includes comprehensive localization, mapping, path planning, and visualization techniques for a mobile robot to operate autonomously in complex three-dimensional (3D) indoor and outdoor environments. In doing so we integrate robust visual odometry localization techniques with real-time 3D mapping methods from stereo data to obtain consistent global models annotated with semantic labels. These models are used by a multiregion motion planner that adapts existing two-dimensional planning techniques to operate in 3D terrain. All the system components are evaluated on a variety of real-world data sets, and their computational performance is shown to be favorable for high-speed autonomous navigation. © 2009 Wiley Periodicals, Inc.