Abstract: In this talk I describe perception algorithms that use curved patches to model contact surfaces in uneven environments like rocky trails. First I introduce a set of 10 patch models for contact areas both in the environment and on an articulated robot, and an algorithm for fitting these to point cloud data with estimated uncertainty both in the input points and the output patch. Then I describe an algorithm for sparsely covering nearby environment surfaces with patches appropriate for a robot to touch. The algorithm keeps only those patches which pass several validation checks to ensure fidelity to the sensed point cloud data. I also introduce a notion of saliency of a patch with respect to a locomotion task using local surface properties like normal vectors and curvatures. I present results on datasets of natural rocky terrain taken with a Kinect and compare point neighborhoods based on k-d trees vs. triangle meshes.