Find the volume enclosed by terrain and a certain sea level I have a terrain, which is represented by  one mesh with a lot of polygons as shown below:

This terrain will be cut by a plane at a certain level. So there are volumes of the terrains that are located above the plane ( cut volume), and volumes that are located below the plane ( fill volume). 
The question is, how do I obtain the cut/ fill volume? My current approach is simply take one mesh at a time, and then form a tetrahedron with the plane, and compute the volume. But this is slow. Is there other better approach?
One approach that I have in mind, is to try to form Bezier surface for the terrain, and then try to use integration to compute the volume. But I don't know how to proceed with this. Any idea?
Edit: Terminology updated
 A: How close do you have to be?
Can you just find the center of the each triangle in space then divide the cutting plane into a 2d grid and do a series of rectangular volume calculations using the length and width of the grid section and the average height of the triangle midpoint above/below that grid section?
A: One way to do it is to compute the volume under (or above) each triangle. The volume from a triangle to the plane z=0 can be computed as:
V  =  (z1+z2+z3)(x1y2-x2y1+x2y3-x3y2+x3y1-x1y3)/6

In python:
def volume_under_triangle(triangle):
    p1, p2, p3 = triangle
    x1, y1, z1 = p1
    x2, y2, z2 = p2
    x3, y3, z3 = p3
    return (z1+z2+z3)*(x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3)/6

Full explanation here. You will need to adapt the formula for z=sea_level by substracting sea_level to the z of each point. For a given sea level, the sign of the volume will be positive or negative depending on whether you numbered the points clockwise or
counter-clockwise.
As some of your triangles will be above sea level and others under it, you will need to keep a consistent, clockwise or counter-clockwise point ordering. You can run this computation for all your triangles, then you add the positive volumes together to get the cut or fill volume (depending on your ordering) and the negative ones to get the other one.
As to how efficient is this, I've made a basic test that computes the volume of a surface with ~70k triangles using Python and it took ~2seconds running on mid-tier 6yo hardware, however I guess it could be improved quite a bit.
A: Can you graph a subsection of terrain by volume? Doing it by hand I imagine would be painstakingly long. Maybe use a computer to iterate through the data. Something like:
[i for in n if y_1 ==, >, <.... #for every axis, you get the gist

The shape of the plane for your cut will also matter I guess but for simplicity of your just doing a rectangular plane as a cut i would use comprehension as above so when you set your plane height, length and width you only log the data points that correspond to that value of y. Iterated over all the data points in the ${x, y, z}$ axis should give you your cubic volume right, above and below if you know the maximum heights of all points?
