Exploiting the huge amount of real time range data provided by new multi-beam three-dimensional (3D) laser scanners is challenging for vehicle and mobile robot applications. The Coarse Binary Cube (CBC) method was proposed to achieve fast and accurate scene registration by maximizing the number of coincident cubes between a pair of scans. The aim of this paper is speeding up CBC with a fast spatial subsampling strategy for raw point clouds that employs the same type of efficient data structures as CBC. Experimental results have been obtained with the Velodyne HDL-32E sensor mounted on the Quadriga mobile robot on irregular terrain. The influence of the subsampling rate has been analyzed. Preliminary results show a relevant gain in computation time without losing matching accuracy.