We present a method for the segmentation of unstructured and unfiltered 3D data. The core of this approach is based on the construction of a local neighborhood structure and its recursive subdivision. 3D points will be organized into groups according to their spatial proximity, but also to their similarity in the attribute space. Our method is robust to noise, missing data, and local anomalies thanks to the organization of the points into a Minimal Spanning Tree in attribute space. We assume that the 3D image is composed of regions homogeneous according to some criterion (color, curvature, etc.), but no assumption about noise, nor spatial repartition/shape of the regions or points is made. Thus, this approach can be applied to a wide variety of segmentation problems, unlike most existing specialized methods. We demonstrate the performance of our algorithm with experimental results on real range images.