Volume Calculations

While building a physics engine the problem of determining the volume enclosed by a collision hull (or some other surface bound topology) is likely to present itself.  A simple volume determination can be carried out by dividing the space around a volume into a regular grid and summing up the volume of all the voxels enclosed by the bounding surface; while straight forward to implement this is extraordinarily slow due to the number of containment tests involved.  Collision hulls are defined by an explicit description of their bounding surface, usually in the form of a mesh tessellated by a set of n sided polygons.  With this in mind we would like to relate the volume of a collision hull to an explicit calculation on the surface of the hull.  This leads us to the Divergence Theorem:

Roughly stated (with apologies to mathematicians for the sloppy wording) the Divergence Theorem tells us that the divergence of the vector field F within the closed volume V is equal to the flux of F through the boundary of V where the boundary of V is given as the closed, oriented, 2d surface S.  The so called orientation of S comes from the unit length vector n which consistently points “outside” of V and is well defined for every point on S.  Note that the left hand side of the theorem looks very similar to the triple integral you would use to directly calculate the volume of V.

If we choose F as the vector field (x, 0, 0) then the divergence of F is trivially computed as 1.

Which of course collapses the internals of the integral on the LHS of the Divergence Theorem into a simple unit integration through the volume of V.

The Divergence Theorem can then be used to relate the volume of V to the divergence of F through S.

We now have the volume-to-surface relationship needed for the efficient calculation of the volume enclosed by a collision hull.  Assuming a straight forward mesh representation the volume of a collision hull can be computed as the piece wise summation of the flux of F = (x, 0, 0) through each polygon in the mesh.

Calculating the flux of F through Si requires integrating a vector field across area Si and therefore a 2 dimension parameterization of Si.  For the sake of simplicity we restrict ourselves to the decomposition of S into n triangular regions described by a set of counter-clock-wise wound vector triplets.

In other words, S is a triangulated mesh.  A straight forward parameterization of triangle Si is given by the parametric equation Ti.

Under this parameterization the outward facing differential area dAi is computed as:

The flux of F through triangle Ti can now be written as an explicit 2d integral.

The symbolic evaluation of the double integral is tedious and mundane and in the interest of space has been omitted; the final result follows.

Finally, the total volume of V can be expressed as:

For the mathematically adverse a basic C++ implementation should look something like this:

 float32 CalculateVolume(const Vector3* a_pVerts,
                         const int32*   a_pIndices,
                         const int32    a_nNumTris)
{
    float32 fVolume = 0.0f;

    for(int32 i = 0; i < a_nNumTris; i++)
    {
        Vector3 v1 = a_pVerts[a_pIndices[3*i  ]];
        Vector3 v2 = a_pVerts[a_pIndices[3*i+1]];
        Vector3 v3 = a_pVerts[a_pIndices[3*i+2]];

        fVolume += (v1.x+v2.x+v3.x)*((v2.y-v1.y)*(v3.z-v1.z)-
                                     (v2.z-v1.z)*(v3.y-v1.y));
    }

    return fVolume / 6.0f;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s