Non-rigid surface registration is fundamental when accurate tracking or reconstruction of 3D deformable shapes is desirable. However, the majority of non-rigid registration methods are not as fast as the ones developed in the field of rigid registration. Fast methods for non-rigid surface registration are particularly interesting for markerless augmented reality applications, in which the object being used as marker can support non-rigid user interaction. In this paper, we present an adaptive algorithm for non-rigid surface registration. Taking advantage from this adaptivity and the parallelism of the GPU, we show that the proposed algorithm is capable to achieve near real-time performance with an approach as accurate as the ones proposed in the literature.