Understanding vtkStaticCellLocator

This does not sound good. By utilizing the massively parallel execution of graphics hardware and/or by using images for computations instead of meshes you may achieve several magnitudes faster computations. Using SMP on CPU you can expect maybe one magnitude faster computations.