We present a fast proximity query algorithm for haptic display of complex deformable models using a layered representation. Assuming that each solid model can be represented as a rigid core covered by a layer of deformable material, the deformation field of the surface can be expressed as a function in the parametric domain of the rigid core. Our 2-stage collision query algorithm starts by performing an approximate objectspace collision detection between low-resolution polygonal proxies. We then refine the query result by computing a directional penetration depth field using a local height-field representation of the deformable layers to detect the interference between the high-resolution surface geometry. We have developed a proof-of-concept demonstration using commodity graphics processors and been able to perform fast proximity queries between two highly complex deformable models in less than 2 ms.