This paper describes a new approach to the surface-based segmentation of scenes with occluded curved objects. Unlike most existing methods which proceed in different stages searching mainly for jump and crease boundaries by computing, respectively, at every point, zero-crossings and extrema of surface curvature in some chosen directions, in this paper, a single-step process is adopted to localize all types of edges. It consists of applying new directional curvature operators to signal the presence of edge points in a simpler and a more efficient way. Once edge curves are extracted, these are expressed in terms of primitives such as linear segments, cylindrical and spherical arcs. These primitives are then used to infer simpler surface models: planar, cylindrical and spherical surfaces. The determined surfaces are then described using a boundary representation scheme, and an edge-junction graph is constructed to interpret the spatial relationship between these surfaces. It is shown that by enforcing a consistent interpretation between these two representations, it is possible to derive a surface-based description that is unambiguous and not too sensitive to quantization noise and occlusion. The proposed method has been applied on a set of noisy synthetic and real-range images and the experimental results were very promising in terms of computation and localization.