We present a new data structure, called the Multi-Sculpture to represent 3D shapes at multiple levels of detail. The input shape at high resolution is described as a mesh of triangles. A coarse approximation of this shape is provided by the convex hull of the mesh, while intermediate approximations are obtained by sculpturing the space that separates the convex hull from the mesh. A higher level of detail corresponds to a higher degree of concavity in the shape approximation. The data structure supports on-line extraction of a shape representation at a user-defined level of detail, possibly varying over different parts of the shape. This mechanism allows speeding up recognition, classification, collision detection, and planning of manipulation tasks.