8
$\begingroup$

I have a terrain, which is represented by one mesh with a lot of polygons as shown below:

alt text

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

$\endgroup$
9
  • $\begingroup$ I'd first start by figuring out what interpolating function(s) were used to create that mesh. $\endgroup$
    – J. M. ain't a mathematician
    Sep 17, 2010 at 7:35
  • $\begingroup$ @J.M., no interpolation function were used; they were obtained from field survey, or at least this is the assumption I have to make. $\endgroup$
    – Graviton
    Sep 17, 2010 at 7:38
  • $\begingroup$ Ah, so you have an array of coordinate triples as data? Then Bézier isn't what you want (that would be within the data as the convex hull, not interpolate through it). Would there be sharp bumps/peaks/valleys in the data you have? $\endgroup$
    – J. M. ain't a mathematician
    Sep 17, 2010 at 8:08
  • $\begingroup$ @J.M., there will be. But if Bezier surface is not a good choice, why is it not a good choice? And is there any other alternatives that I can use? $\endgroup$
    – Graviton
    Sep 17, 2010 at 10:45
  • $\begingroup$ As I said, Bézier treats your data as a convex hull instead of points to interpolate. Bicubic interpolation is standard fare, but without seeing what the data looks like, I don't want to give a definite recommendation. $\endgroup$
    – J. M. ain't a mathematician
    Sep 17, 2010 at 10:52

3 Answers 3

Reset to default
1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Yes, if this is actual survey data, then chopping it up into many tall, thin "straws" or "french fries" (triangular prisms or rectangular boxes or hexagonal prisms) -- either one for each point, or one for each triangle -- is going to be the best you can do. $\endgroup$
    – David Cary
    Sep 18, 2010 at 23:58
  • $\begingroup$ yes, that's my strategy now. But I don't really like it because I have too many polygons, too many points and the calculation is slow. I'm looking for a more efficient way to doing things. $\endgroup$
    – Graviton
    Sep 19, 2010 at 8:27
  • $\begingroup$ if you average the height (z) of the triangle centers for a certain x,y region you can get a faster estimate of the volume. For example if you break the cutting plane into four quadrants and find the height of the triangle centers above that quadrant then you can just use the x,y lengths and the z height for an estimate of the volume. There is some error when the triangle of the polygon go over the border between quadrants but you can break the plane into smaller segments to minimize this. thus it is a tradeoff between speed and accuracy. $\endgroup$
    – AvatarOfChronos
    Sep 19, 2010 at 16:14
  • $\begingroup$ basically you can extend this ( demonstrations.wolfram.com/… ) into the third dimension. $\endgroup$
    – AvatarOfChronos
    Sep 19, 2010 at 16:15
  • $\begingroup$ other than that the algorithm is data parallel and XNA is on the .net platform so you could use the task parallel library to try and speed things up. $\endgroup$
    – AvatarOfChronos
    Sep 19, 2010 at 16:16
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .