Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I'd first start by figuring out what interpolating function(s) were used to create that mesh. –  J. M. Sep 17 '10 at 7:35
    
@J.M., no interpolation function were used; they were obtained from field survey, or at least this is the assumption I have to make. –  Graviton Sep 17 '10 at 7:38
    
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? –  J. M. Sep 17 '10 at 8:08
    
@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? –  Graviton Sep 17 '10 at 10:45
    
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. –  J. M. Sep 17 '10 at 10:52
show 4 more comments

1 Answer

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?

share|improve this answer
    
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. –  David Cary Sep 18 '10 at 23:58
    
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. –  Graviton Sep 19 '10 at 8:27
    
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. –  AvatarOfChronos Sep 19 '10 at 16:14
    
basically you can extend this ( demonstrations.wolfram.com/… ) into the third dimension. –  AvatarOfChronos Sep 19 '10 at 16:15
    
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. –  AvatarOfChronos Sep 19 '10 at 16:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.