*
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

   Nuclear reaction networks
   Nuclear statistical equilibrium
   Laminar deflagrations
   CJ detonations
   ZND detonations
   Fitting to conic sections
   Unusual linear algebra
   Derivatives on uneven grids
   Pentadiagonal solver
   Quadratics, Cubics, Quartics
   Supernova light curves
   Exact Riemann solutions
   1D PPM Hydrodynamics
   Verification problems
   Plane - Cube Intersection

   MESA
   MESA-Web
   FLASH

   Zingale's software
   Brown's dStar
   GR1D code
   Iliadis' STARLIB database
   Herwig's NuGRID
   Meyer's NetNuc
Presentations
Illustrations
Videos
Bicycle adventures

AAS Journals
2017 MESA Summer School
ASU+EdX AST111x
Teaching materials
Education and Public Outreach
2016 NSF SI2 PI Workshop


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.