Volume of a Polyhedron

Here are several methods.
  1. The traditional method to determine the volume of a polyhedron partitions it into pyramids, one per face.

    1. Observe that, when the origin is joined to the vertices of any face, then it forms a pyramid.
    2. The volume of the pyramid is the area of the base polygon times the distance from the base plane to the origin. Either of these might be negative. For polygon areas, see here.
    3. Sum those volumes.
    4. Instead of using the origin, you could use one vertex. This means messier code but fewer pyramids. It's probably not worth the bother.

  2. Alternatively, the polyhedron might be partitioned into tetrahedra, with each face partitioned into triangles.

    1. To partition a face, simply join its first vertex to each non-adjacent edge in turn.
    2. If the face is concave, this will cause negative triangles that are outside the original face. That is ok.
    3. The volume of the tetrahedron formed by one triangle and the origin is the 3x3 determinant of the 3 triangle vertices.
    4. Be careful of signs since some tetrahedra should have negative volumes.

  3. Alternatively only local topological info might be used. Here, the input is a set of tuples derived from vertex-edge-face adjacency info:

    {(V,T,N,B)}

    where there is one quadruple for each case of a vertex-edge-face adjacency. I.e., for a cube, there are 6 such adjacencies for each vertex, or 48 total.

    V Coordinates of a vertex.
    T Unit tangent vector from the vertex along the edge towards the other end.
    N Unit vector normal to the edge in the plane of the face, and pointing from the edge into the face.
    B Unit vector normal to the plane of the face, and pointing into the polyhedron.

    Then the volume of the polyhedron,

    VOLUME = -1/6 sum( V.T V.N V.B )

    Also, the total area of all the faces,

    AREA = 1/2 sum( V.T V.N )

    and the total length of all the edges,

    LENGTH = - 1/2 sum( V.T )

    "." is the scalar, dot, product.

    The formulae are my own. They use no global information about the polyhedron. E.g., there is no concept of an edge as one entity, but only of the directions that the edges leave the vertices.

    For more info and the derivation, see the slides of a talk. There are some typos in the slides.

    This method is good when the polyhedron has a complicated global topology, with many nested shells of faces and loops of edges.

    It's ideal when the polyhedron is being calculated as the output of some process, such as the intersection of two other polyhedra. In fact, you don't need to find the complete intersection polyhedron, but can stop when you have the set of output vertices and their local topology. This saves time and reduces the problems caused by messy topologies.


Wm. Randolph Franklin, Associate Professor
Email: wrfATecse.rpi.edu
http://wrfranklin.org/
☎ +1 (518) 276-6077; Fax: -6261
ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, Troy NY, 12180 USA
(GPG and PGP keys available)