OOF: Finite Element Analysis of Microstructures
Robustly calculating the intersection of a convex polyhedron and a set of voxels
A crucial part of OOF3D is the calculation of the volume of intersection of a finite element with a set of voxels (three dimensional pixels). This calculation must be fast, and it must be robust, so that small numerical errors in the position of an intersection point do not lead to large errors in the result. Because it is easy to write code that is not robust, we are here providing the OOF3D code in a separate module that can be easily used elsewhere.
These routines are called VSB, which stands for "Voxel Set Boundary" because "Intersection of Voxel Set Boundary with Convex Polyhedron", or IOVSBWCP, is too long. They are based on Powell and Abel's r3d algorithm.
This page provides information on how to download and use VSB. It doesn't explain the philosophy behind it. For details on how VSB works, see our paper and the comments in the code.
VSB requires a C++ compiler supporting the C++11 standard. It is a template library that must be compiled with your C++ program. It is not a stand-alone program.
Click to download vsb-1.0.1.tgz (36004 bytes, md5 checksum fb8aab2aa20d2c182ab8d5cf85b2020f).
Unpack the file with tar -xf vsb-1.0.1.tgz. This will create a directory called VSB containing C++ files.
Include vsb.h. Create an instance of the VoxelSetBdy class. Its arguments include an image and an voxel value. Then call VoxelSetBdy::clippedVolume(). The arguments to clippedVolume are the sides of a polyhedron, and its return value is the volume of the intersection of the polyhedron with all voxels in the image with the given voxel value.
At a minimum, you must include VSB/vsb.h in your C++ code, call the methods described below, and compile and link to vsb.C. (Rename vsb.C to vsb.cxx if that's your convention.)
Almost all of the classes and functions in VSB are templates. The template arguments are C++ classes that you must provide, representing coordinates, images, voxel values, etc. If you're writing a program that involves polyhedra and voxels you probably already have these classes. VSB assumes that these classes have certain minimal abilities, spelled out below and in VSB/vsb.h.
These are the types that you must provide as template arguments to the VSB classes and functions.
The VoxelSetBdy class
VoxelSetBdy is the main class in VSB. It represents a set of voxels, which is stored in terms of the edges of boundary of the set. Its clippedVolume method computes the volume remaining after the voxel set is clipped by a set of planes. Clipping by all of the planes of a convex polyhedron produces the intersection of the voxel set and the polyhedron.
One VoxelSetBdy object can be clipped multiple times by multiple sets of planes. Clipping does not change the VoxelSetBdy.
The constructor is:
VoxelSetBdy<COORD, ICOORD, IMAGE, IMAGEVAL>( const IMAGE &image, const IMAGEVAL &imageVal, double voxelVolume, const std::vector<ICRectPrism<ICOORD>> &subregions)with arguments:
The VSBPlane class
VSBPlane is a templated class, defined in VSB/cplane.h that represents an oriented plane. The single template parameter is a COORD. The constructor is
VSBPlane(const COORD &normal, double offset)where normal is the outward normal vector of the plane, and offset is the distance from the origin to the plane in the normal direction. The offset can be negative.
The ICRectPrism and CRectPrism classes
ICRectPrism and CRectPrism, defined in VSB/cplane.h, represent rectangular prisms (3D rectangles). The difference between them is that the corners of an ICRectPrism are at integer coordinates, while the corners of a CRectPrism are floating point numbers. Both are template classes. The template parameter for ICRectPrism is ICOORD. The template parameter for CRectPrism is COORD.
The constructors are:
Other useful methods for setting up a prism are:
See VSB/cprism.h for other methods, including retrieving corners and bounds, determining if a prism contains a given point, and whether or not two prisms intersect.
|Disclaimer and Copyright||
This software was produced by NIST, an agency of the U.S. government, and by statute is not subject to copyright in the United States. Recipients of this software assume all responsibilities associated with its operation, modification and maintenance. However, to facilitate maintenance we ask that before distributing modified versions of this software, you first contact the authors at email@example.com.