We describe a novel method for discovering and incorporating higher level map structure in a real-time visual SLAM system. Previous approaches use sparse maps, populated by isolated features such as 3-D points or edgelets. Although this facilitates efficient localisation, it yields very limited scene representation and ignores the inherent redundancy amongst features resulting from physical structure in the scene. In this work, higher level structure, in the form of lines and surfaces, is discovered concurrently with SLAM operation and then incorporated into the map in a rigorous manner, attempting to maintain important cross covariance information and allow consistent update of the feature parameters. This is achieved by using a bottom-up process, in which subsets of low level features are `folded in' to a parameterisation of an associated higher level feature, thus collapsing the state space as well as building structure into the map. We demonstrate and analyse the effects of the approach for the cases of line and plane discovery, both in simulation and within a real-time system operating with a hand-held camera in an office environment.