Cut and Fill Volumes in C++

Cut And Fill (Wikipedia) Earthwork volume computations for C++. The library module Cut And Fill takes two overlapping surfaces and computes the volume between. The result is a set of volumes where soil must be filled or where material must be digged off to turn one surface into the other one.

Example Source Code

The source code example below creates two random surfaces, each consisting of approx. 10 000 triangles. Two Zone2 objects are made from these triangulations. These are called pZoneBefore and pZoneAfter to denote the surface before the earthworks and the final surface.

Cut Fill, Earthworks volume computation between two surfaces

Surface before the earthworks (RED), Surface afterwards (GREEN). Output: One cut volume and one fill volume

vector<Point2> vRndSurfacePoints0;
vector<Point2> vRndSurfacePoints1;
  70, // numPointsX
  70, // numPointsY
  10, // numCenters
  0,0,-30,1000,1000,30, // Bounds xmin,ymin,zmin,xmax,ymax,zmax
  vRndSurfacePoints0,// Output vector
  1// Seed
  70, // numPointsX
  70, // numPointsY
  1, // numCenters
  0,0,-30,1000,1000,30, // Bounds xmin,ymin,zmin,xmax,ymax,zmax
  vRndSurfacePoints1,// Output vector
  5// Seed
Fade_2D dt0;
Fade_2D dt1;

// One zone before the earthworks and one zone after. The two zones
// do not need to match exactly. The overlapping area is used.
Zone2* pZoneBefore(dt0.createZone(NULL,ZL_GLOBAL,false));
Zone2* pZoneAfter(dt1.createZone(NULL,ZL_GLOBAL,false));

Cut And Fill Computations

Below a Cut And Fill object is created with the two surfaces (zones) as input. A progress bar is added (this is an optional step, an example of a terminal progress bar is shown at the end of this post). Finally the command CutAndFill::go() launches the Cut And Fill algorithm.

The Cut&Fill algorithm computes the height differences between the two TIN’s and forms connected areas where the elevation of one surface is completely above or below the other one. Then the volume between the two surfaces is computed for each connected area. There is no need for compatible input triangulations (same triangles) and also the input areas do not need to match exactly. The overlapping area is determined automatically, triangles are cut where it is necessary and a compatible output triangulation is computed.

CutAndFill caf(pZoneBefore,pZoneAfter);
MyProgressBar progBar;

Create a report

Iterate over all Cut And Fill components (CAF_Component) and let them report to stdout. Other access methods exist also in the CAF_Component class:

cout<<"Number of components: "<<caf.getNumberOfComponents()<<endl;
for(size_t i=0;i<caf.getNumberOfComponents();++i)
  CAF_Component* pComponent(caf.getComponent(i));

In the present example only two connected components exist:

Number of components: 2
Component 0, Type: CUT , Volume: 2.84332e+07
Component 1, Type: FILL, Volume: 3.32667e+06

Postscript visualization

The code below creates a graphical report.

Visualizer2 vis("");;
Cut And Fill Result. Two connected components


Progress Bar

The code snippet below defines a terminal progress bar that receives updates while Cut And Fill runs.

class MyProgressBar:public GEOM_FADE25D::MsgBase
  // Fade calls the update method with d={0.0,...,1.0}
  void update(MsgType ,const std::string& s,double d)
    cout<<s<<" [";
    for(size_t i=0;i<10;++i)
      if(i/10.0<d) cout<<"=";
        else cout<<" ";
    cout<<"] "<<d*100.0<<" %    \r"<<flush;
    if(d==1.0) cout<<endl<<endl;


Spread the word. Share this post!

Leave A Reply

Your email address will not be published. Required fields are marked *


By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.