It costs nothing to try, which is what I'd do before declaring it impossible..
For a dense mesh it wont' matter if they are triangles or not, especially since all you are going to do with it is run a boolean through it.
You can select the whole thing and hit P to turn them into flat triangles just as the polygon program thought they were gong to be anyway.