This paper presents a method to handle walking on non-planar surfaces. The trajectories of the center of mass and the next position of the foot are given by a pattern generator. Then, an inverse dynamics control scheme with a quadratic programming optimization solver is used to let the foot go from its initial to its final position, controlling also the center of mass and the waist. The solver can handle an arbitrary number of contact points. When the swinging foot is going down, collision points are detected and they are added as contact points to the model as soon as they appear. If there are three or more contact points, the foot can safely step, but if there are one or two contact points, the foot rotates properly to generate the largest support polygon. Using this heuristic, the foot can stand on non-planar surfaces. Simulation results of the HRP-2 robot walking on a surface with obstacles are presented. © 2012 IEEE.