The medial surface is a skeletal abstraction of a solid that provides useful shape information, which compliments existing model representation schemes. The medial surface and its associated topological entities are defined, and an algorithm for computing the medial surface of a large class of B-rep solids is then presented. The algorithm is based on the domain Delaunay triangulation of a relatively sparse distribution of points, which are generated on the boundary of the object. This strategy is adaptive in that the boundary point set is refined to guarantee a correct topological representation of the medial surface.