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. The convex hull of the mesh provides a coarse approximation of this shape, 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.