I was trying to avoid shaders thinking that even if this was not the optimal route I could optimize to get it fast enough to at least be acceptable. I think I have optimized as much as I can and I have only gained a few seconds, but the result is not even close to acceptable speeds.

So I have no option but to start to learn HLSL. I hope I can understand shaders with those workshops because if I can't I will have to stick to using my current code... Thanks alot for the link!

and thanks alot EvilSOB for helping me optimize this code as much as we could (and the previous stuff we did for terrains). Even if I can't use this last part I have learned alot while doing it thanks to you, and if I don't manage to understand HLSL at least we got this working as fast as it can possibly go.