In this paper, a method to accelerate Soft Vector Quantization (VQ), making it a quasi-real time procedure, is described. Through the local analysis of the data density a criterion to set a reasonable value of the parameters and to initialize the position of the Reference Vectors (Hyper-Box preprocessing), allows to cut about 75% of the iterations and to make the computational cost of each iteration, constant, independent of the number of sampled points. Moreover, it makes Soft VQ of possible implementation on parallel machines. Overall, the processing time with Hyper-Box pre-processing can be brought down to 3%. This method, in conjunction with Delaunay tessellation, has been extensively applied to the construction of 3D triangular meshes from dense noisy data. Results on the reconstruction of 3D models of Human faces are reported and discussed.