By the way, I have no trouble clearing a surface and building up a whole new triangle + vertice list of about 3000 vertices and 1500 triangles within the space of 1 millisecond. My game does this every frame. So I think complete reconstruction could be an option.