Representation of complex, curved objects is still a challenging and difficult problem. In this paper, we present a scheme for multi-level, structural, qualitative representation of object surfaces. The analysis begins with local, face-based descriptions of object surfaces (surface primitive graphs), and global, high-level, structural, and qualitative features are derived from these local descriptions. The final descriptions (global feature graphs) are based on the quasi-convexity (concavity) structures incorporating quantized directional features of closed boundaries of cross-sections along several directions. The global feature graphs have the following properties: (1) They provide a characterization of global, structural, qualitative properties of the object; (2) The graphs are composed of a few components (nodes and edges) with rich features, and give compact descriptions of the objects; (3) The global feature graph representations are robust and qualitative in that they are not affected by geometrical, quantitative properties of the shape such as curvatures, length, and position; (4) The representation has clear and rigorous properties. Furthermore, we present some theoretical basis for object recognition using the global features graphs.