Cococubed.com Volume from a plane and cube intersection

Home

Astronomy research
Software instruments
Stellar equation of states
EOS with ionization
EOS for supernovae
Chemical potentials
Stellar atmospheres

Voigt Function
Jeans escape
Polytropic stars
Cold white dwarfs
Hotter white dwarfs

Cold neutron stars
Stellar opacities
Neutrino energy loss rates
Ephemeris routines
Fermi-Dirac functions

Galactic chemical evolution
Coating an ellipsoid
Universal two-body problem

Nuclear reaction networks
Nuclear statistical equilibrium
Laminar deflagrations
CJ detonations
ZND detonations

Fitting to conic sections
Unusual linear algebra
Derivatives on uneven grids

Supernova light curves
Exact Riemann solutions
1D PPM hydrodynamics
Verification problems
Plane - cube Intersection

Phyllotaxis
The pendulum
Circular and elliptical 3 body

MESA
MESA-Web
FLASH

Zingale's software
Brown's dStar
GR1D code
Herwig's NuGRID
Meyer's NetNuc
Presentations
Illustrations
Videos

AAS Journals
2019 JINA R-process Workshop
2019 MESA Marketplace
2019 MESA Summer School
Teaching materials
Education and Public Outreach

Contact: F.X.Timmes
my one page vitae,
full vitae,
research statement, and
teaching statement.

The intersection between a box and a plane is a geometric computation with numerous applications in computer graphics, solid modeling, and computational physics (e.g., fraction of cell that may be partial ionized or covered by a burning front). Most of the ray-box algorithms we could find provided a binary answer to the question of whether a given ray, the normal to the plane, was inside a specied box or not, while a few algorithms computed the vertices of the intersection plane.

Here we give two methods (public_volume_fraction.tbz, and public_triangular_pyramid.tbz) to compute the volume of the intersection between a cube and a plane. The first method is based on computing the volume of an arbitrary polyhedron given the vertices of each bounding face, while the second method is founded on adding and subtracting triangular pyramids. Both methods give volume fractions that have a maximum relative difference of 10-7, but the triangular pyramid method has a smaller operational count.

General Polyhedra Method
The intersection between a cube and a plane results in an inscribed, irregular polygon with one of five basic shapes that have 3 to 6 intersection points, as illustrated in figure below. The resulting irregular polyhedron is composed of 4 to 7 faces, 6 to 14 edges, 4 to 9 vertices, and satisfies the Euler identity Nfaces - Nedges + Nvertices = 2. Our approach extends the method of Salama & Kolb (2005) by simulateously constructing the faces, edges, vertices, and volume of the irregular polyhedron.
 The five basic shapes Faces, edges and intersection ordering

We work on the unit cube with vertices and faces enumerated and ordered as shown by the figure above. There are only three independent paths from the front vertex V1 to the back vertex V8 as marked by the black, dark gray, and light gray lines. The intersecting plane is defined by the length of the normal ray dl, and the spherical angles 0 ≤ θ ≤ 2π and 0 ≤ φ &le π. The maximum length of the normal ray in this coordinate system is dlmax/dx = (cos(θ) + sin(θ)) sin(φ) + cos(φ), otherwise the plane does not intersect the cube. We begin by forming the Cartesian coordinates of the normal ray

and take the equation of the plane to be in Hessian normal form

where n hat is the unit normal vector. Edge E i → j between vertices Vi and Vj of the cube can be described by the straight line

and the intersection point between the plane and the straight line spanned by Edge E i → j is calculated as

There is a valid intersection point only if 0 ≤ λ ≤ 1, otherwise the plane does not intersect the edge within the cube. The denominator becomes zero only if the edge is coplanar with the plane. In this case, we simply ignore the intersection.

A key point in performing the plane-edge intersection calculations is to maintain a consistent ordering, clockwise or counter-clockwise, of the intersection points such that the final result forms a valid polygon. A consistent ordering can be achieved by traversing the edges in a manner described by Salama & Kolb (2005). There are only 3 independent paths from the front vertex V1 to the back vertex V8. These independent paths, which do not share any vertices other than the start and end vertex, are constructed by requiring the edges of each path form a right-handed orientation. Figure 6 shows the three independent paths as the black, dark gray, and light gray solid lines. These three independent paths can determine 3 of the 6 intersection points. If there are more than 3 intersecting points, they must lie on one or more of the three dotted lines in the fgure above and must be inserted between the intersection points determined by the 3 independent paths. For example, consider the dark gray dotted edge E 3 → 7 is calculated as If there exists a valid intersection with this edge, then it must be inserted between the intersection points determined by solid dark gray path and the solid black path.

We start accumulating the intersection points with the light gray path by checking edges E 1 → 2 for a valid intersection. If there is no intersection, we continue along the light gray path by checking E 2 → 5 and then onto E 5 → 7 if there is still no intersection. If an intersection point exists along the light gray path, we terminate the search along the light gray path and add the relevant vertices to a polyhedron face list. Next we check the dashed light gray path E 2 → 6, adding the face information for the resulting polyhedron if there is an intersection point. Similiarily we traverse the dark gray paths E 1 → 3, E 3 → 6 E 6 → 8, E 3 → 7 followed by black paths E 1 → 4, E 4 → 7, E 7 → 8, E 4 → 5 In this manner we determine all the intersection points in a sequence that forms a valid polygon while simultaneously constructing the face and vertex information of the resulting irregular polyhedra. The movie below shows the number of vertices of the intersecting polygon in the θ-φ plane as a function of the length of the normal ray dl.

 Number of vertices of the intersecting polygon. Volume fraction as a function of the normal ray.

Finally, to calculate the total volume of the polyhedron, which equals the volume fraction on a unit cube, we sum the individual volumes of a series of pyramids, V = ∑ 1/3 · base · height. Each face of the polyhedron forms the base of one pyramid and the point V1 is arbitrarily chosen as the height of each pyramid. The area of each base (face) is calculated by transforming the base into a coordinate system where the faces z-coordinates are zero and then applying the Surveyors Formula. Note the choice of V1 as the reference height point means pyramids with faces 1, 4, and 5 as the base have zero volume because these pyramids have zero height. The movie above shows the volume fraction in the θ-φ plane as a function of the length of the normal ray dl.

Triangular Pyramid Method
Our triangular pyramid method constructs 9 explicit formula for the volume of the polyhedron generated by the intersection a plane with a cube. The intersecting plane is defined by the length of the normal ray dl, and the spherical angles 0 ≤ α ≤ 2π and -π/2 ≤ β ≤ π/2. The maximum length of the normal ray in this coordinate system is dlmax/dx = (cos(α) + sin(α)) cos(β) + sin(β), otherwise the plane does not intersect the cube. Reflection symmetry about dlmax/2 allows the same 9 formula to be reused. We work on a cube whose edges have length dx. We begin by forming the distances along the coordinate axes of the intersecting plane

We limit α and β values near 0 and π/2 such that the denominators do not go to zero. The simplest pyramid has x < dx, y < dx, and z < dx and volume fraction

Please cite the relevant references if you publish a piece of work that use these codes, pieces of these codes, or modified versions of them. Offer co-authorship as appropriate.