CODEWITHSUNDEEP
algorithm3d
john doe
john doe

Reputation: 557

Can this mesh volume calculation algorithm handle imperfect meshes?

As per this answer, I read this research paper (very brief). To quote the answer:

This all boils down to the following simple function:

public float SignedVolumeOfTriangle(Vector p1, Vector p2, Vector p3) {
    var v321 = p3.X*p2.Y*p1.Z;
    var v231 = p2.X*p3.Y*p1.Z;
    var v312 = p3.X*p1.Y*p2.Z;
    var v132 = p1.X*p3.Y*p2.Z;
    var v213 = p2.X*p1.Y*p3.Z;
    var v123 = p1.X*p2.Y*p3.Z;
    return (1.0f/6.0f)*(-v321 + v231 + v312 - v132 - v213 + v123);
}

and then a driver to calculate the volume of the mesh:

public float VolumeOfMesh(Mesh mesh) {
    var vols = from t in mesh.Triangles
               select SignedVolumeOfTriangle(t.P1, t.P2, t.P3);
    return Math.Abs(vols.Sum());
}

This seems much better than the voxel based approach for determining volume of an advanced 3D object, however, in the models I currently have available to me:

enter image description here

enter image description here

And I'm unsure about how the algorithm will handle imperfect 3D models.

Do I need to produce models which are made up only of true, complete, voluminous 3D objects for this method to work, or will it work on common 3D models as shown above?

Upvotes: 1

Views: 1253

Answers (1)

kolenda
kolenda

Reputation: 2811

The method you've found works by iterating over all triangles, for each triangle it connects its corners with (0,0,0) point making a tetrahedron. Then it computes its volume and sum up all the results. The signed word used here means that some tetrahedrons will have negative volume, based on triangle facing. Thanks to this trick overlapping tetrahedrons will cancel out each other.

If you have correct mesh it just works, but your imperfect mesh is basically a perfect one but with few triangles missing, so you'll miss some of your tetrahedrons in your final sum. Statistically some of them are positive volumes and some are negative ones, so this will also cancel out to some extent.

The more triangles you lack and/or the bigger they get then the more error you'll get in computed volume value, but the algorithm won't break or explode, just loose precision.

There's also another problem with this approach:

When you have two perfectly closed cube meshes that are overlapping each other this algorithm will compute the sum of their volumes, not the volume of the shape they've created. We don't know much about your models but I'd consider it a bigger problem than non-closed mesh. To solve this you'd need to do CSG Union operation, but it works only for closed meshes :/.

Upvotes: 3

Related Questions