Abstract: We present the first quality physics-based smoke animation method which runs in time approximately linear in the size of the rendered two-dimensional visual detail. Our fundamental representation is a closed triangle mesh surface dividing space between clear air and a uniformly smoky region, on which we compute vortex sheet dynamics to accurately solve inviscid buoyant flow. We handle arbitrary moving no-stick solid boundaries and by default handle an infinite domain. The simulation itself runs in time linear to the number of triangles thanks to the use of a well-conditioned integral equation treatment together with a Fast Multipole Method for linear-time summations, providing excellent performance. Basic zero-albedo smoke rendering, with embedded solids, is easy to implement for interactive rates, and the mesh output can also serve as an extremely compact and detailed input to more sophisticated volume rendering.